Closed Bug 110163 Opened 23 years ago Closed 19 years ago

footprint: 135236 bytes allocated by disk cache on startup

Categories

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

defect

Tracking

()

RESOLVED FIXED
mozilla1.8beta2

People

(Reporter: blythe, Assigned: darin.moz)

References

Details

(Keywords: embed, memory-footprint, topembed-)

Attachments

(2 files, 5 obsolete files)

in nsDiskCacheDevice::Init

While using SpaceTrace it came to my attention that this memory was allocated
and stayed around for the length of the application.

I tracked the source down, and I came to:
nsDiskCacheMap

The comment in the header said "Future: make dynamic" indicating that there
should be plans to lower the memory consumption of the disk cache by making the
number of buckets dynamic.

It would really reduce our startup footprint (by 2.25%) and lessen the impact of
the mozilla running over time.
gordon, can you take a look at this footprint issue, and assign to an
appropriate milestone.  thx!
Keywords: footprint
Target Milestone: --- → mozilla0.9.8
Target Milestone: mozilla0.9.8 → mozilla0.9.9
Priority: -- → P3
footprint is top priority for last 2 milestones.  
please address this bug soon.
thanks!!!
Blocks: 92580
Target Milestone: mozilla0.9.9 → mozilla1.0
Keywords: mozilla1.0+
nominating topembed. 
Keywords: topembed
topembed- per EDT, adding embed keyword.

Gordon, can you provide an estimate of the work/risk here?
Keywords: topembedembed, topembed-
We have plans to make this dynamic, but we have been concentrating on other
cache performance improvements.  The work on this has not been started yet.  I
would estimate it might take a couple weeks.
Target Milestone: mozilla1.0 → mozilla1.0.1
Keywords: mozilla1.0.1
OS: Linux → All
Hardware: PC → All
minusing due to owner's time assessment. should the target milestone be changed?
Any new target milestone information?
retargeting
Target Milestone: mozilla1.0.1 → Future
Some analysis:

nsDiskCacheRecord = 16 bytes
nsDiskCacheBucket = 256 (kRecordsPerBucket) * 16 sizeof(nsDiskCacheRecord) = 4096
    kCacheMapSize = sizeof(nsDiskCacheHeader) +
                    kBucketsPerTable * sizeof(nsDiskCacheBucket)
sizeof(nsDiskCacheHeader) is padded to sizeof(nsDiskCacheBucket), so also 4096
    actual data is 36*4 = 144 bytes
So, the total nsDiskCacheMap = comptr + FD* + 3*nsDiskCacheBlockFile +
nsDiskCacheHeader + nsDiskCacheBucket*kBucketsPerTable=
4+4+3*20+4096+4096*(1<<5) = 135236.

So, two culprits: 
1. the nsDiskCacheHeader which is padded to 4096, resulting in 3952 bytes overhead.
2. the 32 times 256 times 16 bytes for each DiskCacheRecord
The reason this is structured in this way, is that is easy to read/write from/to
disk (header+records).
Making this structure dynamically allocated is probably better for memory, but
no so good for the reading and writing.

Each DiskCacheBucket contains 256 entries for DiskCacheRecord, these form a sort
of linked list for each of the 32 hash entries (the 32 buckets).
One could either dynamically allocate the buckets, or the entries in the bucket
(may be incremental 16, 32, 64, 128, 256 entries, on demand). Both require more
memory allocation/free operations... And also instead of reading/writing the
whole map from/to disk, it needs to be then written in steps...
Not sure how much this would save... One of the advantages of the current setup
is that the memory usage is not fluctuating/growing/leaking because of this setup.


Checking my current disk cache, I saw only 231 entries, while the 32*256
bucket/recordentries allow for 8192 entries. May be a setup where initially only
1024 are used, but allowing expansion to 2048, 8192 when needed would help?
Or even start at 512 (so 1/16th of the original size, so about 9K instead of
135K)...
Patch coming up real soon now.
Based on the idea of using on array of records, logically divided into buckets,
growing with the need (from 512 to 8192). Code size will be comparable (may be
even less), but memory usage will be much less (instead of 135K, between 9k and
131K the most).
This patch implements a dynamic record array (from 256 entries to 8192).
This save 135K static allocated memory. Empty cache only needs just over 4K.
Growing in small steps (multiply by 2) the memory usage will remain close to
actual cache usage. 

Also the _CACHE_MAP_ file will be mostly smaller than 135K (a fresh cache only
4K), after some browsing 16K or 32K is a normal value.

This patch also removes the padding from the header (saving also 4K).

Also the 'EvictEntries' now uses NS_QuickSort to sort the records on
EvictionRank to better eviction according to the rank. The original algorithm
could be in worst case about O n2, but qsort is O n LN n...

It compiles, runs and even grows the map on demand.
There seems to be an issue with the 'EvictionRank' calculation, and needs
probably much more testing (and reviewing)
Attached patch Version 2: Works like a charm (obsolete) — Splinter Review
This version has some detected bugs removed (cleaning structures when growing).

Also some little patch cleanup, and removed all printf statements.
Note, still more testing required, before asking for reviews.
But comments are welcome anyway!
Attachment #178724 - Attachment is obsolete: true
Attached patch Version 3: Cleaned version (obsolete) — Splinter Review
Note that besides less memory usage (upto 128K!), the
nsDiskCacheMap code is also slightly faster and shrunk with ±1K codesize.
Attachment #178785 - Attachment is obsolete: true
Alfred: So, I'm very interested in moving the location of the cache for Firefox
1.1 into a user's Local Settings folder (on Windows that is).  Migrating cache
files from the current location to that location might be difficult, and I was
debating about whether or not to do so.  If we take this patch, then we'll be
scrapping the old cache files anyways, so that makes my decision easier.

Do you have any data to compare the performance of this modified cache map to
the old one?

-> me (gordon doesn't work on mozilla anymore)
Assignee: gordon → darin
Target Milestone: Future → mozilla1.8beta2
This excel sheet contains some performance statistics about this patch.
These are numbers collected by using PR_IntervalNow(), in a testrun opening by
hand a number of websites: ibm.com, mozilla.org, yahoo.com, netscape.com,
microsoft.com, excite.com, mirabilis.com and time.com.

Because of the testing I have reverted from QuickSort to the old algorithm for
EvictEntries. But other than that the patched code seems to be as fast as the
old code. The results are very noisy, and the average difference is very small.

The Find operation seems much faster, but this is probably still noise...
The numbers for Open range dramatically, but that's probably due to the file
operation (finding and opening a file is very dependent on the current state of
the filesystem).
This version reverts (after some performance analysis) to the old EvictRecords
algorithm, instead of using QuickSort (quicksort may be faster, but Malloc/Free
makes it slower, and keeping the memory is not nice for the footprint).

So, this patch now only changes from a fixed 132KB buffer (and _CACHE_MAP_)
size to a dynamic size, replacing the nsDiskCacheBucket class, with a more
flexible record array. The array grows 'on demand', and shrinks when 'Trim' is
called (to trim the blockfiles and _cache_map_).

Also removed some dead #include "nsCRT.h"
Attachment #179271 - Attachment is obsolete: true
Comment on attachment 180691 [details] [diff] [review]
Reverted to 'old' EvictRecords algorithm

Darin, can you review this? Requested performance statistics are attached, and
the net results are that the timings are comparable, but memory footprint is
100K less, codesize is slightly smaller, and disk usage is also 100K less.

This patch has been tested with large and very small disk cache sizes.
Attachment #180691 - Flags: review?(darin)
Attachment #180690 - Attachment is patch: false
Attachment #180690 - Attachment mime type: text/plain → application/octet-stream
If you eliminate the largest number for both old and new open times, then the
average open time sure seems to improve significantly.

Alfred, thanks for putting this patch together.  I will try to give it a careful
code review soon.
I still haven't found the cycles to review this, but I'm trying.  My patch for
bug 291033 currently discards the user's disk cache, so there is that window of
opportunity to change the disk cache format as well.
The patch doesn't compile in a debug build:

/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp: In member
   function `nsresult nsDiskCacheMap::Open(nsILocalFile*)':
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:99: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:111: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:128: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp: In member
   function `nsresult nsDiskCacheMap::FlushRecords(int)':
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:237: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:248: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:255: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp: In member
   function `nsresult nsDiskCacheMap::GrowRecords()':
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:309: warning:
comparison
   between signed and unsigned integer expressions
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp: In member
   function `nsresult nsDiskCacheMap::ShrinkRecords()':
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:342: warning: name
   lookup of `bucketIndex' changed for new ISO `for' scoping
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:328: warning:
   using obsolete binding at `bucketIndex'
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp: In member
   function `nsresult nsDiskCacheMap::DeleteRecord(nsDiskCacheRecord*)':
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:481: no matching
   function for call to `nsDiskCacheMap::GetBucketRank(PRUint32&)'
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:269: candidates
   are: PRUint32 nsDiskCacheMap::GetBucketRank(unsigned int, unsigned int)
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp: In member
   function `PRInt32 nsDiskCacheMap::VisitEachRecord(unsigned int,
   nsDiskCacheRecordVisitor*, unsigned int)':
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:520: no matching
   function for call to `nsDiskCacheMap::GetBucketRank(PRUint32&)'
/builds/moz-trunk/mozilla/netwerk/cache/src/nsDiskCacheMap.cpp:269: candidates
   are: PRUint32 nsDiskCacheMap::GetBucketRank(unsigned int, unsigned int)
gmake[1]: *** [nsDiskCacheMap.o] Error 1
gmake[1]: Leaving directory `/builds/moz-trunk/ffox-debug-build/netwerk/cache/src'
make: *** [all] Error 2

I think the problem is with the GetBucketRank calls made within NS_ASSERTION.  I
believe I can fix that problem.
Alfred: I'm probably going to post a slightly revised patch with fixes for the
build errors and warnings.  I may include other changes as well as I go over the
patch in detail.
Attached patch v4.1 patch (obsolete) — Splinter Review
This is a slightly revised version of the v4 patch.  Changes include the
following:

  rename mRecordArraySize to mRecordCount
  rename MIN/MAX_RECORD_COUNT to kMin/MaxRecordCount
  rename GetBucketSize to GetRecordsPerBucket (and similar changes to vars)
  rename GetBucketRecord to GetFirstRecordInBucket
  fix debug compile errors
  fix warnings about signed/unsigned mismatches

Good work on this patch.  I've tested it out, and I feel confident that it is
something ready to land.  I'd like to get this into 1.1a2 to maximize user
testing.
Attachment #180691 - Attachment is obsolete: true
Attachment #187249 - Flags: review+
Attachment #187249 - Flags: approval1.8b3?
Attachment #187249 - Flags: approval-aviary1.1a2?
Comment on attachment 187249 [details] [diff] [review]
v4.1 patch

Backup... something is wrong.  I don't see the cache being reused from session
to session.  Something about the way the cache map is being written out to disk
is causing it to not be loaded in properly.

Investigating...
Attachment #187249 - Flags: review-
Attachment #187249 - Flags: review+
Attachment #187249 - Flags: approval1.8b3?
Attachment #187249 - Flags: approval-aviary1.1a2?
Attached patch v4.2 patchSplinter Review
The problem with the previous patch was introduced by the v4.1 patch and was
just something silly on my part.
Attachment #187249 - Attachment is obsolete: true
Attachment #187253 - Flags: approval1.8b3?
Attachment #187253 - Flags: approval-aviary1.1a2?
Attachment #180691 - Flags: review?(darin)
Attachment #187253 - Flags: superreview+
Attachment #187253 - Flags: review+
Summary: footprint: 135236 btyes allocated by disk cache on startup → footprint: 135236 bytes allocated by disk cache on startup
Attachment #187253 - Flags: approval1.8b3?
Attachment #187253 - Flags: approval1.8b3+
Attachment #187253 - Flags: approval-aviary1.1a2?
fixed-on-trunk

now, to see if this makes any impact on tinderbox! :)
Status: NEW → RESOLVED
Closed: 19 years ago
Resolution: --- → FIXED
I really hate to bugspam but could someone post back the results like 
percentage on program startup time saved and memory saved? thanks
See comment #16, and check out the performance results on the tinderboxen:
http://tinderbox.mozilla.org/showbuilds.cgi?tree=SeaMonkey

It looks like this might of had a very slight impact on startup time on comet.
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: