Merge lp:~jameinel/bzr/2.3-btree-chk-leaf into lp:bzr

[John A Meinel]

Use a custom class definition for CHK BTree leaf nodes.

This changes the BTreeGraphIndex class for CHK indexes.
It replaces them with a custom structure that I described on the list. The net effect is to change us from using something like 200+ bytes / index record (400+ on 64-bit) down to very close to 42bytes/record (32 and 64 bit))

It also speeds up creating these objects, though my overall timing shows that isn't really a dominant factor.

It creates the appropriate tuples as-requested, which is where most of the memory savings gain is. (40-bytes is going to be 1 string, much less all the extra tuples and such that go along with it.)

This is valid to do, because often our chk indexes are underutilized. Every time we read 1 we have to read ~100, and because they are hashes, they are distributed and we rarely read more than 1 from a single index.

The main thing I'm not sure about, is how I expose this to the repository. We've done a 'unlimited_cache=True' flag for the last round of chk-specific changes. I didn't really want to add yet-another flag, but manually setting a private member isn't a lot better.

If someone has a good idea here, I'm happy to change that code.

This also changes the BTreeIndex code, so that it treats the LeafNodes themselves as dicts, rather than using an attribute on them. This is potentially a small slowdown (according to timeit). (x in o._dict), is slightly faster than (x in subclass_dict), which really surprised me. Though a custom __getitem__ that thunks over to self._dict is much slower.

 11.3us dict[x]
 15.6us class._dict[x]
 28.2us subclass[x]
 56us __getitem__(return self._dict[x])

I think it is okay, though it is a shame to regress the normal case.

[lp:~jameinel/bzr/2.3-btree-chk-leaf]

5388. By John A Meinel on 2010-08-06

A __sizeof__ check that ensure we are getting what we are looking for.

It also checks that it grows appropriately for how many new entries are added.

[Vincent Ladeuil (vila)]

Wow, I clicked Status -> Approved while my comment was being processed and it get lost :-/

Here it is again:

Nice catch !

You had test code (_test_* functions) in production code which has a bad smell,
with this tweaked, please land.

review: Needs Fixing

[John A Meinel (jameinel)]

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

On 8/20/2010 7:19 AM, Vincent Ladeuil wrote:
> Review: Needs Fixing
> Wow, I clicked Status -> Approved while my comment was being processed and it get lost :-/
>
> Here it is again:
>
> Nice catch !
>
> You had test code (_test_* functions) in production code which has a bad smell,
> with this tweaked, please land.
>

They aren't actually test functions. They are Python wrappers to expose
the pure C functions to the test infrastructure.

How would you like me to tweak it? I intentionally called them "test_*"
so that it would be obvious not to call them from production code...

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

iEYEARECAAYFAkxyfoMACgkQJdeBCYSNAANsYwCggTDnJPLzlmlM+erieFXnsWK5
/S8AoL7RVhlsMx0RSMykIKqZul2GwWCv
=oeNU
-----END PGP SIGNATURE-----

[lp:~jameinel/bzr/2.3-btree-chk-leaf]

5389. By John A Meinel on 2010-08-23

Change the _test names to _get and _py so that it doesn't provoke bad smells :)

5390. By John A Meinel on 2010-08-23

Merge bzr.dev 5387 in prep for NEWS

5391. By John A Meinel on 2010-08-23

Update What's New and NEWS

[John A Meinel (jameinel)]

sent to pqm by email

[lp:~jameinel/bzr/2.3-btree-chk-leaf]

5392. By John A Meinel on 2010-08-23

switch 'x += 1' to 'x = x + 1' to deal with brain-damaged old versions of pyrex.

[John A Meinel (jameinel)]

sent to pqm by email

[lp:~jameinel/bzr/2.3-btree-chk-leaf]

5393. By John A Meinel on 2010-08-23

Lots of compatibility changes for python2.4 and mingw32 compilers.

gcc has strtoll available, and does the wrong thing if you use _strtoi64 (it implicitly
defines it to return an 'int' which isn't a 64-bit integer.)

Further, python2.4 doesn't support the %lu syntax, only having %ld and %d. So we go
back to casting everything into real python objects and then stringifying them, but
only for python 2.4.

[John A Meinel (jameinel)]

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

On 8/23/2010 2:38 PM, John A Meinel wrote:
> sent to pqm by email
>

Sorry for the extra merge noise. It turns out things were a bit uglier
than I thought for older versions of python.

Specifically, python 2.4 PyString_FromFormat() only supports ('%d'). It
doesn't support '%lu' or even '%u'. This was changed again in python 2.7
to support '%llu', but the docs only mention that last change, not the
python2.5 change to add '%lu' support.

You can see the difference in here:
  http://docs.python.org/release/2.4.4/api/stringObjects.html

versus:
  http://docs.python.org/release/2.5.4/api/stringObjects.html

versus:
  http://docs.python.org/c-api/string.html#PyString_FromFormat

I also ran into pyrex 0.9.6 vs 0.9.8 vs Cython incompatibilities, etc.

However, I've now ran the test suite on python 2.4.4 w/ pyrex 0.9.6.4
(matching hardy, I think), and python 2.5 pyrex 0.9.8.5 and python 2.6
Cython 0.11.2

Which I think should cover everything.

Oh, and it also covers using 'gcc' vs 'cl'. Since 'gcc' supports strtoll
directly, while cl needs to use _strtoi64. (If you use _strtoi64 w/ gcc,
but don't define it, then it auto-defines it to return a simple 'int'
which is only 32 bits.)

So I'm pretty sure this will handle what we need. Babune can tell me if
I missed anything, I guess. :)

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

iEYEARECAAYFAkxy75gACgkQJdeBCYSNAAPdvwCgifspGLbTe5vaHvCvE0Y+P3Oi
MQYAnjuxPkiBcKI18jnxNfznp0zmKmT7
=pU3B
-----END PGP SIGNATURE-----

[John A Meinel (jameinel)]

sent to pqm by email

[lp:~jameinel/bzr/2.3-btree-chk-leaf]

5394. By John A Meinel on 2010-08-24

Handle test_source and extensions. Also define an 'extern' protocol, to allow
the test suite to recognize that returning an object of that type is a Python object.

=== modified file 'NEWS'
--- NEWS	2010-08-21 17:09:54 +0000
+++ NEWS	2010-08-24 19:24:49 +0000
@@ -104,6 +104,13 @@
   will be backed up (adding an extention of the form .~#~).
   (Marius Kruger, #400554)
 
+* Decrease memory consumption when many chk index pages are loaded. (Such
+  as during ``bzr co`` or ``bzr ls -R`` of a large tree.) Often we need to
+  read many chk pages because the individual chk map nodes will be spread
+  randomly. Peak memory for 'bzr ls -R' on a large tree dropped from 396MB
+  down to 247MB, expect even more significant savings on 64-bit platforms.
+  (John Arbash Meinel)
+
 * Inventory entries now consume less memory (on 32-bit Ubuntu file entries
   have dropped from 68 bytes to 40, and directory entries from 120 bytes
   to 48).  (Andrew Bennetts)

=== modified file 'bzrlib/_btree_serializer_pyx.pyx'
--- bzrlib/_btree_serializer_pyx.pyx	2010-02-17 17:11:16 +0000
+++ bzrlib/_btree_serializer_pyx.pyx	2010-08-24 19:24:49 +0000
@@ -33,6 +33,7 @@
     char *PyString_AsString(object p) except NULL
     object PyString_FromStringAndSize(char *, Py_ssize_t)
     PyObject *PyString_FromStringAndSize_ptr "PyString_FromStringAndSize" (char *, Py_ssize_t)
+    object PyString_FromFormat(char *, ...)
     int PyString_CheckExact(object s)
     int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *)
     Py_ssize_t PyString_Size(object p)
@@ -49,19 +50,31 @@
     PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
     void Py_INCREF(object)
     void Py_DECREF_ptr "Py_DECREF" (PyObject *)
+    void *PyMem_Malloc(size_t nbytes)
+    void PyMem_Free(void *)
+    void memset(void *, int, size_t)
 
 cdef extern from "string.h":
     void *memcpy(void *dest, void *src, size_t n)
     void *memchr(void *s, int c, size_t n)
+    int memcmp(void *s1, void *s2, size_t n)
     # GNU extension
     # void *memrchr(void *s, int c, size_t n)
     int strncmp(char *s1, char *s2, size_t n)
+    unsigned long strtoul(char *s1, char **out, int base)
+    long long strtoll(char *s1, char **out, int base)
+
 
 # It seems we need to import the definitions so that the pyrex compiler has
 # local names to access them.
 from _static_tuple_c cimport StaticTuple, \
     import_static_tuple_c, StaticTuple_New, \
-    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
+    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact, \
+    StaticTuple_GET_SIZE, StaticTuple_GET_ITEM
+# This tells the test infrastructure that StaticTuple is a class, so we don't
+# have to worry about exception checking.
+## extern cdef class StaticTuple
+import sys
 
 
 # TODO: Find some way to import this from _dirstate_helpers
@@ -103,7 +116,6 @@
     Py_DECREF_ptr(py_str)
     return result
 
-from bzrlib import _static_tuple_c
 # This sets up the StaticTuple C_API functionality
 import_static_tuple_c()
 
@@ -315,6 +327,537 @@
     return parser.parse()
 
 
+# TODO: We can go from 8 byte offset + 4 byte length to a simple lookup,
+#       because the block_offset + length is likely to be repeated. However,
+#       the big win there is to cache across pages, and not just one page
+#       Though if we did cache in a page, we could certainly use a short int.
+#       And this goes from 40 bytes to 30 bytes.
+#       One slightly ugly option would be to cache block offsets in a global.
+#       However, that leads to thread-safety issues, etc.
+ctypedef struct gc_chk_sha1_record:
+    long long block_offset
+    unsigned int block_length
+    unsigned int record_start
+    unsigned int record_end
+    char sha1[20]
+
+
+cdef int _unhexbuf[256]
+cdef char *_hexbuf
+_hexbuf = '0123456789abcdef'
+
+cdef _populate_unhexbuf():
+    cdef int i
+    for i from 0 <= i < 256:
+        _unhexbuf[i] = -1
+    for i from 0 <= i < 10: # 0123456789 => map to the raw number
+        _unhexbuf[(i + c'0')] = i
+    for i from 10 <= i < 16: # abcdef => 10, 11, 12, 13, 14, 15, 16
+        _unhexbuf[(i - 10 + c'a')] = i
+    for i from 10 <= i < 16: # ABCDEF => 10, 11, 12, 13, 14, 15, 16
+        _unhexbuf[(i - 10 + c'A')] = i
+_populate_unhexbuf()
+
+
+cdef int _unhexlify_sha1(char *as_hex, char *as_bin): # cannot_raise
+    """Take the hex sha1 in as_hex and make it binary in as_bin
+    
+    Same as binascii.unhexlify, but working on C strings, not Python objects.
+    """
+    cdef int top
+    cdef int bot
+    cdef int i, j
+    cdef char *cur
+    
+    # binascii does this using isupper() and tolower() and ?: syntax. I'm
+    # guessing a simple lookup array should be faster.
+    j = 0
+    for i from 0 <= i < 20:
+        top = _unhexbuf[<unsigned char>(as_hex[j])]
+        j = j + 1
+        bot = _unhexbuf[<unsigned char>(as_hex[j])]
+        j = j + 1
+        if top == -1 or bot == -1:
+            return 0
+        as_bin[i] = <unsigned char>((top << 4) + bot);
+    return 1
+
+
+def _py_unhexlify(as_hex):
+    """For the test infrastructure, just thunks to _unhexlify_sha1"""
+    if len(as_hex) != 40 or not PyString_CheckExact(as_hex):
+        raise ValueError('not a 40-byte hex digest')
+    as_bin = PyString_FromStringAndSize(NULL, 20)
+    if _unhexlify_sha1(PyString_AS_STRING(as_hex), PyString_AS_STRING(as_bin)):
+        return as_bin
+    return None
+
+
+cdef void _hexlify_sha1(char *as_bin, char *as_hex): # cannot_raise
+    cdef int i, j
+    cdef char c
+
+    j = 0
+    for i from 0 <= i < 20:
+        c = as_bin[i]
+        as_hex[j] = _hexbuf[(c>>4)&0xf]
+        j = j + 1
+        as_hex[j] = _hexbuf[(c)&0xf]
+        j = j + 1
+
+
+def _py_hexlify(as_bin):
+    """For test infrastructure, thunk to _hexlify_sha1"""
+    if len(as_bin) != 20 or not PyString_CheckExact(as_bin):
+        raise ValueError('not a 20-byte binary digest')
+    as_hex = PyString_FromStringAndSize(NULL, 40)
+    _hexlify_sha1(PyString_AS_STRING(as_bin), PyString_AS_STRING(as_hex))
+    return as_hex
+
+
+cdef int _key_to_sha1(key, char *sha1): # cannot_raise
+    """Map a key into its sha1 content.
+
+    :param key: A tuple of style ('sha1:abcd...',)
+    :param sha1: A char buffer of 20 bytes
+    :return: 1 if this could be converted, 0 otherwise
+    """
+    cdef char *c_val
+    cdef PyObject *p_val
+
+    if StaticTuple_CheckExact(key) and StaticTuple_GET_SIZE(key) == 1:
+        p_val = <PyObject *>StaticTuple_GET_ITEM(key, 0)
+    elif (PyTuple_CheckExact(key) and PyTuple_GET_SIZE(key) == 1):
+        p_val = PyTuple_GET_ITEM_ptr_object(key, 0)
+    else:
+        # Not a tuple or a StaticTuple
+        return 0
+    if (PyString_CheckExact_ptr(p_val) and PyString_GET_SIZE_ptr(p_val) == 45):
+        c_val = PyString_AS_STRING_ptr(p_val)
+    else:
+        return 0
+    if strncmp(c_val, 'sha1:', 5) != 0:
+        return 0
+    if not _unhexlify_sha1(c_val + 5, sha1):
+        return 0
+    return 1
+
+
+def _py_key_to_sha1(key):
+    """Map a key to a simple sha1 string.
+
+    This is a testing thunk to the C function.
+    """
+    as_bin_sha = PyString_FromStringAndSize(NULL, 20)
+    if _key_to_sha1(key, PyString_AS_STRING(as_bin_sha)):
+        return as_bin_sha
+    return None
+
+
+cdef StaticTuple _sha1_to_key(char *sha1):
+    """Compute a ('sha1:abcd',) key for a given sha1."""
+    cdef StaticTuple key
+    cdef object hexxed
+    cdef char *c_buf
+    hexxed = PyString_FromStringAndSize(NULL, 45)
+    c_buf = PyString_AS_STRING(hexxed)
+    memcpy(c_buf, 'sha1:', 5)
+    _hexlify_sha1(sha1, c_buf+5)
+    key = StaticTuple_New(1)
+    Py_INCREF(hexxed)
+    StaticTuple_SET_ITEM(key, 0, hexxed)
+    # This is a bit expensive. To parse 120 keys takes 48us, to return them all
+    # can be done in 66.6us (so 18.6us to build them all).
+    # Adding simple hash() here brings it to 76.6us (so computing the hash
+    # value of 120keys is 10us), Intern is 86.9us (another 10us to look and add
+    # them to the intern structure.)
+    # However, since we only intern keys that are in active use, it is probably
+    # a win. Since they would have been read from elsewhere anyway.
+    # We *could* hang the PyObject form off of the gc_chk_sha1_record for ones
+    # that we have deserialized. Something to think about, at least.
+    key = StaticTuple_Intern(key)
+    return key
+
+
+def _py_sha1_to_key(sha1_bin):
+    """Test thunk to check the sha1 mapping."""
+    if not PyString_CheckExact(sha1_bin) or PyString_GET_SIZE(sha1_bin) != 20:
+        raise ValueError('sha1_bin must be a str of exactly 20 bytes')
+    return _sha1_to_key(PyString_AS_STRING(sha1_bin))
+
+
+cdef unsigned int _sha1_to_uint(char *sha1): # cannot_raise
+    cdef unsigned int val
+    # Must be in MSB, because that is how the content is sorted
+    val = (((<unsigned int>(sha1[0]) & 0xff) << 24)
+           | ((<unsigned int>(sha1[1]) & 0xff) << 16)
+           | ((<unsigned int>(sha1[2]) & 0xff) << 8)
+           | ((<unsigned int>(sha1[3]) & 0xff) << 0))
+    return val
+
+
+cdef _format_record_py24(gc_chk_sha1_record *record):
+    """Python2.4 PyString_FromFormat doesn't have %u.
+
+    It only has %d and %ld. We would really like to even have %llu, which
+    is only in python2.7. So we go back into casting to regular objects.
+    """
+    return "%s %s %s %s" % (record.block_offset, record.block_length,
+                            record.record_start, record.record_end)
+
+
+cdef _format_record(gc_chk_sha1_record *record):
+    # This is inefficient to go from a logical state back to a
+    # string, but it makes things work a bit better internally for now.
+    if record.block_offset >= 0xFFFFFFFF:
+        # %llu is what we really want, but unfortunately it was only added
+        # in python 2.7... :(
+        block_offset_str = str(record.block_offset)
+        value = PyString_FromFormat('%s %lu %lu %lu',
+                                PyString_AS_STRING(block_offset_str),
+                                record.block_length,
+                                record.record_start, record.record_end)
+    else:
+        value = PyString_FromFormat('%lu %lu %lu %lu',
+                                    <unsigned long>record.block_offset,
+                                    record.block_length,
+                                    record.record_start, record.record_end)
+    return value
+
+ctypedef object (*formatproc)(gc_chk_sha1_record *)
+cdef formatproc _record_formatter
+_record_formatter = _format_record
+if sys.version_info[:2] == (2, 4):
+    _record_formatter = _format_record_py24
+
+
+cdef class GCCHKSHA1LeafNode:
+    """Track all the entries for a given leaf node."""
+
+    cdef gc_chk_sha1_record *records
+    cdef public object last_key
+    cdef gc_chk_sha1_record *last_record
+    cdef public int num_records
+    # This is the number of bits to shift to get to the interesting byte. A
+    # value of 24 means that the very first byte changes across all keys.
+    # Anything else means that there is a common prefix of bits that we can
+    # ignore. 0 means that at least the first 3 bytes are identical, though
+    # that is going to be very rare
+    cdef public unsigned char common_shift
+    # This maps an interesting byte to the first record that matches.
+    # Equivalent to bisect.bisect_left(self.records, sha1), though only taking
+    # into account that one byte.
+    cdef unsigned char offsets[257]
+
+    def __sizeof__(self):
+        # :( Why doesn't Pyrex let me do a simple sizeof(GCCHKSHA1LeafNode)
+        # like Cython? Explicitly enumerating everything here seems to leave my
+        # size off by 2 (286 bytes vs 288 bytes actual). I'm guessing it is an
+        # alignment/padding issue. Oh well- at least we scale properly with
+        # num_records and are very close to correct, which is what I care
+        # about.
+        # If we ever decide to require cython:
+        # return (sizeof(GCCHKSHA1LeafNode)
+        #     + sizeof(gc_chk_sha1_record)*self.num_records)
+        return (sizeof(PyObject) + sizeof(void*) + sizeof(int)
+            + sizeof(gc_chk_sha1_record*) + sizeof(PyObject *)
+            + sizeof(gc_chk_sha1_record*) + sizeof(char)
+            + sizeof(unsigned char)*257
+            + sizeof(gc_chk_sha1_record)*self.num_records)
+
+    def __dealloc__(self):
+        if self.records != NULL:
+            PyMem_Free(self.records)
+            self.records = NULL
+
+    def __init__(self, bytes):
+        self._parse_bytes(bytes)
+        self.last_key = None
+        self.last_record = NULL
+
+    property min_key:
+        def __get__(self):
+            if self.num_records > 0:
+                return _sha1_to_key(self.records[0].sha1)
+            return None
+
+    property max_key:
+        def __get__(self):
+            if self.num_records > 0:
+                return _sha1_to_key(self.records[self.num_records-1].sha1)
+            return None
+
+    cdef StaticTuple _record_to_value_and_refs(self,
+                                               gc_chk_sha1_record *record):
+        """Extract the refs and value part of this record."""
+        cdef StaticTuple value_and_refs
+        cdef StaticTuple empty
+        value_and_refs = StaticTuple_New(2)
+        value = _record_formatter(record)
+        Py_INCREF(value)
+        StaticTuple_SET_ITEM(value_and_refs, 0, value)
+        # Always empty refs
+        empty = StaticTuple_New(0)
+        Py_INCREF(empty)
+        StaticTuple_SET_ITEM(value_and_refs, 1, empty)
+        return value_and_refs
+
+    cdef StaticTuple _record_to_item(self, gc_chk_sha1_record *record):
+        """Turn a given record back into a fully fledged item.
+        """
+        cdef StaticTuple item
+        cdef StaticTuple key
+        cdef StaticTuple value_and_refs
+        cdef object value
+        key = _sha1_to_key(record.sha1)
+        item = StaticTuple_New(2)
+        Py_INCREF(key)
+        StaticTuple_SET_ITEM(item, 0, key)
+        value_and_refs = self._record_to_value_and_refs(record)
+        Py_INCREF(value_and_refs)
+        StaticTuple_SET_ITEM(item, 1, value_and_refs)
+        return item
+
+    cdef gc_chk_sha1_record* _lookup_record(self, char *sha1) except? NULL:
+        """Find a gc_chk_sha1_record that matches the sha1 supplied."""
+        cdef int lo, hi, mid, the_cmp
+        cdef int offset
+
+        # TODO: We can speed up misses by comparing this sha1 to the common
+        #       bits, and seeing if the common prefix matches, if not, we don't
+        #       need to search for anything because it cannot match
+        # Use the offset array to find the closest fit for this entry
+        # follow that up with bisecting, since multiple keys can be in one
+        # spot
+        # Bisecting dropped us from 7000 comparisons to 582 (4.8/key), using
+        # the offset array dropped us from 23us to 20us and 156 comparisions
+        # (1.3/key)
+        offset = self._offset_for_sha1(sha1)
+        lo = self.offsets[offset]
+        hi = self.offsets[offset+1]
+        if hi == 255:
+            # if hi == 255 that means we potentially ran off the end of the
+            # list, so push it up to num_records
+            # note that if 'lo' == 255, that is ok, because we can start
+            # searching from that part of the list.
+            hi = self.num_records
+        local_n_cmp = 0
+        while lo < hi:
+            mid = (lo + hi) / 2
+            the_cmp = memcmp(self.records[mid].sha1, sha1, 20)
+            if the_cmp == 0:
+                return &self.records[mid]
+            elif the_cmp < 0:
+                lo = mid + 1
+            else:
+                hi = mid
+        return NULL
+
+    def __contains__(self, key):
+        cdef char sha1[20]
+        cdef gc_chk_sha1_record *record
+        if _key_to_sha1(key, sha1):
+            # If it isn't a sha1 key, then it won't be in this leaf node
+            record = self._lookup_record(sha1)
+            if record != NULL:
+                self.last_key = key
+                self.last_record = record
+                return True
+        return False
+
+    def __getitem__(self, key):
+        cdef char sha1[20]
+        cdef gc_chk_sha1_record *record
+        record = NULL
+        if self.last_record != NULL and key is self.last_key:
+            record = self.last_record
+        elif _key_to_sha1(key, sha1):
+            record = self._lookup_record(sha1)
+        if record == NULL:
+            raise KeyError('key %r is not present' % (key,))
+        return self._record_to_value_and_refs(record)
+
+    def __len__(self):
+        return self.num_records
+
+    def all_keys(self):
+        cdef int i
+        result = []
+        for i from 0 <= i < self.num_records:
+            PyList_Append(result, _sha1_to_key(self.records[i].sha1))
+        return result
+
+    def all_items(self):
+        cdef int i
+        result = []
+        for i from 0 <= i < self.num_records:
+            item = self._record_to_item(&self.records[i])
+            PyList_Append(result, item)
+        return result
+
+    cdef int _count_records(self, char *c_content, char *c_end): # cannot_raise
+        """Count how many records are in this section."""
+        cdef char *c_cur
+        cdef int num_records
+
+        c_cur = c_content
+        num_records = 0
+        while c_cur != NULL and c_cur < c_end:
+            c_cur = <char *>memchr(c_cur, c'\n', c_end - c_cur);
+            if c_cur == NULL:
+                break
+            c_cur = c_cur + 1
+            num_records = num_records + 1
+        return num_records
+
+    cdef _parse_bytes(self, bytes):
+        """Parse the string 'bytes' into content."""
+        cdef char *c_bytes
+        cdef char *c_cur
+        cdef char *c_end
+        cdef Py_ssize_t n_bytes
+        cdef int num_records
+        cdef int entry
+        cdef gc_chk_sha1_record *cur_record
+
+        if not PyString_CheckExact(bytes):
+            raise TypeError('We only support parsing plain 8-bit strings.')
+        # Pass 1, count how many records there will be
+        n_bytes = PyString_GET_SIZE(bytes)
+        c_bytes = PyString_AS_STRING(bytes)
+        c_end = c_bytes + n_bytes
+        if strncmp(c_bytes, 'type=leaf\n', 10):
+            raise ValueError("bytes did not start with 'type=leaf\\n': %r"
+                             % (bytes[:10],))
+        c_cur = c_bytes + 10
+        num_records = self._count_records(c_cur, c_end)
+        # Now allocate the memory for these items, and go to town
+        self.records = <gc_chk_sha1_record*>PyMem_Malloc(num_records *
+            (sizeof(unsigned short) + sizeof(gc_chk_sha1_record)))
+        self.num_records = num_records
+        cur_record = self.records
+        entry = 0
+        while c_cur != NULL and c_cur < c_end and entry < num_records:
+            c_cur = self._parse_one_entry(c_cur, c_end, cur_record)
+            cur_record = cur_record + 1
+            entry = entry + 1
+        if (entry != self.num_records
+            or c_cur != c_end
+            or cur_record != self.records + self.num_records):
+            raise ValueError('Something went wrong while parsing.')
+        # Pass 3: build the offset map
+        self._compute_common()
+
+    cdef char *_parse_one_entry(self, char *c_cur, char *c_end,
+                                gc_chk_sha1_record *cur_record) except NULL:
+        """Read a single sha record from the bytes.
+        :param c_cur: The pointer to the start of bytes
+        :param cur_record: 
+        """
+        cdef char *c_next
+        if strncmp(c_cur, 'sha1:', 5):
+            raise ValueError('line did not start with sha1: %r'
+                % (safe_string_from_size(c_cur, 10),))
+        c_cur = c_cur + 5
+        c_next = <char *>memchr(c_cur, c'\0', c_end - c_cur)
+        if c_next == NULL or (c_next - c_cur != 40):
+            raise ValueError('Line did not contain 40 hex bytes')
+        if not _unhexlify_sha1(c_cur, cur_record.sha1):
+            raise ValueError('We failed to unhexlify')
+        c_cur = c_next + 1
+        if c_cur[0] != c'\0':
+            raise ValueError('only 1 null, not 2 as expected')
+        c_cur = c_cur + 1
+        cur_record.block_offset = strtoll(c_cur, &c_next, 10)
+        if c_cur == c_next or c_next[0] != c' ':
+            raise ValueError('Failed to parse block offset')
+        c_cur = c_next + 1
+        cur_record.block_length = strtoul(c_cur, &c_next, 10)
+        if c_cur == c_next or c_next[0] != c' ':
+            raise ValueError('Failed to parse block length')
+        c_cur = c_next + 1
+        cur_record.record_start = strtoul(c_cur, &c_next, 10)
+        if c_cur == c_next or c_next[0] != c' ':
+            raise ValueError('Failed to parse block length')
+        c_cur = c_next + 1
+        cur_record.record_end = strtoul(c_cur, &c_next, 10)
+        if c_cur == c_next or c_next[0] != c'\n':
+            raise ValueError('Failed to parse record end')
+        c_cur = c_next + 1
+        return c_cur
+
+    cdef int _offset_for_sha1(self, char *sha1) except -1:
+        """Find the first interesting 8-bits of this sha1."""
+        cdef int this_offset
+        cdef unsigned int as_uint
+        as_uint = _sha1_to_uint(sha1)
+        this_offset = (as_uint >> self.common_shift) & 0xFF
+        return this_offset
+
+    def _get_offset_for_sha1(self, sha1):
+        return self._offset_for_sha1(PyString_AS_STRING(sha1))
+
+    cdef _compute_common(self):
+        cdef unsigned int first
+        cdef unsigned int this
+        cdef unsigned int common_mask
+        cdef unsigned char common_shift
+        cdef int i
+        cdef int offset, this_offset
+        cdef int max_offset
+        # The idea with the offset map is that we should be able to quickly
+        # jump to the key that matches a gives sha1. We know that the keys are
+        # in sorted order, and we know that a lot of the prefix is going to be
+        # the same across them.
+        # By XORing the records together, we can determine what bits are set in
+        # all of them
+        if self.num_records < 2:
+            # Everything is in common if you have 0 or 1 leaves
+            # So we'll always just shift to the first byte
+            self.common_shift = 24
+        else:
+            common_mask = 0xFFFFFFFF
+            first = _sha1_to_uint(self.records[0].sha1)
+            for i from 0 < i < self.num_records:
+                this = _sha1_to_uint(self.records[i].sha1)
+                common_mask = (~(first ^ this)) & common_mask
+            common_shift = 24
+            while common_mask & 0x80000000 and common_shift > 0:
+                common_mask = common_mask << 1
+                common_shift = common_shift - 1
+            self.common_shift = common_shift
+        offset = 0
+        max_offset = self.num_records
+        # We cap this loop at 254 records. All the other offsets just get
+        # filled with 0xff as the singleton saying 'too many'.
+        # It means that if we have >255 records we have to bisect the second
+        # half of the list, but this is going to be very rare in practice.
+        if max_offset > 255:
+            max_offset = 255
+        for i from 0 <= i < max_offset:
+            this_offset = self._offset_for_sha1(self.records[i].sha1)
+            while offset <= this_offset:
+                self.offsets[offset] = i
+                offset = offset + 1
+        while offset < 257:
+            self.offsets[offset] = max_offset
+            offset = offset + 1
+
+    def _get_offsets(self):
+        cdef int i
+        result = []
+        for i from 0 <= i < 257:
+            PyList_Append(result, self.offsets[i])
+        return result
+
+
+def _parse_into_chk(bytes, key_length, ref_list_length):
+    """Parse into a format optimized for chk records."""
+    assert key_length == 1
+    assert ref_list_length == 0
+    return GCCHKSHA1LeafNode(bytes)
+
+
 def _flatten_node(node, reference_lists):
     """Convert a node into the serialized form.
 

=== modified file 'bzrlib/_static_tuple_c.pxd'
--- bzrlib/_static_tuple_c.pxd	2010-05-11 14:13:31 +0000
+++ bzrlib/_static_tuple_c.pxd	2010-08-24 19:24:49 +0000
@@ -33,6 +33,7 @@
     int import_static_tuple_c() except -1
     StaticTuple StaticTuple_New(Py_ssize_t)
     StaticTuple StaticTuple_Intern(StaticTuple)
+    StaticTuple StaticTuple_FromSequence(object)
 
     # Steals a reference and val must be a valid type, no checking is done
     void StaticTuple_SET_ITEM(StaticTuple key, Py_ssize_t offset, object val)

=== modified file 'bzrlib/btree_index.py'
--- bzrlib/btree_index.py	2010-06-20 11:18:38 +0000
+++ bzrlib/btree_index.py	2010-08-24 19:24:49 +0000
@@ -602,10 +602,10 @@
         """In memory index's have no known corruption at the moment."""
 
 
-class _LeafNode(object):
+class _LeafNode(dict):
     """A leaf node for a serialised B+Tree index."""
 
-    __slots__ = ('keys', 'min_key', 'max_key')
+    __slots__ = ('min_key', 'max_key', '_keys')
 
     def __init__(self, bytes, key_length, ref_list_length):
         """Parse bytes to create a leaf node object."""
@@ -617,7 +617,20 @@
             self.max_key = key_list[-1][0]
         else:
             self.min_key = self.max_key = None
-        self.keys = dict(key_list)
+        super(_LeafNode, self).__init__(key_list)
+        self._keys = dict(self)
+
+    def all_items(self):
+        """Return a sorted list of (key, (value, refs)) items"""
+        items = self.items()
+        items.sort()
+        return items
+
+    def all_keys(self):
+        """Return a sorted list of all keys."""
+        keys = self.keys()
+        keys.sort()
+        return keys
 
 
 class _InternalNode(object):
@@ -672,6 +685,7 @@
         self._recommended_pages = self._compute_recommended_pages()
         self._root_node = None
         self._base_offset = offset
+        self._leaf_factory = _LeafNode
         # Default max size is 100,000 leave values
         self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
         if unlimited_cache:
@@ -950,7 +964,7 @@
         """Cache directly from key => value, skipping the btree."""
         if self._leaf_value_cache is not None:
             for node in nodes.itervalues():
-                for key, value in node.keys.iteritems():
+                for key, value in node.all_items():
                     if key in self._leaf_value_cache:
                         # Don't add the rest of the keys, we've seen this node
                         # before.
@@ -980,10 +994,10 @@
         if self._row_offsets[-1] == 1:
             # There is only the root node, and we read that via key_count()
             if self.node_ref_lists:
-                for key, (value, refs) in sorted(self._root_node.keys.items()):
+                for key, (value, refs) in self._root_node.all_items():
                     yield (self, key, value, refs)
             else:
-                for key, (value, refs) in sorted(self._root_node.keys.items()):
+                for key, (value, refs) in self._root_node.all_items():
                     yield (self, key, value)
             return
         start_of_leaves = self._row_offsets[-2]
@@ -999,11 +1013,11 @@
         # for spilling index builds to disk.
         if self.node_ref_lists:
             for _, node in nodes:
-                for key, (value, refs) in sorted(node.keys.items()):
+                for key, (value, refs) in node.all_items():
                     yield (self, key, value, refs)
         else:
             for _, node in nodes:
-                for key, (value, refs) in sorted(node.keys.items()):
+                for key, (value, refs) in node.all_items():
                     yield (self, key, value)
 
     @staticmethod
@@ -1170,8 +1184,8 @@
                 continue
             node = nodes[node_index]
             for next_sub_key in sub_keys:
-                if next_sub_key in node.keys:
-                    value, refs = node.keys[next_sub_key]
+                if next_sub_key in node:
+                    value, refs = node[next_sub_key]
                     if self.node_ref_lists:
                         yield (self, next_sub_key, value, refs)
                     else:
@@ -1245,14 +1259,13 @@
             # sub_keys is all of the keys we are looking for that should exist
             # on this page, if they aren't here, then they won't be found
             node = nodes[node_index]
-            node_keys = node.keys
             parents_to_check = set()
             for next_sub_key in sub_keys:
-                if next_sub_key not in node_keys:
+                if next_sub_key not in node:
                     # This one is just not present in the index at all
                     missing_keys.add(next_sub_key)
                 else:
-                    value, refs = node_keys[next_sub_key]
+                    value, refs = node[next_sub_key]
                     parent_keys = refs[ref_list_num]
                     parent_map[next_sub_key] = parent_keys
                     parents_to_check.update(parent_keys)
@@ -1265,8 +1278,8 @@
             while parents_to_check:
                 next_parents_to_check = set()
                 for key in parents_to_check:
-                    if key in node_keys:
-                        value, refs = node_keys[key]
+                    if key in node:
+                        value, refs = node[key]
                         parent_keys = refs[ref_list_num]
                         parent_map[key] = parent_keys
                         next_parents_to_check.update(parent_keys)
@@ -1546,7 +1559,8 @@
                     continue
             bytes = zlib.decompress(data)
             if bytes.startswith(_LEAF_FLAG):
-                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
+                node = self._leaf_factory(bytes, self._key_length,
+                                          self.node_ref_lists)
             elif bytes.startswith(_INTERNAL_FLAG):
                 node = _InternalNode(bytes)
             else:
@@ -1571,8 +1585,11 @@
             pass
 
 
+_gcchk_factory = _LeafNode
+
 try:
     from bzrlib import _btree_serializer_pyx as _btree_serializer
+    _gcchk_factory = _btree_serializer._parse_into_chk
 except ImportError, e:
     osutils.failed_to_load_extension(e)
     from bzrlib import _btree_serializer_py as _btree_serializer

=== modified file 'bzrlib/clean_tree.py'
--- bzrlib/clean_tree.py	2010-08-21 03:42:26 +0000
+++ bzrlib/clean_tree.py	2010-08-24 19:24:49 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2005 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/generate_ids.py'
--- bzrlib/generate_ids.py	2010-08-10 19:17:49 +0000
+++ bzrlib/generate_ids.py	2010-08-24 19:24:49 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2006 Canonical Ltd
+# Copyright (C) 2006, 2007, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/python-compat.h'
--- bzrlib/python-compat.h	2009-10-21 20:53:21 +0000
+++ bzrlib/python-compat.h	2010-08-24 19:24:49 +0000
@@ -74,6 +74,9 @@
 
 #ifdef _MSC_VER
 #define  snprintf  _snprintf
+/* gcc (mingw32) has strtoll, while the MSVC compiler uses _strtoi64 */
+#define strtoll _strtoi64
+#define strtoull _strtoui64
 #endif
 
 /* Introduced in Python 2.6 */

=== modified file 'bzrlib/repofmt/pack_repo.py'
--- bzrlib/repofmt/pack_repo.py	2010-05-11 08:36:16 +0000
+++ bzrlib/repofmt/pack_repo.py	2010-08-24 19:24:49 +0000
@@ -49,6 +49,7 @@
 """)
 from bzrlib import (
     bzrdir,
+    btree_index,
     errors,
     lockable_files,
     lockdir,
@@ -56,10 +57,6 @@
     )
 
 from bzrlib.decorators import needs_write_lock, only_raises
-from bzrlib.btree_index import (
-    BTreeGraphIndex,
-    BTreeBuilder,
-    )
 from bzrlib.index import (
     GraphIndex,
     InMemoryGraphIndex,
@@ -231,11 +228,13 @@
         unlimited_cache = False
         if index_type == 'chk':
             unlimited_cache = True
-        setattr(self, index_type + '_index',
-            self.index_class(self.index_transport,
-                self.index_name(index_type, self.name),
-                self.index_sizes[self.index_offset(index_type)],
-                unlimited_cache=unlimited_cache))
+        index = self.index_class(self.index_transport,
+                    self.index_name(index_type, self.name),
+                    self.index_sizes[self.index_offset(index_type)],
+                    unlimited_cache=unlimited_cache)
+        if index_type == 'chk':
+            index._leaf_factory = btree_index._gcchk_factory
+        setattr(self, index_type + '_index', index)
 
 
 class ExistingPack(Pack):
@@ -1680,7 +1679,7 @@
             txt_index = self._make_index(name, '.tix')
             sig_index = self._make_index(name, '.six')
             if self.chk_index is not None:
-                chk_index = self._make_index(name, '.cix', unlimited_cache=True)
+                chk_index = self._make_index(name, '.cix', is_chk=True)
             else:
                 chk_index = None
             result = ExistingPack(self._pack_transport, name, rev_index,
@@ -1706,7 +1705,7 @@
             sig_index = self._make_index(name, '.six', resume=True)
             if self.chk_index is not None:
                 chk_index = self._make_index(name, '.cix', resume=True,
-                                             unlimited_cache=True)
+                                             is_chk=True)
             else:
                 chk_index = None
             result = self.resumed_pack_factory(name, rev_index, inv_index,
@@ -1742,7 +1741,7 @@
         return self._index_class(self.transport, 'pack-names', None
                 ).iter_all_entries()
 
-    def _make_index(self, name, suffix, resume=False, unlimited_cache=False):
+    def _make_index(self, name, suffix, resume=False, is_chk=False):
         size_offset = self._suffix_offsets[suffix]
         index_name = name + suffix
         if resume:
@@ -1751,8 +1750,11 @@
         else:
             transport = self._index_transport
             index_size = self._names[name][size_offset]
-        return self._index_class(transport, index_name, index_size,
-                                 unlimited_cache=unlimited_cache)
+        index = self._index_class(transport, index_name, index_size,
+                                  unlimited_cache=is_chk)
+        if is_chk and self._index_class is btree_index.BTreeGraphIndex: 
+            index._leaf_factory = btree_index._gcchk_factory
+        return index
 
     def _max_pack_count(self, total_revisions):
         """Return the maximum number of packs to use for total revisions.
@@ -2829,8 +2831,8 @@
     _commit_builder_class = PackCommitBuilder
     supports_external_lookups = True
     # What index classes to use
-    index_builder_class = BTreeBuilder
-    index_class = BTreeGraphIndex
+    index_builder_class = btree_index.BTreeBuilder
+    index_class = btree_index.BTreeGraphIndex
 
     @property
     def _serializer(self):
@@ -2865,8 +2867,8 @@
     supports_tree_reference = False # no subtrees
     supports_external_lookups = True
     # What index classes to use
-    index_builder_class = BTreeBuilder
-    index_class = BTreeGraphIndex
+    index_builder_class = btree_index.BTreeBuilder
+    index_class = btree_index.BTreeGraphIndex
 
     @property
     def _serializer(self):
@@ -2907,8 +2909,8 @@
     supports_tree_reference = True
     supports_external_lookups = True
     # What index classes to use
-    index_builder_class = BTreeBuilder
-    index_class = BTreeGraphIndex
+    index_builder_class = btree_index.BTreeBuilder
+    index_class = btree_index.BTreeGraphIndex
 
     @property
     def _serializer(self):

=== modified file 'bzrlib/tests/__init__.py'
--- bzrlib/tests/__init__.py	2010-08-10 18:07:54 +0000
+++ bzrlib/tests/__init__.py	2010-08-24 19:24:49 +0000
@@ -3669,6 +3669,7 @@
         'bzrlib.tests.per_workingtree',
         'bzrlib.tests.test__annotator',
         'bzrlib.tests.test__bencode',
+        'bzrlib.tests.test__btree_serializer',
         'bzrlib.tests.test__chk_map',
         'bzrlib.tests.test__dirstate_helpers',
         'bzrlib.tests.test__groupcompress',

=== added file 'bzrlib/tests/test__btree_serializer.py'
--- bzrlib/tests/test__btree_serializer.py	1970-01-01 00:00:00 +0000
+++ bzrlib/tests/test__btree_serializer.py	2010-08-24 19:24:49 +0000
@@ -0,0 +1,305 @@
+# Copyright (C) 2010 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+#
+
+"""Direct tests of the btree serializer extension"""
+
+import binascii
+import bisect
+
+from bzrlib import tests
+
+from bzrlib.tests.test_btree_index import compiled_btreeparser_feature
+
+
+class TestBtreeSerializer(tests.TestCase):
+
+    _test_needs_features = [compiled_btreeparser_feature]
+
+    def setUp(self):
+        super(TestBtreeSerializer, self).setUp()
+        self.module = compiled_btreeparser_feature.module
+
+
+class TestHexAndUnhex(TestBtreeSerializer):
+
+    def assertHexlify(self, as_binary):
+        self.assertEqual(binascii.hexlify(as_binary),
+                         self.module._py_hexlify(as_binary))
+
+    def assertUnhexlify(self, as_hex):
+        ba_unhex = binascii.unhexlify(as_hex)
+        mod_unhex = self.module._py_unhexlify(as_hex)
+        if ba_unhex != mod_unhex:
+            if mod_unhex is None:
+                mod_hex = '<None>'
+            else:
+                mod_hex = binascii.hexlify(mod_unhex)
+            self.fail('_py_unhexlify returned a different answer'
+                      ' from binascii:\n    %s\n != %s'
+                      % (binascii.hexlify(ba_unhex), mod_hex))
+
+    def assertFailUnhexlify(self, as_hex):
+        # Invalid hex content
+        self.assertIs(None, self.module._py_unhexlify(as_hex))
+
+    def test_to_hex(self):
+        raw_bytes = ''.join(map(chr, range(256)))
+        for i in range(0, 240, 20):
+            self.assertHexlify(raw_bytes[i:i+20])
+        self.assertHexlify(raw_bytes[240:]+raw_bytes[0:4])
+
+    def test_from_hex(self):
+        self.assertUnhexlify('0123456789abcdef0123456789abcdef01234567')
+        self.assertUnhexlify('123456789abcdef0123456789abcdef012345678')
+        self.assertUnhexlify('0123456789ABCDEF0123456789ABCDEF01234567')
+        self.assertUnhexlify('123456789ABCDEF0123456789ABCDEF012345678')
+        hex_chars = binascii.hexlify(''.join(map(chr, range(256))))
+        for i in range(0, 480, 40):
+            self.assertUnhexlify(hex_chars[i:i+40])
+        self.assertUnhexlify(hex_chars[480:]+hex_chars[0:8])
+
+    def test_from_invalid_hex(self):
+        self.assertFailUnhexlify('123456789012345678901234567890123456789X')
+        self.assertFailUnhexlify('12345678901234567890123456789012345678X9')
+
+
+_hex_form = '123456789012345678901234567890abcdefabcd'
+
+class Test_KeyToSha1(TestBtreeSerializer):
+
+    def assertKeyToSha1(self, expected, key):
+        if expected is None:
+            expected_bin = None
+        else:
+            expected_bin = binascii.unhexlify(expected)
+        actual_sha1 = self.module._py_key_to_sha1(key)
+        if expected_bin != actual_sha1:
+            actual_hex_sha1 = None
+            if actual_sha1 is not None:
+                actual_hex_sha1 = binascii.hexlify(actual_sha1)
+            self.fail('_key_to_sha1 returned:\n    %s\n != %s'
+                      % (actual_sha1, expected))
+
+    def test_simple(self):
+        self.assertKeyToSha1(_hex_form, ('sha1:' + _hex_form,))
+
+    def test_invalid_not_tuple(self):
+        self.assertKeyToSha1(None, _hex_form)
+        self.assertKeyToSha1(None, 'sha1:' + _hex_form)
+
+    def test_invalid_empty(self):
+        self.assertKeyToSha1(None, ())
+
+    def test_invalid_not_string(self):
+        self.assertKeyToSha1(None, (None,))
+        self.assertKeyToSha1(None, (list(_hex_form),))
+
+    def test_invalid_not_sha1(self):
+        self.assertKeyToSha1(None, (_hex_form,))
+        self.assertKeyToSha1(None, ('sha2:' + _hex_form,))
+
+    def test_invalid_not_hex(self):
+        self.assertKeyToSha1(None,
+            ('sha1:abcdefghijklmnopqrstuvwxyz12345678901234',))
+
+
+class Test_Sha1ToKey(TestBtreeSerializer):
+
+    def assertSha1ToKey(self, hex_sha1):
+        bin_sha1 = binascii.unhexlify(hex_sha1)
+        key = self.module._py_sha1_to_key(bin_sha1)
+        self.assertEqual(('sha1:' + hex_sha1,), key)
+
+    def test_simple(self):
+        self.assertSha1ToKey(_hex_form)
+
+
+_one_key_content = """type=leaf
+sha1:123456789012345678901234567890abcdefabcd\x00\x001 2 3 4
+"""
+
+_large_offsets = """type=leaf
+sha1:123456789012345678901234567890abcdefabcd\x00\x0012345678901 1234567890 0 1
+sha1:abcd123456789012345678901234567890abcdef\x00\x002147483648 2147483647 0 1
+sha1:abcdefabcd123456789012345678901234567890\x00\x004294967296 4294967295 4294967294 1
+"""
+
+_multi_key_content = """type=leaf
+sha1:c80c881d4a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
+sha1:c86f7e437faa5a7fce15d1ddcb9eaeaea377667b\x00\x001 1 1 1
+sha1:c8e240de74fb1ed08fa08d38063f6a6a91462a81\x00\x002 2 2 2
+sha1:cda39a3ee5e6b4b0d3255bfef95601890afd8070\x00\x003 3 3 3
+sha1:cdf51e37c269aa94d38f93e537bf6e2020b21406\x00\x004 4 4 4
+sha1:ce0c9035898dd52fc65c41454cec9c4d2611bfb3\x00\x005 5 5 5
+sha1:ce93b4e3c464ffd51732fbd6ded717e9efda28aa\x00\x006 6 6 6
+sha1:cf7a9e24777ec23212c54d7a350bc5bea5477fdb\x00\x007 7 7 7
+"""
+
+_multi_key_same_offset = """type=leaf
+sha1:080c881d4a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
+sha1:c86f7e437faa5a7fce15d1ddcb9eaeaea377667b\x00\x001 1 1 1
+sha1:cd0c9035898dd52fc65c41454cec9c4d2611bfb3\x00\x002 2 2 2
+sha1:cda39a3ee5e6b4b0d3255bfef95601890afd8070\x00\x003 3 3 3
+sha1:cde240de74fb1ed08fa08d38063f6a6a91462a81\x00\x004 4 4 4
+sha1:cdf51e37c269aa94d38f93e537bf6e2020b21406\x00\x005 5 5 5
+sha1:ce7a9e24777ec23212c54d7a350bc5bea5477fdb\x00\x006 6 6 6
+sha1:ce93b4e3c464ffd51732fbd6ded717e9efda28aa\x00\x007 7 7 7
+"""
+
+_common_32_bits = """type=leaf
+sha1:123456784a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
+sha1:1234567874fb1ed08fa08d38063f6a6a91462a81\x00\x001 1 1 1
+sha1:12345678777ec23212c54d7a350bc5bea5477fdb\x00\x002 2 2 2
+sha1:123456787faa5a7fce15d1ddcb9eaeaea377667b\x00\x003 3 3 3
+sha1:12345678898dd52fc65c41454cec9c4d2611bfb3\x00\x004 4 4 4
+sha1:12345678c269aa94d38f93e537bf6e2020b21406\x00\x005 5 5 5
+sha1:12345678c464ffd51732fbd6ded717e9efda28aa\x00\x006 6 6 6
+sha1:12345678e5e6b4b0d3255bfef95601890afd8070\x00\x007 7 7 7
+"""
+
+
+class TestGCCKHSHA1LeafNode(TestBtreeSerializer):
+
+    def assertInvalid(self, bytes):
+        """Ensure that we get a proper error when trying to parse invalid bytes.
+
+        (mostly this is testing that bad input doesn't cause us to segfault)
+        """
+        self.assertRaises((ValueError, TypeError), 
+                          self.module._parse_into_chk, bytes, 1, 0)
+
+    def test_non_str(self):
+        self.assertInvalid(u'type=leaf\n')
+
+    def test_not_leaf(self):
+        self.assertInvalid('type=internal\n')
+
+    def test_empty_leaf(self):
+        leaf = self.module._parse_into_chk('type=leaf\n', 1, 0)
+        self.assertEqual(0, len(leaf))
+        self.assertEqual([], leaf.all_items())
+        self.assertEqual([], leaf.all_keys())
+        # It should allow any key to be queried
+        self.assertFalse(('key',) in leaf)
+
+    def test_one_key_leaf(self):
+        leaf = self.module._parse_into_chk(_one_key_content, 1, 0)
+        self.assertEqual(1, len(leaf))
+        sha_key = ('sha1:' + _hex_form,)
+        self.assertEqual([sha_key], leaf.all_keys())
+        self.assertEqual([(sha_key, ('1 2 3 4', ()))], leaf.all_items())
+        self.assertTrue(sha_key in leaf)
+
+    def test_large_offsets(self):
+        leaf = self.module._parse_into_chk(_large_offsets, 1, 0)
+        self.assertEqual(['12345678901 1234567890 0 1',
+                          '2147483648 2147483647 0 1',
+                          '4294967296 4294967295 4294967294 1',
+                         ], [x[1][0] for x in leaf.all_items()])
+
+    def test_many_key_leaf(self):
+        leaf = self.module._parse_into_chk(_multi_key_content, 1, 0)
+        self.assertEqual(8, len(leaf))
+        all_keys = leaf.all_keys()
+        self.assertEqual(8, len(leaf.all_keys()))
+        for idx, key in enumerate(all_keys):
+            self.assertEqual(str(idx), leaf[key][0].split()[0])
+
+    def test_common_shift(self):
+        # The keys were deliberately chosen so that the first 5 bits all
+        # overlapped, it also happens that a later bit overlaps
+        # Note that by 'overlap' we mean that given bit is either on in all
+        # keys, or off in all keys
+        leaf = self.module._parse_into_chk(_multi_key_content, 1, 0)
+        self.assertEqual(19, leaf.common_shift)
+        # The interesting byte for each key is
+        # (defined as the 8-bits that come after the common prefix)
+        lst = [1, 13, 28, 180, 190, 193, 210, 239]
+        offsets = leaf._get_offsets()
+        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
+                         offsets)
+        for idx, val in enumerate(lst):
+            self.assertEqual(idx, offsets[val])
+        for idx, key in enumerate(leaf.all_keys()):
+            self.assertEqual(str(idx), leaf[key][0].split()[0])
+
+    def test_multi_key_same_offset(self):
+        # there is no common prefix, though there are some common bits
+        leaf = self.module._parse_into_chk(_multi_key_same_offset, 1, 0)
+        self.assertEqual(24, leaf.common_shift)
+        offsets = leaf._get_offsets()
+        # The interesting byte is just the first 8-bits of the key
+        lst = [8, 200, 205, 205, 205, 205, 206, 206]
+        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
+                         offsets)
+        for val in lst:
+            self.assertEqual(lst.index(val), offsets[val])
+        for idx, key in enumerate(leaf.all_keys()):
+            self.assertEqual(str(idx), leaf[key][0].split()[0])
+
+    def test_all_common_prefix(self):
+        # The first 32 bits of all hashes are the same. This is going to be
+        # pretty much impossible, but I don't want to fail because of this
+        leaf = self.module._parse_into_chk(_common_32_bits, 1, 0)
+        self.assertEqual(0, leaf.common_shift)
+        lst = [0x78] * 8
+        offsets = leaf._get_offsets()
+        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
+                         offsets)
+        for val in lst:
+            self.assertEqual(lst.index(val), offsets[val])
+        for idx, key in enumerate(leaf.all_keys()):
+            self.assertEqual(str(idx), leaf[key][0].split()[0])
+
+    def test_many_entries(self):
+        # Again, this is almost impossible, but we should still work
+        # It would be hard to fit more that 120 entries in a 4k page, much less
+        # more than 256 of them. but hey, weird stuff happens sometimes
+        lines = ['type=leaf\n']
+        for i in range(500):
+            key_str = 'sha1:%04x%s' % (i, _hex_form[:36])
+            key = (key_str,)
+            lines.append('%s\0\0%d %d %d %d\n' % (key_str, i, i, i, i))
+        bytes = ''.join(lines)
+        leaf = self.module._parse_into_chk(bytes, 1, 0)
+        self.assertEqual(24-7, leaf.common_shift)
+        offsets = leaf._get_offsets()
+        # This is the interesting bits for each entry
+        lst = [x // 2 for x in range(500)]
+        expected_offsets = [x * 2 for x in range(128)] + [255]*129
+        self.assertEqual(expected_offsets, offsets)
+        # We truncate because offsets is an unsigned char. So the bisection
+        # will just say 'greater than the last one' for all the rest
+        lst = lst[:255]
+        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
+                         offsets)
+        for val in lst:
+            self.assertEqual(lst.index(val), offsets[val])
+        for idx, key in enumerate(leaf.all_keys()):
+            self.assertEqual(str(idx), leaf[key][0].split()[0])
+
+    def test__sizeof__(self):
+        # We can't use the exact numbers because of platform variations, etc.
+        # But what we really care about is that it does get bigger with more
+        # content.
+        leaf0 = self.module._parse_into_chk('type=leaf\n', 1, 0)
+        leaf1 = self.module._parse_into_chk(_one_key_content, 1, 0)
+        leafN = self.module._parse_into_chk(_multi_key_content, 1, 0)
+        sizeof_1 = leaf1.__sizeof__() - leaf0.__sizeof__()
+        self.assertTrue(sizeof_1 > 0)
+        sizeof_N = leafN.__sizeof__() - leaf0.__sizeof__()
+        self.assertEqual(sizeof_1 * len(leafN), sizeof_N)

=== modified file 'bzrlib/tests/test_btree_index.py'
--- bzrlib/tests/test_btree_index.py	2010-06-20 11:18:38 +0000
+++ bzrlib/tests/test_btree_index.py	2010-08-24 19:24:49 +0000
@@ -216,12 +216,12 @@
         leaf1_bytes = zlib.decompress(leaf1)
         sorted_node_keys = sorted(node[0] for node in nodes)
         node = btree_index._LeafNode(leaf1_bytes, 1, 0)
-        self.assertEqual(231, len(node.keys))
-        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
+        self.assertEqual(231, len(node))
+        self.assertEqual(sorted_node_keys[:231], node.all_keys())
         leaf2_bytes = zlib.decompress(leaf2)
         node = btree_index._LeafNode(leaf2_bytes, 1, 0)
-        self.assertEqual(400 - 231, len(node.keys))
-        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
+        self.assertEqual(400 - 231, len(node))
+        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
     def test_last_page_rounded_1_layer(self):
         builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
@@ -241,9 +241,9 @@
         leaf2 = content[74:]
         leaf2_bytes = zlib.decompress(leaf2)
         node = btree_index._LeafNode(leaf2_bytes, 1, 0)
-        self.assertEqual(10, len(node.keys))
+        self.assertEqual(10, len(node))
         sorted_node_keys = sorted(node[0] for node in nodes)
-        self.assertEqual(sorted_node_keys, sorted(node.keys))
+        self.assertEqual(sorted_node_keys, node.all_keys())
 
     def test_last_page_not_rounded_2_layer(self):
         builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
@@ -263,9 +263,9 @@
         leaf2 = content[8192:]
         leaf2_bytes = zlib.decompress(leaf2)
         node = btree_index._LeafNode(leaf2_bytes, 1, 0)
-        self.assertEqual(400 - 231, len(node.keys))
+        self.assertEqual(400 - 231, len(node))
         sorted_node_keys = sorted(node[0] for node in nodes)
-        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
+        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
     def test_three_level_tree_details(self):
         # The left most pointer in the second internal node in a row should
@@ -302,7 +302,7 @@
         # in the second node it points at
         pos = index._row_offsets[2] + internal_node2.offset + 1
         leaf = index._get_leaf_nodes([pos])[pos]
-        self.assertTrue(internal_node2.keys[0] in leaf.keys)
+        self.assertTrue(internal_node2.keys[0] in leaf)
 
     def test_2_leaves_2_2(self):
         builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
@@ -728,7 +728,7 @@
         nodes = dict(index._read_nodes([0]))
         self.assertEqual([0], nodes.keys())
         node = nodes[0]
-        self.assertEqual([('key',)], node.keys.keys())
+        self.assertEqual([('key',)], node.all_keys())
         self.assertEqual([('get', 'index')], trans._activity)
 
     def test__read_nodes_no_size_multiple_pages(self):
@@ -1112,7 +1112,7 @@
         min_l2_key = l2.min_key
         max_l1_key = l1.max_key
         self.assertTrue(max_l1_key < min_l2_key)
-        parents_min_l2_key = l2.keys[min_l2_key][1][0]
+        parents_min_l2_key = l2[min_l2_key][1][0]
         self.assertEqual((l1.max_key,), parents_min_l2_key)
         # Now, whatever key we select that would fall on the second page,
         # should give us all the parents until the page break
@@ -1131,7 +1131,7 @@
         parent_map = {}
         search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
                                             missing_keys)
-        self.assertEqual(sorted(l1.keys), sorted(parent_map))
+        self.assertEqual(l1.all_keys(), sorted(parent_map))
         self.assertEqual(set(), missing_keys)
         self.assertEqual(set(), search_keys)
 
@@ -1205,7 +1205,7 @@
             ("2222222222222222222222222222222222222222",): ("value:2", ()),
             ("3333333333333333333333333333333333333333",): ("value:3", ()),
             ("4444444444444444444444444444444444444444",): ("value:4", ()),
-            }, node.keys)
+            }, dict(node.all_items()))
 
     def test_LeafNode_2_2(self):
         node_bytes = ("type=leaf\n"
@@ -1225,7 +1225,7 @@
             ('11', '33'): ('value:3',
                 ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
             ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
-            }, node.keys)
+            }, dict(node.all_items()))
 
     def test_InternalNode_1(self):
         node_bytes = ("type=internal\n"
@@ -1266,7 +1266,7 @@
             ('11', '33'): ('value:3',
                 ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
             ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
-            }, node.keys)
+            }, dict(node.all_items()))
 
     def assertFlattened(self, expected, key, value, refs):
         flat_key, flat_line = self.parse_btree._flatten_node(

=== modified file 'bzrlib/tests/test_clean_tree.py'
--- bzrlib/tests/test_clean_tree.py	2010-08-21 03:42:26 +0000
+++ bzrlib/tests/test_clean_tree.py	2010-08-24 19:24:49 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2005, 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/tests/test_inv.py'
--- bzrlib/tests/test_inv.py	2010-08-03 13:31:06 +0000
+++ bzrlib/tests/test_inv.py	2010-08-24 19:24:49 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2005, 2006, 2007, 2008, 2009 Canonical Ltd
+# Copyright (C) 2005-2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/tests/test_inventory_delta.py'
--- bzrlib/tests/test_inventory_delta.py	2010-08-03 13:31:06 +0000
+++ bzrlib/tests/test_inventory_delta.py	2010-08-24 19:24:49 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2008, 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/tests/test_repository.py'
--- bzrlib/tests/test_repository.py	2010-03-31 16:29:25 +0000
+++ bzrlib/tests/test_repository.py	2010-08-24 19:24:49 +0000
@@ -31,6 +31,7 @@
                            UnsupportedFormatError,
                            )
 from bzrlib import (
+    btree_index,
     graph,
     tests,
     )
@@ -681,6 +682,21 @@
 
 class Test2a(tests.TestCaseWithMemoryTransport):
 
+    def test_chk_bytes_uses_custom_btree_parser(self):
+        mt = self.make_branch_and_memory_tree('test', format='2a')
+        mt.lock_write()
+        self.addCleanup(mt.unlock)
+        mt.add([''], ['root-id'])
+        mt.commit('first')
+        index = mt.branch.repository.chk_bytes._index._graph_index._indices[0]
+        self.assertEqual(btree_index._gcchk_factory, index._leaf_factory)
+        # It should also work if we re-open the repo
+        repo = mt.branch.repository.bzrdir.open_repository()
+        repo.lock_read()
+        self.addCleanup(repo.unlock)
+        index = repo.chk_bytes._index._graph_index._indices[0]
+        self.assertEqual(btree_index._gcchk_factory, index._leaf_factory)
+
     def test_fetch_combines_groups(self):
         builder = self.make_branch_builder('source', format='2a')
         builder.start_series()

=== modified file 'bzrlib/tests/test_source.py'
--- bzrlib/tests/test_source.py	2010-07-05 16:01:33 +0000
+++ bzrlib/tests/test_source.py	2010-08-24 19:24:49 +0000
@@ -388,8 +388,10 @@
         """
         both_exc_and_no_exc = []
         missing_except = []
-        class_re = re.compile(r'^(cdef\s+)?(public\s+)?(api\s+)?class (\w+).*:',
-                              re.MULTILINE)
+        class_re = re.compile(r'^(cdef\s+)?(public\s+)?'
+                              r'(api\s+)?class (\w+).*:', re.MULTILINE)
+        extern_class_re = re.compile(r'## extern cdef class (\w+)',
+                                     re.MULTILINE)
         except_re = re.compile(r'cdef\s+' # start with cdef
                                r'([\w *]*?)\s*' # this is the return signature
                                r'(\w+)\s*\(' # the function name
@@ -400,6 +402,7 @@
         for fname, text in self.get_source_file_contents(
                 extensions=('.pyx',)):
             known_classes = set([m[-1] for m in class_re.findall(text)])
+            known_classes.update(extern_class_re.findall(text))
             cdefs = except_re.findall(text)
             for sig, func, exc_clause, no_exc_comment in cdefs:
                 if sig.startswith('api '):

=== modified file 'doc/en/whats-new/whats-new-in-2.3.txt'
--- doc/en/whats-new/whats-new-in-2.3.txt	2010-08-18 07:25:22 +0000
+++ doc/en/whats-new/whats-new-in-2.3.txt	2010-08-24 19:24:49 +0000
@@ -37,6 +37,10 @@
   tree may substantially improve the speed of operations like ``bzr
   commit``.  (Andrew Bennetts)
 
+* Lower memory consumption when reading many chk index pages. Helpful for
+  things like ``bzr co`` or ``bzr ls -R`` on large trees.
+  (John Arbash Meinel)
+
 * When building new working trees, default to reading from the repository
   rather than the source tree unless explicitly requested. (via
   ``--files-from`` and ``--hardlink`` for ``bzr branch`` and