← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-10-18 04:05:14 UTC
  • mfrom: (2911.3.1 index)
  • Revision ID: pqm@pqm.ubuntu.com-20071018040514-3hc1k2nj1umg3tig
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
574
574
        readv_ranges = []
575
575
        for location, key in location_keys:
576
576
            # can we answer from cache?
577
 
            # - if we know the answer - yes
 
577
            if self._bisect_nodes and key in self._bisect_nodes:
 
578
                # We have the key parsed.
 
579
                continue
578
580
            index = self._parsed_key_index(key)
579
581
            if (len(self._parsed_key_map) and 
580
582
                self._parsed_key_map[index][0] <= key and
581
 
                (self._parsed_key_map[index][1] > key or
 
583
                (self._parsed_key_map[index][1] >= key or
582
584
                 # end of the file has been parsed
583
585
                 self._parsed_byte_map[index][1] == self._size)):
584
 
                # the key has been parsed, so no lookup is needed
 
586
                # the key has been parsed, so no lookup is needed even if its
 
587
                # not present.
585
588
                continue
586
589
            # - if we have examined this part of the file already - yes
587
590
            index = self._parsed_byte_index(location)
609
612
        pending_locations = set()
610
613
        for location, key in location_keys:
611
614
            # can we answer from cache?
612
 
            index = self._parsed_key_index(key)
613
 
            if (self._parsed_key_map[index][0] <= key and
614
 
                (self._parsed_key_map[index][1] > key or
615
 
                 # end of the file has been parsed
616
 
                 self._parsed_byte_map[index][1] == self._size)):
 
615
            if key in self._bisect_nodes:
617
616
                # the key has been parsed, so no lookup is needed
618
 
                if key in self._bisect_nodes:
619
 
                    if self.node_ref_lists:
620
 
                        # the references may not have been all parsed.
621
 
                        value, refs = self._bisect_nodes[key]
622
 
                        wanted_locations = []
623
 
                        for ref_list in refs:
624
 
                            for ref in ref_list:
625
 
                                if ref not in self._keys_by_offset:
626
 
                                    wanted_locations.append(ref)
627
 
                        if wanted_locations:
628
 
                            pending_locations.update(wanted_locations)
629
 
                            pending_references.append((location, key))
630
 
                            continue
631
 
                        result.append(((location, key), (self, key,
632
 
                            value, self._resolve_references(refs))))
633
 
                    else:
634
 
                        result.append(((location, key),
635
 
                            (self, key, self._bisect_nodes[key])))
 
617
                if self.node_ref_lists:
 
618
                    # the references may not have been all parsed.
 
619
                    value, refs = self._bisect_nodes[key]
 
620
                    wanted_locations = []
 
621
                    for ref_list in refs:
 
622
                        for ref in ref_list:
 
623
                            if ref not in self._keys_by_offset:
 
624
                                wanted_locations.append(ref)
 
625
                    if wanted_locations:
 
626
                        pending_locations.update(wanted_locations)
 
627
                        pending_references.append((location, key))
 
628
                        continue
 
629
                    result.append(((location, key), (self, key,
 
630
                        value, self._resolve_references(refs))))
636
631
                else:
 
632
                    result.append(((location, key),
 
633
                        (self, key, self._bisect_nodes[key])))
 
634
                continue
 
635
            else:
 
636
                # has the region the key should be in, been parsed?
 
637
                index = self._parsed_key_index(key)
 
638
                if (self._parsed_key_map[index][0] <= key and
 
639
                    (self._parsed_key_map[index][1] >= key or
 
640
                     # end of the file has been parsed
 
641
                     self._parsed_byte_map[index][1] == self._size)):
637
642
                    result.append(((location, key), False))
638
 
                continue
 
643
                    continue
639
644
            # no, is the key above or below the probed location:
640
645
            # get the range of the probed & parsed location
641
646
            index = self._parsed_byte_index(location)