Re: git and larger trees, not so fast?

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

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