Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object
Junio C Hamanowrites: >> Yes. But I think the default limit for the number of loose objects, 7000, >> gives us small overhead when we do enumeration of all objects. > > Hmph, I didn't see the code that does the estimation of loose object > count before starting to enumerate, though. Another thing the code could do to avoid negative consequences on projects that look quite different from yours (e.g. the other side does not have insane number of refs, but there are locally quite a few loose objects) is to count how many entries are on *refs list before we decide to enumerate all loose objects. When the refs list is relatively shorter than the estimated number of loose objects (you can actually do the estimation based on sampling, or just rely on your assumed 7k), it may be a win _not_ to trigger the new code you are adding to this codepath with this patch. I would imagine that the simplest implementaion may just count for (ref = *refs, count = 0; ref && count++ < LIMIT; ref = ref->next) ; use_oidset_optim = (LIMIT <= count); assuming your "up to 7k loose objects" and then experimenting to determine the LIMIT which is a rough number of refs that makes the oidset optimization worthwhile. We need a bit better/descriptive name for the LIMIT, if we go that route, though. Thanks.
Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object
Takuto Ikutawrites: > Yes, I just wanted to say 'git fetch' invokes fetch-pack. > fetch-pack is skipped when running git fetch repeatedly while > remote has no update by quickfetch. So I disabled it to see the > performance of fetch-pack. In chromium repository, master branch > is updated several times in an hour, so git fetch invokes fetch-pack > in such frequency. I do understand that if you run "git fetch" against the same place in quick succession three times, the first one may cost a lot (not just that it has to do the everything_local() computation that you care about, it also has to actually do the network transfer), while the second and third ones that are done before anything new happens on the other end will not involve everything_local() overhead thanks to quickfetch. A "fetch" that is run against a remote that has nothing new, but still triggers everything_local() only because quickfetch is disabled, is an artificial case that has no relevance to the real world, I suspect, because the quickfetch optimization is to solve the "there is nothing to be done, still do_fetch_pack() spends so much cycles only to realize that it does not have anything to do, why?" issue. Isn't running the "git fetch" command with the "--dry-run" option many times in quick succession a lot closer to what you really want to measure, I wonder? That way, your first fetch won't be touching the state of the local side to affect your second and subsequent fetches. >> In any case, do_fetch_pack() tries to see if all of the tip commits >> we are going to fetch exist locally, so when you are trying a fetch >> that grabs huge number of refs (by the way, it means that the first >> sentence of the proposed log message is not quite true---it is "When >> fetching a large number of refs", as it does not matter how many >> refs _we_ have, no?), everything_local() ends up making repeated >> calls to has_object_file_with_flags() to all of the refs. > > I fixed description by changing 'refs' to 'remote refs'. In my understanding, > git tries to check existence of remote refs even if we won't fetch such refs. During fetch, everything_local() tries to mark common part by walking the refs the other side advertised upon the first contact, so it is correct that the number of checks is not reduced in a fetch that does not fetch many refs, but the number of remote-tracking refs you have has no effect, so I doubt such a rephrasing would make the description more understandable. "When fetching from a repository with large number of refs" is probably what you want to say, no? > Yes. But I think the default limit for the number of loose objects, 7000, > gives us small overhead when we do enumeration of all objects. Hmph, I didn't see the code that does the estimation of loose object count before starting to enumerate, though. >> Hmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc >> ("sha1_file: teach sha1_object_info_extended more flags", >> 2017-06-21), but since 8b4c0103 ("sha1_file: support lazily fetching >> missing objects", 2017-12-08) it appears that passing >> OBJECT_INFO_QUICK down the codepath does not do anything >> interesting. Jonathan (cc'ed), are all remaining hits from "git >> grep OBJECT_INFO_QUICK" all dead no-ops these days? > > Yes the flag is no-op now, but let me untouched the flag in this patch. Yeah, I do not want you to be touching that in this change. It is an independent/orthogonal clean-up. Thanks.
Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object
2018-03-09 3:42 GMT+09:00 Junio C Hamano: > Takuto Ikuta writes: >> This patch stores existing loose objects in hashmap beforehand and use >> it to check existence instead of using lstat. >> >> With this patch, the number of lstat calls in `git fetch` is reduced >> from 411412 to 13794 for chromium repository. >> >> I took time stat of `git fetch` disabling quickfetch for chromium >> repository 3 time on linux with SSD. > > Now you drop a clue that would help to fill in the blanks above, but > I am not sure what the significance of your having to disable > quickfetch in order to take measurements---it makes it sound as if > it is an articificial problem that does not exist in real life > (i.e. when quickfetch is not disabled), but I am getting the feeling > that it is not what you wanted to say here. > Yes, I just wanted to say 'git fetch' invokes fetch-pack. fetch-pack is skipped when running git fetch repeatedly while remote has no update by quickfetch. So I disabled it to see the performance of fetch-pack. In chromium repository, master branch is updated several times in an hour, so git fetch invokes fetch-pack in such frequency. > In any case, do_fetch_pack() tries to see if all of the tip commits > we are going to fetch exist locally, so when you are trying a fetch > that grabs huge number of refs (by the way, it means that the first > sentence of the proposed log message is not quite true---it is "When > fetching a large number of refs", as it does not matter how many > refs _we_ have, no?), everything_local() ends up making repeated > calls to has_object_file_with_flags() to all of the refs. > I fixed description by changing 'refs' to 'remote refs'. In my understanding, git tries to check existence of remote refs even if we won't fetch such refs. > I like the idea---this turns "for each of these many things, check > if it exists with lstat(2)" into "enumerate what exists with > lstat(2), and then use that for the existence test"; if you need to > try N objects for existence, and you only have M objects loose where > N is vastly larger than M, it will be a huge win. If you have very > many loose objects and checking only a handful of objects for > existence check, you would lose big, though, no? > Yes. But I think the default limit for the number of loose objects, 7000, gives us small overhead when we do enumeration of all objects. >> diff --git a/fetch-pack.c b/fetch-pack.c >> index d97461296..1658487f7 100644 >> --- a/fetch-pack.c >> +++ b/fetch-pack.c >> @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj) >> mark_complete(>oid); >> } >> >> +static int add_loose_objects_to_set(const struct object_id *oid, >> + const char *path, >> + void *data) >> +{ >> + struct oidset* set = (struct oidset*)(data); > > Style: in our codebase, asterisk does not stick to the type. > > struct oidset *set = (struct oidset *)(data); > >> @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args >> *args, >> int retval; >> int old_save_commit_buffer = save_commit_buffer; >> timestamp_t cutoff = 0; >> + struct oidset loose_oid_set = OIDSET_INIT; >> + >> + for_each_loose_object(add_loose_objects_to_set, _oid_set, 0); > > OK, so this is the "enumerate all loose objects" phase. > >> save_commit_buffer = 0; >> >> for (ref = *refs; ref; ref = ref->next) { >> struct object *o; >> + unsigned int flag = OBJECT_INFO_QUICK; > > Hmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc > ("sha1_file: teach sha1_object_info_extended more flags", > 2017-06-21), but since 8b4c0103 ("sha1_file: support lazily fetching > missing objects", 2017-12-08) it appears that passing > OBJECT_INFO_QUICK down the codepath does not do anything > interesting. Jonathan (cc'ed), are all remaining hits from "git > grep OBJECT_INFO_QUICK" all dead no-ops these days? > Yes the flag is no-op now, but let me untouched the flag in this patch. >> diff --git a/sha1_file.c b/sha1_file.c >> index 1b94f39c4..c903cbcec 100644 >> --- a/sha1_file.c >> +++ b/sha1_file.c >> @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char >> *sha1, struct object_info *oi, >> if (find_pack_entry(real, )) >> break; >> >> + if (flags & OBJECT_INFO_SKIP_LOOSE) >> + return -1; >> + > > I cannot quite convince myself that this is done at the right layer; > it smells to be at a bit too low a layer. This change makes sense > only to a caller that is interested in the existence test. If the > flag is named after what it does, i.e. "ignore loose object", then > it does sort-of make sense, though. > Couldn't come up with good alternative for this, I followed your flag name suggestion in patch v3. Takuto
Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object
2018-03-09 2:19 GMT+09:00 René Scharfe: > Am 08.03.2018 um 13:06 schrieb Takuto Ikuta: >> +static int add_loose_objects_to_set(const struct object_id *oid, >> + const char *path, >> + void *data) >> +{ >> + struct oidset* set = (struct oidset*)(data); > > This cast is not needed (unlike in C++). And the asterisk should be stuck > to the variable, not the type (see Documentation/CodingGuidelines). > >> + oidset_insert(set, oid); > > In fact, you could just put "data" in here instead of "set" (without a > cast), with no loss in readability or safety. > Thank you for review, changed to use data directly in v2. >> + return 0; >> +} >> + >> static int everything_local(struct fetch_pack_args *args, >> struct ref **refs, >> struct ref **sought, int nr_sought) >> @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args >> *args, >> int retval; >> int old_save_commit_buffer = save_commit_buffer; >> timestamp_t cutoff = 0; >> + struct oidset loose_oid_set = OIDSET_INIT; >> + >> + for_each_loose_object(add_loose_objects_to_set, _oid_set, 0); >> >> save_commit_buffer = 0; >> >> for (ref = *refs; ref; ref = ref->next) { >> struct object *o; >> + unsigned int flag = OBJECT_INFO_QUICK; >> >> - if (!has_object_file_with_flags(>old_oid, >> - OBJECT_INFO_QUICK)) >> - continue; >> + if (!oidset_contains(_oid_set, >old_oid)) >> + flag |= OBJECT_INFO_SKIP_LOOSE; >> >> + if (!has_object_file_with_flags(>old_oid, flag)) >> + continue; >> o = parse_object(>old_oid); >> if (!o) >> continue; >> @@ -744,6 +758,8 @@ static int everything_local(struct fetch_pack_args *args, >> } >> } >> >> + oidset_clear(_oid_set); >> + > > This part looks fine to me. (Except perhaps call the variable "flags" > because you sometimes have two?) > Changed flag names. > Why not include packed objects as well? Probably because packs have > indexes which can queried quickly to determine object existence, and > because there are only few loose objects in typical repositories, > right? > Correct. In my target repository, chromium, fetch-pack's slowness comes from many lstat to non-existing loose objects for remote refs. I focus on to remove such lstat. > A similar cache was introduced by cc817ca3ef (sha1_name: cache > readdir(3) results in find_short_object_filename()) to speed up > finding unambiguous shorts object hashes. I wonder if it could be > used here as well, but I don't see an easy way. > >> if (!args->no_dependents) { >> if (!args->deepen) { >> for_each_ref(mark_complete_oid, NULL); >> diff --git a/sha1_file.c b/sha1_file.c >> index 1b94f39c4..c903cbcec 100644 >> --- a/sha1_file.c >> +++ b/sha1_file.c >> @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char >> *sha1, struct object_info *oi, >> if (find_pack_entry(real, )) >> break; >> >> + if (flags & OBJECT_INFO_SKIP_LOOSE) >> + return -1; >> + >> /* Most likely it's a loose object. */ >> if (!sha1_loose_object_info(real, oi, flags)) >> return 0; >> > > This early return doesn't just skip checking loose objects. It > also skips reloading packs and fetching missing objects for > partial clones. That may not be a problem for fetch-pack, but > it means the flag has a misleading name. Do you get the same > performance improvement if you make it only skip that > sha1_loose_object_info() call? > I changed the flag name following Junio's suggestion. If we skip sha1_loose_object_info call, reprepare_packed_git(...) runs for every non-existing refs and git fetch becomes slower. Takuto
Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object
Takuto Ikutawrites: > In repository having large number of refs, lstat for non-existing loose > objects makes `git fetch` slow. It is not immediately clear how "large number of refs" and "lstat for loose objects" interact with each other to create a problem. "In repository having large number of refs, because such and such processing needs to do this and that, 'git fetch' ends up doing a lot of lstat(2) calls to see if many objects exist in the loose form, which makes it slow". Please fill in the blanks. > This patch stores existing loose objects in hashmap beforehand and use > it to check existence instead of using lstat. > > With this patch, the number of lstat calls in `git fetch` is reduced > from 411412 to 13794 for chromium repository. > > I took time stat of `git fetch` disabling quickfetch for chromium > repository 3 time on linux with SSD. Now you drop a clue that would help to fill in the blanks above, but I am not sure what the significance of your having to disable quickfetch in order to take measurements---it makes it sound as if it is an articificial problem that does not exist in real life (i.e. when quickfetch is not disabled), but I am getting the feeling that it is not what you wanted to say here. In any case, do_fetch_pack() tries to see if all of the tip commits we are going to fetch exist locally, so when you are trying a fetch that grabs huge number of refs (by the way, it means that the first sentence of the proposed log message is not quite true---it is "When fetching a large number of refs", as it does not matter how many refs _we_ have, no?), everything_local() ends up making repeated calls to has_object_file_with_flags() to all of the refs. I like the idea---this turns "for each of these many things, check if it exists with lstat(2)" into "enumerate what exists with lstat(2), and then use that for the existence test"; if you need to try N objects for existence, and you only have M objects loose where N is vastly larger than M, it will be a huge win. If you have very many loose objects and checking only a handful of objects for existence check, you would lose big, though, no? > diff --git a/fetch-pack.c b/fetch-pack.c > index d97461296..1658487f7 100644 > --- a/fetch-pack.c > +++ b/fetch-pack.c > @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj) > mark_complete(>oid); > } > > +static int add_loose_objects_to_set(const struct object_id *oid, > + const char *path, > + void *data) > +{ > + struct oidset* set = (struct oidset*)(data); Style: in our codebase, asterisk does not stick to the type. struct oidset *set = (struct oidset *)(data); > @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args > *args, > int retval; > int old_save_commit_buffer = save_commit_buffer; > timestamp_t cutoff = 0; > + struct oidset loose_oid_set = OIDSET_INIT; > + > + for_each_loose_object(add_loose_objects_to_set, _oid_set, 0); OK, so this is the "enumerate all loose objects" phase. > save_commit_buffer = 0; > > for (ref = *refs; ref; ref = ref->next) { > struct object *o; > + unsigned int flag = OBJECT_INFO_QUICK; Hmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc ("sha1_file: teach sha1_object_info_extended more flags", 2017-06-21), but since 8b4c0103 ("sha1_file: support lazily fetching missing objects", 2017-12-08) it appears that passing OBJECT_INFO_QUICK down the codepath does not do anything interesting. Jonathan (cc'ed), are all remaining hits from "git grep OBJECT_INFO_QUICK" all dead no-ops these days? > > - if (!has_object_file_with_flags(>old_oid, > - OBJECT_INFO_QUICK)) > - continue; > + if (!oidset_contains(_oid_set, >old_oid)) > + flag |= OBJECT_INFO_SKIP_LOOSE; > > + if (!has_object_file_with_flags(>old_oid, flag)) > + continue; Here, you want a way to say "I know this does not exist in the loose form, so check if it exists in a non-loose form", and that is why you invented the new flag. > diff --git a/sha1_file.c b/sha1_file.c > index 1b94f39c4..c903cbcec 100644 > --- a/sha1_file.c > +++ b/sha1_file.c > @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char > *sha1, struct object_info *oi, > if (find_pack_entry(real, )) > break; > > + if (flags & OBJECT_INFO_SKIP_LOOSE) > + return -1; > + I cannot quite convince myself that this is done at the right layer; it smells to be at a bit too low a layer. This change makes sense only to a caller that is interested in the existence test. If the flag is named after what it does, i.e. "ignore loose object", then it does sort-of make sense, though. > /* Most
Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object
Am 08.03.2018 um 13:06 schrieb Takuto Ikuta: > In repository having large number of refs, lstat for non-existing loose > objects makes `git fetch` slow. > > This patch stores existing loose objects in hashmap beforehand and use > it to check existence instead of using lstat. > > With this patch, the number of lstat calls in `git fetch` is reduced > from 411412 to 13794 for chromium repository. > > I took time stat of `git fetch` disabling quickfetch for chromium > repository 3 time on linux with SSD. > * with this patch > 8.105s > 8.309s > 7.640s > avg: 8.018s > > * master > 12.287s > 11.175s > 12.227s > avg: 11.896s > > On my MacBook Air which has slower lstat. > * with this patch > 14.501s > > * master > 1m16.027s Nice improvement! > > `git fetch` on slow disk will be improved largely. > > Signed-off-by: Takuto Ikuta> --- > cache.h | 2 ++ > fetch-pack.c | 22 +++--- > sha1_file.c | 3 +++ > 3 files changed, 24 insertions(+), 3 deletions(-) > > diff --git a/cache.h b/cache.h > index d06932ed0..db38db40e 100644 > --- a/cache.h > +++ b/cache.h > @@ -1773,6 +1773,8 @@ struct object_info { > #define OBJECT_INFO_SKIP_CACHED 4 > /* Do not retry packed storage after checking packed and loose storage */ > #define OBJECT_INFO_QUICK 8 > +/* Do not check loose object */ > +#define OBJECT_INFO_SKIP_LOOSE 16 > extern int sha1_object_info_extended(const unsigned char *, struct > object_info *, unsigned flags); > > /* > diff --git a/fetch-pack.c b/fetch-pack.c > index d97461296..1658487f7 100644 > --- a/fetch-pack.c > +++ b/fetch-pack.c > @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj) > mark_complete(>oid); > } > > +static int add_loose_objects_to_set(const struct object_id *oid, > + const char *path, > + void *data) > +{ > + struct oidset* set = (struct oidset*)(data); This cast is not needed (unlike in C++). And the asterisk should be stuck to the variable, not the type (see Documentation/CodingGuidelines). > + oidset_insert(set, oid); In fact, you could just put "data" in here instead of "set" (without a cast), with no loss in readability or safety. > + return 0; > +} > + > static int everything_local(struct fetch_pack_args *args, > struct ref **refs, > struct ref **sought, int nr_sought) > @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args > *args, > int retval; > int old_save_commit_buffer = save_commit_buffer; > timestamp_t cutoff = 0; > + struct oidset loose_oid_set = OIDSET_INIT; > + > + for_each_loose_object(add_loose_objects_to_set, _oid_set, 0); > > save_commit_buffer = 0; > > for (ref = *refs; ref; ref = ref->next) { > struct object *o; > + unsigned int flag = OBJECT_INFO_QUICK; > > - if (!has_object_file_with_flags(>old_oid, > - OBJECT_INFO_QUICK)) > - continue; > + if (!oidset_contains(_oid_set, >old_oid)) > + flag |= OBJECT_INFO_SKIP_LOOSE; > > + if (!has_object_file_with_flags(>old_oid, flag)) > + continue; > o = parse_object(>old_oid); > if (!o) > continue; > @@ -744,6 +758,8 @@ static int everything_local(struct fetch_pack_args *args, > } > } > > + oidset_clear(_oid_set); > + This part looks fine to me. (Except perhaps call the variable "flags" because you sometimes have two?) Why not include packed objects as well? Probably because packs have indexes which can queried quickly to determine object existence, and because there are only few loose objects in typical repositories, right? A similar cache was introduced by cc817ca3ef (sha1_name: cache readdir(3) results in find_short_object_filename()) to speed up finding unambiguous shorts object hashes. I wonder if it could be used here as well, but I don't see an easy way. > if (!args->no_dependents) { > if (!args->deepen) { > for_each_ref(mark_complete_oid, NULL); > diff --git a/sha1_file.c b/sha1_file.c > index 1b94f39c4..c903cbcec 100644 > --- a/sha1_file.c > +++ b/sha1_file.c > @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char > *sha1, struct object_info *oi, > if (find_pack_entry(real, )) > break; > > + if (flags & OBJECT_INFO_SKIP_LOOSE) > + return -1; > + > /* Most likely it's a loose object. */ > if (!sha1_loose_object_info(real, oi, flags)) > return 0; > This early return doesn't just skip checking loose objects. It also skips reloading packs and fetching missing objects for partial clones.
[PATCH] fetch-pack.c: use oidset to check existence of loose object
In repository having large number of refs, lstat for non-existing loose objects makes `git fetch` slow. This patch stores existing loose objects in hashmap beforehand and use it to check existence instead of using lstat. With this patch, the number of lstat calls in `git fetch` is reduced from 411412 to 13794 for chromium repository. I took time stat of `git fetch` disabling quickfetch for chromium repository 3 time on linux with SSD. * with this patch 8.105s 8.309s 7.640s avg: 8.018s * master 12.287s 11.175s 12.227s avg: 11.896s On my MacBook Air which has slower lstat. * with this patch 14.501s * master 1m16.027s `git fetch` on slow disk will be improved largely. Signed-off-by: Takuto Ikuta--- cache.h | 2 ++ fetch-pack.c | 22 +++--- sha1_file.c | 3 +++ 3 files changed, 24 insertions(+), 3 deletions(-) diff --git a/cache.h b/cache.h index d06932ed0..db38db40e 100644 --- a/cache.h +++ b/cache.h @@ -1773,6 +1773,8 @@ struct object_info { #define OBJECT_INFO_SKIP_CACHED 4 /* Do not retry packed storage after checking packed and loose storage */ #define OBJECT_INFO_QUICK 8 +/* Do not check loose object */ +#define OBJECT_INFO_SKIP_LOOSE 16 extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags); /* diff --git a/fetch-pack.c b/fetch-pack.c index d97461296..1658487f7 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj) mark_complete(>oid); } +static int add_loose_objects_to_set(const struct object_id *oid, + const char *path, + void *data) +{ + struct oidset* set = (struct oidset*)(data); + oidset_insert(set, oid); + return 0; +} + static int everything_local(struct fetch_pack_args *args, struct ref **refs, struct ref **sought, int nr_sought) @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args *args, int retval; int old_save_commit_buffer = save_commit_buffer; timestamp_t cutoff = 0; + struct oidset loose_oid_set = OIDSET_INIT; + + for_each_loose_object(add_loose_objects_to_set, _oid_set, 0); save_commit_buffer = 0; for (ref = *refs; ref; ref = ref->next) { struct object *o; + unsigned int flag = OBJECT_INFO_QUICK; - if (!has_object_file_with_flags(>old_oid, - OBJECT_INFO_QUICK)) - continue; + if (!oidset_contains(_oid_set, >old_oid)) + flag |= OBJECT_INFO_SKIP_LOOSE; + if (!has_object_file_with_flags(>old_oid, flag)) + continue; o = parse_object(>old_oid); if (!o) continue; @@ -744,6 +758,8 @@ static int everything_local(struct fetch_pack_args *args, } } + oidset_clear(_oid_set); + if (!args->no_dependents) { if (!args->deepen) { for_each_ref(mark_complete_oid, NULL); diff --git a/sha1_file.c b/sha1_file.c index 1b94f39c4..c903cbcec 100644 --- a/sha1_file.c +++ b/sha1_file.c @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi, if (find_pack_entry(real, )) break; + if (flags & OBJECT_INFO_SKIP_LOOSE) + return -1; + /* Most likely it's a loose object. */ if (!sha1_loose_object_info(real, oi, flags)) return 0; -- 2.16.2