417154 - nsMemoryCacheDevice::EvictEntriesIfNecessary could be optimized

Status: RESOLVED WONTFIX

(Core :: Networking: Cache, defect, P3)

Description

[Mike Schroepfer]

Spinoff of bug 411379.  

Profile there shows a ton of time spent in:

http://lxr.mozilla.org/mozilla/source/netwerk/cache/src/nsMemoryCacheDevice.cpp#354

When there is a very large set of images.  This routine looks to be a double iteration walking a set of queues looking for elements for which IsInUse() is not true - which is a problem if I've got a big list and very few unused elements this is slow.

I'm wondering if it is possible to just add elements to a free list (or free them) as soon as the conditions for IsInUse change?

Comment 1

[Robert Roessler]

While someone is looking at this code, it should be noted that SM trunks are back to an occasional nasty [memory cache] behavior, starting with the 20080211 nightly... what is wrong with this about:cache picture?

Memory cache device

Number of entries: 	1326
Maximum storage size: 	24576 KiB
Storage in use: 	146285 KiB
Inactive storage: 	0 KiB

This happens after loading up a lot of [mostly JPEG] images.

Comment 2

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Nothing's wrong with that, assuming that all the images are still visible.  The memory cache will always grow to contain the active set of images; the "max size" is really mislabeled.  (Actually the entire 'memory cache' is mislabeled, but that's a separate issue..)

Comment 3

[Alfred Kayser]

The term 'cache' is indeed misleading.
The memory cache contains all images (and some other memory cache objects) that are used and recent images released (not in use) upto the maximum storage size. 

The eviction is indeed hard because:
1. mEvictionList contains all elements used, active, doomed or what else.
2. In situations like in comment #1, the mHardLimit is lower than total storage in use, the eviction walks through the whole list, but fails to get below the limits. The eviction pattern is based on the assumption that in normal cases on one or two evictions the limits are satisfied. This happens a lot in the disk case: when a file is being added to the cache, the eviction process removes just enough to make space for that.

Without changing libpr0n and the way images are cached, at least we could change the memory cache to only store notused objects in mEvictionList.

(Note the 'Inactive storage' is zero in comment #1, so eviction doesn't even need to try to evict... But (mTotalSize < mHardLimit) not true, so it will still try to evict entries...

Comment 4

[Stuart Parmenter]

I would like to stop using the memory cache in imagelib at some point in the not-so-distant future, but I don't think we want to do that for Firefox3.  I think we can do a much more efficient cache directly in imagelib with much better policies for caching that are very image specific.

Comment 5

[Mike Schroepfer]

(In reply to comment #3)
> Without changing libpr0n and the way images are cached, at least we could
> change the memory cache to only store notused objects in mEvictionList.
> 

Want to whip up a patch for that?

Comment 6

[Alfred Kayser]

Attachment: Initial version for performance testing and first review

This patch makes the EvictionIfNeeded only work on the really inactive items, by only placing the inactive items into mEvictionList. This means that other operations, like normal eviction, shutdown and about:cache visitor need to work from the mMemCacheEntries hashtable. 

Note that the total code is now smaller than before, and the eviction process should be drastically less than before.

So, who can do some performance tests on this? (see also bug 411379)

Comment 7

[Alfred Kayser]

Considering that image performance improvements (and spec. bug 411379) are blocking, and that there is now a patch for this, can this one also be marked blocking1.9?

Comment 8

[Steve Snyder]

(In reply to comment #6)
> Created an attachment (id=303501) [details]
> Initial version for performance testing and first review
[snip]
> So, who can do some performance tests on this? (see also bug 411379)

I'm the guy that reported the high eviction times in bug 411379.

After rebuilding with this patch applied, I don't see a difference in behavior.

To recap: I populated a small HTML file with image tags referring to ~2600 misc. JPEG files ('<img src="mostlynotporn.jpg">').  I see unexpectedly high cache maintainnce times when this HTML file is dropped onto an optimized build of SeaMonkey v1.1.8.  This is on a fully-updated Fedora 7 system.  My hardware is a dual-Pentium4/2.4GHz with 1024MB of RAM.

After loading these images into (i.e. dropping the HTML file onto) SM several times to warm up the system disk cache, I did it 3 times with oprofile running.

Example oprofile output:

samples  %        app name                 symbol name
62507    23.8786  libnecko.so
nsMemoryCacheDevice::EvictEntriesIfNecessary()
23401     8.9395  libjpeg.so.62.1.0        decode_mcu
16191     6.1852  libgdk-x11-2.0.so.0.1000.14 (no symbols)
14968     5.7180  libfb.so                 (no symbols)
10546     4.0287  libgklayout.so           nsLineBox::IndexOf(nsIFrame*) const
9911      3.7861  libjpeg.so.62.1.0        [e-mail]
9623      3.6761  libc-2.6.so              memcpy
7503      2.8663  libjpeg.so.62.1.0        jpeg_idct_islow_sse2.column_end
6309      2.4101  libjpeg.so.62.1.0        jpeg_idct_islow_sse2.columnDCT
4346      1.6602  Xorg                     (no symbols)
3345      1.2778  libc-2.6.so              _int_malloc
2947      1.1258  nvidia_drv.so            (no symbols)

Results of patch test: 

  Before patch: Avg 24.67% = (24.6063, 24.3877, 25.0347)
  After patch:  Avg 24.12% = (23.8710, 23.8786, 24.6334)

Possibly a more specific test, such as a cummulative timing if nsMemoryCacheDevice::EvictEntriesIfNecessary() alone rather than an overall system test, might yeild more encouraging results.

BTW, a lot of warnings were generated by GCC v4.1.2.  These may have been generated all along, but seem related to the code you changed:

$ grep nsCacheEntry /tmp/mozbuild.log | grep -v nsCacheEntryDescriptor
nsCacheEntry.cpp
c++ -o nsCacheEntry.o -c -I../../../dist/include/system_wrappers -include ../../../config/gcc_hidden.h -DMOZILLA_INTERNAL_API -DOSTYPE=\"Linux2.6.23.15-80.fc7\" -DOSARCH=\"Linux\" -DBUILD_ID=2008021506 -DIMPL_NS_NET  -I../../../dist/include/xpcom -I../../../dist/include/string -I../../../dist/include/necko -I../../../dist/include/pref -I../../../dist/include/nkcache -I../../../dist/include -I/usr/include/nspr4    -I../../../dist/sdk/include    -fPIC   -fno-rtti -fno-exceptions -Wall -Wconversion -Wpointer-arith -Wcast-align -Woverloaded-virtual -Wsynth -Wno-ctor-dtor-privacy -Wno-non-virtual-dtor -Wno-long-long -pedantic -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -m32 -march=pentium4 -fomit-frame-pointer -fasynchronous-unwind-tables -fno-exceptions -fno-stack-protector -Wno-non-virtual-dtor -fshort-wchar -pthread -pipe  -DNDEBUG -DTRIMMED -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -m32 -march=pentium4 -fomit-frame-pointer -fasynchronous-unwind-tables -fno-exceptions -fno-stack-protector   -DMOZILLA_CLIENT -include ../../../mozilla-config.h -Wp,-MD,.deps/nsCacheEntry.pp nsCacheEntry.cpp
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsMemoryCacheDevice.cpp: In member function 'virtual nsresult nsMemoryCacheDevice::OnDataSizeChange(nsCacheEntry*, PRInt32)':
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
nsDiskCacheDevice.cpp: In member function 'virtual void nsDiskCacheDevice::DoomEntry(nsCacheEntry*)':
nsDiskCacheDevice.cpp: In member function 'virtual nsresult nsDiskCacheDevice::OnDataSizeChange(nsCacheEntry*, PRInt32)':
nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor
./../cache/src/nsCacheEntry.h:295: warning: 'class nsCacheEntryHashTable::Visitor' has virtual functions but non-virtual destructor

Comment 9

[Alfred Kayser]

Attachment: V2: Tuned & twiggled...

Another version to test.
I have changed EvictEntriesIfNecessary into EvictInactiveEntries, and optimized the loop.

But I am afraid the performance hit is not really in this function itself but in the destructor of nsCacheEntry, where mData is released through a complex thread aware mechanism...

So, can this be tested? Could this be done at more detailed level within the EvictInactiveEntries code?

Comment 10

[Steve Snyder]

I did the profiling above with oprofile to provide a quick apples-to-apples comparison with the original observation.  I'll test your 2nd patch at a lower level and get back to you in about 12 hours (the burden of gainful employment...).

Am I correct in thinking that this is a platform-independant problem and that I should be able to reproduce it on a Windows machine?

Comment 11

[Mike Schroepfer]

Sure - thanks for jumping on this Alfred

Comment 12

[Honza Bambas (:mayhemer)]

Just for info (maybe I am doing something wrong). I was testing with a quality windows profiller. I was loading google image result pages (about 12 of them each 18 pictures on it). It was debug (non-optimized) build of trunk not older then 3 days.

Profiling in necko.dll on windows with ignoring the most loading routines like nsHttpChannel::OnTransportStatus etc shows that nsMemoryCacheDevice::EvictEntriesIfNecessary has almost no load. Much bigger problem is its OnDataSizeChange method that with its 421 hits spents almost 0.25ms.

The complete results are:

Routine Name	Time	% Time	Time with Children	% with Children	Shared Time	Average Time	Hit Count
nsMemoryCacheDevice::OnDataSizeChange	0.25541	0.02 %	0.43	0.03 %	59.47	0.00061	421
nsMemoryCacheDevice::EvictionList	0.17480	0.01 %	0.17	0.01 %	100.00	0.00006	2916
nsMemoryCacheDevice::BindEntry	0.14068	0.01 %	0.38	0.03 %	36.69	0.00060	236
nsMemoryCacheDevice::FindEntry	0.08684	0.01 %	0.53	0.04 %	16.53	0.00011	799
nsMemoryCacheDevice::EvictEntriesIfNecessary	0.06148	0.00 %	0.06	0.00 %	100.00	0.00008	785
nsMemoryCacheDevice::DeactivateEntry	0.02258	0.00 %	0.08	0.01 %	29.41	0.00015	154
nsMemoryCacheDevice::EvictEntry	0.00695	0.00 %	0.06	0.00 %	12.35	0.00027	26
nsMemoryCacheDevice::DoomEntry	0.00577	0.00 %	0.06	0.00 %	9.30	0.00022	26

I am personally not sure if this all even needs any optimization.

Comment 13

[Alfred Kayser]

Attachment: V3: Unbitrotted (after my patch for cacheVisitor cleanup)

With this patch, memoryCache entries are only added to the mEvictionList if they are no longer used. This makes EvictIfNeccessary much faster, as it doesn't need to walk across all active entries to do its work.
Furthermore, OnDataSizeChange now doesn't have to move entries from one eviction list to another (as only active entries change their size).
This also removes two unused member variables, and one local function.
By only tracking size based on 'DataSize' this patch prevents miscounting in TotalSize.

In total this saves about 4K code, and it does make the memory cache faster.

Steve or Mike, can you test this patch and try to reproduce the problem that triggered this bug (see comment #1)?

Comment 14

[Alfred Kayser]

Moving to 1.9.2.

Note, with images now cached in their own cache, this cache is less used, but the patch is still valid.

Comment 15

[Vasto_Lorde]

Hi, I applied you patch to 1.9.1, firefox 3.5.3

and the results are very favorable, mantaining low memory usage when closing unneeded tabs or windows.

also, I limmited the ammount of memory firefox can use to almacenate cache to 16384 via preference.

keep up the good work.

Comment 16

[Jo Hermans]

Vasto Lorde: in Firefox 3.5.*, the memory cache is not used much, since images are not stored in it anymore. Are you sure that you're seeing in your testcase that this algorithm actually works ?

Eviction can still happen, but since the default size of the memory cache is so large (23M is my cache, it depends on the amount of RAM), in reality it rarely happens. Note that this patch can still be useful, but I fear that the test for mHardLimit and mSoftLimit will always return immediately, so that EvictEntriesIfNecessary returns immediately. So I fear that you're not measuring the speed-touch of this patch.

See also bug 454001 for a request to lower the amount of memory to a much lower
value (4MB for example).

Comment 17

[Vasto_Lorde]

thanks for the comment.

I've activated the bfcache in firefox, 
browser.sessionhistory.cache_subframes;true
browser.sessionhistory.max_total_viewers;4

this optimization frees memory a little faster, about 5-15% faster than the default config.

Comment 18

[Marco Castelluccio [:marco]]

This is waiting for a review since 2008.

Comment 19

[Dave Camp (:dcamp)]

Comment on attachment 308619 [details] [diff] [review]
V3: Unbitrotted (after my patch for cacheVisitor cleanup)

I'm not the right reviewer here anymore (sorry for the delay).  Please re-request review if this is still useful.

Comment 20

[Josh Matthews [:jdm]]

Whenever someone decides this is still worth pursuing, the correct reviewer would be Michal Novotny.

Comment 21

[Honza Bambas (:mayhemer)]

We have cache2!