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

[Linus Torvalds <torvalds@osdl.org>]

On Thu, 8 Sep 2005, Chuck Lever wrote:
> 
> in my case the merges were taking significantly longer than a half 
> second.  making this change is certainly not worth it if merges are 
> running fast...

Note that in cold-cache cases, all the expense of read-tree is in actually
reading the tree objects themselves (a kernel tree has more than a
thousand subdirectories). Also, a full "git pull" will do the diffstat 
etc, and then the expense ends up being in the actual "git diff" part.

So read-tree itself may be half a second, but a merge ends up having other 
parts.

> they are still read-only with my linked list implementation.

Btw, in the sparse project, we have this really smart "pointer list" data
structure, which is extremely space- and time-efficient. It ends up
_looking_ like a linked list, but it batches things up in hunks of 29
entries (29 pointers plus overhead gives you blocks of 32 longwords, which
is the allocation size) and thus gives basically a cache-friendly
doubly-linked list. It knows how to do insertions, traversals etc very 
efficiently.

Any interest?

		Linus