Re: CFT: merge-recursive in C (updated)

From: Linus Torvalds <torvalds@osdl.org>
Date: Jun 27, 2006, 18:22 UTC
Message-ID: <Pine.LNX.4.64.0606271116360.3927@g5.osdl.org>
In-Reply-To: <81b0412b0606270848v2253209aw52466de632ab25c1@mail.gmail.com>

On Tue, 27 Jun 2006, Alex Riesen wrote:

Show 5 quoted lines

> 
> Good news is that it is faster: 6min vs 10min. Bad news is that it is still
> not enough for me and it is only on Linux (Windows will be slower,
> still testing),
> uses an awful lot of memory and CPU.

Why do you do that horrible node_list, and the broken "find common ancestors?"

I can't follow your code, but it _looks_ like you are using some totally broken graph walking function.

For git, the #1 optimization ALWAYS is to avoid walking the full commit graph. That fundamentally _cannot_ scale.

Almost all of the "hard work" in git has been to try to read the minimum amount of commits possible. That means that you absolutely must not just walk the commits the "obvious" way, because that will always require you to build up the whole graph of the whole history, even if the common shared point is much closer.

So it look slike your "graph.c" is _fundamentally_ flawed.

You need to really read "git-merge-base.c" and understand it thoroughly. And then you need to throw away your graph.c, and use git-merge-base instead.

			Linus