← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2008-08-20 20:21:00 UTC
  • mto: This revision was merged to the branch mainline in revision 3644.
  • Revision ID: john@arbash-meinel.com-20080820202100-hu678q27vjhcgrrl
Dropping the number of nodes to 100k from 200k
It is still enough to create a 3-level index, but all tests
run 2x faster.
We currently spend 1.635s creating and 3.733s adding nodes
and 9.842s flushing in the three_level and iter_all tests.
The test is 15s down from 68s which is a lot better.
It would be nice to have sub second tests, though.
For now, we'll live with this.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
16
16
 
17
17
"""Tests for btree indices."""
18
18
 
 
19
import pprint
19
20
import time
20
 
import pprint
21
21
import zlib
22
22
 
23
23
from bzrlib import (
85
85
                prefix = (str(prefix_pos) * 40,)
86
86
            else:
87
87
                prefix = ()
88
 
            for pos in range(count):
 
88
            for pos in xrange(count):
 
89
                # TODO: This creates odd keys. When count == 100,000, it
 
90
                #       creates a 240 byte key
89
91
                key = prefix + (str(pos) * 40,)
90
92
                value = "value:%s" % pos
91
93
                if reference_lists:
95
97
                        # as many keys in each list as its index + the key depth
96
98
                        # mod 2 - this generates both 0 length lists and
97
99
                        # ones slightly longer than the number of lists.
98
 
                        # It alsu ensures we have non homogeneous lists.
 
100
                        # It also ensures we have non homogeneous lists.
99
101
                        refs.append([])
100
102
                        for ref_pos in range(list_pos + pos % 2):
101
103
                            if pos % 2:
276
278
        # pointer to the second node that the internal node is for, _not_
277
279
        # the first, otherwise the first node overlaps with the last node of
278
280
        # the prior internal node on that row.
279
 
        # We will be adding 200,000 nodes, so spill at 200,001 to prevent
 
281
        # We will be adding 100,000 nodes, so spill at 100,001 to prevent
280
282
        # having to flush anything out to disk.
281
283
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
282
 
            spill_at=200001)
283
 
        # 200K nodes is enough to create a two internal nodes on the second level
 
284
                                           spill_at=100001)
 
285
        # 100K nodes is enough to create a two internal nodes on the second level
284
286
        tstart = time.time()
285
 
        nodes = self.make_nodes(100000, 2, 2)
 
287
        nodes = self.make_nodes(50000, 2, 2)
286
288
        delta_make = time.time() - tstart
287
289
 
288
290
        tstart = time.time()
691
693
        # iterating all entries reads the header, then does a linear
692
694
        # read.
693
695
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
694
 
                                           spill_at=200001)
695
 
        # 200k nodes is enough to create a three-level index.
696
 
        nodes = self.make_nodes(100000, 2, 2)
 
696
                                           spill_at=100001)
 
697
        # 100k nodes is enough to create a three-level index, which shows that
 
698
        # we skip the internal nodes and just read the leaf nodes.
 
699
        nodes = self.make_nodes(50000, 2, 2)
697
700
        for node in nodes:
698
701
            builder.add_node(*node)
699
702
        transport = get_transport('trace+' + self.get_url(''))
700
703
        size = transport.put_file('index', builder.finish())
701
 
        self.assertEqual(4058469, size, 'number of expected bytes in the'
 
704
        self.assertEqual(2026722, size, 'number of expected bytes in the'
702
705
                                        ' output changed')
703
706
        del builder
704
707
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
712
715
        self.assertEqual(3, len(index._row_lengths),
713
716
            "Not enough rows: %r" % index._row_lengths)
714
717
        # Should be as long as the nodes we supplied
715
 
        self.assertEqual(200000, len(found_nodes))
 
718
        self.assertEqual(100000, len(found_nodes))
716
719
        # Should have the same content
717
720
        self.assertEqual(set(nodes), set(bare_nodes))
718
721
        # Should have done linear scan IO up the index, ignoring
720
723
        # The entire index should have been read
721
724
        total_pages = sum(index._row_lengths)
722
725
        self.assertEqual(total_pages, index._row_offsets[-1])
723
 
        self.assertEqual(4058469, size)
 
726
        self.assertEqual(2026722, size)
724
727
        # The start of the leaves
725
728
        first_byte = index._row_offsets[-2] * btree_index._PAGE_SIZE
726
729
        readv_request = []
727
730
        for offset in range(first_byte, size, 4096):
728
731
            readv_request.append((offset, 4096))
729
 
        readv_request[-1] = (readv_request[-1][0], 3429)
 
732
        # The last page is truncated
 
733
        readv_request[-1] = (readv_request[-1][0], 3298)
730
734
        expected = [('readv', 'index', [(0, 4096)], False, None),
731
735
             ('readv',  'index', readv_request, False, None)]
732
736
        if expected != transport._activity: