Re: [PATCH 0/2] A new merge algorithm, take 3

From: Linus Torvalds <>
Date: 2005-09-09 03:19:57
On Thu, 8 Sep 2005, Junio C Hamano wrote:
> Yes, the reading of three trees upfront is probably the culprit
> in your case

However, note that _most_ tree reading just reads one.

Merges may take half a second, and yes, when I did it, the fact that we 
move things around in the array is by far the highest cost. But the thing 
is, if merges take half a second, that's still not only damn good, it's 
not even the most common operation.

Yes, the active_cache[] layout as one big array is inconvenient for 
read_tree(), which tends to want to interleave different trees in the 
array and thus forces things to be moved around.

But remember what the most common use for the index is - it's the "single 
tree" case from read_cache(). That's _so_ much more common than 
read_tree() that it's not even funny.

So the data structure is optimized for a different case than reading in 
trees. Big deal. That optimization is definitely worth it: it allows us to 
do the read_cache() with the actual index entries being totally read-only 
(a linked list would have to add a "next" pointer to the cache entries and 
not allow the in-place thing that read_cache() does).

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at
Received on Fri Sep 09 03:21:30 2005

This archive was generated by hypermail 2.1.8 : 2005-09-09 03:21:32 EST