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
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
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
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
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
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.
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
title:Member of Technical Staff
tel;work:+1 734 763-4415
tel;fax:+1 734 763 4434
tel;home:+1 734 668-1089