← 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: 2009-11-07 01:58:11 UTC
  • mto: This revision was merged to the branch mainline in revision 4842.
  • Revision ID: john@arbash-meinel.com-20091107015811-apybkqd40koa4b98
Get rid of the GraphIndexBuilder/BTreeBuilder._keys attribute.

This removes a set that grows O(N). We used it for some performance
stuff, because set.intersection is not efficient if other is not
a set. But we can work around that differently. It saves about 2MB
for a set with 100k items in it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
359
359
        # Test the parts of the index that take up memory are doing so
360
360
        # predictably.
361
361
        self.assertEqual(1, len(builder._nodes))
362
 
        self.assertEqual(1, len(builder._keys))
363
362
        self.assertIs(None, builder._nodes_by_key)
364
363
        builder.add_node(*nodes[1])
365
364
        self.assertEqual(0, len(builder._nodes))
366
 
        self.assertEqual(0, len(builder._keys))
367
365
        self.assertIs(None, builder._nodes_by_key)
368
366
        self.assertEqual(1, len(builder._backing_indices))
369
367
        self.assertEqual(2, builder._backing_indices[0].key_count())
370
368
        # now back to memory
371
369
        builder.add_node(*nodes[2])
372
370
        self.assertEqual(1, len(builder._nodes))
373
 
        self.assertEqual(1, len(builder._keys))
374
371
        self.assertIs(None, builder._nodes_by_key)
375
372
        # And spills to a second backing index combing all
376
373
        builder.add_node(*nodes[3])
377
374
        self.assertEqual(0, len(builder._nodes))
378
 
        self.assertEqual(0, len(builder._keys))
379
375
        self.assertIs(None, builder._nodes_by_key)
380
376
        self.assertEqual(2, len(builder._backing_indices))
381
377
        self.assertEqual(None, builder._backing_indices[0])
384
380
        builder.add_node(*nodes[4])
385
381
        builder.add_node(*nodes[5])
386
382
        self.assertEqual(0, len(builder._nodes))
387
 
        self.assertEqual(0, len(builder._keys))
388
383
        self.assertIs(None, builder._nodes_by_key)
389
384
        self.assertEqual(2, len(builder._backing_indices))
390
385
        self.assertEqual(2, builder._backing_indices[0].key_count())
448
443
        # Test the parts of the index that take up memory are doing so
449
444
        # predictably.
450
445
        self.assertEqual(1, len(builder._nodes))
451
 
        self.assertEqual(1, len(builder._keys))
452
446
        self.assertIs(None, builder._nodes_by_key)
453
447
        builder.add_node(*nodes[1])
454
448
        self.assertEqual(0, len(builder._nodes))
455
 
        self.assertEqual(0, len(builder._keys))
456
449
        self.assertIs(None, builder._nodes_by_key)
457
450
        self.assertEqual(1, len(builder._backing_indices))
458
451
        self.assertEqual(2, builder._backing_indices[0].key_count())
459
452
        # now back to memory
460
453
        builder.add_node(*nodes[2])
461
454
        self.assertEqual(1, len(builder._nodes))
462
 
        self.assertEqual(1, len(builder._keys))
463
455
        self.assertIs(None, builder._nodes_by_key)
464
456
        # And spills to a second backing index but doesn't combine
465
457
        builder.add_node(*nodes[3])
466
458
        self.assertEqual(0, len(builder._nodes))
467
 
        self.assertEqual(0, len(builder._keys))
468
459
        self.assertIs(None, builder._nodes_by_key)
469
460
        self.assertEqual(2, len(builder._backing_indices))
470
461
        for backing_index in builder._backing_indices:
473
464
        builder.add_node(*nodes[4])
474
465
        builder.add_node(*nodes[5])
475
466
        self.assertEqual(0, len(builder._nodes))
476
 
        self.assertEqual(0, len(builder._keys))
477
467
        self.assertIs(None, builder._nodes_by_key)
478
468
        self.assertEqual(3, len(builder._backing_indices))
479
469
        for backing_index in builder._backing_indices:
538
528
        builder.add_node(*nodes[0])
539
529
        # Test the parts of the index that take up memory are doing so
540
530
        # predictably.
541
 
        self.assertEqual(1, len(builder._keys))
542
531
        self.assertEqual(1, len(builder._nodes))
543
532
        self.assertIs(None, builder._nodes_by_key)
544
533
        builder.add_node(*nodes[1])
545
 
        self.assertEqual(0, len(builder._keys))
546
534
        self.assertEqual(0, len(builder._nodes))
547
535
        self.assertIs(None, builder._nodes_by_key)
548
536
        self.assertEqual(1, len(builder._backing_indices))
551
539
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
552
540
        builder.add_node(*nodes[2])
553
541
        self.assertEqual(1, len(builder._nodes))
554
 
        self.assertEqual(1, len(builder._keys))
555
542
        self.assertIsNot(None, builder._nodes_by_key)
556
543
        self.assertNotEqual({}, builder._nodes_by_key)
557
544
        # We should have a new entry
559
546
        # And spills to a second backing index combing all
560
547
        builder.add_node(*nodes[3])
561
548
        self.assertEqual(0, len(builder._nodes))
562
 
        self.assertEqual(0, len(builder._keys))
563
549
        self.assertIs(None, builder._nodes_by_key)
564
550
        self.assertEqual(2, len(builder._backing_indices))
565
551
        self.assertEqual(None, builder._backing_indices[0])
568
554
        builder.add_node(*nodes[4])
569
555
        builder.add_node(*nodes[5])
570
556
        self.assertEqual(0, len(builder._nodes))
571
 
        self.assertEqual(0, len(builder._keys))
572
557
        self.assertIs(None, builder._nodes_by_key)
573
558
        self.assertEqual(2, len(builder._backing_indices))
574
559
        self.assertEqual(2, builder._backing_indices[0].key_count())