| Message ID | 9f51ac28-73e9-2855-c650-7d695945e286@web.de (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | oidset: use khash | expand |
> Determine if the oidset needs to be populated upfront and then do that > instead. This duplicates a loop, but simplifies the existing one by > separating concerns between the two. [snip] > + if (strict) { > + for (i = 0; i < nr_sought; i++) { > + ref = sought[i]; > + if (!is_unmatched_ref(ref)) > + continue; > + > + add_refs_to_oidset(&tip_oids, unmatched); > + add_refs_to_oidset(&tip_oids, newlist); > + break; > + } > + } > + > /* Append unmatched requests to the list */ > for (i = 0; i < nr_sought; i++) { > ref = sought[i]; > if (!is_unmatched_ref(ref)) > continue; > > - if ((allow_unadvertised_object_request & > - (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) || > - tip_oids_contain(&tip_oids, unmatched, newlist, > - &ref->old_oid)) { > + if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) { > ref->match_status = REF_MATCHED; > *newtail = copy_ref(ref); > newtail = &(*newtail)->next; I don't think the concerns are truly separated - the first loop quoted needs to know that in the second loop, tip_oids is accessed only if there is at least one unmatched ref. Would it be better to expose the size of the oidset and then use it in place of "tip_oids->map.map.tablesize"? Checking for initialization (using "tablesize") is conceptually different from checking the size, but in this code, both initialization and the first increase in size occur upon the first oidset_insert(), so we should still get the same result. But if we do end up going with the approach in this patch, then this patch is obviously correct. I also looked at patch 1 of this patch set and it is obviously correct. I didn't look at the other patches.
On Thu, Oct 04, 2018 at 05:09:39PM +0200, René Scharfe wrote: > tip_oids_contain() lazily loads refs into an oidset at its first call. > It abuses the internal (sub)member .map.tablesize of that oidset to > check if it has done that already. > > Determine if the oidset needs to be populated upfront and then do that > instead. This duplicates a loop, but simplifies the existing one by > separating concerns between the two. I like this approach much better than what I showed earlier. But... > diff --git a/fetch-pack.c b/fetch-pack.c > index 3b317952f0..53914563b5 100644 > --- a/fetch-pack.c > +++ b/fetch-pack.c > @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs) > oidset_insert(oids, &refs->old_oid); > } > > -static int tip_oids_contain(struct oidset *tip_oids, > - struct ref *unmatched, struct ref *newlist, > - const struct object_id *id) > -{ > - /* > - * Note that this only looks at the ref lists the first time it's > - * called. This works out in filter_refs() because even though it may > - * add to "newlist" between calls, the additions will always be for > - * oids that are already in the set. > - */ I don't think the subtle point this comment is making goes away. We're still growing the list in the loop that calls tip_oids_contain() (and which now calls just oidset_contains). That's OK for the reasons given here, but I think that would need to be moved down to this code: > + if (strict) { > + for (i = 0; i < nr_sought; i++) { > + ref = sought[i]; > + if (!is_unmatched_ref(ref)) > + continue; > + > + add_refs_to_oidset(&tip_oids, unmatched); > + add_refs_to_oidset(&tip_oids, newlist); > + break; > + } > + } I.e., we need to say here why it's OK to summarize newlist in the oidset, even though we're adding to it later. -Peff
Am 04.10.2018 um 23:38 schrieb Jonathan Tan: >> Determine if the oidset needs to be populated upfront and then do that >> instead. This duplicates a loop, but simplifies the existing one by >> separating concerns between the two. > > [snip] > >> + if (strict) { >> + for (i = 0; i < nr_sought; i++) { >> + ref = sought[i]; >> + if (!is_unmatched_ref(ref)) >> + continue; >> + >> + add_refs_to_oidset(&tip_oids, unmatched); >> + add_refs_to_oidset(&tip_oids, newlist); >> + break; >> + } >> + } >> + >> /* Append unmatched requests to the list */ >> for (i = 0; i < nr_sought; i++) { >> ref = sought[i]; >> if (!is_unmatched_ref(ref)) >> continue; >> >> - if ((allow_unadvertised_object_request & >> - (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) || >> - tip_oids_contain(&tip_oids, unmatched, newlist, >> - &ref->old_oid)) { >> + if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) { >> ref->match_status = REF_MATCHED; >> *newtail = copy_ref(ref); >> newtail = &(*newtail)->next; > > I don't think the concerns are truly separated - the first loop quoted > needs to know that in the second loop, tip_oids is accessed only if > there is at least one unmatched ref. Right, the two loops are still closely related, but only the first one is concerned with loading refs. For a true separation we could first build a list of unmatched refs and then loop through that instead of `sought`. Not sure if that's better, but maybe the overhead I imagine it would introduce isn't all that big. > Would it be better to expose the > size of the oidset and then use it in place of > "tip_oids->map.map.tablesize"? Checking for initialization (using > "tablesize") is conceptually different from checking the size, but in > this code, both initialization and the first increase in size occur upon > the first oidset_insert(), so we should still get the same result. It would work in practice. If there are no refs to load then it would try to load those zero refs for each unmatched ref, which shouldn't really be a problem, but I still find it a wee bit sloppy. Too theoretical? René
On Thu, Oct 04, 2018 at 02:38:13PM -0700, Jonathan Tan wrote: > > - if ((allow_unadvertised_object_request & > > - (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) || > > - tip_oids_contain(&tip_oids, unmatched, newlist, > > - &ref->old_oid)) { > > + if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) { > > ref->match_status = REF_MATCHED; > > *newtail = copy_ref(ref); > > newtail = &(*newtail)->next; > > I don't think the concerns are truly separated - the first loop quoted > needs to know that in the second loop, tip_oids is accessed only if > there is at least one unmatched ref. Would it be better to expose the > size of the oidset and then use it in place of > "tip_oids->map.map.tablesize"? Checking for initialization (using > "tablesize") is conceptually different from checking the size, but in > this code, both initialization and the first increase in size occur upon > the first oidset_insert(), so we should still get the same result. Yes, I agree with you that the loops are still entwined. They're at least now in a single function, though, which IMHO is a slight improvement. I agree with you that just checking: if (oidset_count() != 0) would be fine, too. Or I am even OK with leaving the existing tablesize check. It is a little intimate with the implementation details, but I suspect that if oidset were to change (e.g., to initialize the buckets immediately), the problem would be pretty apparent in the tests. And in fact, we can test by just changing the conditional in tip_oid_contains to if(0), which quite clearly fails t5500.60 (along with others). So I don't think it's the end of the world to leave it (but I also am not opposed to the other options discussed). -Peff
> Yes, I agree with you that the loops are still entwined. They're at > least now in a single function, though, which IMHO is a slight > improvement. Hmm...originally, the main functionality was in a single loop in a single function. But I say that because I consider the lazy loading in tip_oids_contain() as something both peripheral and independent (if the main loop's logic changes, the lazy loading most likely does not need to be changed). > I agree with you that just checking: > > if (oidset_count() != 0) > > would be fine, too. OK, we're agreed on this :-) > Or I am even OK with leaving the existing tablesize > check. It is a little intimate with the implementation details, but I > suspect that if oidset were to change (e.g., to initialize the buckets > immediately), the problem would be pretty apparent in the tests. I am OK with this too, except that (as far as I can tell) the point of this patch set is to replace the internals of oidset, so we no longer have the tablesize check. Unless you meant the khash analog of tablesize? I would be OK if all tablesize references are replaced with the khash analog in the same patch that the oidset internals are replaced.
On Thu, Oct 04, 2018 at 03:52:05PM -0700, Jonathan Tan wrote: > > Or I am even OK with leaving the existing tablesize > > check. It is a little intimate with the implementation details, but I > > suspect that if oidset were to change (e.g., to initialize the buckets > > immediately), the problem would be pretty apparent in the tests. > > I am OK with this too, except that (as far as I can tell) the point of > this patch set is to replace the internals of oidset, so we no longer > have the tablesize check. Unless you meant the khash analog of > tablesize? I would be OK if all tablesize references are replaced with > the khash analog in the same patch that the oidset internals are > replaced. Yeah, in khash it's n_buckets, but it's basically the same thing. René's original patch did that update, and we were musing on whether there was a way to avoid crossing the module boundary so intimately. Hence the patch you saw. :) -Peff
Am 05.10.2018 um 00:11 schrieb René Scharfe: > Am 04.10.2018 um 23:38 schrieb Jonathan Tan: >> I don't think the concerns are truly separated - the first loop quoted >> needs to know that in the second loop, tip_oids is accessed only if >> there is at least one unmatched ref. > > Right, the two loops are still closely related, but only the first one > is concerned with loading refs. > > For a true separation we could first build a list of unmatched refs and > then loop through that instead of `sought`. Not sure if that's better, > but maybe the overhead I imagine it would introduce isn't all that big. Here's what I mean, on top of the other two patches: --- fetch-pack.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-) diff --git a/fetch-pack.c b/fetch-pack.c index 53914563b5..7f28584bce 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -543,6 +543,8 @@ static void filter_refs(struct fetch_pack_args *args, struct ref *newlist = NULL; struct ref **newtail = &newlist; struct ref *unmatched = NULL; + struct ref **unfound; + int nr_unfound = 0; struct ref *ref, *next; struct oidset tip_oids = OIDSET_INIT; int i; @@ -584,23 +586,19 @@ static void filter_refs(struct fetch_pack_args *args, } } - if (strict) { - for (i = 0; i < nr_sought; i++) { - ref = sought[i]; - if (!is_unmatched_ref(ref)) - continue; - - add_refs_to_oidset(&tip_oids, unmatched); - add_refs_to_oidset(&tip_oids, newlist); - break; - } + ALLOC_ARRAY(unfound, nr_sought); + for (i = 0; i < nr_sought; i++) { + if (is_unmatched_ref(sought[i])) + unfound[nr_unfound++] = sought[i]; + } + if (strict && nr_unfound) { + add_refs_to_oidset(&tip_oids, unmatched); + add_refs_to_oidset(&tip_oids, newlist); } /* Append unmatched requests to the list */ - for (i = 0; i < nr_sought; i++) { - ref = sought[i]; - if (!is_unmatched_ref(ref)) - continue; + for (i = 0; i < nr_unfound; i++) { + ref = unfound[i]; if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) { ref->match_status = REF_MATCHED; @@ -611,6 +609,7 @@ static void filter_refs(struct fetch_pack_args *args, } } + free(unfound); oidset_clear(&tip_oids); for (ref = unmatched; ref; ref = next) { next = ref->next;
Am 05.10.2018 um 00:07 schrieb Jeff King: > On Thu, Oct 04, 2018 at 05:09:39PM +0200, René Scharfe wrote: > >> tip_oids_contain() lazily loads refs into an oidset at its first call. >> It abuses the internal (sub)member .map.tablesize of that oidset to >> check if it has done that already. >> >> Determine if the oidset needs to be populated upfront and then do that >> instead. This duplicates a loop, but simplifies the existing one by >> separating concerns between the two. > > I like this approach much better than what I showed earlier. But... > >> diff --git a/fetch-pack.c b/fetch-pack.c >> index 3b317952f0..53914563b5 100644 >> --- a/fetch-pack.c >> +++ b/fetch-pack.c >> @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs) >> oidset_insert(oids, &refs->old_oid); >> } >> >> -static int tip_oids_contain(struct oidset *tip_oids, >> - struct ref *unmatched, struct ref *newlist, >> - const struct object_id *id) >> -{ >> - /* >> - * Note that this only looks at the ref lists the first time it's >> - * called. This works out in filter_refs() because even though it may >> - * add to "newlist" between calls, the additions will always be for >> - * oids that are already in the set. >> - */ > > I don't think the subtle point this comment is making goes away. We're > still growing the list in the loop that calls tip_oids_contain() (and > which now calls just oidset_contains). That's OK for the reasons given > here, but I think that would need to be moved down to this code: > >> + if (strict) { >> + for (i = 0; i < nr_sought; i++) { >> + ref = sought[i]; >> + if (!is_unmatched_ref(ref)) >> + continue; >> + >> + add_refs_to_oidset(&tip_oids, unmatched); >> + add_refs_to_oidset(&tip_oids, newlist); >> + break; >> + } >> + } > > I.e., we need to say here why it's OK to summarize newlist in the > oidset, even though we're adding to it later. There is already this comment: /* Append unmatched requests to the list */ And that's enough in my eyes. The refs loop at the top splits the list into matched ("the list") and unmatched, and the loop below said comment adds a few more. I see no subtlety left -- what do I miss? René
On Fri, Oct 05, 2018 at 10:13:34PM +0200, René Scharfe wrote: > >> -{ > >> - /* > >> - * Note that this only looks at the ref lists the first time it's > >> - * called. This works out in filter_refs() because even though it may > >> - * add to "newlist" between calls, the additions will always be for > >> - * oids that are already in the set. > >> - */ > > > > I don't think the subtle point this comment is making goes away. We're > > still growing the list in the loop that calls tip_oids_contain() (and > > which now calls just oidset_contains). That's OK for the reasons given > > here, but I think that would need to be moved down to this code: > > > >> + if (strict) { > >> + for (i = 0; i < nr_sought; i++) { > >> + ref = sought[i]; > >> + if (!is_unmatched_ref(ref)) > >> + continue; > >> + > >> + add_refs_to_oidset(&tip_oids, unmatched); > >> + add_refs_to_oidset(&tip_oids, newlist); > >> + break; > >> + } > >> + } > > > > I.e., we need to say here why it's OK to summarize newlist in the > > oidset, even though we're adding to it later. > > There is already this comment: > > /* Append unmatched requests to the list */ > > And that's enough in my eyes. The refs loop at the top splits the list > into matched ("the list") and unmatched, and the loop below said comment > adds a few more. I see no subtlety left -- what do I miss? It looks like tip_oids is meant as a fast lookup into what's in unmatched and newlist. But in the second loop we continue appending to newlist. Why is it OK that we do not update tip_oids when we do so? I.e., something like this explains it: diff --git a/fetch-pack.c b/fetch-pack.c index 53914563b5..c0a1b80f4c 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args, ref->match_status = REF_MATCHED; *newtail = copy_ref(ref); newtail = &(*newtail)->next; + /* + * No need to update tip_oids with ref->old_oid; we got + * here because either it was already there, or we are + * in !strict mode, in which case we do not use + * tip_oids at all. + */ } else { ref->match_status = REF_UNADVERTISED_NOT_ALLOWED; }
Am 05.10.2018 um 22:27 schrieb Jeff King: > On Fri, Oct 05, 2018 at 10:13:34PM +0200, René Scharfe wrote: > >>>> -{ >>>> - /* >>>> - * Note that this only looks at the ref lists the first time it's >>>> - * called. This works out in filter_refs() because even though it may >>>> - * add to "newlist" between calls, the additions will always be for >>>> - * oids that are already in the set. >>>> - */ >>> >>> I don't think the subtle point this comment is making goes away. We're >>> still growing the list in the loop that calls tip_oids_contain() (and >>> which now calls just oidset_contains). That's OK for the reasons given >>> here, but I think that would need to be moved down to this code: >>> >>>> + if (strict) { >>>> + for (i = 0; i < nr_sought; i++) { >>>> + ref = sought[i]; >>>> + if (!is_unmatched_ref(ref)) >>>> + continue; >>>> + >>>> + add_refs_to_oidset(&tip_oids, unmatched); >>>> + add_refs_to_oidset(&tip_oids, newlist); >>>> + break; >>>> + } >>>> + } >>> >>> I.e., we need to say here why it's OK to summarize newlist in the >>> oidset, even though we're adding to it later. >> >> There is already this comment: >> >> /* Append unmatched requests to the list */ >> >> And that's enough in my eyes. The refs loop at the top splits the list >> into matched ("the list") and unmatched, and the loop below said comment >> adds a few more. I see no subtlety left -- what do I miss? > > It looks like tip_oids is meant as a fast lookup into what's in > unmatched and newlist. But in the second loop we continue appending to > newlist. Why is it OK that we do not update tip_oids when we do so? `tip_oids` contains the object_ids of the all `refs` passed to filter_refs(). Instead of adding them at the top of the function that is done only when it has become clear that there are unmatched ones, as an optimization. (That optimization was implemented by lazy-loading in tip_oids_contain() earlier.) At that point the list has been split into `newlist` and `unmatched`, so we load from them instead of `refs`. > > I.e., something like this explains it: > > diff --git a/fetch-pack.c b/fetch-pack.c > index 53914563b5..c0a1b80f4c 100644 > --- a/fetch-pack.c > +++ b/fetch-pack.c > @@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args, > ref->match_status = REF_MATCHED; > *newtail = copy_ref(ref); > newtail = &(*newtail)->next; > + /* > + * No need to update tip_oids with ref->old_oid; we got > + * here because either it was already there, or we are > + * in !strict mode, in which case we do not use > + * tip_oids at all. > + */ > } else { > ref->match_status = REF_UNADVERTISED_NOT_ALLOWED; > } This comment puzzles me -- why ask the question it answers? `tip_oids` has been loaded with all `refs` at that point; adding more seems odd. I feel the code needs be simplified further; not sure how, though, except perhaps by using the `unfound` array added in another reply. René
On Fri, Oct 05, 2018 at 11:22:31PM +0200, René Scharfe wrote: > > diff --git a/fetch-pack.c b/fetch-pack.c > > index 53914563b5..c0a1b80f4c 100644 > > --- a/fetch-pack.c > > +++ b/fetch-pack.c > > @@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args, > > ref->match_status = REF_MATCHED; > > *newtail = copy_ref(ref); > > newtail = &(*newtail)->next; > > + /* > > + * No need to update tip_oids with ref->old_oid; we got > > + * here because either it was already there, or we are > > + * in !strict mode, in which case we do not use > > + * tip_oids at all. > > + */ > > } else { > > ref->match_status = REF_UNADVERTISED_NOT_ALLOWED; > > } > > This comment puzzles me -- why ask the question it answers? > `tip_oids` has been loaded with all `refs` at that point; adding > more seems odd. If you think that tip_oids is a fast lookup for what's in newlist, then I think it is a reasonable question to ask whether new additions to newlist need the same treatment. That was what the comment in the original lazy-load was answering. > I feel the code needs be simplified further; not sure how, though, > except perhaps by using the `unfound` array added in another reply. I agree it's not the most clear code in the world, but we may be reaching a point of diminishing returns in discussing it further. -Peff
diff --git a/fetch-pack.c b/fetch-pack.c index 3b317952f0..53914563b5 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs) oidset_insert(oids, &refs->old_oid); } -static int tip_oids_contain(struct oidset *tip_oids, - struct ref *unmatched, struct ref *newlist, - const struct object_id *id) -{ - /* - * Note that this only looks at the ref lists the first time it's - * called. This works out in filter_refs() because even though it may - * add to "newlist" between calls, the additions will always be for - * oids that are already in the set. - */ - if (!tip_oids->map.map.tablesize) { - add_refs_to_oidset(tip_oids, unmatched); - add_refs_to_oidset(tip_oids, newlist); - } - return oidset_contains(tip_oids, id); -} - static int is_unmatched_ref(const struct ref *ref) { struct object_id oid; @@ -563,6 +546,8 @@ static void filter_refs(struct fetch_pack_args *args, struct ref *ref, *next; struct oidset tip_oids = OIDSET_INIT; int i; + int strict = !(allow_unadvertised_object_request & + (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)); i = 0; for (ref = *refs; ref; ref = next) { @@ -599,16 +584,25 @@ static void filter_refs(struct fetch_pack_args *args, } } + if (strict) { + for (i = 0; i < nr_sought; i++) { + ref = sought[i]; + if (!is_unmatched_ref(ref)) + continue; + + add_refs_to_oidset(&tip_oids, unmatched); + add_refs_to_oidset(&tip_oids, newlist); + break; + } + } + /* Append unmatched requests to the list */ for (i = 0; i < nr_sought; i++) { ref = sought[i]; if (!is_unmatched_ref(ref)) continue; - if ((allow_unadvertised_object_request & - (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) || - tip_oids_contain(&tip_oids, unmatched, newlist, - &ref->old_oid)) { + if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) { ref->match_status = REF_MATCHED; *newtail = copy_ref(ref); newtail = &(*newtail)->next;
tip_oids_contain() lazily loads refs into an oidset at its first call. It abuses the internal (sub)member .map.tablesize of that oidset to check if it has done that already. Determine if the oidset needs to be populated upfront and then do that instead. This duplicates a loop, but simplifies the existing one by separating concerns between the two. Signed-off-by: Rene Scharfe <l.s.r@web.de> --- fetch-pack.c | 36 +++++++++++++++--------------------- 1 file changed, 15 insertions(+), 21 deletions(-)