From mboxrd@z Thu Jan  1 00:00:00 1970
From: David Hopwood <david.nospam.hopwood@blueyonder.co.uk>
Subject: Re: Bitkeeper
Date: Tue, 12 Apr 2005 01:21:01 +0100
Message-ID: <425B146D.5020909@blueyonder.co.uk>
References: <1112911404.7186.75.camel@localhost.localdomain>	<4255B1B7.2030403@diku.dk>	<4255C1B7.6050509@tupshin.com>	<20050407235521.GC29680@us.ibm.com>	<4255CE7B.8050300@diku.dk>
	<42594770.8010805@speakeasy.net> <425A1F16.6000207@diku.dk>
Reply-To: david.nospam.hopwood@blueyonder.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Return-path: <xen-devel-bounces@lists.xensource.com>
In-Reply-To: <425A1F16.6000207@diku.dk>
List-Unsubscribe: <http://lists.xensource.com/cgi-bin/mailman/listinfo/xen-devel>,
	<mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
List-Post: <mailto:xen-devel@lists.xensource.com>
List-Help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-Subscribe: <http://lists.xensource.com/cgi-bin/mailman/listinfo/xen-devel>,
	<mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
Sender: xen-devel-bounces@lists.xensource.com
Errors-To: xen-devel-bounces@lists.xensource.com
To: xen-devel@lists.xensource.com
List-Id: xen-devel@lists.xenproject.org

Jacob Gorm Hansen wrote:
> From what I have read about darcs, the problem is the 'theory of 
> patches' approach which demands that all patches be loaded into memory 
> at once so that the order in which they should be applied can be 
> determined via a n*n comparison of the contents of each patch against 
> the contents of all other patches.

I don't know precisely why the current darcs implementation needs as
much memory as it does, but I know it is not for the above reason. An
important property of the 'theory of patches' is that merges can be done
in arbitrary order (see <http://abridgegame.org/darcs/manual/node8.html>).

The size of a merged patch will be similar to the sum of the sizes of the
input patches, just as in other SCSs. A very simple-minded implementation
that literally reconstructs the whole repository by patching an empty one
would require memory proportional to the repository size, but there's
nothing about the theory that would require you to handle the whole
repository at once.

 > Hmm, the Wiki page about darcs performance looks rather scary:
 >
 > http://www.scannedinavian.org/DarcsWiki/Performance

Those look like implementation nits to me, with known workarounds.

Also remember that other SCSs only support what darcs calls 'hunk patches'.
IIUC, it's only if you use features of darcs that are not present in other
SCSs that you hit the exponential complexity cases that are mentioned on the
wiki page.

That said, I've heard reports that the current darcs implementation can get
a repository into states that require an understanding of its internals to
get out of. It wouldn't be the only SCS that has that property, but people
may be more used to the particular ways in which CVS et al get confused.

> While all this talk of quantum operators may sound sexy at first, I am
> fairly sure it is vastly overkill for real-world source-control.

<sigh>. From a marketing point of view, even mentioning quantum mechanics
is a disaster. It might have been fine when the audience for darcs was three
physicists, but that page really should be rewritten. Anyway, the limit of
the analogy between QM and darcs' theory of patches is that they both involve
commutative operators; that's all.

> I other words, I would not be too optimistic about darcs having its 
> performance issues cleared up in the shorter term. Besides, there is the 
> issue of using a tool written in a language that the majority of 
> programmers will find hard to understand*.

The majority of programmers would have difficulty in understanding an SCS
implementation written in any language. Plenty of programmers understand
Haskell.

-- 
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>