Re: [Gnu-arch-users] Re: situations where cached revisions are not so good

[Robert Collins]

On Sun, 2003-09-28 at 11:27, Jason McCarty wrote:

> It would not cause any problems, but if they aren't transitive, then my
> algorithm's performance may be less efficient than a human's analysis of
> which deltas to apply. So if you have 36 and want 134, the summaries
> {(12, 75), (75, 130), (12, 130)} will patch with 36..75->130..134, but
> given the summaries {(12, 75), (75, 130), (39, 129)}, my algorithm will
> do 36..75->130..134 when it should do 36..39->129..134. This seems to
> indicate to me that a n-ary tree of summaries (possibly chopping off the
> top few nodes) would yield the best time/space tradeoff.

Note that your algorithm is a cut down (read broken :])
shortest-path-first finder. If you consider the problem a SPF case
(which it is) then non transitive summaries would be no issue: the
algorithm would continue probing the cheapest path out until a match is
found or the cost exceeds that of another candidate. Neatly, this allows
adding reverse patching in the future. Also, if the cost includes patch
transmission time, this handles choosing between cached revisions,
individual changesets and summaries.

Oh, and lastly: SPF is a well known, many times coded, generic solution,
as opposed to a custom roll our own solution to the problem. All we need
is a traversal cost algorithm for a link, and that is needed regardless.

Rob
-- 
GPG key available at: <http://members.aardvark.net.au/lifeless/keys.txt>.

signature.asc
Description: This is a digitally signed message part