pure mpatch: avoid using list.insert(0, ...)
authorDan Villiom Podlaski Christiansen <danchr@gmail.com>
Sat, 30 Apr 2011 15:05:34 +0200
changeset 14065 8f7132fa5e59
parent 14064 e4bfb9c337f3
child 14066 14fac6c0536a
pure mpatch: avoid using list.insert(0, ...) In Python lists are implemented as arrays with overallocation. As a result, list.insert(0, ...) is O(n), whereas list.append() has an amortised running time of O(1). Reversing the internal representation of the list should cause a slight speedup for pure Python builds.
mercurial/pure/mpatch.py
--- a/mercurial/pure/mpatch.py	Sat Apr 30 13:59:14 2011 +0200
+++ b/mercurial/pure/mpatch.py	Sat Apr 30 15:05:34 2011 +0200
@@ -56,9 +56,9 @@
 
     def pull(dst, src, l): # pull l bytes from src
         while l:
-            f = src.pop(0)
+            f = src.pop()
             if f[0] > l: # do we need to split?
-                src.insert(0, (f[0] - l, f[1] + l))
+                src.append((f[0] - l, f[1] + l))
                 dst.append((l, f[1]))
                 return
             dst.append(f)
@@ -66,7 +66,7 @@
 
     def collect(buf, list):
         start = buf
-        for l, p in list:
+        for l, p in reversed(list):
             move(buf, p, l)
             buf += l
         return (buf - start, start)
@@ -88,7 +88,7 @@
             new.append((l, pos + 12))        # what got added
             pos += l + 12
             last = p2
-        frags = new + frags                    # what was left at the end
+        frags.extend(reversed(new))                    # what was left at the end
 
     t = collect(b2, frags)