Adaptive Replacement Algorithm Templates and EELRU - Advanced Operating Systems and Kernel Applications - page 272

contents using a single data structure with little
space overhead. At the same time, EELRU can be
shown to be robust with respect to LRU by just
treating it preferentially.

factors (e.g., 2x) that represent tight theoretical
lower bounds can be unacceptable overheads.
We present here a representative sample of a
simulated performance evaluation of EELRU on
real memory reference sequences. (An extensive
empirical evaluation can be found in Smaragdakis,
Kaplan, & Wilson, 2003.)
Specifically, we compare EELRU both to
LRU—the standard on-line policy—and OPT—
the provably optimal, off-line policy. In particular,
by comparing EELRU to OPT, we see the amount
of the potential improvement over LRU that
EELRU obtains. When compared to these two
policies, EELRU provides substantial fraction
of the available improvement over LRU. Just as

empirical performance
of eelru

It is interesting to see how the theoretical prop-
erties of an adaptive replacement template (e.g.,
robustness) translate to practice. In particular, is
it the case that an adaptive algorithm like EELRU
can achieve benefit without hurting performance
much in the worst case? In practice, constant

Table 1.

Program name Mean potential improvement

acrord32 -6.82%

Applu 35.85%

cc1 -6.12%

compress95 78.08%

espresso 10.61%

gcc-2.7.2 9.44%

Gnuplot 89.00%

Go 16.35%

grobner 30.96%

gs3.33 -1.84%

Ijpeg 40.62%

Lindsay -1.77%

m88ksim 37.95%

Murphi -2.39%

netscape -3.73%

p2c 3.56%

perl-etch 34.02%

perl-wisconsin 20.81%

photoshp -8.69%

powerpnt -8.10%

Trygtsl 29.31%

Vortex 0.60%

wave5 70.31%

winword -7.03%