Index initialization improvements for Simple Cache.

Index initialization improvements for Simple Cache.

The Simple Cache index initialization path was making far too
many allocations, which caused an unneeded early peak in the
heap during index initialization. By reserving memory for
table resizes and making merges from small sets into big sets,
this peak is cut significantly.

R=pliard,ttuttle
BUG=None

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=216941

[gavinp, 2013-08-09 20:33:29]

FYI: here's the version that made the -reserve heap on
http://ytz.ca/~gavin/heaps

This version similar memory use blockfile cache on my sample, down from being
1.6MB higher.

I see tc-unused (i.e. free memory held by tcmalloc) at 5 980 965 bytes for
simple vs 5 996 813 for blockfile. total-exclude-profiler is 109 383 680 bytes
for simple vs 109 248 512 for blockfile, only 135 168 bytes more.

The code needs to be written properly, but the general approach is to avoid high
peak allocations and save memory to memory copies.

Is a transient mmap like this safe on teh androids?

[gavinp, 2013-08-10 15:35:50]

This is much closer to what I think we should land here. I'll add a unit test (I
had a bug in merge that tests didn't find during development), and make the
official request for review.

I'm not expert on the Android problems with memory maps; is a brief read only
map like used here kosher, or should we go back to using the std::string?

[gavinp, 2013-08-10 18:18:24]

rdsmith, ttuttle: PTAL. This is now ready for review, with the unit test.

pliard, digit1: FYI, and have a great vacation!

[Philippe, 2013-08-11 09:01:47]

lgtm, thanks Gavin! (yes, I know, I'm on vacation :))

Not related to this CL, but I was thinking that we should experiment with a
std::vector<> (I you haven't already done that) to get a lower bound for memory
usage as you suggested previously to see how much we could gain by working on
the index container. Also, this would definitely not be as elaborated as cuckoo
hashing or other alternatives that you mentioned but I was thinking that maybe
we could consider maintaining two containers:
- a sorted std::vector for the (rather old?) index entries that we load from
disk. These entries should be most of the index, right (for an old cache)? We
would be as compact as possible for them (and could also use discardable memory
maybe).
- a smaller (hash) map for the others that are added later through Insert()
assuming that this container would be much smaller (for old caches). It would be
useful to see with histograms which of those two containers is accessed more
often. Ideally we shouldn't keep dirty memory around for data that we
never/rarely access.  

But removal would be problematic with the vector (although we could perform the
actual removal for a bunch of keys every once in a while to have an amortized
cost). It would also not be convenient to have two separate containers.
Should we optimize in general for insert (I would expect so) or remove or both
of them? Maybe an insert vs remove histogram would be nice then if the answer is
not obvious. We will also need some benchmarks. I think we should rather
optimize for memory in general rather than aiming for screaming fast lookups
(e.g. binary search vs hashing) which should not matter as much as memory does
at this scale. But maybe we can also have both speed and compactness with more
elaborated hashing techniques :)

[gavinp, 2013-08-11 17:49:06]

On 2013/08/11 09:01:47, Philippe wrote:
> lgtm, thanks Gavin! (yes, I know, I'm on vacation :))
> 
> Not related to this CL, but I was thinking that we should experiment with a
> std::vector<> (I you haven't already done that) to get a lower bound for
memory
> usage as you suggested previously to see how much we could gain by working on
> the index container. Also, this would definitely not be as elaborated as
cuckoo
> hashing or other alternatives that you mentioned but I was thinking that maybe
> we could consider maintaining two containers:
> - a sorted std::vector for the (rather old?) index entries that we load from
> disk. These entries should be most of the index, right (for an old cache)? We
> would be as compact as possible for them (and could also use discardable
memory
> maybe).
> - a smaller (hash) map for the others that are added later through Insert()
> assuming that this container would be much smaller (for old caches). It would
be
> useful to see with histograms which of those two containers is accessed more
> often. Ideally we shouldn't keep dirty memory around for data that we
> never/rarely access.  
> 
> But removal would be problematic with the vector (although we could perform
the
> actual removal for a bunch of keys every once in a while to have an amortized
> cost). It would also not be convenient to have two separate containers.
> Should we optimize in general for insert (I would expect so) or remove or both
> of them? Maybe an insert vs remove histogram would be nice then if the answer
is
> not obvious. We will also need some benchmarks. I think we should rather
> optimize for memory in general rather than aiming for screaming fast lookups
> (e.g. binary search vs hashing) which should not matter as much as memory does
> at this scale. But maybe we can also have both speed and compactness with more
> elaborated hashing techniques :)

Philippe,

I agree on every point; cutting memory use on this structure is a good goal. We
have the 64 bit key + 128 bits of data per entry = 24 bytes, but the hash table
is allocating ~34-36 bytes per entry.

Strictly speaking, we need a lot less data: 40 bit keys are fine (and save disk
space too), and we don't need to store per-entry size if we can accurately
communicate deltas (we do need to keep a whole cache size to calculate
evictions)... So we could definitely use less memory. Cuckoo hashing is
interesting because it's a hash structure that lets this work well; but it's
also true that a vector for searching is fine. We do lots and lots of deletes in
the normal path (recall: we create for all outgoing HTTP requests, and delete
when no-store responses come back), so if we did, we'd want a process to merge
periodically from a smaller in-memory hash table of some kind.

The whole area deserves good consideration if we want to save more memory. I'm
glad we've gotten rid of the early peak.

[gavinp, 2013-08-11 17:50:08]

I've CQ+ed this. Reviewers, please don't let that stop you from looking over
this important CL.

Offline talking to Philippe, he expressed quite a bit of comfort in the short,
read only, sequentially accessed memory map we use here.

[commit-bot: I haz the power, 2013-08-11 17:50:25]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/gavinp@chromium.org/22406005/48001

[commit-bot: I haz the power, 2013-08-12 05:50:24]

Change committed as 216941

[Randy Smith (Not in Mondays), 2013-08-12 17:02:19]

LGTM.

https://codereview.chromium.org/22406005/diff/48001/net/disk_cache/simple/sim...
File net/disk_cache/simple/simple_index.cc (right):

https://codereview.chromium.org/22406005/diff/48001/net/disk_cache/simple/sim...
net/disk_cache/simple/simple_index.cc:369: possibly_inserted_entry->second =
it->second;
Suggestion: Why not test insert_result.second to decide whether to insert?  I
sorta assume it's in cache anyway since we're touching .first, and it'd save a
24 byte copy.  I don't see a reason to believe that that case would be
particularly common or uncommon.

(I believe your judgement will be better than mine as to whether this is a good
idea, thus "suggestion".)

[gavinp, 2013-08-13 11:11:04]

https://chromiumcodereview.appspot.com/22406005/diff/48001/net/disk_cache/sim...
File net/disk_cache/simple/simple_index.cc (right):

https://chromiumcodereview.appspot.com/22406005/diff/48001/net/disk_cache/sim...
net/disk_cache/simple/simple_index.cc:369: possibly_inserted_entry->second =
it->second;
On 2013/08/12 17:02:20, rdsmith wrote:
> Suggestion: Why not test insert_result.second to decide whether to insert?  I
> sorta assume it's in cache anyway since we're touching .first, and it'd save a
> 24 byte copy.  I don't see a reason to believe that that case would be
> particularly common or uncommon.

I think it's just a copy of EntrySet::data_type you're talking about saving, not
EntrySet::value_type, so it's 16 bytes, not 24. But that's a minor detail.

I originally coded it this way you mentioned. The constructor EntryMetadata() on
line 368 had to be replaced with |it->second|, and then recapitulated in the
case that insert_result.second is false; that repetition seemed a bit confusing,
so I went with the less conditional path.

I'm pretty sure, but I didn't check by compiling, that data flow analysis should
be able to toss out the redundant call to EntryMetadata(), making this just as
efficient. The constructor to EntryMetadata is inline able in this context. The
STL authors are actually fairly careful about this, because this code is the
same as:

  index_file_entries[entry_hash] = it->second;

And now that I think about it, perhaps we should replace lihnes 368-370 with
just that. I'll upload that CL later today.
> 
> (I believe your judgement will be better than mine as to whether this is a
good
> idea, thus "suggestion".)

[gavinp, 2013-08-13 14:12:08]

I just created Bug 272062 for this.

[gavinp, 2013-08-13 14:12:24]

On 2013/08/13 14:12:08, gavinp wrote:
> I just created Bug 272062 for this.

https://code.google.com/p/chromium/issues/detail?id=272062