[PATCH 2 of 4] revlog: calculate base revisions iteratively

Matt Mackall mpm at selenic.com
Fri May 6 00:58:40 CDT 2011


On Thu, 2011-05-05 at 18:27 +0200, Sune Foldager wrote:
> # HG changeset patch
> # User Sune Foldager <cryo at cyanite.org>
> # Date 1304611530 -7200
> # Node ID e94b057be38fc9362d4ea3f50d22d0470502b617
> # Parent  1b9d53b3eb06728afc9aae4198a53fd0e05e04e9
> revlog: calculate base revisions iteratively
> 
> This is in preparation for generaldelta, where the revlog entry base field
> is reinterpreted as the deltaparent. For that reason we also rename the base
> function to chainbase.

Hmm, I don't think this is ideal.

a) in linear delta, base is just e[3], let's just return that
b) in generaldelta, we need to walk the chain to find base.. but it's
conceptually still base
c) looks like we're walking the chain twice in revision/addrevision

And it turns out that this chain-walking is actually fairly visible for
performance of things like verify (I spent a bit tuning the inner loop
in the parentdelta version). We don't want to do it more than once, and
we don't want to do it at all for old revlogs.

> diff -r 1b9d53b3eb06 -r e94b057be38f mercurial/commands.py
> --- a/mercurial/commands.py	Thu May 05 18:05:24 2011 +0200
> +++ b/mercurial/commands.py	Thu May 05 18:05:30 2011 +0200
> @@ -1565,13 +1565,13 @@
>              except:
>                  pp = [nullid, nullid]
>              ui.write("% 6d % 9d % 7d % 6d % 7d %s %s %s\n" % (
> -                    i, r.start(i), r.length(i), r.base(i), r.linkrev(i),
> +                    i, r.start(i), r.length(i), r.chainbase(i), r.linkrev(i),
>                      short(node), short(pp[0]), short(pp[1])))
>          elif format == 1:
>              pr = r.parentrevs(i)
>              ui.write("% 6d %04x % 8d % 8d % 8d % 6d % 6d % 6d % 6d %s\n" % (
>                      i, r.flags(i), r.start(i), r.length(i), r.rawsize(i),
> -                    r.base(i), r.linkrev(i), pr[0], pr[1], short(node)))
> +                    r.chainbase(i), r.linkrev(i), pr[0], pr[1], short(node)))
>  
>  def debugindexdot(ui, repo, file_):
>      """dump an index DAG as a graphviz dot file"""
> diff -r 1b9d53b3eb06 -r e94b057be38f mercurial/revlog.py
> --- a/mercurial/revlog.py	Thu May 05 18:05:24 2011 +0200
> +++ b/mercurial/revlog.py	Thu May 05 18:05:30 2011 +0200
> @@ -319,8 +319,13 @@
>          return self.start(rev) + self.length(rev)
>      def length(self, rev):
>          return self.index[rev][1]
> -    def base(self, rev):
> -        return self.index[rev][3]
> +    def chainbase(self, rev):
> +        index = self.index
> +        base = index[rev][3]
> +        while base != rev:
> +            rev = base
> +            base = index[rev][3]
> +        return base
>      def flags(self, rev):
>          return self.index[rev][0] & 0xFFFF
>      def rawsize(self, rev):
> @@ -856,7 +861,6 @@
>          # look up what we need to read
>          text = None
>          rev = self.rev(node)
> -        base = self.base(rev)
>  
>          # check rev flags
>          if self.flags(rev) & ~REVIDX_KNOWN_FLAGS:
> @@ -865,10 +869,13 @@
>  
>          # build delta chain
>          chain = []
> +        index = self.index # for performance
>          iterrev = rev
> -        while iterrev != base and iterrev != cachedrev:
> +        e = index[iterrev]
> +        while iterrev != e[3] and iterrev != cachedrev:
>              chain.append(iterrev)
>              iterrev -= 1
> +            e = index[iterrev]
>          chain.reverse()
>          base = iterrev
>  
> @@ -990,7 +997,7 @@
>                  delta = mdiff.textdiff(ptext, t)
>              data = compress(delta)
>              l = len(data[1]) + len(data[0])
> -            base = self.base(rev)
> +            base = self.chainbase(rev)
>              dist = l + offset - self.start(base)
>              return dist, l, data, base
>  
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel


-- 
Mathematics is the supreme nostalgia of our time.




More information about the Mercurial-devel mailing list