threads / discuss / 16178

Slow "git rev-list origin/master --not --all" or "git fetch" slow when downloading nothing

Subject: Slow "git rev-list origin/master --not --all" or "git fetch" slow when downloading nothing

## tl;dr

5 messages between Nov 5, 2008 and Nov 5, 2008.

replies: 4people: 3as markdown or json

Santi Béjar· Nov 5, 2008, 09:38 UTC · lore
Hi *,
  In cold cache "git rev-list origin/master --not --all" is slow
reading many files:

cold cache: $ /usr/bin/time git rev-list origin/master --not --all 0.03user 0.02system 0:04.57elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k 77848inputs+0outputs (410major+1798minor)pagefaults 0swaps

hot cache: $ /usr/bin/time git rev-list origin/master --not --all 0.01user 0.00system 0:00.06elapsed 31%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+2207minor)pagefaults 0swaps

I think that, in this particular case (when the arguments are the tips of some of the branches), this should not read that many files.

Moreover, this is used in "git fetch" (git rev-list --quiet --objects <list_of_remote_sha1> --not --all) to detect if all the objects are reachable from the local repository. When nothing has changed in the remote repository (so refs/<remote>/* has all the remote refs) the "git fetch" could be almost instantaneous (even in coldcache), but currently it is not because of the above.

Thanks, Santi

Junio C Hamano· Nov 5, 2008, 17:32 UTC · re: Santi Béjar · lore

Re* Slow "git rev-list origin/master --not --all" or "git fetch" slow when downloading nothing

"Santi Béjar" <santi@agolina.net> writes:
Show 15 quoted lines
>   In cold cache "git rev-list origin/master --not --all" is slow
> reading many files:
>
> cold cache:
> $ /usr/bin/time git rev-list origin/master --not --all
> 0.03user 0.02system 0:04.57elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
> 77848inputs+0outputs (410major+1798minor)pagefaults 0swaps
>
> hot cache:
> $ /usr/bin/time git rev-list origin/master --not --all
> 0.01user 0.00system 0:00.06elapsed 31%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+2207minor)pagefaults 0swaps
>
> I think that, in this particular case (when the arguments are the tips
> of some of the branches), this should not read that many files.

What kind of "many files" are you making git read? Do you have too many unpacked refs? Too many loose objects?

> ... When nothing has changed in the remote repository (so
> refs/<remote>/* has all the remote refs) the "git fetch" could be almost
> instantaneous (even in coldcache),...
You at least need to read:
 - what "--all" refs point at; to find this out, you need to read all
   unpacked refs files, and one packed-refs file;
 - commit objects that these refs point at; to cull refs that do not point
   at committish and dereference tag objects that point at commit, you
   need to read these objects (either loose objects or in packs);
 - commit objects on the ancestry graph starting from the commit pointed
   at by origin/master and the commits from "--all" refs, until your
   traversal from origin/master hit one of the ancestors of "--all" refs.

I noticed that when you "git pack-refs" (or "git gc"), we do not remove the leading directories of loose refs that become empty because of pruning. This can cause many opendir() when you used to have too many hierachy of refs even after packing them.

 dir.c       |   13 +++++++++----
 pack-refs.c |    5 +++++
 2 files changed, 14 insertions(+), 4 deletions(-)
diff --git c/dir.c w/dir.c
index 0131983..7241631 100644
--- c/dir.c
+++ w/dir.c
@@ -779,7 +779,12 @@ int is_inside_dir(const char *dir)
 	return get_relative_cwd(buffer, sizeof(buffer), dir) != NULL;
 }
 
-int remove_dir_recursively(struct strbuf *path, int only_empty)
+/*
+ * option:
+ * 1: remove empty directory;
+ * 2: remove empty subdirectories, but not the directory itself
+ */
+int remove_dir_recursively(struct strbuf *path, int option)
 {
 	DIR *dir = opendir(path->buf);
 	struct dirent *e;
@@ -803,9 +808,9 @@ int remove_dir_recursively(struct strbuf *path, int only_empty)
 		if (lstat(path->buf, &st))
 			; /* fall thru */
 		else if (S_ISDIR(st.st_mode)) {
-			if (!remove_dir_recursively(path, only_empty))
+			if (!remove_dir_recursively(path, !!option))
 				continue; /* happy */
-		} else if (!only_empty && !unlink(path->buf))
+		} else if (!option && !unlink(path->buf))
 			continue; /* happy, too */
 
 		/* path too long, stat fails, or non-directory still exists */
@@ -815,7 +820,7 @@ int remove_dir_recursively(struct strbuf *path, int only_empty)
 	closedir(dir);
 
 	strbuf_setlen(path, original_len);
-	if (!ret)
+	if (!ret && option != 2)
 		ret = rmdir(path->buf);
 	return ret;
 }
diff --git c/pack-refs.c w/pack-refs.c
index 2c76fb1..30fbae8 100644
--- c/pack-refs.c
+++ w/pack-refs.c
@@ -2,6 +2,7 @@
 #include "refs.h"
 #include "tag.h"
 #include "pack-refs.h"
+#include "dir.h"
 
 struct ref_to_prune {
 	struct ref_to_prune *next;
@@ -73,10 +74,14 @@ static void prune_ref(struct ref_to_prune *r)
 
 static void prune_refs(struct ref_to_prune *r)
 {
+	struct strbuf refs = STRBUF_INIT;
+
+	strbuf_addstr(&refs, git_path("refs"));
 	while (r) {
 		prune_ref(r);
 		r = r->next;
 	}
+	remove_dir_recursively(&refs, 2);
 }
 
 static struct lock_file packed;
Linus Torvalds· Nov 5, 2008, 17:37 UTC · re: Santi Béjar · lore

Re: Slow "git rev-list origin/master --not --all" or "git fetch" slow when downloading nothing

On Wed, 5 Nov 2008, Santi Béjar wrote:
> 
>   In cold cache "git rev-list origin/master --not --all" is slow
> reading many files:
Hmm. It sounds like you possibly don't have packed refs. 
Have you done "git gc" on that thing lately? What does "strace" say?
		Linus
Santi Béjar· Nov 5, 2008, 21:37 UTC · re: Linus Torvalds · lore

Re: Slow "git rev-list origin/master --not --all" or "git fetch" slow when downloading nothing

On Wed, Nov 5, 2008 at 6:37 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote:

Show 6 quoted lines
>
>
> On Wed, 5 Nov 2008, Santi Béjar wrote:
>>
>>   In cold cache "git rev-list origin/master --not --all" is slow
>> reading many files:
Sorry, s/files/data/
>
> Hmm. It sounds like you possibly don't have packed refs.
They are packed up to v2.6.27.
Show 5 quoted lines
>
> Have you done "git gc" on that thing lately? What does "strace" say?
>
>                Linus
>

It is a recently cloned linux-2.6 repo, with 10 or so packs and 70 loose objects. It spends a good fraction in:

brk(0x8318000)                          = 0x8318000
and
mmap2(NULL, 33554432, PROT_READ, MAP_PRIVATE, 4, 0x2000) = 0xb2227000
(strace attatched).
I should have given more info:

It is an old computer (Pentium 4 2.5 GHz) and the repo is on an external USB drive.

On Wed, Nov 5, 2008 at 6:32 PM, Junio C Hamano <gitster@pobox.com> wrote:
Show 21 quoted lines
> "Santi Béjar" <santi@agolina.net> writes:
>
>>   In cold cache "git rev-list origin/master --not --all" is slow
>> reading many files:
>>
>> cold cache:
>> $ /usr/bin/time git rev-list origin/master --not --all
>> 0.03user 0.02system 0:04.57elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
>> 77848inputs+0outputs (410major+1798minor)pagefaults 0swaps
>>
>> hot cache:
>> $ /usr/bin/time git rev-list origin/master --not --all
>> 0.01user 0.00system 0:00.06elapsed 31%CPU (0avgtext+0avgdata 0maxresident)k
>> 0inputs+0outputs (0major+2207minor)pagefaults 0swaps
>>
>> I think that, in this particular case (when the arguments are the tips
>> of some of the branches), this should not read that many files.
>
> What kind of "many files" are you making git read?  Do you have too many
> unpacked refs?  Too many loose objects?
>
See above.
Show 16 quoted lines
>> ... When nothing has changed in the remote repository (so
>> refs/<remote>/* has all the remote refs) the "git fetch" could be almost
>> instantaneous (even in coldcache),...
>
> You at least need to read:
>
>  - what "--all" refs point at; to find this out, you need to read all
>   unpacked refs files, and one packed-refs file;
>
>  - commit objects that these refs point at; to cull refs that do not point
>   at committish and dereference tag objects that point at commit, you
>   need to read these objects (either loose objects or in packs);
>
>  - commit objects on the ancestry graph starting from the commit pointed
>   at by origin/master and the commits from "--all" refs, until your
>   traversal from origin/master hit one of the ancestors of "--all" refs.

Yes, in the general case it is, but in this case we can bypass the checking of the --all refs after checking if all the given refs are equal to some of the --all refs.

For me the main thing is the slow "git fetch" when downloading nothing. I think it was/is faster without the quickfetch path (at least in the coldcache case). Maybe we can just check if the new fetched refs are already the tips of the corresponding remote branch.

Santi
Linus Torvalds· Nov 5, 2008, 22:08 UTC · re: Santi Béjar · lore

Re: Slow "git rev-list origin/master --not --all" or "git fetch" slow when downloading nothing

On Wed, 5 Nov 2008, Santi Béjar wrote:
> >
> > Hmm. It sounds like you possibly don't have packed refs.
> 
> They are packed up to v2.6.27.

Yeah, your strace isn't at all horrible. You don't open very many files at all, and you don't have any big directories.

The biggest cost when things are cold-cache is probably the seeking from just opening all those index files.

> It is an old computer (Pentium 4 2.5 GHz) and the repo is on an external 
> USB drive.

There should be basically no CPU spent on that load, so your computer is fine. But I think the issue is the dog-slow IO on the USB drive, especially since there are multiple pack-files and thus index files.

Your strace would be more interesting with "-Ttt", but much of the cost is likely in the page faulting of the mmap'ed data, and none of that would show up in the trace, except indirectly (ie just looking at the times between the system calls).

> Yes, in the general case it is, but in this case we can bypass the
> checking of the --all refs after checking if all the given refs are
> equal to some of the --all refs.

I don't think we'll actually walk anything, because all commits will end up being negative.

But we'll look up the objects for even the negative commits, yes. So we're doing several "unnecessary" object lookups, and in that sense we could make this much faster by not even bothering to look them up.

But we do that to validate that the refs are _valid_, so in that sense the object lookup is not "unnecessary" at all. Oh, and we need to peel them to see if they are tag objects, in order to mark the _commit_ uninteresting if the object itself was uninteresting.

So in practice we do end up having to pretty much parse them all. 

We could do some crazy special case for the empty set, but it would be better to see if you can improve performance with a slow disk some other, less hacky, way. If you use a USB stick to move between machines, maybe you can make sure that it's fully packed (ie a single index file) before moving it to the USB stick? That would likely help quite a bit.

		Linus

← back to recent threads