[ZODB-Dev] Another possible ZODB optimization

[Greg Ward]

Hi all --

you may recall my ranting back in December about how slow it is to open
a FileStorage under certain circumstances, and the profiling that
resulted from that, and one patch that resulted from that.  (Namely, I
rewrote the p64(), u64, and U64() functions from ZODB.utils in C.  This
yielded a 2x speedup in the time to open a FileStorage with no .index
file; it should also speed up everyday object fetching by some amount,
possibly measurable.  I haven't publicly released that patch yet because
my employer has yet to formalize a policy for releasing patches.  Sigh.)

I've been cooking up another patch in the meantime: specifically, I
wanted to reduce the memory overhead of FileStorage.  Since Jim and
Jeremy have already gone to some effort to do so for ZODB 3.2 --
specifically, by replacing the in-memory object index with a BTree --
you may wonder why.  Well, again you may recall that one of my profiling
tests found that that ZODB 3.2 code (ie. current CVS trunk) was both
slower and fatter than the 3.1 branch.  I haven't actually tracked this
down and pinned the blame on the BTree index, but that's certainly one
possibility.

So what I have cooked up is an alternate in-memory index, using a
custom-written hash table that just maps 8-byte strings (OIDs) to 64-bit
unsigned integers (file offsets).  This will certainly serve for the
main FileStorage 'index' attribute; I think it will also work for
'vindex' (which seems to map version IDs to file offsets, if I'm reading
the code correctly) and 'tindex'.  But 'index' is the real memory hog.

Anyways, initial results look promising: I wrote a script that creates
either a FastIndex object (my new type) or a plain dictionary, and
adds consecutive integers to it, eg.

  index['\0\0\0\0\0\0\0\0'] = ...
  index['\0\0\0\0\0\0\0\1'] = ...
  ...

Off the cuff, it looks like FastIndex is about 10% faster and 3x smaller
than a regular dictionary.  Specifically, to add 750,000 entries:

  dict        4.5 sec     64804 kB RSS
  FastIndex   4.1 sec     18568 kB RSS

Guess I should rename it to CompactIndex, eh?  (Note that 750,000
entries means a hash table of size 1,048,576; each table element is 16
bytes (8-byte OID, 8-byte file offset), so the hash table is 16 MB.  A
bare Python interpreter takes up 2212 kB on my system.  So the overhead
of this type, whatever I call it, is pretty minimal!)

It's entirely possible that I could make it faster -- Tim optimized the
snot out of Python's dictionaries a few releases back, and I've spent
only a few hours on FastIndex's performance, and all I did was make sure
the hash function isn't totally stupid.  Haven't done any profiling or
extensive tests of the hash function.

Anyways, does this sound like something worth pursuing?  Actually using
it would be a two-line change to FileStorage.py -- import it and modify
newIndeces() -- but I would need to write a good test suite before
anyone could take me seriously.

Also, I haven't done any performance tests of retrieval -- here I expect
Python dicts to be faster, because the values are already stored as
PyIntObjects or PyLongObjects -- retrieving a file pos from my FastIndex
requires creating a Py{Int,Long}Object to wrap the C uint64_t stored in
the table.  IOW, the whole thing could end up being performance-neutral
but still save memory.

        Greg
-- 
Greg Ward - software developer                gward@mems-exchange.org
MEMS Exchange                            http://www.mems-exchange.org