Rev 4763: Remove 2 more mallocs per line by using a fixed-width StaticTuple for reflists. in http://bazaar.launchpad.net/~jameinel/bzr/2.1-static-tuple

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.1-static-tuple

------------------------------------------------------------
revno: 4763
revision-id: john at arbash-meinel.com-20091007211747-tlgi6myzn54wdyxa
parent: john at arbash-meinel.com-20091007193509-ncpv7t7amrrnk5ti
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.1-static-tuple
timestamp: Wed 2009-10-07 16:17:47 -0500
message:
  Remove 2 more mallocs per line by using a fixed-width StaticTuple for reflists.
  
  Note that 'ref_list' is arbitrary width (think parent pointers), so we can't pre-allocate that.
  I suppose we *could* count the occurences of the separator in the memory buffer, though.
  That may be more efficient...
-------------- next part --------------
=== modified file 'bzrlib/_btree_serializer_pyx.pyx'
--- a/bzrlib/_btree_serializer_pyx.pyx	2009-10-07 15:57:25 +0000
+++ b/bzrlib/_btree_serializer_pyx.pyx	2009-10-07 21:17:47 +0000
@@ -236,7 +236,7 @@
             # 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 = []
@@ -268,12 +268,13 @@
                     if temp_ptr == NULL:
                         # key runs to the end
                         temp_ptr = ref_ptr
+                                        
                     PyList_Append(ref_list, self.extract_key(temp_ptr))
                 ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
-                PyList_Append(ref_lists, 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 = StaticTuple(*ref_lists)
             node_value = StaticTuple(value, ref_lists)
         else:
             if last != self._start:

=== modified file 'bzrlib/_simple_set_pyx.pyx'
--- a/bzrlib/_simple_set_pyx.pyx	2009-10-07 19:31:39 +0000
+++ b/bzrlib/_simple_set_pyx.pyx	2009-10-07 21:17:47 +0000
@@ -20,6 +20,8 @@
     ctypedef unsigned long size_t
     ctypedef long (*hashfunc)(PyObject*)
     ctypedef PyObject *(*richcmpfunc)(PyObject *, PyObject *, int)
+    ctypedef int (*visitproc)(PyObject *, void *)
+    ctypedef int (*traverseproc)(PyObject *, visitproc, void *)
     int Py_EQ
     PyObject *Py_True
     PyObject *Py_NotImplemented
@@ -28,6 +30,7 @@
     ctypedef struct PyTypeObject:
         hashfunc tp_hash
         richcmpfunc tp_richcompare
+        traverseproc tp_traverse
 
     PyTypeObject *Py_TYPE(PyObject *)
         
@@ -112,6 +115,10 @@
         def __get__(self):
             return self._mask
 
+    def _memory_size(self):
+        """Return the number of bytes of memory consumed by this class."""
+        return sizeof(self) + (sizeof(PyObject*)*(self._mask + 1))
+
     def __len__(self):
         return self._used
 
@@ -451,8 +458,7 @@
     raise AssertionError('should never get here')
 
 
-cdef api PyObject **_SimpleSet_Lookup(object self,
-                                                object key) except NULL:
+cdef api PyObject **_SimpleSet_Lookup(object self, object key) except NULL:
     """Find the slot where 'key' would fit.
 
     This is the same as a dicts 'lookup' function. This is a private
@@ -515,8 +521,7 @@
 
 
 # TODO: this should probably have direct tests, since it isn't used by __iter__
-cdef api int SimpleSet_Next(object self, Py_ssize_t *pos,
-                                      PyObject **key):
+cdef api int SimpleSet_Next(object self, Py_ssize_t *pos, PyObject **key):
     """Walk over items in a SimpleSet.
 
     :param pos: should be initialized to 0 by the caller, and will be updated
@@ -542,3 +547,26 @@
         key[0] = table[i]
     return 1
 
+
+cdef int SimpleSet_traverse(SimpleSet self, visitproc visit, void *arg):
+    """This is an implementation of 'tp_traverse' that hits the whole table.
+
+    Cython/Pyrex don't seem to let you define a tp_traverse, and they only
+    define one for you if you have an 'object' attribute. Since they don't
+    support C arrays of objects, we access the PyObject * directly.
+    """
+    cdef Py_ssize_t pos
+    cdef PyObject *next_key
+    cdef int ret
+
+    pos = 0
+    while SimpleSet_Next(self, &pos, &next_key):
+        ret = visit(next_key, arg)
+        if ret:
+            return ret
+
+    return 0;
+
+# It is a little bit ugly to do this, but it works, and means that Meliae can
+# dump the total memory consumed by all child objects.
+(<PyTypeObject *>SimpleSet).tp_traverse = <traverseproc>SimpleSet_traverse