[MERGE] Repository.get_revision_graph improvements

[John Arbash Meinel]

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

Robert Collins wrote:
> On Tue, 2008-02-26 at 16:16 -0600, John Arbash Meinel wrote:
> ...
> 

...

> 
> You should check the branch out sometime :)
> 
> -Rob
> 

After reading through the details, it is missing one of the things that
I think would be key for scalability. Specifically, the ability to
combine the hash maps across packs. Without it, we will always have to
scale O(num_packs) because you will end up checking in each index to see
if it hits. (arguably n/2, but still scaling with n).

If we instead chose a fixed hash algorithm to say 32-bit integers then
the combined index can have 1 single hash => (index, offset) map. So
when looking up revision-foo-bar you hash it 1 time, and get back the
possible indexes and positions right away.

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

iD8DBQFHxKEgJdeBCYSNAAMRAh8CAKC3CHK72v2Kz6dP7koPeP4uiTaUDwCbBtB9
/EjzFEPhVffPP5gAsec7cOk=
=XGPY
-----END PGP SIGNATURE-----