Rev 2262: Collapsing if _links grows to long has very good benefits for performance. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

------------------------------------------------------------
revno: 2262
revision-id: john at arbash-meinel.com-20070130224637-f3c7gx2ya50r1rej
parent: john at arbash-meinel.com-20070130210407-ny0eh3g3fpf2bwnm
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 16:46:37 -0600
message:
  Collapsing if _links grows to long has very good benefits for performance.
modified:
  bzrlib/hybrid_linked_list.py   hybrid_linked_list.p-20070130001028-zlexwz74tzo56o2t-1
-------------- next part --------------
=== modified file 'bzrlib/hybrid_linked_list.py'
--- a/bzrlib/hybrid_linked_list.py	2007-01-30 21:04:07 +0000
+++ b/bzrlib/hybrid_linked_list.py	2007-01-30 22:46:37 +0000
@@ -40,8 +40,32 @@
         be stored with _ranges, but it makes it easier to update links if they
         are in a separate dict. (less tuple churn)
     :ivar _length: The current length of the output content
+    :cvar _max_links: When copying, flatten the text if we exceed _max_links
     """
 
+    # This was determined empirically on a knit with 55,000 lines of content,
+    # and 458 line-deltas. A number of 100 caused flatten to occur 28 times, at
+    # approximately 300ms each. Without any flattening max_links grows to 4000,
+    # and _find_nodes_for_pos starts to become a bottleneck.
+    # Under --lsprof, 1000 looks the best (it flattens 3 times). However real
+    # testing shows that 500 is better (it flattens 7 times). This is because
+    # --lsprof penalizes __iter__ more than it penalizes _find_nodes_for_pos
+
+    # TODO: jam 20070130 We could make this dynamic based on the length of the
+    #       text versus the length of the delta chain.
+    #       For example, in the current tradeoff, we have 55,000 lines, and we
+    #       want to collapse if we have more than 500 links. This works out to
+    #       be very close to 1/100 (if links grows larger that 1/100th of the
+    #       total length, we want to collapse).
+    #       However, I'm not convinced that _find_nodes_for_pos is going to
+    #       scale based on relative amount, versus scaling based on actual
+    #       number of nodes. But theoretically we are trading off flatten()
+    #       calls for _find_nodes_for_pos performance.
+    #
+    # TODO: jam 20070130 This seems like a pretty good class to
+    #       optimize as a C or pyrex extension.
+    _max_links = 500
+
     __slots__ = ['_head', '_ranges', '_links', '_length']
 
     def __init__(self, starting=[]):
@@ -71,11 +95,13 @@
         """Iterate over the final content."""
         cur_range_id = self._head
 
+        _ranges = self._ranges
+        _links = self._links
         while cur_range_id is not None:
-            start, end, content = self._ranges[cur_range_id]
+            start, end, content = _ranges[cur_range_id]
             for pos in xrange(start, end):
                 yield content[pos]
-            cur_range_id = self._links[cur_range_id]
+            cur_range_id = _links[cur_range_id]
 
     def __len__(self):
         # Profiling shows __len__ to be adding a lot of overhead, so we use a
@@ -164,8 +190,9 @@
         """repr(HybridLinkedList) gives more information about internals."""
         flattened = []
         cur = self._head
+        _ranges = self._ranges
         while cur is not None:
-            flattened.append('%s:%s' % (cur, self._ranges[cur]))
+            flattened.append('%s:%s' % (cur, _ranges[cur]))
             cur = self._links[cur]
         return 'HybridLinkedList(' + ', '.join(flattened) + ')'
 
@@ -193,6 +220,11 @@
         # 4716 3.9053 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
         # and switching to lists instead of dicts
         # 4716 3.4728 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
+        # flattening if we exceed 1000 links yields:
+        #    3 1.0809 bzrlib.hybrid_linked_list:179(flatten)
+        # 4719 1.4945 bzrlib.hybrid_linked_list:183(_find_nodes_for_pos)
+        # So while it takes 300+ms to flatten, we avoid bad O(N) behavior for
+        # number of links.
         _ranges = self._ranges
         _links = self._links
 
@@ -385,6 +417,12 @@
         copies of the contents. However, since contents are never modified,
         that should be fine.
         """
+        # If we get too many links, just collapse them.
+        # Without flattening on the mozilla tree, with 458 deltas, we end up
+        # with 4000 links. Which starts being a bottleneck in
+        # _find_nodes_for_pos
+        if len(self._links) > self._max_links:
+            self.flatten()
         new_hll = HybridLinkedList()
         new_hll._head = self._head
         new_hll._ranges = self._ranges[:]