[PATCH v2 0/3] Improving performance of git clean

[PATCH v2 0/3] Improving performance of git clean

[Erik Elfström]

v1 of the patch can be found here:
http://thread.gmane.org/gmane.comp.version-control.git/266839/focus=266839

changes in v2:
* fixed commit message,
  "p7300: added performance tests for clean"
  change to:
  "p7300: add performance tests for clean"
* simplified test code
* removed non portable ls -A in test
* removed non portable $(seq ) in test
* fixed missing " || return $?" in test
* fixed missing sub shell for 'cd' command in test
* fixed broken && chains in test
* added assert new clean.c:is_git_repository to guard against
  negative array index
* use size_t instead of int for strbuf->len

fixes held back for cleanup patches:
* fixed existing broken && chains
* added assert in existing code to guard against
  negative array index

Thanks to Eric Sunshine and Torsten Bögershausen for the very helpful
review!


Erik Elfström (3):
  t7300: add tests to document behavior of clean and nested git
  p7300: add performance tests for clean
  clean: improve performance when removing lots of directories

 builtin/clean.c       | 24 ++++++++++++++---
 t/perf/p7300-clean.sh | 37 ++++++++++++++++++++++++++
 t/t7300-clean.sh      | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 129 insertions(+), 4 deletions(-)
 create mode 100755 t/perf/p7300-clean.sh

-- 
2.4.0.rc0.37.ga3b75b3

[PATCH v2 0/3] Improving performance of git clean

[Erik Elfström]

v1 of the patch can be found here:
http://thread.gmane.org/gmane.comp.version-control.git/266839/focus=266839

changes in v2:
* fixed commit message,
  "p7300: added performance tests for clean"
  change to:
  "p7300: add performance tests for clean"
* simplified test code
* removed non portable ls -A in test
* removed non portable $(seq ) in test
* fixed missing " || return $?" in test
* fixed missing sub shell for 'cd' command in test
* fixed broken && chains in test
* added assert new clean.c:is_git_repository to guard aginst
  negative array index
* use size_t instead of int for strbuf->len

fixes held back for cleanup patches:
* fixed existing broken && chains
* added assert in existing code to guard gainst
  negative array index

Thanks to Eric Sunshine and Torsten Bögershausen for the very helpful
review!


Erik Elfström (3):
  t7300: add tests to document behavior of clean and nested git
  p7300: add performance tests for clean
  clean: improve performance when removing lots of directories

 builtin/clean.c       | 24 ++++++++++++++---
 t/perf/p7300-clean.sh | 37 ++++++++++++++++++++++++++
 t/t7300-clean.sh      | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 129 insertions(+), 4 deletions(-)
 create mode 100755 t/perf/p7300-clean.sh

-- 
2.4.0.rc0.37.ga3b75b3

[PATCH v2 1/3] t7300: add tests to document behavior of clean and nested git

[Erik Elfström]

Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
---
 t/t7300-clean.sh | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)

diff --git a/t/t7300-clean.sh b/t/t7300-clean.sh
index 99be5d9..58e6b4a 100755
--- a/t/t7300-clean.sh
+++ b/t/t7300-clean.sh
@@ -455,6 +455,78 @@ test_expect_success 'nested git work tree' '
 	! test -d bar
 '
 
+test_expect_failure 'nested git (only init) should be kept' '
+	rm -fr foo bar &&
+	git init foo &&
+	mkdir bar &&
+	>bar/goodbye.people &&
+	git clean -f -d &&
+	test_path_is_file foo/.git/HEAD &&
+	test_path_is_missing bar
+'
+
+test_expect_failure 'nested git (bare) should be kept' '
+	rm -fr foo bar &&
+	git init --bare foo &&
+	mkdir bar &&
+	>bar/goodbye.people &&
+	git clean -f -d &&
+	test_path_is_file foo/HEAD &&
+	test_path_is_missing bar
+'
+
+test_expect_success 'giving path in nested git work tree will remove it' '
+	rm -fr foo &&
+	mkdir foo &&
+	(
+		cd foo &&
+		git init &&
+		mkdir -p bar/baz &&
+		(
+			cd bar/baz &&
+			>hello.world &&
+			git add . &&
+			git commit -a -m nested
+		)
+	) &&
+	git clean -f -d foo/bar/baz &&
+	test_path_is_file foo/.git/HEAD &&
+	test_path_is_dir foo/bar/ &&
+	test_path_is_missing foo/bar/baz
+'
+
+test_expect_success 'giving path to nested .git will not remove it' '
+	rm -fr foo &&
+	mkdir foo bar &&
+	(
+		cd foo &&
+		git init &&
+		>hello.world &&
+		git add . &&
+		git commit -a -m nested
+	) &&
+	git clean -f -d foo/.git &&
+	test_path_is_file foo/.git/HEAD &&
+	test_path_is_dir foo/.git/refs &&
+	test_path_is_dir foo/.git/objects &&
+	test_path_is_dir bar/
+'
+
+test_expect_success 'giving path to nested .git/ will remove contents' '
+	rm -fr foo bar &&
+	mkdir foo bar &&
+	(
+		cd foo &&
+		git init &&
+		>hello.world &&
+		git add . &&
+		git commit -a -m nested
+	) &&
+	git clean -f -d foo/.git/ &&
+	test_path_is_dir foo/.git &&
+	test_dir_is_empty foo/.git
+'
+
 test_expect_success 'force removal of nested git work tree' '
 	rm -fr foo bar baz &&
 	mkdir -p foo bar baz/boo &&
-- 
2.4.0.rc0.37.ga3b75b3

[PATCH v2 2/3] p7300: add performance tests for clean

[Erik Elfström]

Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
---
 t/perf/p7300-clean.sh | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
 create mode 100755 t/perf/p7300-clean.sh

diff --git a/t/perf/p7300-clean.sh b/t/perf/p7300-clean.sh
new file mode 100755
index 0000000..af50d5d
--- /dev/null
+++ b/t/perf/p7300-clean.sh
@@ -0,0 +1,37 @@
+#!/bin/sh
+
+test_description="Test git-clean performance"
+
+. ./perf-lib.sh
+
+test_perf_large_repo
+test_checkout_worktree
+
+test_expect_success 'setup untracked directory with many sub dirs' '
+	rm -rf 500_sub_dirs 50000_sub_dirs clean_test_dir &&
+	mkdir 500_sub_dirs 50000_sub_dirs clean_test_dir &&
+	for i in $(test_seq 1 500)
+	do
+		mkdir 500_sub_dirs/dir$i || return $?
+	done &&
+	for i in $(test_seq 1 100)
+	do
+		cp -r 500_sub_dirs 50000_sub_dirs/dir$i || return $?
+	done
+'
+
+test_perf 'clean many untracked sub dirs, check for nested git' '
+	rm -rf clean_test_dir/50000_sub_dirs_cpy &&
+	cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
+	git clean -q -f -d  clean_test_dir/ &&
+	test_dir_is_empty clean_test_dir
+'
+
+test_perf 'clean many untracked sub dirs, ignore nested git' '
+	rm -rf clean_test_dir/50000_sub_dirs_cpy &&
+	cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
+	git clean -q -f -f -d  clean_test_dir/ &&
+	test_dir_is_empty clean_test_dir
+'
+
+test_done
-- 
2.4.0.rc0.37.ga3b75b3

Re: [PATCH v2 2/3] p7300: add performance tests for clean

[Thomas Gummerer]

On 04/11, Erik Elfström wrote:
> Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
> ---
>  t/perf/p7300-clean.sh | 37 +++++++++++++++++++++++++++++++++++++
>  1 file changed, 37 insertions(+)
>  create mode 100755 t/perf/p7300-clean.sh
>
> diff --git a/t/perf/p7300-clean.sh b/t/perf/p7300-clean.sh
> new file mode 100755
> index 0000000..af50d5d
> --- /dev/null
> +++ b/t/perf/p7300-clean.sh
> @@ -0,0 +1,37 @@
> +#!/bin/sh
> +
> +test_description="Test git-clean performance"
> +
> +. ./perf-lib.sh
> +
> +test_perf_large_repo
> +test_checkout_worktree
> +
> +test_expect_success 'setup untracked directory with many sub dirs' '
> +	rm -rf 500_sub_dirs 50000_sub_dirs clean_test_dir &&
> +	mkdir 500_sub_dirs 50000_sub_dirs clean_test_dir &&
> +	for i in $(test_seq 1 500)
> +	do
> +		mkdir 500_sub_dirs/dir$i || return $?
> +	done &&
> +	for i in $(test_seq 1 100)
> +	do
> +		cp -r 500_sub_dirs 50000_sub_dirs/dir$i || return $?
> +	done
> +'
> +
> +test_perf 'clean many untracked sub dirs, check for nested git' '
> +	rm -rf clean_test_dir/50000_sub_dirs_cpy &&
> +	cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&

Maybe this would be a good place to use test_perf_cleanup, which I
introduced a while ago and you can find in the
tg/perf-lib-test-perf-cleanup branch?  It probably won't influence the
performance a lot, but still better separate the code that actually
needs to be tested from the cleanup/preparation code.  Ditto in the
other test.

> +	git clean -q -f -d  clean_test_dir/ &&
> +	test_dir_is_empty clean_test_dir
> +'
> +
> +test_perf 'clean many untracked sub dirs, ignore nested git' '
> +	rm -rf clean_test_dir/50000_sub_dirs_cpy &&
> +	cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
> +	git clean -q -f -f -d  clean_test_dir/ &&
> +	test_dir_is_empty clean_test_dir
> +'
> +
> +test_done
> --
> 2.4.0.rc0.37.ga3b75b3
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v2 2/3] p7300: add performance tests for clean

[erik elfström]

On Sat, Apr 11, 2015 at 7:59 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
> On 04/11, Erik Elfström wrote:
>> Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
>> ---
>>  t/perf/p7300-clean.sh | 37 +++++++++++++++++++++++++++++++++++++
>>  1 file changed, 37 insertions(+)
>>  create mode 100755 t/perf/p7300-clean.sh
>>
>> diff --git a/t/perf/p7300-clean.sh b/t/perf/p7300-clean.sh
>> new file mode 100755
>> index 0000000..af50d5d
>> --- /dev/null
>> +++ b/t/perf/p7300-clean.sh
>> @@ -0,0 +1,37 @@
>> +#!/bin/sh
>> +
>> +test_description="Test git-clean performance"
>> +
>> +. ./perf-lib.sh
>> +
>> +test_perf_large_repo
>> +test_checkout_worktree
>> +
>> +test_expect_success 'setup untracked directory with many sub dirs' '
>> +     rm -rf 500_sub_dirs 50000_sub_dirs clean_test_dir &&
>> +     mkdir 500_sub_dirs 50000_sub_dirs clean_test_dir &&
>> +     for i in $(test_seq 1 500)
>> +     do
>> +             mkdir 500_sub_dirs/dir$i || return $?
>> +     done &&
>> +     for i in $(test_seq 1 100)
>> +     do
>> +             cp -r 500_sub_dirs 50000_sub_dirs/dir$i || return $?
>> +     done
>> +'
>> +
>> +test_perf 'clean many untracked sub dirs, check for nested git' '
>> +     rm -rf clean_test_dir/50000_sub_dirs_cpy &&
>> +     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
>
> Maybe this would be a good place to use test_perf_cleanup, which I
> introduced a while ago and you can find in the
> tg/perf-lib-test-perf-cleanup branch?  It probably won't influence the
> performance a lot, but still better separate the code that actually
> needs to be tested from the cleanup/preparation code.  Ditto in the
> other test.
>

Yes, that would be a clear improvement. I was looking for something like
this, the copy takes more time than the clean currently.

The cleanup hook is maybe not exactly the right fit here though. I would
need to do one initial copy in the setup test and then a copy in the
cleanup, something like this:

test_expect_success 'setup untracked directory with many sub dirs' '
    ...
    cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
'

test_perf_cleanup 'clean many untracked sub dirs, check for nested git' '
    git clean -q -f -d  clean_test_dir/
' '
    test_dir_is_empty clean_test_dir &&
    rm -rf clean_test_dir/50000_sub_dirs_cpy &&
    cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
'

This works better than my original code but maybe we can do even better
with something like:

test_setup_perf_cleanup 'clean many untracked sub dirs, check for nested git' '
    rm -rf clean_test_dir/50000_sub_dirs_cpy &&
    cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
' '
    git clean -q -f -d  clean_test_dir/
' '
    test_dir_is_empty clean_test_dir
'

Having a setup phase avoids the initial copy in the setup test making
things a little easier to follow. I'm not sure its worth the extra complexity
in perf-lib though (and I'm not sure I would be able to implement it either).

Also, what would the implications be if I were to use your new cleanup
function that is not yet on master? Should I rebase on top of your topic
or make a follow up patch to switch over?

>> +     git clean -q -f -d  clean_test_dir/ &&
>> +     test_dir_is_empty clean_test_dir
>> +'
>> +
>> +test_perf 'clean many untracked sub dirs, ignore nested git' '
>> +     rm -rf clean_test_dir/50000_sub_dirs_cpy &&
>> +     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
>> +     git clean -q -f -f -d  clean_test_dir/ &&
>> +     test_dir_is_empty clean_test_dir
>> +'
>> +
>> +test_done
>> --
>> 2.4.0.rc0.37.ga3b75b3
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe git" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v2 2/3] p7300: add performance tests for clean

[Thomas Gummerer]

On 04/12, erik elfström wrote:
> On Sat, Apr 11, 2015 at 7:59 PM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
> > On 04/11, Erik Elfström wrote:
> >> Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
> >> ---
> >>  t/perf/p7300-clean.sh | 37 +++++++++++++++++++++++++++++++++++++
> >>  1 file changed, 37 insertions(+)
> >>  create mode 100755 t/perf/p7300-clean.sh
> >>
> >> diff --git a/t/perf/p7300-clean.sh b/t/perf/p7300-clean.sh
> >> new file mode 100755
> >> index 0000000..af50d5d
> >> --- /dev/null
> >> +++ b/t/perf/p7300-clean.sh
> >> @@ -0,0 +1,37 @@
> >> +#!/bin/sh
> >> +
> >> +test_description="Test git-clean performance"
> >> +
> >> +. ./perf-lib.sh
> >> +
> >> +test_perf_large_repo
> >> +test_checkout_worktree
> >> +
> >> +test_expect_success 'setup untracked directory with many sub dirs' '
> >> +     rm -rf 500_sub_dirs 50000_sub_dirs clean_test_dir &&
> >> +     mkdir 500_sub_dirs 50000_sub_dirs clean_test_dir &&
> >> +     for i in $(test_seq 1 500)
> >> +     do
> >> +             mkdir 500_sub_dirs/dir$i || return $?
> >> +     done &&
> >> +     for i in $(test_seq 1 100)
> >> +     do
> >> +             cp -r 500_sub_dirs 50000_sub_dirs/dir$i || return $?
> >> +     done
> >> +'
> >> +
> >> +test_perf 'clean many untracked sub dirs, check for nested git' '
> >> +     rm -rf clean_test_dir/50000_sub_dirs_cpy &&
> >> +     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
> >
> > Maybe this would be a good place to use test_perf_cleanup, which I
> > introduced a while ago and you can find in the
> > tg/perf-lib-test-perf-cleanup branch?  It probably won't influence the
> > performance a lot, but still better separate the code that actually
> > needs to be tested from the cleanup/preparation code.  Ditto in the
> > other test.
> >
>
> Yes, that would be a clear improvement. I was looking for something like
> this, the copy takes more time than the clean currently.
>
> The cleanup hook is maybe not exactly the right fit here though. I would
> need to do one initial copy in the setup test and then a copy in the
> cleanup, something like this:
>
> test_expect_success 'setup untracked directory with many sub dirs' '
>     ...
>     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
> '
>
> test_perf_cleanup 'clean many untracked sub dirs, check for nested git' '
>     git clean -q -f -d  clean_test_dir/
> ' '
>     test_dir_is_empty clean_test_dir &&
>     rm -rf clean_test_dir/50000_sub_dirs_cpy &&
>     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
> '
>
> This works better than my original code but maybe we can do even better
> with something like:
>
> test_setup_perf_cleanup 'clean many untracked sub dirs, check for nested git' '
>     rm -rf clean_test_dir/50000_sub_dirs_cpy &&
>     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
> ' '
>     git clean -q -f -d  clean_test_dir/
> ' '
>     test_dir_is_empty clean_test_dir
> '
>
> Having a setup phase avoids the initial copy in the setup test making
> things a little easier to follow. I'm not sure its worth the extra complexity
> in perf-lib though (and I'm not sure I would be able to implement it either).

Yeah, you're right, that would look even better.  In order to avoid
the extra complexity we might actually go the other route that was
proposed by Junio in the discussion back then
(http://thread.gmane.org/gmane.comp.version-control.git/234874/focus=235241).

Using that and adding a setup option we could have something like:

test_perf --setup '
	rm -rf clean_test_dir/50000_sub_dirs_cpy &&
	cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy
' --cleanup '
	test_dir_is_empty clean_test_dir
' 'clean many untracked sub dirs, check for nested git' '
	git clean -q -f -d clean_test_dir
'

> Also, what would the implications be if I were to use your new cleanup
> function that is not yet on master? Should I rebase on top of your topic
> or make a follow up patch to switch over?

If the consensus is to go that route, I think you could just rebase
the topic onto my topic.  If we introduce the "modern" test style as
described before it might be worth merging this series first and then
switch over to the new style.  You should probably wait for other
opinions before changing it though.

> >> +     git clean -q -f -d  clean_test_dir/ &&
> >> +     test_dir_is_empty clean_test_dir
> >> +'
> >> +
> >> +test_perf 'clean many untracked sub dirs, ignore nested git' '
> >> +     rm -rf clean_test_dir/50000_sub_dirs_cpy &&
> >> +     cp -r 50000_sub_dirs clean_test_dir/50000_sub_dirs_cpy &&
> >> +     git clean -q -f -f -d  clean_test_dir/ &&
> >> +     test_dir_is_empty clean_test_dir
> >> +'
> >> +
> >> +test_done
> >> --
> >> 2.4.0.rc0.37.ga3b75b3
> >>
> >> --
> >> To unsubscribe from this list: send the line "unsubscribe git" in
> >> the body of a message to majordomo@vger.kernel.org
> >> More majordomo info at  http://vger.kernel.org/majordomo-info.html

--
Thomas Gummerer

[PATCH v2 3/3] clean: improve performance when removing lots of directories

[Erik Elfström]

Before this change, clean used resolve_gitlink_ref to check for the
presence of nested git repositories. This had the drawback of creating
a ref_cache entry for every directory that should potentially be
cleaned. The linear search through the ref_cache list caused a massive
performance hit for large number of directories.

Teach clean.c:remove_dirs to use setup.c:is_git_directory
instead. is_git_directory will actually open HEAD and parse the HEAD
ref but this implies a nested git repository and should be rare when
cleaning.

Using is_git_directory should give a more standardized check for what
is and what isn't a git repository but also gives a slight behavioral
change. We will now detect and respect bare and empty nested git
repositories (only init run). Update t7300 to reflect this.

The time to clean an untracked directory containing 100000 sub
directories went from 61s to 1.7s after this change.

Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
---
 builtin/clean.c  | 24 ++++++++++++++++++++----
 t/t7300-clean.sh |  4 ++--
 2 files changed, 22 insertions(+), 6 deletions(-)

diff --git a/builtin/clean.c b/builtin/clean.c
index 98c103f..b679913 100644
--- a/builtin/clean.c
+++ b/builtin/clean.c
@@ -10,7 +10,6 @@
 #include "cache.h"
 #include "dir.h"
 #include "parse-options.h"
-#include "refs.h"
 #include "string-list.h"
 #include "quote.h"
 #include "column.h"
@@ -148,6 +147,25 @@ static int exclude_cb(const struct option *opt, const char *arg, int unset)
 	return 0;
 }
 
+static int is_git_repository(struct strbuf *path)
+{
+	int ret = 0;
+	if (is_git_directory(path->buf))
+		ret = 1;
+	else {
+		size_t orig_path_len = path->len;
+		assert(orig_path_len != 0);
+		if (path->buf[orig_path_len - 1] != '/')
+			strbuf_addch(path, '/');
+		strbuf_addstr(path, ".git");
+		if (is_git_directory(path->buf))
+			ret = 1;
+		strbuf_setlen(path, orig_path_len);
+	}
+
+	return ret;
+}
+
 static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,
 		int dry_run, int quiet, int *dir_gone)
 {
@@ -155,13 +173,11 @@ static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,
 	struct strbuf quoted = STRBUF_INIT;
 	struct dirent *e;
 	int res = 0, ret = 0, gone = 1, original_len = path->len, len;
-	unsigned char submodule_head[20];
 	struct string_list dels = STRING_LIST_INIT_DUP;
 
 	*dir_gone = 1;
 
-	if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
-			!resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
+	if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) && is_git_repository(path)) {
 		if (!quiet) {
 			quote_path_relative(path->buf, prefix, &quoted);
 			printf(dry_run ?  _(msg_would_skip_git_dir) : _(msg_skip_git_dir),
diff --git a/t/t7300-clean.sh b/t/t7300-clean.sh
index 58e6b4a..da294fe 100755
--- a/t/t7300-clean.sh
+++ b/t/t7300-clean.sh
@@ -455,7 +455,7 @@ test_expect_success 'nested git work tree' '
 	! test -d bar
 '
 
-test_expect_failure 'nested git (only init) should be kept' '
+test_expect_success 'nested git (only init) should be kept' '
 	rm -fr foo bar &&
 	git init foo &&
 	mkdir bar &&
@@ -465,7 +465,7 @@ test_expect_failure 'nested git (only init) should be kept' '
 	test_path_is_missing bar
 '
 
-test_expect_failure 'nested git (bare) should be kept' '
+test_expect_success 'nested git (bare) should be kept' '
 	rm -fr foo bar &&
 	git init --bare foo &&
 	mkdir bar &&
-- 
2.4.0.rc0.37.ga3b75b3

Re: [PATCH v2 3/3] clean: improve performance when removing lots of directories

[Junio C Hamano]

Erik Elfström <erik.elfstrom@gmail.com> writes:

> Before this change, clean used resolve_gitlink_ref to check for the
> presence of nested git repositories. This had the drawback of creating
> a ref_cache entry for every directory that should potentially be
> cleaned. The linear search through the ref_cache list caused a massive
> performance hit for large number of directories.

I'd prefer to see the "current state" described in the current
tense, e.g.

    "git clean" uses resolve_gitlink_ref() to check for the presence of
    nested git repositories, but it has the drawback of creating a
    ref_cache entry for every directory that should potentially be
    cleaned. The linear search through the ref_cache list causes a
    massive performance hit for large number of directories.

> Teach clean.c:remove_dirs to use setup.c:is_git_directory
> instead. is_git_directory will actually open HEAD and parse the HEAD
> ref but this implies a nested git repository and should be rare when
> cleaning.

I am not sure what you wanted to say in this paragraph.  What does
it being rare have to do with it?  Even if it is not rare (i.e. the
top-level project you are working with has many submodules checked
out without using the more recent "a file .git pointing into
.git/modules/ via 'gitdir: $overThere'" mechanism), if we found a
nested git repository, we treat it as special and exclude it from
cleaning it out, which is a good thing, no?

Doesn't this implementation get confused by modern submodule
checkouts and descend into and clean their working tree, though?
Module M with path P would have a directory P in the working tree of
the top-level project, and P/.git is a regular file that will fail
"is_git_directory()" test but records the location of the real
submodule repository i.e. ".git/modules/M" via the "gitdir:"
mechanism.

> Using is_git_directory should give a more standardized check for what
> is and what isn't a git repository but also gives a slight behavioral
> change. We will now detect and respect bare and empty nested git
> repositories (only init run). Update t7300 to reflect this.
>
> The time to clean an untracked directory containing 100000 sub
> directories went from 61s to 1.7s after this change.
>
> Helped-by: Jeff King <peff@peff.net>
> Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
> ---
>  builtin/clean.c  | 24 ++++++++++++++++++++----
>  t/t7300-clean.sh |  4 ++--
>  2 files changed, 22 insertions(+), 6 deletions(-)
>
> diff --git a/builtin/clean.c b/builtin/clean.c
> index 98c103f..b679913 100644
> --- a/builtin/clean.c
> +++ b/builtin/clean.c
> @@ -10,7 +10,6 @@
>  #include "cache.h"
>  #include "dir.h"
>  #include "parse-options.h"
> -#include "refs.h"
>  #include "string-list.h"
>  #include "quote.h"
>  #include "column.h"
> @@ -148,6 +147,25 @@ static int exclude_cb(const struct option *opt, const char *arg, int unset)
>  	return 0;
>  }
>  
> +static int is_git_repository(struct strbuf *path)
> +{
> +	int ret = 0;
> +	if (is_git_directory(path->buf))
> +		ret = 1;
> +	else {
> +		size_t orig_path_len = path->len;
> +		assert(orig_path_len != 0);
> +		if (path->buf[orig_path_len - 1] != '/')
> +			strbuf_addch(path, '/');
> +		strbuf_addstr(path, ".git");
> +		if (is_git_directory(path->buf))
> +			ret = 1;
> +		strbuf_setlen(path, orig_path_len);
> +	}
> +
> +	return ret;
> +}
> +
>  static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,
>  		int dry_run, int quiet, int *dir_gone)
>  {
> @@ -155,13 +173,11 @@ static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,
>  	struct strbuf quoted = STRBUF_INIT;
>  	struct dirent *e;
>  	int res = 0, ret = 0, gone = 1, original_len = path->len, len;
> -	unsigned char submodule_head[20];
>  	struct string_list dels = STRING_LIST_INIT_DUP;
>  
>  	*dir_gone = 1;
>  
> -	if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
> -			!resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
> +	if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) && is_git_repository(path)) {
>  		if (!quiet) {
>  			quote_path_relative(path->buf, prefix, &quoted);
>  			printf(dry_run ?  _(msg_would_skip_git_dir) : _(msg_skip_git_dir),
> diff --git a/t/t7300-clean.sh b/t/t7300-clean.sh
> index 58e6b4a..da294fe 100755
> --- a/t/t7300-clean.sh
> +++ b/t/t7300-clean.sh
> @@ -455,7 +455,7 @@ test_expect_success 'nested git work tree' '
>  	! test -d bar
>  '
>  
> -test_expect_failure 'nested git (only init) should be kept' '
> +test_expect_success 'nested git (only init) should be kept' '
>  	rm -fr foo bar &&
>  	git init foo &&
>  	mkdir bar &&
> @@ -465,7 +465,7 @@ test_expect_failure 'nested git (only init) should be kept' '
>  	test_path_is_missing bar
>  '
>  
> -test_expect_failure 'nested git (bare) should be kept' '
> +test_expect_success 'nested git (bare) should be kept' '
>  	rm -fr foo bar &&
>  	git init --bare foo &&
>  	mkdir bar &&

Re: [PATCH v2 3/3] clean: improve performance when removing lots of directories

[erik elfström]

On Wed, Apr 15, 2015 at 7:56 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Erik Elfström <erik.elfstrom@gmail.com> writes:
>
>> Before this change, clean used resolve_gitlink_ref to check for the
>> presence of nested git repositories. This had the drawback of creating
>> a ref_cache entry for every directory that should potentially be
>> cleaned. The linear search through the ref_cache list caused a massive
>> performance hit for large number of directories.
>
> I'd prefer to see the "current state" described in the current
> tense, e.g.
>
>     "git clean" uses resolve_gitlink_ref() to check for the presence of
>     nested git repositories, but it has the drawback of creating a
>     ref_cache entry for every directory that should potentially be
>     cleaned. The linear search through the ref_cache list causes a
>     massive performance hit for large number of directories.
>

Yes, that reads better.

>> Teach clean.c:remove_dirs to use setup.c:is_git_directory
>> instead. is_git_directory will actually open HEAD and parse the HEAD
>> ref but this implies a nested git repository and should be rare when
>> cleaning.
>
> I am not sure what you wanted to say in this paragraph.  What does
> it being rare have to do with it?  Even if it is not rare (i.e. the
> top-level project you are working with has many submodules checked
> out without using the more recent "a file .git pointing into
> .git/modules/ via 'gitdir: $overThere'" mechanism), if we found a
> nested git repository, we treat it as special and exclude it from
> cleaning it out, which is a good thing, no?
>

I was trying to motivate that the performance of is_git_directory is not a
problem for us even though it opens a file and parses it. I see now when I
read it again that this is not very clear.

> Doesn't this implementation get confused by modern submodule
> checkouts and descend into and clean their working tree, though?
> Module M with path P would have a directory P in the working tree of
> the top-level project, and P/.git is a regular file that will fail
> "is_git_directory()" test but records the location of the real
> submodule repository i.e. ".git/modules/M" via the "gitdir:"
> mechanism.
>

Yes, there is a problem here. I've added the test below and it fails after
my change by cleaning sub2 (sub1 is not cleaned). Are there more cases
here that I should test for?

+test_expect_success 'should not clean submodules' '
+       rm -fr repo to_clean sub1 sub2 &&
+       mkdir -p repo to_clean &&
+       (
+               cd repo &&
+               git init &&
+               >hello.world
+               git add . &&
+               git commit -a -m nested
+       ) &&
+       git submodule add ./repo/.git sub1 &&
+       git commit -m "sub1" &&
+       git branch before_sub2 &&
+       git submodule add ./repo/.git sub2 &&
+       git commit -m "sub2" &&
+       git checkout before_sub2 &&
+       >to_clean/should_clean.this &&
+       git clean -f -d &&
+       test_path_is_file repo/.git/index &&
+       test_path_is_file repo/hello.world &&
+       test_path_is_file sub1/.git &&
+       test_path_is_file sub1/hello.world &&
+       test_path_is_file sub2/.git &&
+       test_path_is_file sub2/hello.world &&
+       test_path_is_missing to_clean
+'

Base on the previous discussion of the patch topic I can see 3 options
for how to fix this:

Option 1:
 Plug the hole in my new is_git_repository function. A quick and dirty
 fix that passes the above test would be:

diff --git a/builtin/clean.c b/builtin/clean.c
index b679913..4f2fe95 100644
--- a/builtin/clean.c
+++ b/builtin/clean.c
@@ -153,14 +153,21 @@ static int is_git_repository(struct strbuf *path)
        if (is_git_directory(path->buf))
                ret = 1;
        else {
-               size_t orig_path_len = path->len;
-               assert(orig_path_len != 0);
-               if (path->buf[orig_path_len - 1] != '/')
-                       strbuf_addch(path, '/');
-               strbuf_addstr(path, ".git");
-               if (is_git_directory(path->buf))
-                       ret = 1;
-               strbuf_setlen(path, orig_path_len);
+               struct stat st;
+               const char *submodule_git_dir =
git_path_submodule(path->buf, "");
+               lstat(submodule_git_dir, &st);
+               if (S_ISDIR(st.st_mode))
+                       ret = 1;
+               else {
+                       size_t orig_path_len = path->len;
+                       assert(orig_path_len != 0);
+                       if (path->buf[orig_path_len - 1] != '/')
+                               strbuf_addch(path, '/');
+                       strbuf_addstr(path, ".git");
+                       if (is_git_directory(path->buf))
+                               ret = 1;
+                       strbuf_setlen(path, orig_path_len);
+               }
        }

        return ret;

There are probably more elegant solutions available here, suggestions
welcome.

Option 2:
 Go with the current solution of using resolve_gitlink_ref but either
 A) avoid placing non-submodule paths in the ref_cache list, or
 B) remove non-submodule paths from the ref_cache list after we
 have detected that they are not submodules.

Option 3:
 Speed up the ref_cache enough to make these dummy entires not matter.
 Nothing wrong with speeding up the lookup but it would still feel strange to
 populate it with junk entries.

Are there more options available?
What direction would you prefer?

>> Using is_git_directory should give a more standardized check for what
>> is and what isn't a git repository but also gives a slight behavioral
>> change. We will now detect and respect bare and empty nested git
>> repositories (only init run). Update t7300 to reflect this.
>>
>> The time to clean an untracked directory containing 100000 sub
>> directories went from 61s to 1.7s after this change.
>>
>> Helped-by: Jeff King <peff@peff.net>
>> Signed-off-by: Erik Elfström <erik.elfstrom@gmail.com>
>> ---
>>  builtin/clean.c  | 24 ++++++++++++++++++++----
>>  t/t7300-clean.sh |  4 ++--
>>  2 files changed, 22 insertions(+), 6 deletions(-)
>>
>> diff --git a/builtin/clean.c b/builtin/clean.c
>> index 98c103f..b679913 100644
>> --- a/builtin/clean.c
>> +++ b/builtin/clean.c
>> @@ -10,7 +10,6 @@
>>  #include "cache.h"
>>  #include "dir.h"
>>  #include "parse-options.h"
>> -#include "refs.h"
>>  #include "string-list.h"
>>  #include "quote.h"
>>  #include "column.h"
>> @@ -148,6 +147,25 @@ static int exclude_cb(const struct option *opt, const char *arg, int unset)
>>       return 0;
>>  }
>>
>> +static int is_git_repository(struct strbuf *path)
>> +{
>> +     int ret = 0;
>> +     if (is_git_directory(path->buf))
>> +             ret = 1;
>> +     else {
>> +             size_t orig_path_len = path->len;
>> +             assert(orig_path_len != 0);
>> +             if (path->buf[orig_path_len - 1] != '/')
>> +                     strbuf_addch(path, '/');
>> +             strbuf_addstr(path, ".git");
>> +             if (is_git_directory(path->buf))
>> +                     ret = 1;
>> +             strbuf_setlen(path, orig_path_len);
>> +     }
>> +
>> +     return ret;
>> +}
>> +
>>  static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,
>>               int dry_run, int quiet, int *dir_gone)
>>  {
>> @@ -155,13 +173,11 @@ static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,
>>       struct strbuf quoted = STRBUF_INIT;
>>       struct dirent *e;
>>       int res = 0, ret = 0, gone = 1, original_len = path->len, len;
>> -     unsigned char submodule_head[20];
>>       struct string_list dels = STRING_LIST_INIT_DUP;
>>
>>       *dir_gone = 1;
>>
>> -     if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
>> -                     !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
>> +     if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) && is_git_repository(path)) {
>>               if (!quiet) {
>>                       quote_path_relative(path->buf, prefix, &quoted);
>>                       printf(dry_run ?  _(msg_would_skip_git_dir) : _(msg_skip_git_dir),
>> diff --git a/t/t7300-clean.sh b/t/t7300-clean.sh
>> index 58e6b4a..da294fe 100755
>> --- a/t/t7300-clean.sh
>> +++ b/t/t7300-clean.sh
>> @@ -455,7 +455,7 @@ test_expect_success 'nested git work tree' '
>>       ! test -d bar
>>  '
>>
>> -test_expect_failure 'nested git (only init) should be kept' '
>> +test_expect_success 'nested git (only init) should be kept' '
>>       rm -fr foo bar &&
>>       git init foo &&
>>       mkdir bar &&
>> @@ -465,7 +465,7 @@ test_expect_failure 'nested git (only init) should be kept' '
>>       test_path_is_missing bar
>>  '
>>
>> -test_expect_failure 'nested git (bare) should be kept' '
>> +test_expect_success 'nested git (bare) should be kept' '
>>       rm -fr foo bar &&
>>       git init --bare foo &&
>>       mkdir bar &&

Re: [PATCH v2 3/3] clean: improve performance when removing lots of directories

[Jeff King]

On Fri, Apr 17, 2015 at 08:15:40PM +0200, erik elfström wrote:

> > Doesn't this implementation get confused by modern submodule
> > checkouts and descend into and clean their working tree, though?
> > Module M with path P would have a directory P in the working tree of
> > the top-level project, and P/.git is a regular file that will fail
> > "is_git_directory()" test but records the location of the real
> > submodule repository i.e. ".git/modules/M" via the "gitdir:"
> > mechanism.
> >
> 
> Yes, there is a problem here. I've added the test below and it fails after
> my change by cleaning sub2 (sub1 is not cleaned). Are there more cases
> here that I should test for?

I wonder about the opposite case, too (finding more repos than we used
to).

It looks like your patches will find bare repositories in the tree,
whereas the current code does not (it only cares about ".git"). AFAIK,
submodules will never exist as bare in the working tree. And I have seen
repositories which embed bare repos as test cases. Admittedly this is
because I work on projects that are related to git itself, but I don't
see a reason to regress this case if the submodule code doesn't get any
benefit.

> Base on the previous discussion of the patch topic I can see 3 options
> for how to fix this:
> 
> Option 1:
>  Plug the hole in my new is_git_repository function. A quick and dirty
>  fix that passes the above test would be:

I think that makes sense. It would be nice if you could just call
read_gitfile, but that function is very anxious to die on error. So the
prerequisite step would probably be to refactor that into a
read_gitfile_gently that returns an error code.

-Peff

PS Thank you for working on this. I have been quiet because I haven't
   had a chance to look over your patches carefully yet, but overall
   they look very promising.

Re: [PATCH v2 3/3] clean: improve performance when removing lots of directories

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

>> Option 1:
>>  Plug the hole in my new is_git_repository function. A quick and dirty
>>  fix that passes the above test would be:
>
> I think that makes sense. It would be nice if you could just call
> read_gitfile, but that function is very anxious to die on error. So the
> prerequisite step would probably be to refactor that into a
> read_gitfile_gently that returns an error code.

I agree.

I was looking at the repository discovery loop to see if it makes
sense to update is-git-directory() to take a gitfile, but I do not
think it is a good idea (typically after is-git-directory() says
"yes", we would append paths e.g. "refs/heads/master" after it to
pass the result to system calls like open()).  I agree that adding
read-gitfile-gently and call it before running is-git-directory
would be a good solution for this change.

> PS Thank you for working on this.

That too.

Thanks.

Re: [PATCH v2 0/3] Improving performance of git clean

[Eric Sunshine]

On Sat, Apr 11, 2015 at 12:43 PM, Erik Elfström <erik.elfstrom@gmail.com> wrote:
> v1 of the patch can be found here:
> http://thread.gmane.org/gmane.comp.version-control.git/266839/focus=266839
>
> changes in v2:
> * fixed commit message,
>   "p7300: added performance tests for clean"
>   change to:
>   "p7300: add performance tests for clean"
> * simplified test code
> * removed non portable ls -A in test
> * removed non portable $(seq ) in test
> * fixed missing " || return $?" in test
> * fixed missing sub shell for 'cd' command in test
> * fixed broken && chains in test
> * added assert new clean.c:is_git_repository to guard against
>   negative array index
> * use size_t instead of int for strbuf->len
>
> fixes held back for cleanup patches:
> * fixed existing broken && chains
> * added assert in existing code to guard against
>   negative array index
>
> Thanks to Eric Sunshine and Torsten Bögershausen for the very helpful
> review!

Thanks. This version looks much better.