Heap size has a huge impact on the performance of garbage collected applications. A heap that barely meets the application's needs causes excessive GC overhead, while a heap that exceeds physical memory induces paging. Choosing the best heap size a priori is impossible in multiprogrammed environments, where physical memory allocations to processes change constantly. We present an automatic heap-sizing algorithm applicable to different garbage collectors with only modest changes. It relies on an analytical model and on detailed information from the virtual memory manager. The model characterizes the relation between collection algorithm, heap size, and footprint. The virtual memory manager tracks recent reference behavior, reporting the current footprint and allocation to the collector. The collector uses those values as inputs to its model to compute a heap size that maximizes throughput while minimizing paging. We show that our adaptive heap sizing algorithm can substantially reduce running time over fixed-sized heaps.

No abstract available.

The unmanageably large size of reference traces has spurred the development of sophisticated trace reduction techniques. In this paper we presenttwonew algorithms for trace reduction --- Safely Allowed Drop (SAD) and Optimal LRU Reduction (OLR). Both achieve high reduction factors and guarantee exact simulations for common replacement policies and for memories larger than a user-defined threshold. In particular, simulation on OLR-reduced traces is accurate for the LRU replacement algorithm, while simulation on SAD-reduced traces is accurate for the LRU and OPT algorithms. OLR also satisfies an optimality property: for a given trace and memory size it produces the shortest possible trace that has the same LRU behavior as the original for a memory of at least this size. Our approach has multiple applications, especially in simulating virtual memory systems

Despite the many replacement algorithms proposed throughout the years, approximations of Least Recently Used (LRU) replacement are predominant in actual virtual memory management systems because of their simplicity and efficiency.LRU, however, exhibits well-known performance problems for regular access patterns over more pages than the main memory can hold (e.g., large loops).In this paper we present Early Eviction LRU (EELRU).EELRU is a simple adaptive replacement algorithm, which uses only the kind of information needed by LRU-how recently each page has been touched relative to the others.It exploits this information more effectively than LRU, using a simple on-line cost/benefit analysis to guide its replacement decisions.In the very common situations where LRU is good, EELRU is good because it behaves like LRU.In common worst cases for LRU, EELRU is significantly better, and in fact close to optimal as it opts to sacrifice some pages to allow others to stay in memory longer.Overall, in its worst case, EELRU cannot be more than a constant factor worse than LRU, while LRU can be worse than EELRU by a factor almost equal to the number of pages in memory.In simulation experiments with a variety of programs and wide ranges of memory sizes, we show that EELRU does in fact outperform LRU, typically reducing misses by ten to thirty percent, and occasionally by much more-sometimes by a factor of two to ten.It rarely performs worse than LRU, and then only by a small amount.Overall, EELRU demonstrates several principles which could be widely useful for adaptive page replacement algorithms:(1) it adapts to changes in program behavior, distinguishing important behavior characteristics for each workload.In particular, EELRU is not affected by highfrequency behavior (e.g., loops much smaller than the memory size) as such behavior may obscure important largescale regularities;(2) EELRU chooses pages to evict in a way that respects both the memory size and the aggregate memory-referencing behavior of the program; (3) depending