3.2.2 Frame Usage Computation We could implement replacement by evicting the objects with the lowest usage in the cache, but this approach may pick objects from a large number of frames. Since HAC compacts objects retained from these frames, compaction time may be unacceptable, e.g., compacting 126 frames could take up to 1 second in our experimental environment. Therefore, we compute usage values for frames and use these values to select frames to compact and indirectly objects to evict. Our goals in freeing a frame are to retain hot objects and to free space. The frame usage value reflects these goals.
H is the fraction of objects in the frame that are hot at threshold T .
We require H to be less than the retention fraction , R , where R is a parameter of our system. T is the minimum usage value that results in an H that meets this constraint. Selecting a value for system parameter R involves a tradeoff between retaining hot objects to reduce miss rate and achieving low replacement overhead by reducing the number of frames whose contents need to be compacted. The goal for replacement is to free the least valuable frame. Although in theory one could determine the least valuable frame by examining all frames, such an approach would be much too expensive.