Re: [Monotone-devel] Re: How new-style codeville merge works

[Nathaniel Smith]

On Sat, May 07, 2005 at 11:56:03PM +0100, Bruce Stephens wrote:
> Nathaniel Smith <address@hidden> writes:
> 
> > FYI:
> >   http://thread.gmane.org/gmane.comp.version-control.revctrl/2
> 
> Oh.  If I understand correctly, then it sounds like the basic storage
> that everone's using is suboptimal, and really SCMs should store a big
> database of lines, and files get stored as lists of pointers into that
> database?  (As Stellation did, although Stellation appears to have
> died.  I think they took that idea from a proprietary system, but I
> don't remember which one.)
> 
> Or, if not that, then you'd want to store changes to text files in
> some line-based form, I guess?  Otherwise surely you're recomputing
> diff-like information lots of the time (something cheaper than actual
> diffs, but I feel sure one could store something more useful than
> xdelta; indeed, didn't SCCS use something which would have been useful
> for this)?

Yes, a weave (SCCS's storage format) turns out to be remarkably
well-suited to this.  When Bram says he accidentally invented the
weave from first principles, by asking "now what data structure would
be good for this", he's absolutely not kidding:
   
http://www.loglibrary.com/show_page/view/139?Multiplier=3600&Interval=6&StartTime=1115091103

Everything else here looks like interesting implementation questions,
but somewhat irrelevant to the algorithm itself :-).  There are a lot
of different ways to implement these sorts of ideas, with complicated
trade-offs... some sort of caching may well be a good idea, for sure.
But we don't even know that yet for sure.

-- Nathaniel

-- 
Eternity is very long, especially towards the end.
  -- Woody Allen