From: Shawn Pearce <spearce@spearce.org>
Date: Thu, 08 Dec 2011 16:42:24 GMT
Subject: Re: [PATCH 2/2] index-pack: a naive attempt to flatten find_unresolved_deltas
Message-ID: <CAJo=hJu35cYkWfBXAoL6OoCLVT4fE-mKjgqyGBN5xRLmiBeRdw@mail.gmail.com>
In-Reply-To: <4ee0be70.44f2320a.3fe8.632b@mx.google.com>

2011/12/8  <pclouds@gmail.com>:
> From: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>
> This seems to work for me. But I think this approach uses (much?) more
> memory because it turns a tree of calls into a flat list of calls and
> keep the list until the end, while the recursive version only has to
> keep one call chain at a time.
>
> Any ideas how to improve it?

Well, fortunately JGit is under a very liberal BSD license and has a
pretty efficient version of a heap based algorithm for delta
resolution. You could look at [1] for ideas. I am told the BSD license
is very compatible with the GPLv2. (Unlike the reverse.)


[1] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/transport/PackParser.java;hb=HEAD#l556