← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__btree_serializer.py

  • Committer: John Arbash Meinel
  • Date: 2010-08-04 07:14:54 UTC
  • mto: This revision was merged to the branch mainline in revision 5390.
  • Revision ID: john@arbash-meinel.com-20100804071454-bfhbwrqes7sabvay
Populate the offsets array.

This cuts down the number of bisections dramatically, basically by pre-caching
the first step. On real-world data it drops the steps from 587 to 156.
Or from 4.9/key to 1.3/key.
This drops the time to lookup from 23.7us to 20.3us.
Note that (k in dict) is 12.2us. I do wish we were just a bit closer to that.
However, with _LeafNode inherited from dict, I get 26us, so
maybe there is something in the interpreter that does a PyDict_CheckExact
call, and there isn't much we can do about it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__btree_serializer.py
18
18
"""Direct tests of the btree serializer extension"""
19
19
 
20
20
import binascii
 
21
import bisect
21
22
 
22
23
from bzrlib import tests
23
24
 
138
139
"""
139
140
 
140
141
_multi_key_content = """type=leaf
141
 
sha1:70c881d4a26984ddce795f6f71817c9cf4480e79\x00\x000 0 0 0
142
 
sha1:7e240de74fb1ed08fa08d38063f6a6a91462a815\x00\x001 1 1 1
143
 
sha1:86f7e437faa5a7fce15d1ddcb9eaeaea377667b8\x00\x002 2 2 2
144
 
sha1:da39a3ee5e6b4b0d3255bfef95601890afd80709\x00\x003 3 3 3
145
 
sha1:df51e37c269aa94d38f93e537bf6e2020b21406c\x00\x004 4 4 4
146
 
sha1:e0c9035898dd52fc65c41454cec9c4d2611bfb37\x00\x005 5 5 5
147
 
sha1:e93b4e3c464ffd51732fbd6ded717e9efda28aad\x00\x006 6 6 6
148
 
sha1:f7a9e24777ec23212c54d7a350bc5bea5477fdbb\x00\x007 7 7 7
 
142
sha1:c80c881d4a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
 
143
sha1:c86f7e437faa5a7fce15d1ddcb9eaeaea377667b\x00\x001 1 1 1
 
144
sha1:c8e240de74fb1ed08fa08d38063f6a6a91462a81\x00\x002 2 2 2
 
145
sha1:cda39a3ee5e6b4b0d3255bfef95601890afd8070\x00\x003 3 3 3
 
146
sha1:cdf51e37c269aa94d38f93e537bf6e2020b21406\x00\x004 4 4 4
 
147
sha1:ce0c9035898dd52fc65c41454cec9c4d2611bfb3\x00\x005 5 5 5
 
148
sha1:ce93b4e3c464ffd51732fbd6ded717e9efda28aa\x00\x006 6 6 6
 
149
sha1:cf7a9e24777ec23212c54d7a350bc5bea5477fdb\x00\x007 7 7 7
149
150
"""
150
151
 
151
152
class TestGCCKHSHA1LeafNode(TestBtreeSerializer):
194
195
        self.assertEqual(8, len(leaf.all_keys()))
195
196
        for idx, key in enumerate(all_keys):
196
197
            self.assertEqual(str(idx), leaf[key][0].split()[0])
 
198
 
 
199
    def test_common_mask(self):
 
200
        # The keys were deliberately chosen so that the first 5 bits all
 
201
        # overlapped, it also happens that a later bit overlaps
 
202
        # Note that by 'overlap' we mean that given bit is either on in all
 
203
        # keys, or off in all keys
 
204
        leaf = self.module._parse_into_chk(_multi_key_content, 1, 0)
 
205
        self.assertEqual(hex(0xF8000100), hex(leaf.common_mask))
 
206
        self.assertEqual(5, leaf.common_shift)
 
207
        self.assertEqual(0xc8000000, leaf.common_bits)
 
208
        # The interesting byte for each key is
 
209
        # (defined as the 8-bits that come after the common prefix)
 
210
        # [1, 13, 28, 180, 190, 193, 210, 239]
 
211
        lst = [1, 13, 28, 180, 190, 193, 210, 239]
 
212
        offsets = leaf._test_offsets
 
213
        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
 
214
                         offsets)
 
215
        for idx, val in enumerate(lst):
 
216
            self.assertEqual(idx, offsets[val])