Re: git and larger trees, not so fast?

Junio C Hamano [off-list ref] writes:

Linus Torvalds [off-list ref] writes:

quoted

On Thu, 9 Aug 2007, Linus Torvalds wrote:

quoted

So "builtin-read-tree.c" (or rather unpack-trees.c) would need the same 
kind of logic.

The path seems to be:

  cmd_read_tree ->
    unpack_trees ->
      unpack_trees_rec ->
        [ recursive .. unpack_trees_rec ] ->
	  oneway_merge ->
	    keep_entry ->
	      add_index_entry()

and here again we end up having the same insertion sort issue.

Quite honestly, I was this (shows the "thumb and index finger
almost touching" gesture) close to declare that unpack-trees is
unsalvageable, and was planning to redo the one-tree (and
perhaps two-tree) read-tree without using that mess after 1.5.3.

While I do not think the previous one was hacky at all, this one
IS a hack, not meant for inclusion.  It makes the partial commit
codepath to use vanilla "git read-tree" without any single tree
merge semantics, and rewrite that codepath to use read_tree()
which was changed with my previous patch.



---

 builtin-read-tree.c |    5 ++++-
 git-commit.sh       |    2 +-
 2 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index a3b17a3..61ea15c 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c

@@ -258,7 +258,10 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 			opts.head_idx = 1;
 	}
 
-	unpack_trees(trees, &opts);
+	if (!opts.merge && !opts.prefix && trees && !trees->next)
+		read_tree((struct tree*) trees->item, 0, NULL);
+	else
+		unpack_trees(trees, &opts);
 
 	/*
 	 * When reading only one tree (either the most basic form,

diff --git a/git-commit.sh b/git-commit.sh
index d7e7028..b50468f 100755
--- a/git-commit.sh
+++ b/git-commit.sh

@@ -386,7 +386,7 @@ t,)
 		if test -z "$initial_commit"
 		then
 			GIT_INDEX_FILE="$THIS_INDEX" \
-			git read-tree --index-output="$TMP_INDEX" -i -m HEAD
+			git read-tree --index-output="$TMP_INDEX" HEAD
 		else
 			rm -f "$TMP_INDEX"
 		fi || exit

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