Add mdiff.patches to speed up applying thousands of patches to the manifest

mercurial/mdiff.py

@@ -1,75 +1,144 b''
 #!/usr/bin/python
-import difflib, struct
-from cStringIO import StringIO
+import difflib, struct, mmap
+
+devzero = file("/dev/zero")
 
 def unidiff(a, ad, b, bd, fn):
     if not a and not b: return ""
     a = a.splitlines(1)
     b = b.splitlines(1)
     l = list(difflib.unified_diff(a, b, "a/" + fn, "b/" + fn, ad, bd))
     return "".join(l)
 
 def textdiff(a, b):
     return diff(a.splitlines(1), b.splitlines(1))
 
 def sortdiff(a, b):
     la = lb = 0
 
     while 1:
         if la >= len(a) or lb >= len(b): break
         if b[lb] < a[la]:
             si = lb
             while lb < len(b) and b[lb] < a[la] : lb += 1
             yield "insert", la, la, si, lb
         elif a[la] < b[lb]:
             si = la
             while la < len(a) and a[la] < b[lb]: la += 1
             yield "delete", si, la, lb, lb
         else:
             la += 1
             lb += 1
 
     if lb < len(b):
         yield "insert", la, la, lb, len(b)
 
     if la < len(a):
         yield "delete", la, len(a), lb, lb
 
 def diff(a, b, sorted=0):
     bin = []
     p = [0]
     for i in a: p.append(p[-1] + len(i))
 
     if sorted:
         d = sortdiff(a, b)
     else:
         d = difflib.SequenceMatcher(None, a, b).get_opcodes()
 
     for o, m, n, s, t in d:
         if o == 'equal': continue
         s = "".join(b[s:t])
         bin.append(struct.pack(">lll", p[m], p[n], len(s)) + s)
 
     return "".join(bin)
 
+# This attempts to apply a series of patches in time proportional to
+# the total size of the patches, rather than patches * len(text). This
+# means rather than shuffling strings around, we shuffle around
+# pointers to fragments with fragment lists.
+#
+# When the fragment lists get too long, we collapse them. To do this
+# efficiently, we do all our operations inside a buffer created by
+# mmap and simply use memmove. This avoids creating a bunch of large
+# temporary string buffers.
+
+def patches(a, bins):
+    if not bins: return a
+
+    plens = [len(x) for x in bins]
+    pl = sum(plens)
+    bl = len(a) + pl
+    tl = bl + bl + pl # enough for the patches and two working texts
+    b1, b2 = 0, bl
+    m = mmap.mmap(devzero.fileno(), tl, mmap.MAP_PRIVATE)
+
+    # load our original text
+    m.write(a)
+    frags = [(len(a), b1)]
+
+    # copy all the patches into our segment so we can memmove from them
+    pos = b2 + bl
+    m.seek(pos)
+    for p in bins: m.write(p)
+
+    def pull(dst, src, l): # pull l bytes from src
+        while l:
+            f = src.pop(0)
+            if f[0] > l: # do we need to split?
+                src.insert(0, (f[0] - l, f[1] + l))
+                dst.append((l, f[1]))
+                return
+            dst.append(f)
+            l -= f[0]
+
+    def collect(buf, list):
+        start = buf
+        for l, p in list:
+            m.move(buf, p, l)
+            buf += l
+        return (buf - start, start)
+
+    for plen in plens:
+        # if our list gets too long, execute it
+        if len(frags) > 128:
+            b2, b1 = b1, b2
+            frags = [collect(b1, frags)]
+
+        new = []
+        end = pos + plen
+        last = 0
+        while pos < end:
+            p1, p2, l = struct.unpack(">lll", m[pos:pos + 12])
+            pull(new, frags, p1 - last) # what didn't change
+            pull([], frags, p2 - p1)    # what got deleted
+            new.append((l, pos + 12))        # what got added
+            pos += l + 12
+            last = p2
+        frags = new + frags                    # what was left at the end
+
+    t = collect(b2, frags)
+
+    return m[t[1]:t[1] + t[0]]
+
 def patch(a, bin):
     last = pos = 0
     r = []
 
     c = 0
     while pos < len(bin):
         p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12])
         pos += 12
         r.append(a[last:p1])
         r.append(bin[pos:pos + l])
         pos += l
         last = p2
         c += 1
     r.append(a[last:])
 
     return "".join(r)
 
 
 
 
 

mercurial/revlog.py

@@ -1,412 +1,409 b''
 # revlog.py - storage back-end for mercurial
 #
 # This provides efficient delta storage with O(1) retrieve and append
 # and O(changes) merge between branches
 #
 # Copyright 2005 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms
 # of the GNU General Public License, incorporated herein by reference.
 
 import zlib, struct, sha, os, tempfile, binascii
 from mercurial import mdiff
 
 def hex(node): return binascii.hexlify(node)
 def bin(node): return binascii.unhexlify(node)
 
 def compress(text):
     return zlib.compress(text)
 
 def decompress(bin):
     return zlib.decompress(bin)
 
 def hash(text, p1, p2):
     l = [p1, p2]
     l.sort()
     return sha.sha(l[0] + l[1] + text).digest()
 
 nullid = "\0" * 20
 indexformat = ">4l20s20s20s"
 
 class revlog:
     def __init__(self, opener, indexfile, datafile):
         self.indexfile = indexfile
         self.datafile = datafile
         self.index = []
         self.opener = opener
         self.cache = None
         self.nodemap = {nullid: -1}
         # read the whole index for now, handle on-demand later
         try:
             n = 0
             i = self.opener(self.indexfile).read()
             s = struct.calcsize(indexformat)
-            for f in range(0, len(i), s):
+            for f in xrange(0, len(i), s):
                 # offset, size, base, linkrev, p1, p2, nodeid
                 e = struct.unpack(indexformat, i[f:f + s])
                 self.nodemap[e[6]] = n
                 self.index.append(e)
                 n += 1
         except IOError: pass
 
     def tip(self): return self.node(len(self.index) - 1)
     def count(self): return len(self.index)
     def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]
     def rev(self, node): return self.nodemap[node]
     def linkrev(self, node): return self.index[self.nodemap[node]][3]
     def parents(self, node):
         if node == nullid: return (nullid, nullid)
         return self.index[self.nodemap[node]][4:6]
 
     def start(self, rev): return self.index[rev][0]
     def length(self, rev): return self.index[rev][1]
     def end(self, rev): return self.start(rev) + self.length(rev)
     def base(self, rev): return self.index[rev][2]
 
     def lookup(self, id):
         try:
             rev = int(id)
             return self.node(rev)
         except ValueError:
             c = []
             for n in self.nodemap:
                 if id in hex(n):
                     c.append(n)
             if len(c) > 1: raise KeyError("Ambiguous identifier")
             if len(c) < 1: raise KeyError("No match found")
             return c[0]
                 
         return None
 
     def revisions(self, list):
         # this can be optimized to do spans, etc
         # be stupid for now
         for node in list:
             yield self.revision(node)
 
     def diff(self, a, b):
         return mdiff.textdiff(a, b)
 
-    def patch(self, text, patch):
-        return mdiff.patch(text, patch)
-
     def revision(self, node):
         if node == nullid: return ""
         if self.cache and self.cache[0] == node: return self.cache[2]
 
         text = None
         rev = self.rev(node)
         base = self.base(rev)
         start = self.start(base)
         end = self.end(rev)
 
         if self.cache and self.cache[1] >= base and self.cache[1] < rev:
             base = self.cache[1]
             start = self.start(base + 1)
             text = self.cache[2]
             last = 0
 
         f = self.opener(self.datafile)
         f.seek(start)
         data = f.read(end - start)
 
         if not text:
             last = self.length(base)
             text = decompress(data[:last])
 
+        bins = []
         for r in xrange(base + 1, rev + 1):
             s = self.length(r)
-            b = decompress(data[last:last + s])
-            text = self.patch(text, b)
+            bins.append(decompress(data[last:last + s]))
             last = last + s
 
+        text = mdiff.patches(text, bins)
+
         (p1, p2) = self.parents(node)
         if node != hash(text, p1, p2):
             raise "integrity check failed on %s:%d" % (self.datafile, rev)
 
         self.cache = (node, rev, text)
         return text  
 
     def addrevision(self, text, transaction, link, p1=None, p2=None):
         if text is None: text = ""
         if p1 is None: p1 = self.tip()
         if p2 is None: p2 = nullid
 
         node = hash(text, p1, p2)
 
         n = self.count()
         t = n - 1
 
         if n:
             base = self.base(t)
             start = self.start(base)
             end = self.end(t)
             prev = self.revision(self.tip())
             data = compress(self.diff(prev, text))
             dist = end - start + len(data)
 
         # full versions are inserted when the needed deltas
         # become comparable to the uncompressed text
         if not n or dist > len(text) * 2:
             data = compress(text)
             base = n
         else:
             base = self.base(t)
 
         offset = 0
         if t >= 0:
             offset = self.end(t)
 
         e = (offset, len(data), base, link, p1, p2, node)
         
         self.index.append(e)
         self.nodemap[node] = n
         entry = struct.pack(indexformat, *e)
 
         transaction.add(self.datafile, e[0])
         self.opener(self.datafile, "a").write(data)
         transaction.add(self.indexfile, n * len(entry))
         self.opener(self.indexfile, "a").write(entry)
 
         self.cache = (node, n, text)
         return node
 
     def ancestor(self, a, b):
         def expand(list, map):
             a = []
             while list:
                 n = list.pop(0)
                 map[n] = 1
                 yield n
                 for p in self.parents(n):
                     if p != nullid and p not in map:
                         list.append(p)
             yield nullid
 
         amap = {}
         bmap = {}
         ag = expand([a], amap)
         bg = expand([b], bmap)
         adone = bdone = 0
 
         while not adone or not bdone:
             if not adone:
                 an = ag.next()
                 if an == nullid:
                     adone = 1
                 elif an in bmap:
                     return an
             if not bdone:
                 bn = bg.next()
                 if bn == nullid:
                     bdone = 1
                 elif bn in amap:
                     return bn
 
         return nullid
 
     def mergedag(self, other, transaction, linkseq, accumulate = None):
         """combine the nodes from other's DAG into ours"""
         old = self.tip()
         i = self.count()
         l = []
 
         # merge the other revision log into our DAG
         for r in range(other.count()):
             id = other.node(r)
             if id not in self.nodemap:
                 (xn, yn) = other.parents(id)
                 l.append((id, xn, yn))
                 self.nodemap[id] = i
                 i += 1
 
         # merge node date for new nodes
         r = other.revisions([e[0] for e in l])
         for e in l:
             t = r.next()
             if accumulate: accumulate(t)
             self.addrevision(t, transaction, linkseq.next(), e[1], e[2])
 
         # return the unmerged heads for later resolving
         return (old, self.tip())
 
     def group(self, linkmap):
         # given a list of changeset revs, return a set of deltas and
         # metadata corresponding to nodes the first delta is
         # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
         # have this parent as it has all history before these
         # changesets. parent is parent[0]
 
         revs = []
         needed = {}
 
         # find file nodes/revs that match changeset revs
         for i in xrange(0, self.count()):
             if self.index[i][3] in linkmap:
                 revs.append(i)
                 needed[i] = 1
 
         # if we don't have any revisions touched by these changesets, bail
         if not revs: return struct.pack(">l", 0)
 
         # add the parent of the first rev
         p = self.parents(self.node(revs[0]))[0]
         revs.insert(0, self.rev(p))
 
         # for each delta that isn't contiguous in the log, we need to
         # reconstruct the base, reconstruct the result, and then
         # calculate the delta. We also need to do this where we've
         # stored a full version and not a delta
         for i in xrange(0, len(revs) - 1):
             a, b = revs[i], revs[i + 1]
             if a + 1 != b or self.base(b) == b:
                 for j in xrange(self.base(a), a + 1):
                     needed[j] = 1
                 for j in xrange(self.base(b), b + 1):
                     needed[j] = 1
 
         # calculate spans to retrieve from datafile
         needed = needed.keys()
         needed.sort()
         spans = []
         for n in needed:
             if n < 0: continue
             o = self.start(n)
             l = self.length(n)
             spans.append((o, l, [(n, l)]))
 
         # merge spans
         merge = [spans.pop(0)]
         while spans:
             e = spans.pop(0)
             f = merge[-1]
             if e[0] == f[0] + f[1]:
                 merge[-1] = (f[0], f[1] + e[1], f[2] + e[2])
             else:
                 merge.append(e)
 
         # read spans in, divide up chunks
         chunks = {}
         for span in merge:
             # we reopen the file for each span to make http happy for now
             f = self.opener(self.datafile)
             f.seek(span[0])
             data = f.read(span[1])
 
             # divide up the span
             pos = 0
             for r, l in span[2]:
                 chunks[r] = data[pos: pos + l]
                 pos += l
 
         # helper to reconstruct intermediate versions
         def construct(text, base, rev):
-            for r in range(base + 1, rev + 1):
-                b = decompress(chunks[r])
-                text = self.patch(text, b)
-            return text
+            bins = [decompress(chunks[r]) for r in xrange(base + 1, rev + 1)]
+            return mdiff.patches(text, bins)
 
         # build deltas
         deltas = []
-        for d in range(0, len(revs) - 1):
+        for d in xrange(0, len(revs) - 1):
             a, b = revs[d], revs[d + 1]
             n = self.node(b)
             
             if a + 1 != b or self.base(b) == b:
                 if a >= 0:
                     base = self.base(a)
                     ta = decompress(chunks[self.base(a)])
                     ta = construct(ta, base, a)
                 else:
                     ta = ""
                     
                 base = self.base(b)
                 if a > base:
                     base = a
                     tb = ta
                 else:
                     tb = decompress(chunks[self.base(b)])
                 tb = construct(tb, base, b)
                 d = self.diff(ta, tb)
             else:
                 d = decompress(chunks[b])
 
             p = self.parents(n)
             meta = n + p[0] + p[1] + linkmap[self.linkrev(n)]
             l = struct.pack(">l", len(meta) + len(d) + 4)
             deltas.append(l + meta + d)
 
         l = struct.pack(">l", sum(map(len, deltas)) + 4)
         deltas.insert(0, l)
         return "".join(deltas)
         
     def addgroup(self, data, linkmapper, transaction):
         # given a set of deltas, add them to the revision log. the
         # first delta is against its parent, which should be in our
         # log, the rest are against the previous delta.
 
         if not data: return self.tip()
 
         # retrieve the parent revision of the delta chain
         chain = data[24:44]
 
         # track the base of the current delta log
         r = self.count()
         t = r - 1
         
         base = prev = -1
         start = end = 0
         if r:
             start = self.start(self.base(t))
             end = self.end(t)
             measure = self.length(self.base(t))
             base = self.base(t)
             prev = self.tip()
 
         transaction.add(self.datafile, end)
         transaction.add(self.indexfile, r * struct.calcsize(indexformat))
         dfh = self.opener(self.datafile, "a")
         ifh = self.opener(self.indexfile, "a")
 
         # loop through our set of deltas
         pos = 0
         while pos < len(data):
             l, node, p1, p2, cs = struct.unpack(">l20s20s20s20s",
                                                 data[pos:pos+84])
             link = linkmapper(cs)
             delta = data[pos + 84:pos + l]
             pos += l
 
             # full versions are inserted when the needed deltas become
             # comparable to the uncompressed text or when the previous
             # version is not the one we have a delta against. We use
             # the size of the previous full rev as a proxy for the
             # current size.
 
             if chain == prev:
                 cdelta = compress(delta)
 
             if chain != prev or (end - start + len(cdelta)) > measure * 2:
                 # flush our writes here so we can read it in revision
                 dfh.flush()
                 ifh.flush()
                 text = self.revision(chain)
                 text = self.patch(text, delta)
                 chk = self.addrevision(text, transaction, link, p1, p2)
                 if chk != node:
                     raise "consistency error adding group"
                 measure = len(text)
             else:
                 e = (end, len(cdelta), self.base(t), link, p1, p2, node)
                 self.index.append(e)
                 self.nodemap[node] = r
                 dfh.write(cdelta)
                 ifh.write(struct.pack(indexformat, *e))
 
             t, r, chain, prev = r, r + 1, node, node
             start = self.start(self.base(t))
             end = self.end(t)
 
         dfh.close()
         ifh.close()
         return node