Print indd

3.1
Allocation Site Partitioning
We propose two simple alternatives for partitioning program sites into groups.
The first alternative is called knapsack. Inspired by [
17
], it uses a classical 0/1
knapsack formulation to produce groupings that collectively fit into a knapsack
(of any capacity by which we want to represent the upper tier) while maximizing
aggregate access into it. The second alternative is called hotset. It avoids a
weakness of knapsack, namely, that knapsack may exclude an allocation site
based on the raw capacity of that site, even if allocations from it exhibit a high
access count. In the hotset approach, we sort allocation sites by accesses-per-byte
scores and then select those with highest scores until we exceed an alternate soft
capacity. The limiting capacity for inducing the hot-cold split in each case is
taken as a fraction of an applications total dynamic footprint,
D. Thus, if this
fraction is 12.5%, then the knapsack approach selects allocation sites such that
the aggregate size is just below
D/8, while the hotset approaches stops after
D/8 is crossed.