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

[Tom Lord]

    > From: Aaron Bentley <address@hidden>

    [builder algorithm tweaks]

Sure, thanks.  Basically, it's a standard forward-and-backward
chaining heuristic search and we have to make up rules that bound
the number of possibilities to consider.

    > I also thought at first that you meant each run through the loop
    > could have more paths-in-progress than the last, since there
    > could be multiple ways of continuting a path (ancestry's a tree,
    > after all).  Is that what you meant?

Roughly.  You can also prune paths so that some iterations will have
fewer paths-in-progress than the last.  For example, if you hit a
summary-delta wall (ordinal 0 intermediate or missing summary-delta
revision) that drops paths from paths-in-progress.  "Perfect"
summaries also bound the branching of the search well.

The combinatorics shouldn't bite you.  All but the fallback-path back
through ancestors should be length-limited so either you find one of
those quickly, or you quickly find a nearby ancestor, or you wind up
down to just one path-in-progress and that's the one tracing ancestry
in the usual way.

    >> Plus I still don't agree that adding a new free-form subdir for
    >> whatever deltas people care to add is really all that useful an idea.

    > Just because the flexability's there doesn't mean it has to be
    > used.

Another nice thing about perfect summary deltas is that it is strictly
layered on the core archive design.  The delta-dir approach, on the
other hand, adds a new weird ad-hoc thing to the archive abstraction.
That seems palpably unecessary and, anyway, a non-layered
archive-format change raises all kinds of questions about how it looks
through hypothetical smart servers and things like that.


    > If nothing else, the dirctory-of-deltas approach will require
    > fewer server roundtrips.  Just one directory listing is needed
    > to determine what deltas are available.  Your solution requires

    > - listing categories
    > - reading version variables in a patchlog
    > - verifying that the patchlog isn't out of date
    > - reading 1 patchlog for every backwards patch.

Not quite so, I think.


    > > Setting parameters on my-style of summary deltas can always get you
    > > close to the best you could do with aribtrary deltas

    > Would there be settings to eliminate summaries with revision ordinals of 
    > less than eight?  I thought we'd only be able to eliminate previous 
phases.

It seems that you could sensibly prune non-(2^k-1) current-phase
revisions without getting into too much trouble.


    > Well, this is an evolution of the ideas we discussed a while
    > back about smart servers.  The DELTA command proposed back then
    > would provide one or more changesets which could be applied to
    > produce the revision.

    > The problem is, that assumes the server knows the best way for a 
    > particular client to produce a revision.  I think the right way is to 
    > break it up into a LIST-DELTAS command, that lists deltas that the 
    > server is willing provide.  (This may need to contain a token, so a 
    > smart server doesn't wind up overpromising and underdelivering.)  Then, 
    > the DELTA command can be used to retrieve the individual changesets.

    > You can see how easy that would be to implement with a directory
    > of deltas.

That wouldn't work well.   With LIST-DELTAS, you really will get into
path combinatorics problems on servers that can provide many of them.


    > > Arbitrary deltas are
    > > flexability that nobody really needs.

    > Actually, deltas seem like cacherevs to me.  Just as useful as an 
    > optimization technique, and perhaps even more volatile.  Personally, I'd 
    > like to decide when to summarize based on the aggregate size of my 
    > un-summarized revisions.  Or I might always provide a 
    > delta-from-cacherev-to-latest, which would be deleted when the next 
    > revision was committed.

The latter idea seems to me to be a crude approximation of a
latest-phase-only summary branch --- far less effective but, usually,
only a tiny bit better space-wise.

-t