Re: [Gnu-arch-users] Re: [BUG] FEATURE PLANS: "perfect" summary deltas

[Aaron Bentley]

Tom Lord wrote:

> The builder changes should be utterly trivial.  They amount to this:
>
>     new_build (rev)
>     {
>        if (success == old_build (rev:summary))
>          {
>            remove patch log for summary branch
>            return success
>          }
>        else
>          {
>            return old_build (rev);
>          }
>     }

From what I can tell, this assumes that if building rev:summary would
succeed, then you should do it.  Yes, it's optimal in some important
cases, but it will also perform worse than old_build in other important
cases, like the case where the revision ordinal of rev:summary is 7, and
 you have the immediate ancestor of rev in a revlib.

Also, it doesn't support building summary deltas unless the revision you 
want has been summarized.  If you're doing "tla get VERSION", it's quite 
possible that it hasn't yet been summarized.

Here's how the backbuilder presently works:

1. It maps out a path from the target revision backwards, following
ancestry, to a local revision or archive revision

2. It maps out a path from the closest library revision which is a 
potential same-version descendant to the target revision.  (encountering 
a continuation terminates this)

3. It compares the build paths, and picks the best one.  (Its
current criterion is number of revisions)

4. It builds the revision using the path it selected.

So you can imagine that I'd rather add the summary deltas as yet another
possible path that might or might not be used.

> plus modifying old_build to call new_build whenever it 
> crosses a version boundary.

old_build crosses a version boundary every time it generates a summary
revision, since they're all continuations.  Summary revisions will never
be in revlibs, since they're never target revisions.  So it would seem
that it will always start from base-0.  Have I got something wrong there?

> That's one reason why the "mathematical neatness" of summary deltas is
> cool: because it interacts with the existing build algorithm in a
> useful way.

I don't see anything here that could implement what you described to Greek0:

> For example, to get from  5 to 14, instead of
> applying 9 changesets (6, 7, 8, ...), you could apply
> summary delta changeset and build:
>
>
>         5 --> 3              (reverse apply the changeset of summary-delta
>                          5 to get the spine revision that 5 is a tag
>                          of)
>
>
>         3 --> 0              (reverse apply summary-delta 3)
>
>         0 --> 7              (forward apply summary-delta 7)
>
>         7 --> 14     (forward apply summary-delta 14)

Is this something you expect to work right away?  If so, how does it happen?

(Also, note that building backwards using a summary delta has the
interesting property that you must *add* a patchlog so that
reverse-applying the changeset works.  Good thing the patchlogs can be 
retrived separately.)

> (Another reason is that it's deterministic and
> predictable, and hence a reliable tool.)

Here's an alternative deterministic approach:
Take both the build paths (from step 4. above).  For each of them:

1. find all the deltas whose START-REVISION and END-REVSISION are in the 
path.
2. select the delta with the largest revision ordinal.
3. delete all revisions in the path from START-REVISION to END-REVISION, 
and replace with the delta
4. repeat until no deltas have both START-REVISION and END-REVISION in 
the path

This will always improve performance.  It deterministic and simple, and 
scales O(n) with the number of deltas.  It fits nicely with the 
backbuilder's design.

I haven't sorted out the best way to use external deltas, but I think a 
similar approach could apply (probably as a first step).  The tricky bit 
is determining when to use an external delta whose START-REVISION isn't 
in a revlib.

Aaron