[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Robert Collins
Subject: Re: [Gnu-arch-users] Re: situations where cached revisions are not so good
Date: Mon, 29 Sep 2003 07:36:25 +1000

On Mon, 2003-09-29 at 05:50, Jason McCarty wrote:

> Furthermore, you're no longer looking for a single path. You may have
> multiple pristines and revlib entries (from multiple versions, due to
> continuations) on hand, and you want to find the shortest path to
> _any_one_ of them, which just multiplies the amount of traversal you
> need to do. You almost need to build a spanning tree to find the optimal
> solution.

Well. That is the worst case behaviour of SPF, yes. (A minimal spanning
tree in fact). in terms of finding the shortest path to any element of a
set: this doesn't change the SPF algorithm's loop or search behaviour.
It simply changes the test for 'finished'. Rather than 'a path to X', it
becomes 'a path to any of [set]'.

> I believe that a near-optimal layout of summaries for SPF will also be
> near-optimal for my algorithm, with the difference that mine won't have
> to perform nearly so much remote traversal, and has no need for an index
> to achive good results.

I think that yours will need to perform the -same- remote traversal in
that near-optimal case.

> Reverse patching wouldn't really complicate SPF any, but it would also
> only give a 2x speedup on average, so is it worthwhile vs. my simpler
> solution?

It's likely not even worth it for SPF. but: it's optional.

> > 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.
> A generic solution which IMO is unsuited to this problem, at least
> until the cost metric is very cheap to calculate, which it currently
> isn't.

Hmm. Well the thing I have about your algorithm is that it depends on
very careful placement of summaries and full revs into the archive.

GPG key available at: <>.

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]