[MERGE] Fix LRUNode referencing

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

So I just found a true bug in the LRUNode referencing, and I have a
theoretical fix at the same time.

Specifically, I tracked down a stupid bug, that LRUCache._remove_node()
was removing the node from the dict (so you couldn't look it up) but
*not* removing the node from the linked list (so it stayed in memory).
Now, the referenced value was set to None, so at least we wouldn't hold
on to the actual data, but you could easily swamp memory with LRUNode
objects. With 3M tuples, I hit 750M of memory. (A lot of this would be
the actual tuple and string objects used as the 'key'.)

Anyway, the attached patch updates the test suite to actually check the
linked list after some removals, etc. (it had been checking the
accessible entries in the cache, but didn't walk the list).

It also makes one other change, which is to change the double
linked-list to add a bit of indirection in one way. This is just to make
things nicer for garbage collection. Namely, with a double linked list,
each object is a refcycle, with this change, you only have a single
pointer, which means that the standerd Py_DECREF should clean up the nodes.

In performance testing, fixing the linked-list removal made a big
difference :), using a level of indirection had a very small impact on
performance.

My test was the file_keys for the first 1k revs of mysql. Which amounts
to 2.8M tuples, with 8269 unique entries. I believe a tree is about 3k
files, so if you are <3k LRU and FIFO both have 100% misses, above that
you get decent hit rates with either one.

Time spent in hash(tuple) 2.0s
 0.67s	dict

22.63s	FIFOCache(1*1024) missed 2.8M
 1.47s	FIFOCache(4*1024) missed 18k
 1.38s	FIFOCache(10*1024) only missed the 8.2k unique

39.59s	LRUCache(1*1024) (next_node) missed 2.8M
 7.44s	LRUCache(4*1024) missed 17 keys (+8.2k unique)
 7.25s  LRUCache(10*1024)

38.90s	LRUCache(1*1024) (next_key) missed 2.8M
 7.75s	LRUCache(4*1024)
 7.69s	LRUCache(10*1024)

 8.36s	LRUCache(4*1024) (prev_key)

 9.01s	LRUCache(4*1024) (prev_key & next_key)


So a FIFO cache that has a good hit rate (99%) only costs a tiny bit
more than a dict (which was fairly expected).

One thing that actually surprised me was how big of a difference it made
whether you used next_key or prev_key. I thought it would be symmetric,
but it turned out not to be.

My initial guess is because of improvements in popping of the lru
(because you immediately have the pointer to the previous). During
__getitem__ they seemed very symmetric.

I was also able to do a little bit of tuning in __getitem__ to make it
slightly faster. So the net result is actually that the new form not
only avoids refcycles, but by tuning other code, the net result is just
as fast.

Now if only it wasn't 10x slower than a plain dict...

John
=:->

PS> I also (re)discovered that gzip.GzipFile and even our
tuned_gzip.GzipFile is surprisingly slow. If I did:

  for line in gzip.GzipFile('foo.txt.gz'):
    pass

it took almost 32s. (This was pretty much the same time if I used
tuned_gzip.GzipFile.)

If I did:

  zcat 'foo.txt.gz'

it took only about 3s.

If I did:

  p = subprocess.Popen('gzip -cd foo.txt.gz', stdout=subprocess.PIPE)
  for line in p.stdout:
    pass

It takes about 5s.

I was pretty surprised by the 32s => 3-5s change. I believe it was even
a bit faster to do "zcat | python -c 'import sys;
  for line in sys.stdin:
    pass
'"

I don't have much of an idea why sys.stdin would be faster than
Popen.stdin, but it wasn't a large enough difference for me to worry
about it.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAknnrGkACgkQJdeBCYSNAAM7zgCdFA3zN8WkeL+mkO0MK4rYpHnW
T9gAn2YicT53Cw8AnvUhSzlOC/xFn6DL
=n3vb
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: lru_cache_next_key.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20090416/534d941f/attachment-0001.diff