[RFC] pack index lookup performance

[John Arbash Meinel]

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

Aaron Bentley wrote:
| Robert Collins wrote:
|> Indeed; this is where the hit/miss ratio is useful because hits get
|> cached per index, but there is no miss cache at the moment.
|
|> So if you ask a 1-record index that has been fully parsed for 15K keys
|> it does not have, it does 15K bisections.
|
| It seems we should be examining the hit caches of all indices before
| doing more expensive operations.  Are we doing that?
|
| Aaron

Yes. At least according to the code comments.

The first loop determines what needs to be read from disk, and it does 3 checks.

1) Is the key itself in the _bisect_nodes cache, do not read
2) Would the location of the key fit in the _parsed_key_map, do not read
3) Is the byte range for the key in our _parsed_byte_map ranges, do not read

Then we go and do disk/network reads, and parse the blocks into internal structures.

Then we have a second loop over each key

1) Is the key in self._bisect_nodes, if so append the result and go to next
2) Would the key fit between nodes in our _parsed_key_map, append False and go
to next
3) Since we have already parsed it, if we get here we need to look elsewhere,
note that fact.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkgFGdMACgkQJdeBCYSNAAOe5wCfddb03ZI9+TA5HuaNVUlzdZqc
zTEAn1wVch7h9PWw+KkdtppdWjfMc1m2
=n3ev
-----END PGP SIGNATURE-----