Rev 2916: (robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). in file:///home/pqm/archives/thelove/bzr/%2Btrunk/

[Canonical.com Patch Queue Manager]

At file:///home/pqm/archives/thelove/bzr/%2Btrunk/

------------------------------------------------------------
revno: 2916
revision-id: pqm at pqm.ubuntu.com-20071018040514-3hc1k2nj1umg3tig
parent: pqm at pqm.ubuntu.com-20071018032827-gg3yjbq11ex02168
parent: robertc at robertcollins.net-20071018011222-5o9z30dyowwxxrv9
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Thu 2007-10-18 05:05:14 +0100
message:
  (robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
modified:
  bzrlib/index.py                index.py-20070712131115-lolkarso50vjr64s-1
    ------------------------------------------------------------
    revno: 2911.3.1
    merged: robertc at robertcollins.net-20071018011222-5o9z30dyowwxxrv9
    parent: pqm at pqm.ubuntu.com-20071016112750-1q8brfaq6metpfn8
    committer: Robert Collins <robertc at robertcollins.net>
    branch nick: index
    timestamp: Thu 2007-10-18 11:12:22 +1000
    message:
      (robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py	2007-10-15 07:56:04 +0000
+++ b/bzrlib/index.py	2007-10-18 01:12:22 +0000
@@ -574,14 +574,17 @@
         readv_ranges = []
         for location, key in location_keys:
             # can we answer from cache?
-            # - if we know the answer - yes
+            if self._bisect_nodes and key in self._bisect_nodes:
+                # We have the key parsed.
+                continue
             index = self._parsed_key_index(key)
             if (len(self._parsed_key_map) and 
                 self._parsed_key_map[index][0] <= key and
-                (self._parsed_key_map[index][1] > key or
+                (self._parsed_key_map[index][1] >= key or
                  # end of the file has been parsed
                  self._parsed_byte_map[index][1] == self._size)):
-                # the key has been parsed, so no lookup is needed
+                # the key has been parsed, so no lookup is needed even if its
+                # not present.
                 continue
             # - if we have examined this part of the file already - yes
             index = self._parsed_byte_index(location)
@@ -609,33 +612,35 @@
         pending_locations = set()
         for location, key in location_keys:
             # can we answer from cache?
-            index = self._parsed_key_index(key)
-            if (self._parsed_key_map[index][0] <= key and
-                (self._parsed_key_map[index][1] > key or
-                 # end of the file has been parsed
-                 self._parsed_byte_map[index][1] == self._size)):
+            if key in self._bisect_nodes:
                 # the key has been parsed, so no lookup is needed
-                if key in self._bisect_nodes:
-                    if self.node_ref_lists:
-                        # the references may not have been all parsed.
-                        value, refs = self._bisect_nodes[key]
-                        wanted_locations = []
-                        for ref_list in refs:
-                            for ref in ref_list:
-                                if ref not in self._keys_by_offset:
-                                    wanted_locations.append(ref)
-                        if wanted_locations:
-                            pending_locations.update(wanted_locations)
-                            pending_references.append((location, key))
-                            continue
-                        result.append(((location, key), (self, key,
-                            value, self._resolve_references(refs))))
-                    else:
-                        result.append(((location, key),
-                            (self, key, self._bisect_nodes[key])))
+                if self.node_ref_lists:
+                    # the references may not have been all parsed.
+                    value, refs = self._bisect_nodes[key]
+                    wanted_locations = []
+                    for ref_list in refs:
+                        for ref in ref_list:
+                            if ref not in self._keys_by_offset:
+                                wanted_locations.append(ref)
+                    if wanted_locations:
+                        pending_locations.update(wanted_locations)
+                        pending_references.append((location, key))
+                        continue
+                    result.append(((location, key), (self, key,
+                        value, self._resolve_references(refs))))
                 else:
+                    result.append(((location, key),
+                        (self, key, self._bisect_nodes[key])))
+                continue
+            else:
+                # has the region the key should be in, been parsed?
+                index = self._parsed_key_index(key)
+                if (self._parsed_key_map[index][0] <= key and
+                    (self._parsed_key_map[index][1] >= key or
+                     # end of the file has been parsed
+                     self._parsed_byte_map[index][1] == self._size)):
                     result.append(((location, key), False))
-                continue
+                    continue
             # no, is the key above or below the probed location:
             # get the range of the probed & parsed location
             index = self._parsed_byte_index(location)