Our approach has multiple applications, especially in simulating virtual memory systems; many page replacement algorithms are similar to LRU in that more recently referenced pages are likely to be resident. For several replacement algorithms in the literature, SAD-and OLR-reduced traces yield exact simulations. For many other algorithms, our trace reduction eliminates information that matters little: we present extensive measurements to show that the error for simulations of the CLOCK and SEGQ (segmented queue) replacement policies (the most common LRU approximations) is under 3% for the majority of  memory sizes.  In nearly all cases, the error is much smaller than that incurred by the well known stack deletion technique.

SAD and OLR have many desirable properties. In practice, they achieve reduction factors up to several orders of magnitude. The reduction translates to both storage savings and simulation speedups. Both techniques require little memory and perform a single forward traversal of the original trace, which makes them suitable for on-line trace reduction. Neither requires that the simulator be modified to accept the reduced trace.

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 high-frequency behavior (e.g., loops much smaller than the memory size) as such behavior may obscure important large-scale 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 on the aggregate memory-referencing behavior, EELRU can be ``fair'' (like LRU) or ``unfair'', selectively allowing some pages to stay in memory longer while others are evicted.

In this paper we present generation scoping: an adaptation of hygienic macro-expansion techniques to general-purpose program generation. The conceptual novelty of generation scoping lies in making identifier environments first-class objects and organizing them explicitly into directed graphs. This approach yields significant benefits: We are able to express scoping relationships independently of the structure of the generated program. This way we get a stronger tool for detecting errors in the specification of generated code. Additionally, we are able to simplify the specification by employing powerful implicit qualification. Thus, generation scoping becomes a useful layer of infrastructure for implementing software generators: it both solves binding problems and makes code specification more convenient.