From: Chuck Lever Date: Thu, 08 Sep 2005 18:58:32 GMT Subject: Re: [PATCH 0/2] A new merge algorithm, take 3 Message-ID: <432089D8.4060507@citi.umich.edu> In-Reply-To: Linus Torvalds wrote: > > 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. >>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