performance problem: "git commit filename"

I thought we had fixed this long long ago, but if we did, it has 
re-surfaced.

Using an explicit filename with "git commit" is _extremely_ slow. Lookie 
here:

	[torvalds@woody linux]$ time git commit fs/exec.c
	no changes added to commit (use "git add" and/or "git commit -a")

	real    0m1.671s
	user    0m1.200s
	sys     0m0.328s

that's closer to two seconds on a fast machine, with the whole tree 
cached!

And for the uncached case, it's just unbearably slow: two and a half 
*minutes*.

In contrast, without the filename, it's much faster:

	[torvalds@woody linux]$ time git commit
	no changes added to commit (use "git add" and/or "git commit -a")
	
	real    0m0.387s
	user    0m0.220s
	sys     0m0.168s

with the cold-cache case now being "just" 18s (which is still long, but 
we're talking eight times faster, and certainly not unbearable!)

Doing an "strace -c" on the thing shows why. In the filename case, we 
have:

	% time     seconds  usecs/call     calls    errors syscall
	------ ----------- ----------- --------- --------- ----------------
	 32.69    0.000868           0     92299        37 lstat
	 17.40    0.000462           0     29958      3993 open
	 15.78    0.000419           0      5522           getdents
	 15.56    0.000413           0     23165           mmap
	 11.37    0.000302           0     23118           munmap
	  5.76    0.000153           0     25966         2 close
	  1.43    0.000038           0      2845           fstat
	...

and in the non-filename case we have

	% time     seconds  usecs/call     calls    errors syscall
	------ ----------- ----------- --------- --------- ----------------
	 53.67    0.000600           0     69227        31 lstat
	 23.35    0.000261           0      5522           getdents
	 11.09    0.000124           2        55           munmap
	  4.20    0.000047           0       285           write
	  3.31    0.000037           0      5537      2638 open
	  2.33    0.000026           0      2899         1 close
	  2.06    0.000023           0      2844           fstat
	...

notice how the expensive case has a lot of successful open/mmap/munmap 
calls: it is *literally* ignoring the valid entries in the old index 
entirely, and re-hashing every single file in the tree! No wonder it is 
slow!

Just counting "lstat()" calls, it's worth noticing that the non-filename 
case seems to do three lstat's for each index entry (and yes, that's two
too many), but the named file case has upped that to *four* lstats per 
entry, and then added the one open/mmap/munmap/close on top of that!

I'm pretty sure we didn't use to do things this badly. And if this is a 
regression like I think it is, it should be fixed before a real 1.5.4 
release.

I'll try to see if I can see what's up, but I thought I'd better let 
others know too, in case I don't have time. I *suspect* (but have nothing 
what-so-ever to back that up) that this happened as part of making commit 
a builtin.

			Linus

On Sat, 12 Jan 2008, Linus Torvalds wrote:

I thought we had fixed this long long ago, but if we did, it has 
re-surfaced.

It's new, and yes, it seems to be due to the new builtin-commit.c.

I think I know what is going on.

In the old git-commit.sh, this case used to be handled with

	TMP_INDEX="$GIT_DIR/tmp-index$$"

	GIT_INDEX_FILE="$THIS_INDEX" \
	git read-tree --index-output="$TMP_INDEX" -i -m HEAD

which is a one-way merge of the *old* index and HEAD, taking the index 
information from the old index, but the actual file information from HEAD 
(to then later be updated by the named files).

This logic is implemented by builtin-read-tree.c with

	struct unpack_trees_options opts;
	..
	opts.fn = oneway_merge;
	..
	unpack_trees(nr_trees, t, &opts);

where all the magic is done by that "oneway_merge()" function being called 
for each entry by unpack_trees(). This does everything right, and the 
result is that any index entry that was up-to-date in the old index and 
unchanged in the base tree will be up-to-date in the new index too

HOWEVER. When that logic was converted from that shell-script into a 
builtin-commit.c, that conversion was not done correctly. The old "git 
read-tree -i -m" was not translated as a "unpack_trees()" call, but as 
this in prepare_index():

	discard_cache()
	..
	tree = parse_tree_indirect(head_sha1);
	..
	read_tree(tree, 0, NULL)

which is very wrong, because it replaces the old index entirely, and 
doesn't do that stat information merging.

As a result, the index that is created by read-tree is totally bogus in 
the stat cache, and yes, everything will have to be re-computed.

Kristian?

			Linus

On Sat, 12 Jan 2008, Linus Torvalds wrote:

HOWEVER. When that logic was converted from that shell-script into a 
builtin-commit.c, that conversion was not done correctly. The old "git 
read-tree -i -m" was not translated as a "unpack_trees()" call, but as 
this in prepare_index():

	discard_cache()
	..
	tree = parse_tree_indirect(head_sha1);
	..
	read_tree(tree, 0, NULL)

which is very wrong, because it replaces the old index entirely, and 
doesn't do that stat information merging.

This patch may or may not fix it.

It makes builtin-commit.c use the same logic that "git read-tree -i -m" 
does (which is what the old shell script did), and it seems to pass the 
test-suite, and it looks pretty obvious.

It also brings down the number of open/mmap/munmap/close calls to where it 
should be, although it still does *way* too many "lstat()" operations (ie 
it does 4*lstat for each file in the index - one more than the 
non-filename one does).

With that fixed, performance is also roughly where it should be (ie the 
17-18s for the cold-cache case), because it no longer needs to rehash all 
the files!

HOWEVER. This was just a quick hack, and while it all looks sane, this is 
some damn core code. Somebody else should double- and triple-check this.

[ That 4x lstat thing bothers me. I think we should add a flag to the 
  index saying "we checked this once already, it's clean", so that if we 
  do multiple passes over the index, we can still do just a single lstat() 
  on just the first pass. But that's a separate issue.

  On Linux, a cached lstat() is almost free. Well, at least compared to 
  all the crap operating systems out there. And obviously, if you do 
  multiple lstat's per file, all but the first one *will* be cached.

  However, "almost free" still isn't zero, and with the kernel having 23k 
  files in it, doing almost a hundred thousand lstat's is still something 
  that only takes about half a second or so for me. We _really_ should do 
  only ~23k or so of them, and the cached cache should take on the order 
  of 0.15s, rather than half a second!

  So this is worth optimizing. With bigger repositories, it's going to be 
  more noticeable, and with other operating systems, all those lstat()'s 
  will cost much _much_ more. Of course, any IO overhead will be much 
  bigger, so this is mostly a cached-case issue, but cached-case is still 
  important.. ]

Anyway, consider this being conditionally signed-off-by: me, assuming 
a few other people spend a bit of time double-checking all my logic.

Please?

			Linus

---
 builtin-commit.c |   37 ++++++++++++++++++++++++++++---------
 1 files changed, 28 insertions(+), 9 deletions(-)

diff --git a/builtin-commit.c b/builtin-commit.c
index 73f1e35..cc5134e 100644
--- a/builtin-commit.c
+++ b/builtin-commit.c

@@ -21,6 +21,7 @@
 #include "utf8.h"
 #include "parse-options.h"
 #include "path-list.h"
+#include "unpack-trees.h"
 
 static const char * const builtin_commit_usage[] = {
 	"git-commit [options] [--] <filepattern>...",

@@ -177,10 +178,34 @@ static void add_remove_files(struct path_list *list)
 	}
 }
 
+static void create_base_index(void)
+{
+	struct tree *tree;
+	struct unpack_trees_options opts;
+	struct tree_desc t;
+
+	if (initial_commit) {
+		discard_cache();
+		return;
+	}
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = 1;
+	opts.index_only = 1;
+	opts.merge = 1;
+	
+	opts.fn = oneway_merge;
+	tree = parse_tree_indirect(head_sha1);
+	if (!tree)
+		die("failed to unpack HEAD tree object");
+	parse_tree(tree);
+	init_tree_desc(&t, tree->buffer, tree->size);
+	unpack_trees(1, &t, &opts);
+}
+
 static char *prepare_index(int argc, const char **argv, const char *prefix)
 {
 	int fd;
-	struct tree *tree;
 	struct path_list partial;
 	const char **pathspec = NULL;
 

@@ -278,14 +303,8 @@ static char *prepare_index(int argc, const char **argv, const char *prefix)
 
 	fd = hold_lock_file_for_update(&false_lock,
 				       git_path("next-index-%d", getpid()), 1);
-	discard_cache();
-	if (!initial_commit) {
-		tree = parse_tree_indirect(head_sha1);
-		if (!tree)
-			die("failed to unpack HEAD tree object");
-		if (read_tree(tree, 0, NULL))
-			die("failed to read HEAD tree object");
-	}
+
+	create_base_index();
 	add_remove_files(&partial);
 	refresh_cache(REFRESH_QUIET);
 

On Sat, 12 Jan 2008, Linus Torvalds wrote:

It makes builtin-commit.c use the same logic that "git read-tree -i -m" 
does (which is what the old shell script did), and it seems to pass the 
test-suite, and it looks pretty obvious.

The only issue I know about with using unpack_trees in C as a replacement 
for read-tree in shell is that unpack_trees leaves "deletion" index 
entries in memory which are not written to disk, but may surprise some 
code (these are used to allow -u to remove the files from the working 
tree). So you may want to make sure that you don't get any weird results 
out of a commit of particular files that involves not committing some 
newly-added files:

$ git add new-file
$ (edit old-file)
$ git commit old-file

This may cause the unpack_trees to leave a misleading entry for new-file 
that the code doesn't expect. I've got a patch to make it saner as part of 
my builtin-checkout series, but I can't say for sure that that change 
won't either confuse something else or have performance problems without a 
bunch of analysis I haven't done recently.

	-Daniel
*This .sig left intentionally blank*

On Sun, 13 Jan 2008, Daniel Barkalow wrote:

The only issue I know about with using unpack_trees in C as a replacement 
for read-tree in shell is that unpack_trees leaves "deletion" index 
entries in memory which are not written to disk, but may surprise some 
code (these are used to allow -u to remove the files from the working 
tree).

I certainly agree that this patch should be double-checked. I'm pretty 
sure the issue you mention wouldn't be an issue, since the end result is 
only used for actually updating the index and writing it out as a tree 
(both of which should handle the magic zero ce_mode case ok), but it would 
certainly be good to walk through all cases.

			Linus

On Sun, 13 Jan 2008, Linus Torvalds wrote:

On Sun, 13 Jan 2008, Daniel Barkalow wrote:

quoted

The only issue I know about with using unpack_trees in C as a replacement 
for read-tree in shell is that unpack_trees leaves "deletion" index 
entries in memory which are not written to disk, but may surprise some 
code (these are used to allow -u to remove the files from the working 
tree).

I certainly agree that this patch should be double-checked. I'm pretty 
sure the issue you mention wouldn't be an issue, since the end result is 
only used for actually updating the index and writing it out as a tree 
(both of which should handle the magic zero ce_mode case ok), but it would 
certainly be good to walk through all cases.

Yeah, I didn't think it would be an actual problem, but verifying that 
requires looking outside of the context of the patch. It may even be worth 
putting in a comment for now, since I bet wt_status_print and run_status 
could be optimized in a way that would look perfectly reasonable (use 
the in-memory index, instead of reading a file) but would expose the 
magic case to the diff machinary, which (IIRC) doesn't handle it. But I 
agree (having now looked at the rest of builtin-commit) that the odd index 
entries can't escape, and this should be fine for 1.5.4.

	-Daniel
*This .sig left intentionally blank*

On Sat, 2008-01-12 at 17:46 -0800, Linus Torvalds wrote:

HOWEVER. When that logic was converted from that shell-script into a 
builtin-commit.c, that conversion was not done correctly. The old "git 
read-tree -i -m" was not translated as a "unpack_trees()" call, but as 
this in prepare_index():

	discard_cache()
	..
	tree = parse_tree_indirect(head_sha1);
	..
	read_tree(tree, 0, NULL)

which is very wrong, because it replaces the old index entirely, and 
doesn't do that stat information merging.

As a result, the index that is created by read-tree is totally bogus in 
the stat cache, and yes, everything will have to be re-computed.

Kristian?

Sorry for being late to the game, and yes, it's a bug I introduced with
the rewrite.  When doing the rewrite I was a bit puzzled by the

  git-read-tree --index-output="$TMP_INDEX" -i -m HEAD

part of the shell script.  I carried a FIXME around in the patch for a
while, as can be seen here:

  http://marc.info/?l=git&m=118478660425992&w=2

since I couldn't figure out what the difference in behavior was between
just using read_tree(), which did exactly what I wanted and the more
complicated unpack_tree().  I guess it fell through the cracks,
especially since it never caused the test suite to fail :/

Kristian

On Sat, 2008-01-12 at 20:04 -0800, Linus Torvalds wrote:

It makes builtin-commit.c use the same logic that "git read-tree -i -m" 
does (which is what the old shell script did), and it seems to pass the 
test-suite, and it looks pretty obvious.

It also brings down the number of open/mmap/munmap/close calls to where it 
should be, although it still does *way* too many "lstat()" operations (ie 
it does 4*lstat for each file in the index - one more than the 
non-filename one does).

With that fixed, performance is also roughly where it should be (ie the 
17-18s for the cold-cache case), because it no longer needs to rehash all 
the files!

HOWEVER. This was just a quick hack, and while it all looks sane, this is 
some damn core code. Somebody else should double- and triple-check this.

I took a look too, and it looks to me like the it's the exact same code
path in builtin-read-tree.c that the old

        git read-tree --index-output="$TMP_INDEX" -i -m HEAD

part of the shell script would trigger.  So yes, this look like the
right fix to me.

Signed-off-by: Kristian Høgsberg <redacted>