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

From: Chuck Lever <cel@citi.umich.edu>
Date: Sep 8, 2005, 18:58 UTC
Message-ID: <432089D8.4060507@citi.umich.edu>
In-Reply-To: <Pine.LNX.4.58.0509081131070.5940@g5.osdl.org>

Linus Torvalds wrote:

Show 15 quoted lines

> 
> 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.

i measured this using the following test...

i have a linux kernel git repository under control of stgit and it has about 70 patches in it. i did an "stg status" to heat the page cache. i popped all the patches, then did an "stg pull origin".

i started oprofile, and did an "stg push -a".  it took about 9 minutes.

i stopped oprofile and looked at the results. roughly 65% of the total CPU time was spent in libc:memmove. after instrumenting git, i determined that in the "stg push" case the critical memmove was the one in add_cache_entry.

note that i'm not saying that the 9 minutes of wall clock time was entirely due to CPU... catalin has been steadily improving "stg push" so this time has shortened by more than half, recently. but i do notice that working in a kernel repository is significantly slower than working in my git or stgit source repositories, which are smaller by far. the small repositories behave just as i expect, the tools respond quite snappily.

Show 11 quoted lines

>>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?

i'm not married to splay trees. i think we should explore several different data structures before picking one, and this one sounds reasonable to try.

begin:vcard fn:Chuck Lever n:Lever;Charles org:Network Appliance, Incorporated;Linux NFS Client Development adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA email;internet:cel@citi.umich.edu title:Member of Technical Staff tel;work:+1 734 763-4415 tel;fax:+1 734 763 4434 tel;home:+1 734 668-1089 x-mozilla-html:FALSE url:http://www.monkey.org/~cel/ version:2.1 end:vcard