[MERGE] Repository.get_revision_graph improvements
John Arbash Meinel
john at arbash-meinel.com
Tue Feb 26 23:30:40 GMT 2008
-----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-----
More information about the bazaar
mailing list