Mercurial > hg
changeset 14065:8f7132fa5e59
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.
| author | Dan Villiom Podlaski Christiansen <danchr@gmail.com> |
|---|---|
| date | Sat, 30 Apr 2011 15:05:34 +0200 |
| parents | e4bfb9c337f3 |
| children | 14fac6c0536a |
| files | mercurial/pure/mpatch.py |
| diffstat | 1 files changed, 4 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- 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)