188458 - Investigate LRU-SP eviction policy for memory (and disk?) cache

Status: RESOLVED FIXED

(Core :: Networking: Cache, defect)

Description

[Brian Ryner (not reading)]

When running through the pageload tests, one thing I notice is that a few large
images are taking up most of the memory cache space.  This is causing us to miss
a lot on smaller images.

There's a caching algorithm called LRU-SP which takes into account size and
popularity of cache entries when deciding what to evict.  The algorithm is
described in: 

http://citeseer.nj.nec.com/rd/39823823%2C413170%2C1%2C0.25%2CDownload/http%3AqSqqSqwww.db.soc.i.kyoto-u.ac.jpqSqusrqSqchengkqSqpubqSqpapersqSqcompsac00_A07-07.pdf

My testing with using LRU-SP for the memory cache shows that we do get a slight
speedup on the pageload test.  We can also get an additional speedup by having a
maximum element size (where we just don't put it into the cache at all if it's
too large).

I'll post a patch shortly, I'm sure it could use some refinement.

Comment 1

[Jo Hermans]

that url isn't working ...

Comment 2

[Brian Ryner (not reading)]

Ok, this one should work:

http://citeseer.nj.nec.com/cheng00multicachebased.html

Comment 3

[Brian Ryner (not reading)]

Attachment: patch to implement LRU-SP

This implements the algorithm as described in the paper I mentioned.

One thing I wasn't quite sure about is whether we should still favor
non-expiring entries in the cache, and how that should be factored in (see the
commented out code in EvictionList()).

Comment 4

[Darin Fisher]

Comment on attachment 111278 [details] [diff] [review]
patch to implement LRU-SP

this looks really solid to me.

sr=darin

Comment 5

[Cathleen]

some perf data on windows pageload:

win98, 200MHz, 64MB
--------------------
baseline:  4560
w/ patch:  4631

win2k, 600MHz, 512MB
--------------------
baseline: 632
w/ patch: 635

win2k, 2.4GHz, 1GB
--------------------
baseline: 310
w/ patch: 311

Comment 6

[Darin Fisher]

cathleen: can you also see how this effects ibench/minibench?

Comment 7

[Brian Ryner (not reading)]

Comment on attachment 111278 [details] [diff] [review]
patch to implement LRU-SP

this has a bug in AdjustMemoryLimits that causes a complete hang. Looking into
it.

Comment 8

[Cathleen]

Sorry, i've been busy with other stuff lately.  I've started the mini-bench
test, and just haven't completed on all 3 machine yet.

Here is data for the slowest machine.

win98, 200mHz, 64MB
---------------------
                            baseline       w/ patch
                          ------------   -------------
first loop:                 131.17          126
avg subsequent loops:       119.827         117.707 
Total for all loops:        490.65          479.12
number of loops:              4               4

Comment 9

[Brian Ryner (not reading)]

Attachment: revised patch

This fixes the hang I mentioned (bug in AdjustMemoryLimits).

Comment 10

[Brian Ryner (not reading)]

Comment on attachment 113160 [details] [diff] [review]
revised patch

carrying over darin's sr.

Comment 11

[Brian Ryner (not reading)]

Attachment: restore favoring of non-expiring items

This patch goes back to putting non-expiring items in the least likely to evict
queue.

Comment 12

[gordon]

Comment on attachment 116172 [details] [diff] [review]
restore favoring of non-expiring items

Okay, it looks like we're maintaining the same policy for items with
NO_EXPIRATION_TIME.  

r=gordon.

Comment 13

[Boris Zbarsky [:bzbarsky]]

This seems to have caused crash bug 198267

Comment 14

[gordon]

Checked in, and crash fixed.  Marking FIXED.