Re: git and larger trees, not so fast?

On Thu, 9 Aug 2007, Junio C Hamano wrote:

While I do not think the previous one was hacky at all, this one
IS a hack, not meant for inclusion.

Ugh.

I had some time, so I tried to find out *why* that thing is so slow.

The fact is, "git read-tree -m HEAD" should be really really fast, because 
it should never actually insert multiple entries into the same index 
entry: it should just _replace_ the entry.

But why is it slow?

It doesn't actually replace the entry with "add_cache_entry()" at all. 
What it does is to *remove* the entry entirely at unpack-trees.c, line 
154, unpack_trees_rec(), which does a "remove_cache_entry_at(o->pos);".

That causes us to have to condense the index array, and is one big 
memcpy() for a large index.

It then ADDS THE NEW ENTRY BACK! Which causes *another* expensive index 
array memmove(), as it now needs to make room (at the same location that 
it just compacted).

Sadly, that removal is required for some of the other cases, so it's not 
like we can remove the remove. But we could *possibly* make things 
ridiculously much faster by making the remove a lazy thing, and if the 
next index operation just adds it back in, we wouldn't move things around.

A bit too subtle for my taste.

		Linus