Merge lp:~spiv/bzr/smarter-index-search into lp:bzr

[Andrew Bennetts]

Optimise index lookups in repositories with many pack files.

First, the headline: this greatly improves "bzr pull" of one new revision of grub from savannah by HTTP (as reported on the mailing list, which has further analysis):

bzr.dev: 2424kB (50.2kB/s r:2395kB w:30kB)
this patch: 1034kB (43.3kB/s r:1022kB w:12kB)

Given that the pack data transferred is 701266 bytes (which itself seems quite large for such a small change...), that brings the index-searching overhead from 2.42x to 0.45x of the bytes read. It also halves the wall-clock time :)

That repo has I think 14 packs, and bzr.dev tries 11 indices for each of rix, iix, etc before finding the data it needs for that fetch.

There are two parts to this change:

 1) when a CombinedGraphIndex performs a lookup, it shuffles the index or indices that contained the records to the front of self._indices on the assumption that future lookups should try those first.
 2) propagates that reordering to the other CombinedGraphIndex objects from the same pack collection. This is done by a) associating a name (the pack name) with the elements of CombinedGraphIndex, and b) linking the revisions/inventories/etc CombinedGraphIndex objects belonging to a single pack collection via setting a _sibling_indices attribute on them, c) using those links and names to apply the same reordering to those sibling indices.

I've been pretty conservative with API changes: the new behaviour is only activated by optional keyword arguments, so existing uses of CombinedGraphIndex should see no change of behaviour (including no improvement). This is to make it as easy as possible to backport this change to 2.1 and 2.0 if we choose to.

I think this change needs some tests before it's truly ready to merge, but it's getting to the end of my work week and I think this code is ready for feedback, so here it is!

[John A Meinel (jameinel)]

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

Andrew Bennetts wrote:
> Andrew Bennetts has proposed merging lp:~spiv/bzr/smarter-index-search into lp:bzr.
>
> Requested reviews:
> bzr-core (bzr-core)
>
>
> Optimise index lookups in repositories with many pack files.
>
> First, the headline: this greatly improves "bzr pull" of one new revision of grub from savannah by HTTP (as reported on the mailing list, which has further analysis):
>
> bzr.dev: 2424kB (50.2kB/s r:2395kB w:30kB)
> this patch: 1034kB (43.3kB/s r:1022kB w:12kB)
>
> Given that the pack data transferred is 701266 bytes (which itself seems quite large for such a small change...), that brings the index-searching overhead from 2.42x to 0.45x of the bytes read. It also halves the wall-clock time :)
>
> That repo has I think 14 packs, and bzr.dev tries 11 indices for each of rix, iix, etc before finding the data it needs for that fetch.
>
> There are two parts to this change:
>
> 1) when a CombinedGraphIndex performs a lookup, it shuffles the index or indices that contained the records to the front of self._indices on the assumption that future lookups should try those first.
> 2) propagates that reordering to the other CombinedGraphIndex objects from the same pack collection. This is done by a) associating a name (the pack name) with the elements of CombinedGraphIndex, and b) linking the revisions/inventories/etc CombinedGraphIndex objects belonging to a single pack collection via setting a _sibling_indices attribute on them, c) using those links and names to apply the same reordering to those sibling indices.
>
> I've been pretty conservative with API changes: the new behaviour is only activated by optional keyword arguments, so existing uses of CombinedGraphIndex should see no change of behaviour (including no improvement). This is to make it as easy as possible to backport this change to 2.1 and 2.0 if we choose to.
>
> I think this change needs some tests before it's truly ready to merge, but it's getting to the end of my work week and I think this code is ready for feedback, so here it is!
>

Thanks for doing this. I did the work in Packer, but it is nice to have
it here.

I would tend to set "auto_reorder" to always on. I don't see it ever
making things worse, and there should only be a small overhead for the
reordering. As such, I would also get rid of the constructor flag.

Doing it by names is ok, I think Index already has _name for most
indices. You could also order by "access_tuple()" which I believe is a
public API and returns (transport, name) to the original .pack file. The
*nice* thing about doing that is that you don't have to introduce any
new apis here. But if it isn't as clean, then don't worry too much about it.

It also avoids having to rebuild the mapping for every move call:
+ indices_info = zip(self._index_names, self._indices)
+ hit_indices_info = []
+ hit_names = []
+ unhit_indices_info = []
+ for name, idx in indices_info:
+ if idx in hit_indices:
+ info = hit_indices_info
+ hit_names.append(name)
+ else:
+ info = unhit_indices_info
+ ...

[John A Meinel (jameinel)]

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

Andrew Bennetts wrote:
> Andrew Bennetts has proposed merging lp:~spiv/bzr/smarter-index-search into lp:bzr.
>
> Requested reviews:
> bzr-core (bzr-core)
>
>
> Optimise index lookups in repositories with many pack files.
>
> First, the headline: this greatly improves "bzr pull" of one new revision of grub from savannah by HTTP (as reported on the mailing list, which has further analysis):
>
> bzr.dev: 2424kB (50.2kB/s r:2395kB w:30kB)
> this patch: 1034kB (43.3kB/s r:1022kB w:12kB)
>
> Given that the pack data transferred is 701266 bytes (which itself seems quite large for such a small change...), that brings the index-searching overhead from 2.42x to 0.45x of the bytes read. It also halves the wall-clock time :)
>
> That repo has I think 14 packs, and bzr.dev tries 11 indices for each of rix, iix, etc before finding the data it needs for that fetch.
>
> There are two parts to this change:
>
> 1) when a CombinedGraphIndex performs a lookup, it shuffles the index or indices that contained the records to the front of self._indices on the assumption that future lookups should try those first.
> 2) propagates that reordering to the other CombinedGraphIndex objects from the same pack collection. This is done by a) associating a name (the pack name) with the elements of CombinedGraphIndex, and b) linking the revisions/inventories/etc CombinedGraphIndex objects belonging to a single pack collection via setting a _sibling_indices attribute on them, c) using those links and names to apply the same reordering to those sibling indices.
>
> I've been pretty conservative with API changes: the new behaviour is only activated by optional keyword arguments, so existing uses of CombinedGraphIndex should see no change of behaviour (including no improvement). This is to make it as easy as possible to backport this change to 2.1 and 2.0 if we choose to.
>
> I think this change needs some tests before it's truly ready to merge, but it's getting to the end of my work week and I think this code is ready for feedback, so here it is!
>

I forgot to vote.

  review: needs_fixing

Because it certainly should have some amount of testing. If only to
prevent future regressions (like we already have :). Though you don't
have to test it at the "get_stream()" level.

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

iEYEARECAAYFAkubrdwACgkQJdeBCYSNAAPiOgCcDS74mDZFRHc6TOjROAUcFsjj
0ykAoM7AAlpwfv/uNire7vqtLaBtkohG
=90G5
-----END PGP SIGNATURE-----

review: Needs Fixing

[Andrew Bennetts (spiv)]

John A Meinel wrote:
[...]
> Thanks for doing this. I did the work in Packer, but it is nice to have
> it here.

Ah! I thought we had something like this. I'll see what code and ideas
I can reuse.

> I would tend to set "auto_reorder" to always on. I don't see it ever
> making things worse, and there should only be a small overhead for the
> reordering. As such, I would also get rid of the constructor flag.

Hmm, ok. If I was just targetting bzr.dev I would have done this
already, but if you're confident it won't cause unexpected issues I'm
happy to make it unconditional (including in backports).

> Doing it by names is ok, I think Index already has _name for most
> indices. You could also order by "access_tuple()" which I believe is a
> public API and returns (transport, name) to the original .pack file. The
> *nice* thing about doing that is that you don't have to introduce any
> new apis here. But if it isn't as clean, then don't worry too much about it.

_name is really a path for _transport, and as such includes the suffix.
So I don't think it's as clean either code-wise or conceptually to rely
on that. And as you noticed later access_tuple is on AggregateIndex, so
it's not readily available either.

> If it isn't too much overhead, you might consider:
>
> keys_remove = keys.remove
> # Be careful, if keys starts empty, we would break, and get a name error
> index_hit_count = 0
> for index in self._indices:
> if not keys:
> break
> index_hit_count = 0
> for node in index.iter_entries(keys):
> keys_remove(node[1])
> yield node
> index_hit_count += 1
>
> if index_hit_count:
> hit_indices.append((index_hit_count, index))
>
> hit_indices.sort(reverse=True)
>
> self._move_index_order(hit_indices)
>
>
> The nice thing about it, is that it is adaptive. In that if you start a
> search, and hit it in index 1, then you keep looking there, but if the
> keys start showing up in index 2, then you'll switch. The only other bit
> of logic that I could think of is:

I don't quite follow you here. Wouldn't my logic switch to preferring
index 2 anyway?

It's not clear to me that ordering the hit_indices by hit count is
better.

> if index_hit_count == index.key_count():
> index_hit_count = 0 (or maybe 1)
>
> I realize to do this correctly, you'd need to track hit count between
> calls, which isn't realistic. However, that basic check will work for
> pack files that only have 1 or 2 keys that are found quickly. (And
> commit creates indexes with only 1 entry, so it is fairly common.) Just
> a thought, though.

This is an interesting idea. Although perhaps those look ups will
already fail very quickly because at that point that entire index has
already been read and cached? I don't think I'll do this in this patch
as I think it'd need more investigation and measurement to justify, but
it might make a good incremental improvement later.

> + # Tell all the CombinedGraphIndex objects about each other, so
> they can
> + # share hints about which pack names to search first.
> + all_combined = [agg_idx.combined_index for agg_idx in all_indices]
> + for combined_idx in all_combined:
> + ...

[Andrew Bennetts (spiv)]

Andrew Bennetts wrote:
> John A Meinel wrote:
[...]
> > The nice thing about it, is that it is adaptive. In that if you start a
> > search, and hit it in index 1, then you keep looking there, but if the
> > keys start showing up in index 2, then you'll switch. The only other bit
> > of logic that I could think of is:
>
> I don't quite follow you here. Wouldn't my logic switch to preferring
> index 2 anyway?

On reflection, I *think* what you mean is if a call to iter_entries (via
get_parent_map or otherwise) queries for [key_from_1, key_from_2,
key_from_2], my logic will keep the index order as [1, 2], but it might
be better to switch them to [2, 1]. (I initially thought that you were
talking about a search conducted over multiple calls to iter_entries,
not just one.)

That could be true, but I'm not sure it would really make a big
difference in practice. How about writing a patch for my patch and
doing some measurements? I'll happily review it :)

Or do you already have some analysis that would support this from when
you changed the Packer code?

-Andrew.

[John A Meinel (jameinel)]

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

Andrew Bennetts wrote:
> John A Meinel wrote:
> [...]
>> Thanks for doing this. I did the work in Packer, but it is nice to have
>> it here.
>
> Ah! I thought we had something like this. I'll see what code and ideas
> I can reuse.
>
>> I would tend to set "auto_reorder" to always on. I don't see it ever
>> making things worse, and there should only be a small overhead for the
>> reordering. As such, I would also get rid of the constructor flag.
>
> Hmm, ok. If I was just targetting bzr.dev I would have done this
> already, but if you're confident it won't cause unexpected issues I'm
> happy to make it unconditional (including in backports).
>
>> Doing it by names is ok, I think Index already has _name for most
>> indices. You could also order by "access_tuple()" which I believe is a
>> public API and returns (transport, name) to the original .pack file. The
>> *nice* thing about doing that is that you don't have to introduce any
>> new apis here. But if it isn't as clean, then don't worry too much about it.
>
> _name is really a path for _transport, and as such includes the suffix.
> So I don't think it's as clean either code-wise or conceptually to rely
> on that. And as you noticed later access_tuple is on AggregateIndex, so
> it's not readily available either.
>
>> If it isn't too much overhead, you might consider:
>>
>> keys_remove = keys.remove
>> # Be careful, if keys starts empty, we would break, and get a name error
>> index_hit_count = 0
>> for index in self._indices:
>> if not keys:
>> break
>> index_hit_count = 0
>> for node in index.iter_entries(keys):
>> keys_remove(node[1])
>> yield node
>> index_hit_count += 1
>>
>> if index_hit_count:
>> hit_indices.append((index_hit_count, index))
>>
>> hit_indices.sort(reverse=True)
>>
>> self._move_index_order(hit_indices)
>>
>>
>> The nice thing about it, is that it is adaptive. In that if you start a
>> search, and hit it in index 1, then you keep looking there, but if the
>> keys start showing up in index 2, then you'll switch. The only other bit
>> of logic that I could think of is:
>
> I don't quite follow you here. Wouldn't my logic switch to preferring
> index 2 anyway?
>
> It's not clear to me that ordering the hit_indices by hit count is
> better.
>

The point is that if the first index in the list gets 1 key hit, but the
second gets 10, and the third gets 5, then it will get sorted into
(index2, index3, index1) rather than (index1, index2, index3). At least,
what I saw with your code was that it is just 'preserve existing order,
but move the ones hit to the front'. Put another way, say the hits are:

5 index1
10 index2
0 index3
4 index5
0 index6

your version would sort to

index1
index2
index5
index3
index6

mine would sort to

index2
index1
index5
index3
index6

I think the latter is slightly preferred. I don't have any numbers to
back that up, just a feeling. (Most likely in this case index2 is a
'bigger' index, and thus has more to *be* hit.)

As for small indices getting rejected quickly, it is true they won't
encounter any I/O overhead, which may be sufficient. It is a function
call, but th...

[Andrew Bennetts (spiv)]

John A Meinel wrote:
[...]
> I think the latter is slightly preferred. I don't have any numbers to
> back that up, just a feeling. (Most likely in this case index2 is a
> 'bigger' index, and thus has more to *be* hit.)

I agree it probably helps, a little, but I'm not going to do it without
some measurements to confirm it does, because of the risk of
counter-intuitive results to untested optimisations. I know you've done
more exploring in this area so I trust your intuititions a bit more than
mine, but I'm still reluctant as the bang for buck seems low.

Also, even my simple logic will tend to keep the more hit indices closer
to the front than others after more and more queries, just not quite as
quickly as it might with hit counts. And this way we don't need to
worry about whether we should be keeping and aging hit counts between
queries, etc.

> As for small indices getting rejected quickly, it is true they won't
> encounter any I/O overhead, which may be sufficient. It is a function
> call, but that is probably tiny overhead, and they'll get sorted late
> quickly anyway.

Right. (FWIW, it's I/O overhead I'm most worried about.)

[Andrew Bennetts (spiv)]

I think all review comments have been addressed, but I'm sure John will tell me if I've missed something :)

[Martin Packman (gz)]

Don't know the code well enough to do a thorough review, but looks sane to me, tests pass, and it'll save me bandwidth.

review: Approve

[Robert Collins (lifeless)]

Andrew, when you and John are happy, I think you should just land this.

On the 'always reorder' side; if you do do that please check that the end of transaction stuff that pops off the in-progress indices won't be affected, back in the dim past it used [0] to 'know' that the first index was the one being written.

review: Approve

[Andrew Bennetts (spiv)]

Robert: Thanks for suggesting that. I've re-read a bunch of code and grepped, and as far as I can see, nothing is cheating by assuming [0] is the in-progress index that is being written. The test suite seems to pass too :)

So no changes needed there. I'm going to land this now before it goes stale.

[lp:~spiv/bzr/smarter-index-search]

5095. By Andrew Bennetts on 2010-04-08

Merge lp:bzr.

5096. By Andrew Bennetts on 2010-04-08

Add NEWS entry.

[John A Meinel (jameinel)]

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

Andrew Bennetts wrote:
> Andrew Bennetts has proposed merging lp:~spiv/bzr/smarter-index-search into lp:bzr.
>
> Requested reviews:
> John A Meinel (jameinel)
>
>
> Optimise index lookups in repositories with many pack files.
>
> First, the headline: this greatly improves "bzr pull" of one new revision of grub from savannah by HTTP (as reported on the mailing list, which has further analysis):

This doesn't seem to be as cheap as I expected it to be. I'm not 100%
sure who is at fault here, but I'm doing some profiling of loggerhead +
bzr-history-db, and I came across this:

       25765 3.4509 1.8229 bzrlib.index:1425(_move_to_front_by_index)
     +489715 0.8904 0.8904 +bzrlib.btree_index:689(__eq__)
     +541075 0.6721 0.6721 +<method 'append' of 'list' objects>
      +25765 0.0654 0.0654 +<zip>
      489809 0.8906 0.8906 bzrlib.btree_index:689(__eq__)
      590334 0.7374 0.7374 <method 'append' of 'list' objects>
         153 0.2031 0.2031 <method 'write' of 'file' objects>
       20612 3.0278 0.1986 bzrlib.index:1451(_move_to_front_by_name)
      +20612 2.7483 1.4505 +bzrlib.index:1425(_move_to_front_by_index)

I'm guessing the issue is something walking over the ancestry (like bzr log)

5153 3.8017 0.0712 bzrlib.index:1410(_move_to_front)

Note that only 5k calls to _move_to_front gets increased to 25k calls to
_move_to_front_by_index. (probably because there are
rix/iix/tix/cix/six, so a 5:1 factor).

However, we must be missing something for move to be that expensive.

I'm guessing this is:
https://bugs.launchpad.net/bugs/562429

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

iEYEARECAAYFAkvFOf4ACgkQJdeBCYSNAAN1DACggkq3WmxiFrLuE6Nqi/a7Jr+7
k6gAniipAYSMpW98NK22pdksK588g+1a
=RE1+
-----END PGP SIGNATURE-----

=== modified file 'NEWS'
--- NEWS	2010-04-08 04:34:03 +0000
+++ NEWS	2010-04-08 07:11:22 +0000
@@ -38,6 +38,12 @@
   generated by a template and not edited by the user.
   (Robert Collins, #530265)
 
+* Index lookups in pack repositories search recently hit pack files first.  
+  In repositories with many pack files this can greatly reduce the
+  number of files accessed, the number of bytes read, and the number of
+  read calls.  An incremental pull via plain HTTP takes half the time and
+  bytes for a moderately large repository.  (Andrew Bennetts)
+
 * Less code is loaded at startup.  (Cold-cache start time is about 10-20%
   less.)
   (Martin Pool, #553017)

=== modified file 'bzrlib/index.py'
--- bzrlib/index.py	2010-03-05 17:56:55 +0000
+++ bzrlib/index.py	2010-04-08 07:11:22 +0000
@@ -1245,10 +1245,15 @@
     static data.
 
     Queries against the combined index will be made against the first index,
-    and then the second and so on. The order of index's can thus influence
+    and then the second and so on. The order of indices can thus influence
     performance significantly. For example, if one index is on local disk and a
     second on a remote server, the local disk index should be before the other
     in the index list.
+    
+    Also, queries tend to need results from the same indices as previous
+    queries.  So the indices will be reordered after every query to put the
+    indices that had the result(s) of that query first (while otherwise
+    preserving the relative ordering).
     """
 
     def __init__(self, indices, reload_func=None):
@@ -1261,6 +1266,13 @@
         """
         self._indices = indices
         self._reload_func = reload_func
+        # Sibling indices are other CombinedGraphIndex that we should call
+        # _move_to_front_by_name on when we auto-reorder ourself.
+        self._sibling_indices = []
+        # A list of names that corresponds to the instances in self._indices,
+        # so _index_names[0] is always the name for _indices[0], etc.  Sibling
+        # indices must all use the same set of names as each other.
+        self._index_names = [None] * len(self._indices)
 
     def __repr__(self):
         return "%s(%s)" % (
@@ -1289,13 +1301,17 @@
 
     has_key = _has_key_from_parent_map
 
-    def insert_index(self, pos, index):
+    def insert_index(self, pos, index, name=None):
         """Insert a new index in the list of indices to query.
 
         :param pos: The position to insert the index.
         :param index: The index to insert.
+        :param name: a name for this index, e.g. a pack name.  These names can
+            be used to reflect index reorderings to related CombinedGraphIndex
+            instances that use the same names.  (see set_sibling_indices)
         """
         self._indices.insert(pos, index)
+        self._index_names.insert(pos, name)
 
     def iter_all_entries(self):
         """Iterate over all keys within the index
@@ -1326,22 +1342,28 @@
         value and are only reported once.
 
         :param keys: An iterable providing the keys to be retrieved.
-        :return: An iterable of (index, key, reference_lists, value). There is no
-            defined order for the result iteration - it will be in the most
+        :return: An iterable of (index, key, reference_lists, value). There is
+            no defined order for the result iteration - it will be in the most
             efficient order for the index.
         """
         keys = set(keys)
+        hit_indices = []
         while True:
             try:
                 for index in self._indices:
                     if not keys:
-                        return
+                        break
+                    index_hit = False
                     for node in index.iter_entries(keys):
                         keys.remove(node[1])
                         yield node
-                return
+                        index_hit = True
+                    if index_hit:
+                        hit_indices.append(index)
+                break
             except errors.NoSuchFile:
                 self._reload_or_raise()
+        self._move_to_front(hit_indices)
 
     def iter_entries_prefix(self, keys):
         """Iterate over keys within the index using prefix matching.
@@ -1367,17 +1389,77 @@
         if not keys:
             return
         seen_keys = set()
+        hit_indices = []
         while True:
             try:
                 for index in self._indices:
+                    index_hit = False
                     for node in index.iter_entries_prefix(keys):
                         if node[1] in seen_keys:
                             continue
                         seen_keys.add(node[1])
                         yield node
-                return
+                        index_hit = True
+                    if index_hit:
+                        hit_indices.append(index)
+                break
             except errors.NoSuchFile:
                 self._reload_or_raise()
+        self._move_to_front(hit_indices)
+
+    def _move_to_front(self, hit_indices):
+        """Rearrange self._indices so that hit_indices are first.
+
+        Order is maintained as much as possible, e.g. the first unhit index
+        will be the first index in _indices after the hit_indices, and the
+        hit_indices will be present in exactly the order they are passed to
+        _move_to_front.
+
+        _move_to_front propagates to all objects in self._sibling_indices by
+        calling _move_to_front_by_name.
+        """
+        hit_names = self._move_to_front_by_index(hit_indices)
+        for sibling_idx in self._sibling_indices:
+            sibling_idx._move_to_front_by_name(hit_names)
+
+    def _move_to_front_by_index(self, hit_indices):
+        """Core logic for _move_to_front.
+        
+        Returns a list of names corresponding to the hit_indices param.
+        """
+        indices_info = zip(self._index_names, self._indices)
+        if 'index' in debug.debug_flags:
+            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
+                   indices_info, hit_indices)
+        hit_indices_info = []
+        hit_names = []
+        unhit_indices_info = []
+        for name, idx in indices_info:
+            if idx in hit_indices:
+                info = hit_indices_info
+                hit_names.append(name)
+            else:
+                info = unhit_indices_info
+            info.append((name, idx))
+        final_info = hit_indices_info + unhit_indices_info
+        self._indices = [idx for (name, idx) in final_info]
+        self._index_names = [name for (name, idx) in final_info]
+        if 'index' in debug.debug_flags:
+            mutter('CombinedGraphIndex reordered: %r', self._indices)
+        return hit_names
+
+    def _move_to_front_by_name(self, hit_names):
+        """Moves indices named by 'hit_names' to front of the search order, as
+        described in _move_to_front.
+        """
+        # Translate names to index instances, and then call
+        # _move_to_front_by_index.
+        indices_info = zip(self._index_names, self._indices)
+        hit_indices = []
+        for name, idx in indices_info:
+            if name in hit_names:
+                hit_indices.append(idx)
+        self._move_to_front_by_index(hit_indices)
 
     def find_ancestry(self, keys, ref_list_num):
         """Find the complete ancestry for the given set of keys.
@@ -1390,6 +1472,7 @@
             we care about.
         :return: (parent_map, missing_keys)
         """
+        # XXX: make this call _move_to_front?
         missing_keys = set()
         parent_map = {}
         keys_to_lookup = set(keys)
@@ -1475,6 +1558,11 @@
                          ' Raising original exception.')
             raise exc_type, exc_value, exc_traceback
 
+    def set_sibling_indices(self, sibling_combined_graph_indices):
+        """Set the CombinedGraphIndex objects to reorder after reordering self.
+        """
+        self._sibling_indices = sibling_combined_graph_indices
+
     def validate(self):
         """Validate that everything in the index can be accessed."""
         while True:

=== modified file 'bzrlib/repofmt/pack_repo.py'
--- bzrlib/repofmt/pack_repo.py	2010-02-12 11:58:21 +0000
+++ bzrlib/repofmt/pack_repo.py	2010-04-08 07:11:22 +0000
@@ -587,26 +587,6 @@
                                              flush_func=flush_func)
         self.add_callback = None
 
-    def replace_indices(self, index_to_pack, indices):
-        """Replace the current mappings with fresh ones.
-
-        This should probably not be used eventually, rather incremental add and
-        removal of indices. It has been added during refactoring of existing
-        code.
-
-        :param index_to_pack: A mapping from index objects to
-            (transport, name) tuples for the pack file data.
-        :param indices: A list of indices.
-        """
-        # refresh the revision pack map dict without replacing the instance.
-        self.index_to_pack.clear()
-        self.index_to_pack.update(index_to_pack)
-        # XXX: API break - clearly a 'replace' method would be good?
-        self.combined_index._indices[:] = indices
-        # the current add nodes callback for the current writable index if
-        # there is one.
-        self.add_callback = None
-
     def add_index(self, index, pack):
         """Add index to the aggregate, which is an index for Pack pack.
 
@@ -619,7 +599,7 @@
         # expose it to the index map
         self.index_to_pack[index] = pack.access_tuple()
         # put it at the front of the linear index list
-        self.combined_index.insert_index(0, index)
+        self.combined_index.insert_index(0, index, pack.name)
 
     def add_writable_index(self, index, pack):
         """Add an index which is able to have data added to it.
@@ -645,6 +625,7 @@
         self.data_access.set_writer(None, None, (None, None))
         self.index_to_pack.clear()
         del self.combined_index._indices[:]
+        del self.combined_index._index_names[:]
         self.add_callback = None
 
     def remove_index(self, index):
@@ -653,7 +634,9 @@
         :param index: An index from the pack parameter.
         """
         del self.index_to_pack[index]
-        self.combined_index._indices.remove(index)
+        pos = self.combined_index._indices.index(index)
+        del self.combined_index._indices[pos]
+        del self.combined_index._index_names[pos]
         if (self.add_callback is not None and
             getattr(index, 'add_nodes', None) == self.add_callback):
             self.add_callback = None
@@ -1415,11 +1398,20 @@
         self.inventory_index = AggregateIndex(self.reload_pack_names, flush)
         self.text_index = AggregateIndex(self.reload_pack_names, flush)
         self.signature_index = AggregateIndex(self.reload_pack_names, flush)
+        all_indices = [self.revision_index, self.inventory_index,
+                self.text_index, self.signature_index]
         if use_chk_index:
             self.chk_index = AggregateIndex(self.reload_pack_names, flush)
+            all_indices.append(self.chk_index)
         else:
             # used to determine if we're using a chk_index elsewhere.
             self.chk_index = None
+        # Tell all the CombinedGraphIndex objects about each other, so they can
+        # share hints about which pack names to search first.
+        all_combined = [agg_idx.combined_index for agg_idx in all_indices]
+        for combined_idx in all_combined:
+            combined_idx.set_sibling_indices(
+                set(all_combined).difference([combined_idx]))
         # resumed packs
         self._resumed_packs = []
 

=== modified file 'bzrlib/tests/per_pack_repository.py'
--- bzrlib/tests/per_pack_repository.py	2010-02-23 07:43:11 +0000
+++ bzrlib/tests/per_pack_repository.py	2010-04-08 07:11:22 +0000
@@ -288,6 +288,23 @@
         repo._pack_collection._clear_obsolete_packs()
         self.assertTrue(repo_transport.has('obsolete_packs/.nfsblahblah'))
 
+    def test_pack_collection_sets_sibling_indices(self):
+        """The CombinedGraphIndex objects in the pack collection are all
+        siblings of each other, so that search-order reorderings will be copied
+        to each other.
+        """
+        repo = self.make_repository('repo')
+        pack_coll = repo._pack_collection
+        indices = set([pack_coll.revision_index, pack_coll.inventory_index,
+                pack_coll.text_index, pack_coll.signature_index])
+        if pack_coll.chk_index is not None:
+            indices.add(pack_coll.chk_index)
+        combined_indices = set(idx.combined_index for idx in indices)
+        for combined_index in combined_indices:
+            self.assertEqual(
+                combined_indices.difference([combined_index]),
+                combined_index._sibling_indices)
+
     def test_pack_after_two_commits_packs_everything(self):
         format = self.get_format()
         tree = self.make_branch_and_tree('.', format=format)

=== modified file 'bzrlib/tests/test_index.py'
--- bzrlib/tests/test_index.py	2010-03-05 17:56:55 +0000
+++ bzrlib/tests/test_index.py	2010-04-08 07:11:22 +0000
@@ -1380,6 +1380,50 @@
         self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
                                                  [('1',)])
 
+
+    def make_index_with_simple_nodes(self, name, num_nodes=1):
+        """Make an index named after 'name', with keys named after 'name' too.
+
+        Nodes will have a value of '' and no references.
+        """
+        nodes = [
+            (('index-%s-key-%s' % (name, n),), '', ())
+            for n in range(1, num_nodes+1)]
+        return self.make_index('index-%s' % name, 0, nodes=nodes)
+
+    def test_reorder_after_iter_entries(self):
+        # Four indices: [key1] in index1, [key2,key3] in index2, [] in index3,
+        # [key4] in index4.
+        index = CombinedGraphIndex([])
+        index.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
+        index.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
+        index.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
+        index.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
+        index1, index2, index3, index4 = index._indices
+        # Query a key from index4 and index2.
+        self.assertLength(2, list(index.iter_entries(
+            [('index-4-key-1',), ('index-2-key-1',)])))
+        # Now index2 and index4 should be moved to the front (and index1 should
+        # still be before index3).
+        self.assertEqual([index2, index4, index1, index3], index._indices)
+        self.assertEqual(['2', '4', '1', '3'], index._index_names)
+
+    def test_reorder_propagates_to_siblings(self):
+        # Two CombinedGraphIndex objects, with the same number of indicies with
+        # matching names.
+        cgi1 = CombinedGraphIndex([])
+        cgi2 = CombinedGraphIndex([])
+        cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
+        cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
+        cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
+        cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
+        index2_1, index2_2 = cgi2._indices
+        cgi1.set_sibling_indices([cgi2])
+        # Trigger a reordering in cgi1.  cgi2 will be reordered as well.
+        list(cgi1.iter_entries([('index-1-2-key-1',)]))
+        self.assertEqual([index2_2, index2_1], cgi2._indices)
+        self.assertEqual(['two', 'one'], cgi2._index_names)
+
     def test_validate_reloads(self):
         index, reload_counter = self.make_combined_index_with_missing()
         index.validate()