Would it be possible to have pointers to papers that describe these algorithms on the wiki page? I could find CAR ( http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf) and 2Q (http://www.vldb.org/conf/1994/P439.PDF ) but not CART.
From looking at the graphs, it looks like CART and 2Q are the two choices really. However running a few more experiments may not be a bad idea. Knut mentions adding scans to the zipf mix and that may be worthwhile. Actually the original 2Q paper does mix scans of different lengths with one of the zipf workload. Also given that the two seem to converge around 10K cache size (or 10% of the dataset size), can we go upto 20 or 40% and see if one policy is measurably better than the other?
If there isn't a whole lot of difference between the performance then it makes sense to go with the simpler implementation and/or consider synchronization concerns-- I'm guessing that 2Q (based on LRU) will involve more synchronization than CART (Clock based).
Those papers and the your results were pretty interesting reading. I too am curious about the zig-zag pattern on the zipf 0.8 dataset.
Thanks,
Manish
On 6/4/06,
Gokul Soundararajan <[EMAIL PROTECTED]> wrote:
Hi all,
I'm a Google SoC student working on creating a CacheManager with a
better cache replacement algorithm. After talking with my mentor
(Oystein Grovlen), I have created a bunch of small prototypes to
evaluate different algorithms found in literature.
I have run them for a Zipf workload for 0.5 and 0.8 and posted the
results on the Derby Wiki.
Link: http://wiki.apache.org/db-derby/DerbyLruCacheManager
The results show that the 2Q, CAR, and CART algorithms perform better
than LRU and Clock.
I would like to get some feedback on my results to help me decide what
I should implement in Derby.
Thanks,
Gokul
