« back to all changes in this revision
Viewing changes to bzrlib/chk_map.py
- browse files at revision 4603.1.19
- compare with another revision
- compare with revision 4964
- download diff
- download tarball
- view history from revision 4603.1.19
- Committer: Aaron Bentley
- Date: 2009-10-31 00:44:22 UTC
- mfrom: (4778 +trunk)
- mto: (4603.1.22 shelve-editor)
- mto: This revision was merged to the branch mainline in revision 4795.
- Revision ID: aaron@aaronbentley.com-20091031004422-i2qciijx2ik4gctc
Merged bzr.dev into shelve-editor.
- files added:
- bzrlib/cleanup.py
- files modified:
- Makefile
added
removed
bzrlib/chk_map.py
52
52
registry,
53
53
trace,
54
54
)
55
from bzrlib.static_tuple import StaticTuple
55
56
56
57
# approx 4MB
57
58
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
114
115
"""
115
116
delete_count = 0
116
117
# Check preconditions first.
117
new_items = set([key for (old, key, value) in delta if key is not None
118
and old is None])
118
as_st = StaticTuple.from_sequence
119
new_items = set([as_st(key) for (old, key, value) in delta
120
if key is not None and old is None])
119
121
existing_new = list(self.iteritems(key_filter=new_items))
120
122
if existing_new:
121
123
raise errors.InconsistentDeltaDelta(delta,
135
137
136
138
def _ensure_root(self):
137
139
"""Ensure that the root node is an object not a key."""
138
if type(self._root_node) is tuple:
140
if type(self._root_node) is StaticTuple:
139
141
# Demand-load the root
140
142
self._root_node = self._get_node(self._root_node)
141
143
149
151
:param node: A tuple key or node object.
150
152
:return: A node object.
151
153
"""
152
if type(node) is tuple:
154
if type(node) is StaticTuple:
153
155
bytes = self._read_bytes(node)
154
156
return _deserialise(bytes, node,
155
157
search_key_func=self._search_key_func)
196
198
for key, value in sorted(node._items.iteritems()):
197
199
# Don't use prefix nor indent here to line up when used in
198
200
# tests in conjunction with assertEqualDiff
199
result.append(' %r %r' % (key, value))
201
result.append(' %r %r' % (tuple(key), value))
200
202
return result
201
203
202
204
@classmethod
220
222
root_key = klass._create_directly(store, initial_value,
221
223
maximum_size=maximum_size, key_width=key_width,
222
224
search_key_func=search_key_func)
225
if type(root_key) is not StaticTuple:
226
raise AssertionError('we got a %s instead of a StaticTuple'
227
% (type(root_key),))
223
228
return root_key
224
229
225
230
@classmethod
240
245
node = LeafNode(search_key_func=search_key_func)
241
246
node.set_maximum_size(maximum_size)
242
247
node._key_width = key_width
243
node._items = dict(initial_value)
248
as_st = StaticTuple.from_sequence
249
node._items = dict([(as_st(key), val) for key, val
250
in initial_value.iteritems()])
244
251
node._raw_size = sum([node._key_value_len(key, value)
245
for key,value in initial_value.iteritems()])
252
for key,value in node._items.iteritems()])
246
253
node._len = len(node._items)
247
254
node._compute_search_prefix()
248
255
node._compute_serialised_prefix()
484
491
def iteritems(self, key_filter=None):
485
492
"""Iterate over the entire CHKMap's contents."""
486
493
self._ensure_root()
494
if key_filter is not None:
495
as_st = StaticTuple.from_sequence
496
key_filter = [as_st(key) for key in key_filter]
487
497
return self._root_node.iteritems(self._store, key_filter=key_filter)
488
498
489
499
def key(self):
490
500
"""Return the key for this map."""
491
if type(self._root_node) is tuple:
501
if type(self._root_node) is StaticTuple:
492
502
return self._root_node
493
503
else:
494
504
return self._root_node._key
503
513
:param key: A key to map.
504
514
:param value: The value to assign to key.
505
515
"""
516
key = StaticTuple.from_sequence(key)
506
517
# Need a root object.
507
518
self._ensure_root()
508
519
prefix, node_details = self._root_node.map(self._store, key, value)
519
530
def _node_key(self, node):
520
531
"""Get the key for a node whether it's a tuple or node."""
521
532
if type(node) is tuple:
533
node = StaticTuple.from_sequence(node)
534
if type(node) is StaticTuple:
522
535
return node
523
536
else:
524
537
return node._key
525
538
526
539
def unmap(self, key, check_remap=True):
527
540
"""remove key from the map."""
541
key = StaticTuple.from_sequence(key)
528
542
self._ensure_root()
529
543
if type(self._root_node) is InternalNode:
530
544
unmapped = self._root_node.unmap(self._store, key,
544
558
545
559
:return: The key of the root node.
546
560
"""
547
if type(self._root_node) is tuple:
561
if type(self._root_node) is StaticTuple:
548
562
# Already saved.
549
563
return self._root_node
550
564
keys = list(self._root_node.serialise(self._store))
881
895
lines.append(serialized[prefix_len:])
882
896
lines.extend(value_lines)
883
897
sha1, _, _ = store.add_lines((None,), (), lines)
884
self._key = ("sha1:" + sha1,)
898
self._key = StaticTuple("sha1:" + sha1,).intern()
885
899
bytes = ''.join(lines)
886
900
if len(bytes) != self._current_size():
887
901
raise AssertionError('Invalid _current_size')
1004
1018
:param key: The key that the serialised node has.
1005
1019
:return: An InternalNode instance.
1006
1020
"""
1021
if type(key) is not StaticTuple:
1022
raise AssertionError('deserialise should be called with a'
1023
' StaticTuple not %s' % (type(key),))
1007
1024
return _deserialise_internal_node(bytes, key,
1008
1025
search_key_func=search_key_func)
1009
1026
1034
1051
# for whatever we are missing
1035
1052
shortcut = True
1036
1053
for prefix, node in self._items.iteritems():
1037
if node.__class__ is tuple:
1054
if node.__class__ is StaticTuple:
1038
1055
keys[node] = (prefix, None)
1039
1056
else:
1040
1057
yield node, None
1069
1086
# A given key can only match 1 child node, if it isn't
1070
1087
# there, then we can just return nothing
1071
1088
return
1072
if node.__class__ is tuple:
1089
if node.__class__ is StaticTuple:
1073
1090
keys[node] = (search_prefix, [key])
1074
1091
else:
1075
1092
# This is loaded, and the only thing that can match,
1102
1119
# We can ignore this one
1103
1120
continue
1104
1121
node_key_filter = prefix_to_keys[search_prefix]
1105
if node.__class__ is tuple:
1122
if node.__class__ is StaticTuple:
1106
1123
keys[node] = (search_prefix, node_key_filter)
1107
1124
else:
1108
1125
yield node, node_key_filter
1117
1134
if sub_prefix in length_filter:
1118
1135
node_key_filter.extend(prefix_to_keys[sub_prefix])
1119
1136
if node_key_filter: # this key matched something, yield it
1120
if node.__class__ is tuple:
1137
if node.__class__ is StaticTuple:
1121
1138
keys[node] = (prefix, node_key_filter)
1122
1139
else:
1123
1140
yield node, node_key_filter
1255
1272
:return: An iterable of the keys inserted by this operation.
1256
1273
"""
1257
1274
for node in self._items.itervalues():
1258
if type(node) is tuple:
1275
if type(node) is StaticTuple:
1259
1276
# Never deserialised.
1260
1277
continue
1261
1278
if node._key is not None:
1272
1289
lines.append('%s\n' % (self._search_prefix,))
1273
1290
prefix_len = len(self._search_prefix)
1274
1291
for prefix, node in sorted(self._items.items()):
1275
if type(node) is tuple:
1292
if type(node) is StaticTuple:
1276
1293
key = node[0]
1277
1294
else:
1278
1295
key = node._key[0]
1282
1299
% (serialised, self._search_prefix))
1283
1300
lines.append(serialised[prefix_len:])
1284
1301
sha1, _, _ = store.add_lines((None,), (), lines)
1285
self._key = ("sha1:" + sha1,)
1302
self._key = StaticTuple("sha1:" + sha1,).intern()
1286
1303
_page_cache.add(self._key, ''.join(lines))
1287
1304
yield self._key
1288
1305
1317
1334
raise AssertionError("unserialised nodes have no refs.")
1318
1335
refs = []
1319
1336
for value in self._items.itervalues():
1320
if type(value) is tuple:
1337
if type(value) is StaticTuple:
1321
1338
refs.append(value)
1322
1339
else:
1323
1340
refs.append(value.key())
1437
1454
1438
1455
def __init__(self, store, new_root_keys, old_root_keys,
1439
1456
search_key_func, pb=None):
1457
# TODO: Should we add a StaticTuple barrier here? It would be nice to
1458
# force callers to use StaticTuple, because there will often be
1459
# lots of keys passed in here. And even if we cast it locally,
1460
# that just meanst that we will have *both* a StaticTuple and a
1461
# tuple() in memory, referring to the same object. (so a net
1462
# increase in memory, not a decrease.)
1440
1463
self._store = store
1441
1464
self._new_root_keys = new_root_keys
1442
1465
self._old_root_keys = old_root_keys
1444
1467
# All uninteresting chks that we have seen. By the time they are added
1445
1468
# here, they should be either fully ignored, or queued up for
1446
1469
# processing
1470
# TODO: This might grow to a large size if there are lots of merge
1471
# parents, etc. However, it probably doesn't scale to O(history)
1472
# like _processed_new_refs does.
1447
1473
self._all_old_chks = set(self._old_root_keys)
1448
1474
# All items that we have seen from the old_root_keys
1449
1475
self._all_old_items = set()
1450
1476
# These are interesting items which were either read, or already in the
1451
1477
# interesting queue (so we don't need to walk them again)
1478
# TODO: processed_new_refs becomes O(all_chks), consider switching to
1479
# SimpleSet here.
1452
1480
self._processed_new_refs = set()
1453
1481
self._search_key_func = search_key_func
1454
1482
1466
1494
# this code. (We may want to evaluate saving the raw bytes into the
1467
1495
# page cache, which would allow a working tree update after the fetch
1468
1496
# to not have to read the bytes again.)
1497
as_st = StaticTuple.from_sequence
1469
1498
stream = self._store.get_record_stream(keys, 'unordered', True)
1470
1499
for record in stream:
1471
1500
if self._pb is not None:
1478
1507
if type(node) is InternalNode:
1479
1508
# Note we don't have to do node.refs() because we know that
1480
1509
# there are no children that have been pushed into this node
1510
# Note: Using as_st() here seemed to save 1.2MB, which would
1511
# indicate that we keep 100k prefix_refs around while
1512
# processing. They *should* be shorter lived than that...
1513
# It does cost us ~10s of processing time
1514
#prefix_refs = [as_st(item) for item in node._items.iteritems()]
1481
1515
prefix_refs = node._items.items()
1482
1516
items = []
1483
1517
else:
1484
1518
prefix_refs = []
1519
# Note: We don't use a StaticTuple here. Profiling showed a
1520
# minor memory improvement (0.8MB out of 335MB peak 0.2%)
1521
# But a significant slowdown (15s / 145s, or 10%)
1485
1522
items = node._items.items()
1486
1523
yield record, node, prefix_refs, items
1487
1524
1495
1532
if p_r[1] not in all_old_chks]
1496
1533
new_refs = [p_r[1] for p_r in prefix_refs]
1497
1534
all_old_chks.update(new_refs)
1535
# TODO: This might be a good time to turn items into StaticTuple
1536
# instances and possibly intern them. However, this does not
1537
# impact 'initial branch' performance, so I'm not worrying
1538
# about this yet
1498
1539
self._all_old_items.update(items)
1499
1540
# Queue up the uninteresting references
1500
1541
# Don't actually put them in the 'to-read' queue until we have
1553
1594
# current design allows for this, as callers will do the work
1554
1595
# to make the results unique. We might profile whether we
1555
1596
# gain anything by ensuring unique return values for items
1597
# TODO: This might be a good time to cast to StaticTuple, as
1598
# self._new_item_queue will hold the contents of multiple
1599
# records for an extended lifetime
1556
1600
new_items = [item for item in items
1557
1601
if item not in self._all_old_items]
1558
1602
self._new_item_queue.extend(new_items)
1583
1627
if new_items:
1584
1628
yield None, new_items
1585
1629
refs = refs.difference(all_old_chks)
1630
processed_new_refs.update(refs)
1586
1631
while refs:
1632
# TODO: Using a SimpleSet for self._processed_new_refs and
1633
# saved as much as 10MB of peak memory. However, it requires
1634
# implementing a non-pyrex version.
1587
1635
next_refs = set()
1588
1636
next_refs_update = next_refs.update
1589
1637
# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
1590
1638
# from 1m54s to 1m51s. Consider it.
1591
1639
for record, _, p_refs, items in self._read_nodes_from_store(refs):
1592
items = [item for item in items
1593
if item not in all_old_items]
1640
if all_old_items:
1641
# using the 'if' check saves about 145s => 141s, when
1642
# streaming initial branch of Launchpad data.
1643
items = [item for item in items
1644
if item not in all_old_items]
1594
1645
yield record, items
1595
1646
next_refs_update([p_r[1] for p_r in p_refs])
1647
del p_refs
1648
# set1.difference(set/dict) walks all of set1, and checks if it
1649
# exists in 'other'.
1650
# set1.difference(iterable) walks all of iterable, and does a
1651
# 'difference_update' on a clone of set1. Pick wisely based on the
1652
# expected sizes of objects.
1653
# in our case it is expected that 'new_refs' will always be quite
1654
# small.
1596
1655
next_refs = next_refs.difference(all_old_chks)
1597
1656
next_refs = next_refs.difference(processed_new_refs)
1598
1657
processed_new_refs.update(next_refs)
1605
1664
self._old_queue = []
1606
1665
all_old_chks = self._all_old_chks
1607
1666
for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
1667
# TODO: Use StaticTuple here?
1608
1668
self._all_old_items.update(items)
1609
1669
refs = [r for _,r in prefix_refs if r not in all_old_chks]
1610
1670
self._old_queue.extend(refs)
1660
1720
)
1661
1721
search_key_registry.register('hash-16-way', _search_key_16)
1662
1722
search_key_registry.register('hash-255-way', _search_key_255)
1723
1724
1725
def _check_key(key):
1726
"""Helper function to assert that a key is properly formatted.
1727
1728
This generally shouldn't be used in production code, but it can be helpful
1729
to debug problems.
1730
"""
1731
if type(key) is not StaticTuple:
1732
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1733
if len(key) != 1:
1734
raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
1735
if type(key[0]) is not str:
1736
raise TypeError('key %r should hold a str, not %r'
1737
% (key, type(key[0])))
1738
if not key[0].startswith('sha1:'):
1739
raise ValueError('key %r should point to a sha1:' % (key,))
1740
1741
Loggerhead is a web-based interface for Breezy
Version: 2.0.1