git clean performance issues

Hi,

I'm having a performance issue with "git clean -qxfd" (note, not using
"-ff").

The performance issue shows up when trying to clean untracked
directories that themselves contain many sub directories. The
performance is highly non linear with the number of sub
directories. Some test numbers:

Dirs    Time
10000   0m0.754s
50000   0m16.606s
100000  1m31.418s

When running "git clean -qxffd" (note, using "-ff") the performance is
fast and linear:

Dirs    Time
10000   0m0.158s
50000   0m0.918s
100000  0m1.639s

After checking the source of git-clean my understanding of the problem
is as follows:

When clean.c:cmd_clean finds a directory and the "-d" flag is given it
will call clean.c:remove_dirs to potentially remove the directory and
all sub directories.

Unless "-ff" is given remove_dirs tries to be nice and not remove
directories containing other git repositories. To do this it does the
following check:

    ...
    if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&
            !resolve_gitlink_ref(path->buf, "HEAD", submodule_head)) {
    ...

The problem is that refs.c:resolve_gitlink_ref will call
refs.c:get_ref_cache that will linearly search a linked list of cache
entries and create and insert a new ref_cache entry in the list for
each path it is given if it fails to find an existing entry:

    for (refs = submodule_ref_caches; refs; refs = refs->next)
        if (!strcmp(submodule, refs->name))
            return refs;

    refs = create_ref_cache(submodule);
    refs->next = submodule_ref_caches;
    submodule_ref_caches = refs;
    return refs;

In my scenario get_ref_cache will be called 10000+ times, each time
with a new path. The final few calls will need to search through and
compare 10000+ entries before realizing that there is no existing
entry. This quickly ads up to 100 million+ calls to strcmp().

From what I can understand, the calls to get_ref_cache in this

scenario will never do any useful work. Is this correct? If so, would
it be possible to bypass it, maybe by calling
resolve_gitlink_ref_recursive directly or by using some other way of
checking for the presence of a git repo in clean.c:remove_dirs?

/Erik

On Sat, Apr 04, 2015 at 08:32:45PM +0200, erik elfström wrote:

In my scenario get_ref_cache will be called 10000+ times, each time
with a new path. The final few calls will need to search through and
compare 10000+ entries before realizing that there is no existing
entry. This quickly ads up to 100 million+ calls to strcmp().

From what I can understand, the calls to get_ref_cache in this
scenario will never do any useful work. Is this correct? If so, would
it be possible to bypass it, maybe by calling
resolve_gitlink_ref_recursive directly or by using some other way of
checking for the presence of a git repo in clean.c:remove_dirs?

I think this is the same issue that was discussed here:

  http://thread.gmane.org/gmane.comp.version-control.git/265560/focus=265585

There is some discussion of a possible fix in that thread. I was hoping
that Andreas was going to look further and produce a patch, but I
imagine he got busy with other things. Do you want to try picking it up?

-Peff

That looks like the same issue. The "use is_git_directory" approach
sounds good to me, is that the direction you would prefer? I can try
to cobble something together although I must warn you I have zero
previous experience with this code base so a few iterations will
probably be needed.

/Erik

On Sat, Apr 4, 2015 at 9:55 PM, Jeff King [off-list ref] wrote:

On Sat, Apr 04, 2015 at 08:32:45PM +0200, erik elfström wrote:

quoted

In my scenario get_ref_cache will be called 10000+ times, each time
with a new path. The final few calls will need to search through and
compare 10000+ entries before realizing that there is no existing
entry. This quickly ads up to 100 million+ calls to strcmp().

From what I can understand, the calls to get_ref_cache in this
scenario will never do any useful work. Is this correct? If so, would
it be possible to bypass it, maybe by calling
resolve_gitlink_ref_recursive directly or by using some other way of
checking for the presence of a git repo in clean.c:remove_dirs?

I think this is the same issue that was discussed here:

  http://thread.gmane.org/gmane.comp.version-control.git/265560/focus=265585

There is some discussion of a possible fix in that thread. I was hoping
that Andreas was going to look further and produce a patch, but I
imagine he got busy with other things. Do you want to try picking it up?

-Peff

On Sat, Apr 04, 2015 at 10:39:47PM +0200, erik elfström wrote:

That looks like the same issue. The "use is_git_directory" approach
sounds good to me, is that the direction you would prefer? I can try
to cobble something together although I must warn you I have zero
previous experience with this code base so a few iterations will
probably be needed.

Yeah, I think the preferred direction is building a solution in
is_git_directory. Multiple iterations are fine. That's what review is
for. :) See SubmittingPatches for tips, though.

-Peff

On Sat, 04 Apr 2015 15:55:07 +0000, Jeff King wrote:
...

I think this is the same issue that was discussed here:

  http://thread.gmane.org/gmane.comp.version-control.git/265560/focus&5585

There is some discussion of a possible fix in that thread. I was hoping
that Andreas was going to look further and produce a patch, but I
imagine he got busy with other things.

That about sums it up. However I now have a similar issue;
git ls-files shows the same behaviour (takes relatively
forever at 100% CPU), and runs instantly with my patch
from back then. Nothing seems to have changed, so I
may have another chance to look into this.

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800

On Fri, Nov 13, 2015 at 03:19:07PM +0100, Andreas Krey wrote:

On Sat, 04 Apr 2015 15:55:07 +0000, Jeff King wrote:
...

quoted

I think this is the same issue that was discussed here:

  http://thread.gmane.org/gmane.comp.version-control.git/265560/focus&5585

There is some discussion of a possible fix in that thread. I was hoping
that Andreas was going to look further and produce a patch, but I
imagine he got busy with other things.

That about sums it up. However I now have a similar issue;
git ls-files shows the same behaviour (takes relatively
forever at 100% CPU), and runs instantly with my patch
from back then. Nothing seems to have changed, so I
may have another chance to look into this.

Yeah, I think Erik's patch in 0179ca7 (clean: improve performance when
removing lots of directories, 2015-06-15) handles the git-clean case the
way we want to, but all of the other calls to resolve_gitlink_ref need
to be inspected and fixed similarly.

The one your are hitting with ls-files is probably in dir.c:treat_directory.

-Peff