Rev 4445: (debug) Adding a FIFOCache has a huge hit rate 528k requests, 5k unique items. in http://bazaar.launchpad.net/~jameinel/bzr/1.17-faster-branch
John Arbash Meinel
john at arbash-meinel.com
Mon Jun 15 22:08:26 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/1.17-faster-branch
------------------------------------------------------------
revno: 4445
revision-id: john at arbash-meinel.com-20090615210807-05sotnxmf9fe11fp
parent: john at arbash-meinel.com-20090615202124-o9wf7lioc6kantzj
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.17-faster-branch
timestamp: Mon 2009-06-15 16:08:07 -0500
message:
(debug) Adding a FIFOCache has a huge hit rate 528k requests, 5k unique items.
is a 99.1% hit rate.
However, the extra dict lookup in the inner loop does cost us the 300ms that we saved
with the new bytes_to_info implementation....
-------------- next part --------------
=== modified file 'bzrlib/_chk_map_pyx.pyx'
--- a/bzrlib/_chk_map_pyx.pyx 2009-04-09 20:23:07 +0000
+++ b/bzrlib/_chk_map_pyx.pyx 2009-06-15 21:08:07 +0000
@@ -29,9 +29,8 @@
cdef extern from "Python.h":
ctypedef int Py_ssize_t # Required for older pyrex versions
- struct _PyObject:
+ ctypedef struct PyObject:
pass
- ctypedef _PyObject PyObject
int PyTuple_CheckExact(object p)
Py_ssize_t PyTuple_GET_SIZE(object t)
int PyString_CheckExact(object)
@@ -39,6 +38,7 @@
Py_ssize_t PyString_GET_SIZE(object)
int PyDict_SetItem(object d, object k, object v) except -1
+ PyObject *PyDict_GetItem(object d, object k)
object PyTuple_New(Py_ssize_t count)
void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)
@@ -52,6 +52,10 @@
char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
object PyString_FromStringAndSize(char*, Py_ssize_t)
+ # Consider using the _PyObject_GC_UNTRACK macro...
+ void PyObject_GC_UnTrack(object)
+ void _PyObject_GC_UNTRACK(object)
+
cdef extern from "zlib.h":
ctypedef unsigned long uLong
ctypedef unsigned int uInt
@@ -60,10 +64,38 @@
uLong crc32(uLong crc, Bytef *buf, uInt len)
+from bzrlib import fifo_cache
+
_LeafNode = None
_InternalNode = None
_unknown = None
+cdef object _object_cache
+_object_cache = fifo_cache.FIFOCache(10*1024)
+_counter = [0, 0, 0]
+
+cdef object _cache_object(obj):
+ """Add this object to the _object_cache.
+
+ This is roughly equivalent to intern() except we allow any type that can
+ fit in a dictionary. We use a FIFOCache to limit how many objects we will
+ track.
+ """
+ cdef PyObject *temp
+ # _counter[0] += 1
+ # FIFOCache inherits from dict, so a 'hit' only costs a PyDict_GetItem
+ # lookup. A Miss requires adding the key, and that has more overhead
+ temp = PyDict_GetItem(_object_cache, obj)
+ if temp == NULL:
+ # This item is not present, cache it.
+ # Use the regular [] syntax, because that triggers the FIFO cleaning
+ _object_cache[obj] = obj
+ # _counter[1] += 1
+ return obj
+ # _counter[2] += 1
+ return <object>temp
+
+
# We shouldn't just copy this from _dirstate_helpers_c
cdef void* _my_memrchr(void *s, int c, size_t n):
# memrchr seems to be a GNU extension, so we have to implement it ourselves
@@ -235,8 +267,11 @@
next_null = <char *>memchr(prefix, c'\0', prefix_length)
while next_null != NULL:
num_prefix_bits = num_prefix_bits + 1
- prefix_bits.append(
- PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
+ prefix_bit = PyString_FromStringAndSize(prefix_tail,
+ next_null - prefix_tail)
+ prefix_bit = _cache_object(prefix_bit)
+ prefix_bits.append(prefix_bit)
+
prefix_tail = next_null + 1
next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
prefix_tail_len = next_line - prefix_tail
@@ -246,6 +281,9 @@
items_length = end - cur
items = {}
+ # We might consider:
+ # PyObject_GC_UnTrack(items)
+ # We know what will be in the dict, and it won't be cyclical references.
while cur < end:
line_start = cur
next_line = <char *>memchr(cur, c'\n', end - cur)
@@ -266,12 +304,14 @@
raise ValueError('missing trailing newline')
cur = next_line + 1
entry_bits = PyTuple_New(width)
+ # PyObject_GC_UnTrack(entry_bits)
for i from 0 <= i < num_prefix_bits:
entry = prefix_bits[i]
# SET_ITEM 'steals' a reference
Py_INCREF(entry)
PyTuple_SET_ITEM(entry_bits, i, entry)
value = PyString_FromStringAndSize(value_start, next_line - value_start)
+ value = _cache_object(value)
# The next entry bit needs the 'tail' from the prefix, and first part
# of the line
entry_start = line_start
@@ -286,6 +326,7 @@
memcpy(c_entry, prefix_tail, prefix_tail_len)
if next_null - line_start > 0:
memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
+ entry = _cache_object(entry)
Py_INCREF(entry)
i = num_prefix_bits
PyTuple_SET_ITEM(entry_bits, i, entry)
@@ -300,12 +341,14 @@
raise ValueError('bad no null')
entry = PyString_FromStringAndSize(entry_start,
next_null - entry_start)
+ entry = _cache_object(entry)
Py_INCREF(entry)
PyTuple_SET_ITEM(entry_bits, i, entry)
- if len(entry_bits) != width:
+ if i + 1 != width:
raise AssertionError(
'Incorrect number of elements (%d vs %d)'
% (len(entry_bits)+1, width + 1))
+ entry_bits = _cache_object(entry_bits)
PyDict_SetItem(items, entry_bits, value)
if len(items) != length:
raise ValueError("item count (%d) mismatch for key %s,"
@@ -335,6 +378,7 @@
cdef Py_ssize_t c_bytes_len, prefix_length
cdef int maximum_size, width, length, i, prefix_tail_len
cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
+ cdef PyObject *temp
if _InternalNode is None:
from bzrlib import chk_map
@@ -355,6 +399,9 @@
raise ValueError("bytes does not end in a newline")
items = {}
+ # We might consider:
+ # PyObject_GC_UnTrack(items)
+ # We know what will be in the dict, and it won't be cyclical references.
cur = c_bytes + 9
end = c_bytes + c_bytes_len
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
@@ -382,9 +429,17 @@
if prefix_length:
memcpy(c_item_prefix, prefix, prefix_length)
memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
+ item_prefix = _cache_object(item_prefix)
+
flat_key = PyString_FromStringAndSize(next_null + 1,
next_line - next_null - 1)
- PyDict_SetItem(items, item_prefix, (flat_key,))
+ # Cache both the tuple and the string forms
+ flat_key = _cache_object(flat_key)
+ flat_key = (flat_key,)
+ # We know this tuple will never be in a cyclical reference
+ # PyObject_GC_UnTrack(flat_key)
+ flat_key = _cache_object(flat_key)
+ PyDict_SetItem(items, item_prefix, flat_key)
cur = next_line + 1
assert len(items) > 0
result._items = items
=== modified file 'bzrlib/builtins.py'
--- a/bzrlib/builtins.py 2009-06-11 06:54:33 +0000
+++ b/bzrlib/builtins.py 2009-06-15 21:08:07 +0000
@@ -1163,6 +1163,8 @@
note('Branched %d revision(s).' % branch.revno())
finally:
br_from.unlock()
+ from bzrlib._chk_map_pyx import _counter
+ print _counter
class cmd_checkout(Command):
More information about the bazaar-commits
mailing list