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

[Matthew Dempsky]

Tom Lord <address@hidden> writes:

> [ summary delta description ]

Out of curiousity, I decided to test out how well this idea works with
a copy of Tom's tla--devo--1.2 tree.

The test was conducted by adding cacherevs to every revision in
tla--devo--1.2 along with conducting a delta between each basis-spine
and spine-leaf pair and then tar'ing the result.

The cacherevs ranged in size from about 1.4 to 1.6 MB, however, none
of the summary patches exceeded 200 kB (well under 1/4th of even the
smallest cacherevs).  In fact, only 28 of the 115 patches weighed in
over 100 kB.  Therefor, the entire version fits in a single phase,
giving a very nice alternative to cacherevs if even a single revision
is available.

As to the builder algorithm, why not simply use Dijkstra's shortest
path algorithm using patch size as edge weight and an edge anywhere a
patch or patch summary exists?  (Also a starting node representing an
empty directory, so zero-weight edges between it and revlib'd or
pristine revisions and cacherev-weight edges between it and
cacherevs'd revisions.)  It would be general enough to still meet
Aaron's hypothetical smart server, while simple enough to fulfill
Tom's no-more-complicated-than-necessary goal.

This actually seems pretty similar to the algorithms described, but it
seems to differ that a) I actually called it Dijkstra's shortest path,
and b) I'm not sure if the other described algorithms would allow
mixing regular patches and summary patches.

-jivera