oidset: use khash

Performance of a command that mainly checks for duplicate objects using an oidset, with master and Clang 6.0.1:

  $ cmd="./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'"

  $ /usr/bin/time $cmd >/dev/null
  0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k
  0inputs+0outputs (0major+11204minor)pagefaults 0swaps

  $ hyperfine "$cmd"
  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'

    Time (mean ± σ):     250.0 ms ±   6.0 ms    [User: 225.9 ms, System: 23.6 ms]

    Range (min … max):   242.0 ms … 261.1 ms

And with this patch:

  $ /usr/bin/time $cmd >/dev/null
  0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k
  0inputs+0outputs (0major+8318minor)pagefaults 0swaps

  $ hyperfine "$cmd"
  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'

    Time (mean ± σ):     151.9 ms ±   4.9 ms    [User: 130.5 ms, System: 21.2 ms]

    Range (min … max):   148.2 ms … 170.4 ms

int oidset_insert(struct oidset *set, const struct object_id *oid) {

fetch-pack.c +0 -6

-	struct oidmap_entry *entry;
-
-	if (!set->map.map.tablesize)
-		oidmap_init(&set->map, 0);
-	else if (oidset_contains(set, oid))
-		return 1;

fetch-pack.c static int tip_oids_contain(struct oidset *tip_oids, · line 542

Quoted 13 lines

fetch-pack.c +1 -1

index 75047a4b2a..a839315726 100644
@@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
 	 * add to "newlist" between calls, the additions will always be for
 	 * oids that are already in the set.
 	 */
-	if (!tip_oids->map.map.tablesize) {
+	if (!tip_oids->set.n_buckets) {
 		add_refs_to_oidset(tip_oids, unmatched);
 		add_refs_to_oidset(tip_oids, newlist);
 	}

This is a little intimate with the implementation of khash, but I think it's probably OK (and really no worse than what was there before).

As the comment above notes, I think we're really looking at the case where this gets populated on the first call, but not subsequent ones. It might be less hacky to use a "static int initialized" here. Or if we want to avoid hidden globals, put the logic into filter_refs() to decide when to populate.

oidset.h line 29

Quoted 6 lines

oidset.h +1 -0

index 40ec5f87fe..4b90540cd4 100644
[...]
+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)

This will declare these "static inline". Our other major "macros become inline functions" code is commit-slab.h, and there we found it necessary to add MAYBE_UNUSED. I wonder if we ought to be doing the same here (I don't get any warnings, but I suspect sparse might complain).

It might be nice if these functions could hide inside oidset.c (and just declare the struct here). It looks like we might be able to do that with __KHASH_TYPE(), but the double-underscore implies that we're not supposed to. ;)

I guess we also use a few of them in our inlines here. I'm not 100% sure that oidset_* needs to be inlined either, but this is at least a pretty faithful conversion of the original.

Quoted 5 lines

As the comment above notes, I think we're really looking at the case where this gets populated on the first call, but not subsequent ones. It might be less hacky to use a "static int initialized" here. Or if we want to avoid hidden globals, put the logic into filter_refs() to decide when to populate.

Right. I'd prefer the latter, but was unable to find a nice way that still populates the oidset lazily. It's certainly worth another look, and a separate series.

Quoted 6 lines

Quoted 1 line

+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)

This will declare these "static inline". Our other major "macros become inline functions" code is commit-slab.h, and there we found it necessary to add MAYBE_UNUSED. I wonder if we ought to be doing the same here (I don't get any warnings, but I suspect sparse might complain).

I doubt it (but didn't check) because khash.h defines kh_clear_##name(), which we don't use it anywhere and there have been no complaints so far. And if we wanted to add MAYBE_UNUSED then the right place for that would be in KHASH_INIT, no?

Quoted 8 lines

It might be nice if these functions could hide inside oidset.c (and just declare the struct here). It looks like we might be able to do that with __KHASH_TYPE(), but the double-underscore implies that we're not supposed to. ;)

I guess we also use a few of them in our inlines here. I'm not 100% sure that oidset_* needs to be inlined either, but this is at least a pretty faithful conversion of the original.

We could inline all of the oidset functions, following the spirit of klib/khash.h.

Or we could uninline all of them and then may be able to clean up oidset.h by using KHASH_DECLARE. Perhaps we'd need to guard with an "#ifndef THIS_IS_OIDSET_C" or similar to avoid a clash with KHASH_INIT.

Not sure if any of that would be a worthwhile improvement..

Quoted 6 lines · René Scharfe

Quoted 5 lines

As the comment above notes, I think we're really looking at the case where this gets populated on the first call, but not subsequent ones. It might be less hacky to use a "static int initialized" here. Or if we want to avoid hidden globals, put the logic into filter_refs() to decide when to populate.

Quoted 3 lines

Right. I'd prefer the latter, but was unable to find a nice way that still populates the oidset lazily. It's certainly worth another look, and a separate series.

It's a little awkward because the lazy load happens in a conditional. You can fully encapsulate it like the patch below, but I actually don't think it's really helping readability.

Quoted 7 lines

Quoted 6 lines

As the comment above notes, I think we're really looking at the case where this gets populated on the first call, but not subsequent ones. It might be less hacky to use a "static int initialized" here. Or if we want to avoid hidden globals, put the logic into filter_refs() to decide when to populate.

Quoted 3 lines

Right. I'd prefer the latter, but was unable to find a nice way that still populates the oidset lazily. It's certainly worth another look, and a separate series.

It's a little awkward because the lazy load happens in a conditional. You can fully encapsulate it like the patch below, but I actually don't think it's really helping readability.

Quoted 12 lines

Quoted 8 lines

It might be nice if these functions could hide inside oidset.c (and just declare the struct here). It looks like we might be able to do that with __KHASH_TYPE(), but the double-underscore implies that we're not supposed to. ;)

I guess we also use a few of them in our inlines here. I'm not 100% sure that oidset_* needs to be inlined either, but this is at least a pretty faithful conversion of the original.

We could inline all of the oidset functions, following the spirit of klib/khash.h.

Quoted 5 lines

Or we could uninline all of them and then may be able to clean up oidset.h by using KHASH_DECLARE. Perhaps we'd need to guard with an "#ifndef THIS_IS_OIDSET_C" or similar to avoid a clash with KHASH_INIT.

Not sure if any of that would be a worthwhile improvement..

Unless we know something is a performance win to inline, I'd generally prefer not to.

For a case like this with auto-generated functions, I'm mostly worried about bloating the compiled code. Either with a bunch of inlined non-trivial functions, or cases where the compiler says "this is too big to inline" and generates an anonymous file-scope function, but we end up with a bunch of duplicates, because we're generating the same functions in a bunch of C files.

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.

fetch-pack.c +12 -0

+	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))

Quoted 3 lines

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]

Quoted 18 lines

fetch-pack.c +12 -0

+	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;

fetch-pack.c static void filter_refs(struct fetch_pack_args *args, · line 608

Quoted 8 lines

fetch-pack.c +1 -4

-		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.

Am 04.10.2018 um 23:38 schrieb Jonathan Tan:

Quoted 3 lines

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.

fetch-pack.c static void filter_refs(struct fetch_pack_args *args, · line 608

Quoted 8 lines

fetch-pack.c +1 -4

-		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.

Quoted 4 lines

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.

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.

fetch-pack.c +0 -0

index 3b317952f0..53914563b5 100644
@@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)
 		oidset_insert(oids, &refs->old_oid);
 }
 

Quoted 8 lines

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...

Quoted 8 lines

fetch-pack.c +0 -0

index 3b317952f0..53914563b5 100644
@@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)
 		oidset_insert(oids, &refs->old_oid);
 }
 

fetch-pack.c static void add_refs_to_oidset(struct oidset *oids, struct ref *refs) · line 538

Quoted 10 lines

fetch-pack.c +0 -10

-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:

fetch-pack.c static void filter_refs(struct fetch_pack_args *args, · line 597

Quoted 11 lines

fetch-pack.c +11 -0

+	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.

Quoted 13 lines

Review

Quoted 7 lines

(quoted diff) +0 -7

-{
-	/*
-	 * 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:

Quoted 14 lines

Review

Quoted 11 lines

(quoted diff) +11 -0

+	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?

Quoted 33 lines

Quoted 14 lines

Review

Quoted 8 lines

(quoted diff) +0 -7

-{
-	/*
-	 * 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:

Quoted 14 lines

Review

Quoted 11 lines

(quoted diff) +11 -0

+	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 */

Quoted 3 lines

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:

fetch-pack.c +0 -0

index 53914563b5..c0a1b80f4c 100644
@@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args,
 			ref->match_status = REF_MATCHED;
 			*newtail = copy_ref(ref);

Quoted 13 lines

fetch-pack.c +5 -0

index 53914563b5..c0a1b80f4c 100644
@@ -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.

fetch-pack.c static void filter_refs(struct fetch_pack_args *args, · line 617

Quoted 4 lines

fetch-pack.c +1 -0

+			 */
 		} 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.

Two new patches to avoid using oidset internals in fetch-pack:

fetch-pack: factor out is_unmatched_ref()
fetch-pack: load tip_oids eagerly iff needed

Unchanged patch:

khash: factor out kh_release_*

Unchanged, except it doesn't touch fetch-pack anymore:

oidset: use khash

A new patch, to reduce object text size:

oidset: uninline oidset_init()