Closed Bug 188458 Opened 22 years ago Closed 21 years ago

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

Categories

(Core :: Networking: Cache, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: bryner, Assigned: bryner)

References

Details

(Keywords: perf)

Attachments

(1 file, 2 obsolete files)

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.
that url isn't working ...
Attached patch patch to implement LRU-SP (obsolete) — Splinter Review
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()).
Attachment #111278 - Flags: superreview?(darin)
Attachment #111278 - Flags: review?(gordon)
Comment on attachment 111278 [details] [diff] [review]
patch to implement LRU-SP

this looks really solid to me.

sr=darin
Attachment #111278 - Flags: superreview?(darin) → superreview+
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
cathleen: can you also see how this effects ibench/minibench?
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.
Attachment #111278 - Attachment is obsolete: true
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

Attachment #111278 - Flags: review?(gordon)
Attached patch revised patch (obsolete) — Splinter Review
This fixes the hang I mentioned (bug in AdjustMemoryLimits).
Comment on attachment 113160 [details] [diff] [review]
revised patch

carrying over darin's sr.
Attachment #113160 - Flags: superreview+
Attachment #113160 - Flags: review?(gordon)
This patch goes back to putting non-expiring items in the least likely to evict
queue.
Attachment #113160 - Attachment is obsolete: true
Attachment #113160 - Flags: review?(gordon)
Attachment #116172 - Flags: superreview+
Attachment #116172 - Flags: review?(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.
Attachment #116172 - Flags: review?(gordon) → review+
This seems to have caused crash bug 198267
Depends on: 198267
Checked in, and crash fixed.  Marking FIXED.
Status: NEW → RESOLVED
Closed: 21 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: