Rev 4749: (jam) Start using StaticTuple as part of the btree_index parsing code. in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Thu Oct 15 21:16:35 BST 2009
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 4749 [merge]
revision-id: pqm at pqm.ubuntu.com-20091015201628-3au8qv0a86i6uk8q
parent: pqm at pqm.ubuntu.com-20091015180224-g9dphv661law8y20
parent: john at arbash-meinel.com-20091015182814-nmkoljsluq9uyzkd
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Thu 2009-10-15 21:16:28 +0100
message:
(jam) Start using StaticTuple as part of the btree_index parsing code.
added:
bzrlib/static_tuple.py static_tuple.py-20091012195926-qa7zh2stf4xtblm8-1
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/_bencode_pyx.pyx bencode.pyx-20070806220735-j75g4ebfnado2i60-3
bzrlib/_btree_serializer_pyx.pyx _parse_btree_c.pyx-20080703034413-3q25bklkenti3p8p-2
bzrlib/_static_tuple_c.c _keys_type_c.c-20090908204220-aa346ccw4l37jzt7-1
bzrlib/btree_index.py index.py-20080624222253-p0x5f92uyh5hw734-7
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/tests/test__static_tuple.py test__keys_type.py-20090908204220-aa346ccw4l37jzt7-2
bzrlib/util/_bencode_py.py bencode.py-20070220044742-sltr28q21w2wzlxi-1
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
=== modified file 'NEWS'
--- a/NEWS 2009-10-15 04:06:32 +0000
+++ b/NEWS 2009-10-15 18:18:44 +0000
@@ -25,6 +25,11 @@
Improvements
************
+* When reading index files, we now use a ``StaticTuple`` rather than a
+ plain ``tuple`` object. This generally gives a 20% decrease in peak
+ memory, and can give a performance boost up to 40% on large projects.
+ (John Arbash Meinel)
+
Documentation
*************
@@ -45,13 +50,14 @@
used as the interning structure for StaticTuple objects.
(John Arbash Meinel)
-* ``bzrlib._static_tuple_pyx.StaticTuple`` is now available. This class
- functions similarly to ``tuple`` objects. However, it can only point at
- other ``StaticTuple`` instances or strings. This allows us to remove it
- from the garbage collector (it cannot be in a cycle), it also allows us
- to intern the objects. In testing, this can reduce peak memory by
- 20-40%, and significantly improve performance by removing objects from
- being inspected by the garbage collector. (John Arbash Meinel)
+* ``bzrlib._static_tuple_pyx.StaticTuple`` is now available and used by
+ the btree index parser. This class functions similarly to ``tuple``
+ objects. However, it can only point at other ``StaticTuple`` instances
+ or strings. This allows us to remove it from the garbage collector (it
+ cannot be in a cycle), it also allows us to intern the objects. In
+ testing, this can reduce peak memory by 20-40%, and significantly
+ improve performance by removing objects from being inspected by the
+ garbage collector. (John Arbash Meinel)
Testing
*******
=== modified file 'bzrlib/_bencode_pyx.pyx'
--- a/bzrlib/_bencode_pyx.pyx 2009-06-05 01:48:32 +0000
+++ b/bzrlib/_bencode_pyx.pyx 2009-10-15 18:28:14 +0000
@@ -58,6 +58,13 @@
void D_UPDATE_TAIL(Decoder, int n)
void E_UPDATE_TAIL(Encoder, int n)
+# To maintain compatibility with older versions of pyrex, we have to use the
+# relative import here, rather than 'bzrlib._static_tuple_c'
+from _static_tuple_c cimport StaticTuple, StaticTuple_CheckExact, \
+ import_static_tuple_c
+
+import_static_tuple_c()
+
cdef class Decoder:
"""Bencode decoder"""
@@ -371,7 +378,8 @@
self._encode_int(x)
elif PyLong_CheckExact(x):
self._encode_long(x)
- elif PyList_CheckExact(x) or PyTuple_CheckExact(x):
+ elif (PyList_CheckExact(x) or PyTuple_CheckExact(x)
+ or StaticTuple_CheckExact(x)):
self._encode_list(x)
elif PyDict_CheckExact(x):
self._encode_dict(x)
=== modified file 'bzrlib/_btree_serializer_pyx.pyx'
--- a/bzrlib/_btree_serializer_pyx.pyx 2009-10-08 05:12:01 +0000
+++ b/bzrlib/_btree_serializer_pyx.pyx 2009-10-12 20:07:09 +0000
@@ -38,6 +38,8 @@
Py_ssize_t PyString_Size(object p)
Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
+ char * PyString_AS_STRING(object)
+ Py_ssize_t PyString_GET_SIZE(object)
int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
void PyString_InternInPlace(PyObject **)
int PyTuple_CheckExact(object t)
@@ -55,6 +57,12 @@
# void *memrchr(void *s, int c, size_t n)
int strncmp(char *s1, char *s2, size_t n)
+# 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
+
# TODO: Find some way to import this from _dirstate_helpers
cdef void* _my_memrchr(void *s, int c, size_t n):
@@ -71,6 +79,7 @@
pos = pos - 1
return NULL
+
# TODO: Import this from _dirstate_helpers when it is merged
cdef object safe_string_from_size(char *s, Py_ssize_t size):
if size < 0:
@@ -94,6 +103,10 @@
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()
+
cdef class BTreeLeafParser:
"""Parse the leaf nodes of a BTree index.
@@ -133,6 +146,7 @@
self._cur_str = NULL
self._end_str = NULL
self._header_found = 0
+ # keys are tuples
cdef extract_key(self, char * last):
"""Extract a key.
@@ -142,8 +156,9 @@
"""
cdef char *temp_ptr
cdef int loop_counter
- # keys are tuples
- key = PyTuple_New(self.key_length)
+ cdef StaticTuple key
+
+ key = StaticTuple_New(self.key_length)
for loop_counter from 0 <= loop_counter < self.key_length:
# grab a key segment
temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
@@ -158,15 +173,19 @@
last - self._start)))
raise AssertionError(failure_string)
# capture the key string
- # TODO: Consider using PyIntern_FromString, the only caveat is that
- # it assumes a NULL-terminated string, so we have to check if
- # temp_ptr[0] == c'\0' or some other char.
- key_element = safe_interned_string_from_size(self._start,
+ if (self.key_length == 1
+ and (temp_ptr - self._start) == 45
+ and strncmp(self._start, 'sha1:', 5) == 0):
+ key_element = safe_string_from_size(self._start,
+ temp_ptr - self._start)
+ else:
+ key_element = safe_interned_string_from_size(self._start,
temp_ptr - self._start)
# advance our pointer
self._start = temp_ptr + 1
Py_INCREF(key_element)
- PyTuple_SET_ITEM(key, loop_counter, key_element)
+ StaticTuple_SET_ITEM(key, loop_counter, key_element)
+ key = StaticTuple_Intern(key)
return key
cdef int process_line(self) except -1:
@@ -176,6 +195,7 @@
cdef char *ref_ptr
cdef char *next_start
cdef int loop_counter
+ cdef Py_ssize_t str_len
self._start = self._cur_str
# Find the next newline
@@ -211,12 +231,25 @@
# Invalid line
raise AssertionError("Failed to find the value area")
else:
- # capture the value string
- value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
+ # Because of how conversions were done, we ended up with *lots* of
+ # values that are identical. These are all of the 0-length nodes
+ # that are referred to by the TREE_ROOT (and likely some other
+ # directory nodes.) For example, bzr has 25k references to
+ # something like '12607215 328306 0 0', which ends up consuming 1MB
+ # of memory, just for those strings.
+ str_len = last - temp_ptr - 1
+ if (str_len > 4
+ and strncmp(" 0 0", last - 4, 4) == 0):
+ # This drops peak mem for bzr.dev from 87.4MB => 86.2MB
+ # For Launchpad 236MB => 232MB
+ value = safe_interned_string_from_size(temp_ptr + 1, str_len)
+ else:
+ value = safe_string_from_size(temp_ptr + 1, str_len)
# shrink the references end point
last = temp_ptr
+
if self.ref_list_length:
- ref_lists = []
+ ref_lists = StaticTuple_New(self.ref_list_length)
loop_counter = 0
while loop_counter < self.ref_list_length:
ref_list = []
@@ -248,18 +281,20 @@
if temp_ptr == NULL:
# key runs to the end
temp_ptr = ref_ptr
+
PyList_Append(ref_list, self.extract_key(temp_ptr))
- PyList_Append(ref_lists, tuple(ref_list))
+ ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
+ Py_INCREF(ref_list)
+ StaticTuple_SET_ITEM(ref_lists, loop_counter - 1, ref_list)
# prepare for the next reference list
self._start = next_start
- ref_lists = tuple(ref_lists)
- node_value = (value, ref_lists)
+ node_value = StaticTuple(value, ref_lists)
else:
if last != self._start:
# unexpected reference data present
raise AssertionError("unexpected reference data present")
- node_value = (value, ())
- PyList_Append(self.keys, (key, node_value))
+ node_value = StaticTuple(value, StaticTuple())
+ PyList_Append(self.keys, StaticTuple(key, node_value))
return 0
def parse(self):
@@ -294,7 +329,6 @@
cdef Py_ssize_t flat_len
cdef Py_ssize_t key_len
cdef Py_ssize_t node_len
- cdef PyObject * val
cdef char * value
cdef Py_ssize_t value_len
cdef char * out
@@ -303,13 +337,12 @@
cdef int first_ref_list
cdef int first_reference
cdef int i
- cdef PyObject *ref_bit
cdef Py_ssize_t ref_bit_len
- if not PyTuple_CheckExact(node):
- raise TypeError('We expected a tuple() for node not: %s'
+ if not PyTuple_CheckExact(node) and not StaticTuple_CheckExact(node):
+ raise TypeError('We expected a tuple() or StaticTuple() for node not: %s'
% type(node))
- node_len = PyTuple_GET_SIZE(node)
+ node_len = len(node)
have_reference_lists = reference_lists
if have_reference_lists:
if node_len != 4:
@@ -318,8 +351,17 @@
elif node_len < 3:
raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
% len(node))
- # I don't expect that we can do faster than string.join()
- string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
+ # TODO: We can probably do better than string.join(), namely
+ # when key has only 1 item, we can just grab that string
+ # And when there are 2 items, we could do a single malloc + len() + 1
+ # also, doing .join() requires a PyObject_GetAttrString call, which
+ # we could also avoid.
+ # TODO: Note that pyrex 0.9.6 generates fairly crummy code here, using the
+ # python object interface, versus 0.9.8+ which uses a helper that
+ # checks if this supports the sequence interface.
+ # We *could* do more work on our own, and grab the actual items
+ # lists. For now, just ask people to use a better compiler. :)
+ string_key = '\0'.join(node[1])
# TODO: instead of using string joins, precompute the final string length,
# and then malloc a single string and copy everything in.
@@ -336,7 +378,7 @@
refs_len = 0
if have_reference_lists:
# Figure out how many bytes it will take to store the references
- ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
+ ref_lists = node[3]
next_len = len(ref_lists) # TODO: use a Py function
if next_len > 0:
# If there are no nodes, we don't need to do any work
@@ -350,31 +392,31 @@
# references
refs_len = refs_len + (next_len - 1)
for reference in ref_list:
- if not PyTuple_CheckExact(reference):
+ if (not PyTuple_CheckExact(reference)
+ and not StaticTuple_CheckExact(reference)):
raise TypeError(
'We expect references to be tuples not: %s'
% type(reference))
- next_len = PyTuple_GET_SIZE(reference)
+ next_len = len(reference)
if next_len > 0:
# We will need (len - 1) '\x00' characters to
# separate the reference key
refs_len = refs_len + (next_len - 1)
- for i from 0 <= i < next_len:
- ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
- if not PyString_CheckExact_ptr(ref_bit):
+ for ref_bit in reference:
+ if not PyString_CheckExact(ref_bit):
raise TypeError('We expect reference bits'
' to be strings not: %s'
% type(<object>ref_bit))
- refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
+ refs_len = refs_len + PyString_GET_SIZE(ref_bit)
# So we have the (key NULL refs NULL value LF)
key_len = PyString_Size(string_key)
- val = PyTuple_GET_ITEM_ptr_object(node, 2)
- if not PyString_CheckExact_ptr(val):
+ val = node[2]
+ if not PyString_CheckExact(val):
raise TypeError('Expected a plain str for value not: %s'
- % type(<object>val))
- value = PyString_AS_STRING_ptr(val)
- value_len = PyString_GET_SIZE_ptr(val)
+ % type(val))
+ value = PyString_AS_STRING(val)
+ value_len = PyString_GET_SIZE(val)
flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
line = PyString_FromStringAndSize(NULL, flat_len)
# Get a pointer to the new buffer
@@ -396,14 +438,14 @@
out[0] = c'\r'
out = out + 1
first_reference = 0
- next_len = PyTuple_GET_SIZE(reference)
+ next_len = len(reference)
for i from 0 <= i < next_len:
if i != 0:
out[0] = c'\x00'
out = out + 1
- ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
- ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
- memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
+ ref_bit = reference[i]
+ ref_bit_len = PyString_GET_SIZE(ref_bit)
+ memcpy(out, PyString_AS_STRING(ref_bit), ref_bit_len)
out = out + ref_bit_len
out[0] = c'\0'
out = out + 1
=== modified file 'bzrlib/_static_tuple_c.c'
--- a/bzrlib/_static_tuple_c.c 2009-10-15 16:18:47 +0000
+++ b/bzrlib/_static_tuple_c.c 2009-10-15 18:18:44 +0000
@@ -418,9 +418,15 @@
return NULL; /* There seems to be an error */
}
if (result == Py_NotImplemented) {
- PyErr_BadInternalCall();
Py_DECREF(result);
- return NULL;
+ /* One side must have had a string and the other a StaticTuple.
+ * This clearly means that they are not equal.
+ */
+ if (op == Py_EQ) {
+ Py_INCREF(Py_False);
+ return Py_False;
+ }
+ result = PyObject_RichCompare(v_obj, w_obj, Py_EQ);
}
if (result == Py_False) {
/* This entry is not identical
=== modified file 'bzrlib/btree_index.py'
--- a/bzrlib/btree_index.py 2009-10-15 04:01:26 +0000
+++ b/bzrlib/btree_index.py 2009-10-15 18:18:44 +0000
@@ -163,6 +163,7 @@
node_refs, _ = self._check_key_ref_value(key, references, value)
if key in self._nodes:
raise errors.BadIndexDuplicateKey(key, self)
+ # TODO: StaticTuple
self._nodes[key] = (node_refs, value)
self._keys.add(key)
if self._nodes_by_key is not None and self._key_length > 1:
@@ -625,6 +626,7 @@
for line in lines[2:]:
if line == '':
break
+ # TODO: Switch to StaticTuple here.
nodes.append(tuple(map(intern, line.split('\0'))))
return nodes
=== modified file 'bzrlib/builtins.py'
--- a/bzrlib/builtins.py 2009-10-08 16:32:43 +0000
+++ b/bzrlib/builtins.py 2009-10-12 22:09:19 +0000
@@ -431,7 +431,10 @@
for node in bt.iter_all_entries():
# Node is made up of:
# (index, key, value, [references])
- self.outf.write('%s\n' % (node[1:],))
+ refs_as_tuples = tuple([tuple([tuple(ref) for ref in ref_list])
+ for ref_list in node[3]])
+ as_tuple = (tuple(node[1]), node[2], refs_as_tuples)
+ self.outf.write('%s\n' % (as_tuple,))
class cmd_remove_tree(Command):
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py 2009-10-13 05:20:50 +0000
+++ b/bzrlib/index.py 2009-10-14 13:54:09 +0000
@@ -40,6 +40,7 @@
debug,
errors,
)
+from bzrlib.static_tuple import StaticTuple
_HEADER_READV = (0, 200)
_OPTION_KEY_ELEMENTS = "key_elements="
@@ -102,7 +103,7 @@
def _check_key(self, key):
"""Raise BadIndexKey if key is not a valid key for this index."""
- if type(key) != tuple:
+ if type(key) not in (tuple, StaticTuple):
raise errors.BadIndexKey(key)
if self._key_length != len(key):
raise errors.BadIndexKey(key)
@@ -202,7 +203,9 @@
if reference not in self._nodes:
self._check_key(reference)
absent_references.append(reference)
+ # TODO: StaticTuple
node_refs.append(tuple(reference_list))
+ # TODO: StaticTuple
return tuple(node_refs), absent_references
def add_node(self, key, value, references=()):
=== modified file 'bzrlib/repository.py'
--- a/bzrlib/repository.py 2009-10-08 22:53:13 +0000
+++ b/bzrlib/repository.py 2009-10-12 22:04:23 +0000
@@ -4319,6 +4319,13 @@
):
if versioned_file is None:
continue
+ # TODO: key is often going to be a StaticTuple object
+ # I don't believe we can define a method by which
+ # (prefix,) + StaticTuple will work, though we could
+ # define a StaticTuple.sq_concat that would allow you to
+ # pass in either a tuple or a StaticTuple as the second
+ # object, so instead we could have:
+ # StaticTuple(prefix) + key here...
missing_keys.update((prefix,) + key for key in
versioned_file.get_missing_compression_parent_keys())
except NotImplementedError:
=== added file 'bzrlib/static_tuple.py'
--- a/bzrlib/static_tuple.py 1970-01-01 00:00:00 +0000
+++ b/bzrlib/static_tuple.py 2009-10-12 20:02:27 +0000
@@ -0,0 +1,25 @@
+# Copyright (C) 2009 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
+
+"""Interface thunk for a StaticTuple implementation."""
+
+try:
+ from bzrlib._static_tuple_c import StaticTuple
+except ImportError, e:
+ from bzrlib import osutils
+ osutils.failed_to_load_extension(e)
+ from bzrlib._static_tuple_py import StaticTuple
+
=== modified file 'bzrlib/tests/test__static_tuple.py'
--- a/bzrlib/tests/test__static_tuple.py 2009-10-12 18:10:24 +0000
+++ b/bzrlib/tests/test__static_tuple.py 2009-10-14 14:03:56 +0000
@@ -23,6 +23,7 @@
_static_tuple_py,
errors,
osutils,
+ static_tuple,
tests,
)
@@ -278,6 +279,16 @@
self.assertCompareEqual(k3, (k1, ('foo', 'bar')))
self.assertCompareEqual((k1, ('foo', 'bar')), k3)
+ def test_compare_mixed_depths(self):
+ stuple = self.module.StaticTuple
+ k1 = stuple(stuple('a',), stuple('b',))
+ k2 = stuple(stuple(stuple('c',), stuple('d',)),
+ stuple('b',))
+ # This requires comparing a StaticTuple to a 'string', and then
+ # interpreting that value in the next higher StaticTuple. This used to
+ # generate a PyErr_BadIternalCall. We now fall back to *something*.
+ self.assertCompareNoRelation(k1, k2)
+
def test_hash(self):
k = self.module.StaticTuple('foo')
self.assertEqual(hash(k), hash(('foo',)))
@@ -416,3 +427,13 @@
if self.module is _static_tuple_py:
return
self.assertIsNot(None, self.module._C_API)
+
+ def test_static_tuple_thunk(self):
+ # Make sure the right implementation is available from
+ # bzrlib.static_tuple.StaticTuple.
+ if self.module is _static_tuple_py:
+ if CompiledStaticTuple.available():
+ # We will be using the C version
+ return
+ self.assertIs(static_tuple.StaticTuple,
+ self.module.StaticTuple)
=== modified file 'bzrlib/util/_bencode_py.py'
--- a/bzrlib/util/_bencode_py.py 2009-06-10 03:56:49 +0000
+++ b/bzrlib/util/_bencode_py.py 2009-10-13 14:36:50 +0000
@@ -154,6 +154,13 @@
encode_int(int(x), r)
encode_func[BooleanType] = encode_bool
+try:
+ from bzrlib._static_tuple_c import StaticTuple
+except ImportError:
+ pass
+else:
+ encode_func[StaticTuple] = encode_list
+
def bencode(x):
r = []
=== modified file 'setup.py'
--- a/setup.py 2009-10-12 17:03:40 +0000
+++ b/setup.py 2009-10-12 20:12:32 +0000
@@ -270,7 +270,6 @@
add_pyrex_extension('bzrlib._annotator_pyx')
add_pyrex_extension('bzrlib._bencode_pyx')
-add_pyrex_extension('bzrlib._btree_serializer_pyx')
add_pyrex_extension('bzrlib._chunks_to_lines_pyx')
add_pyrex_extension('bzrlib._groupcompress_pyx',
extra_source=['bzrlib/diff-delta.c'])
@@ -303,6 +302,8 @@
add_pyrex_extension('bzrlib._simple_set_pyx')
ext_modules.append(Extension('bzrlib._static_tuple_c',
['bzrlib/_static_tuple_c.c']))
+add_pyrex_extension('bzrlib._btree_serializer_pyx')
+
if unavailable_files:
print 'C extension(s) not found:'
More information about the bazaar-commits
mailing list