← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_btree_serializer_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2010-08-04 01:52:14 UTC
  • mto: This revision was merged to the branch mainline in revision 5390.
  • Revision ID: john@arbash-meinel.com-20100804015214-5dbdub9p0qyc07dp
Add some tests that key lookup works.

Timing shows that looking up all 120 keys takes 205us, using bisect takes 184us.
So better, but not great. I'm a bit surprised it isn't faster, but perhaps
the comparison is a lot less of total time than the conversion to
python objects.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_btree_serializer_pyx.pyx
561
561
 
562
562
    cdef gc_chk_sha1_record* _lookup_record(self, char *sha1):
563
563
        """Find a gc_chk_sha1_record that matches the sha1 supplied."""
564
 
        # For right now we iterate, in the future we should bisect, or create
565
 
        # a local index, or use the sha1 as a hash into a local table, etc.
566
 
        cdef int i
567
 
        for i from 0 <= i < self.num_entries:
568
 
            if memcmp(self.entries[i].sha1, sha1, 20) == 0:
569
 
                return &self.entries[i]
 
564
        cdef int lo, hi, mid, the_cmp
 
565
 
 
566
        lo = 0
 
567
        hi = self.num_entries
 
568
 
 
569
        # Bisect until we find the right spot
 
570
        while lo < hi:
 
571
            mid = (lo + hi) / 2
 
572
            the_cmp = memcmp(sha1, self.entries[mid].sha1, 20)
 
573
            if the_cmp == 0:
 
574
                return &self.entries[mid]
 
575
            elif the_cmp < 0:
 
576
                hi = mid
 
577
            else:
 
578
                lo = mid + 1
570
579
        return NULL
571
580
 
572
581
    def __contains__(self, key):