{"thread":{"id":"49478","subject":"[PATCH v2 0/2] oidset: use khash","startedAt":"2018-10-03T13:11:17Z","lastAt":"2018-10-05T21:47:25Z","messageCount":26,"participants":["René Scharfe","Jeff King","Jonathan Tan"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"359515","messageId":"64911aec-71cd-d990-5dfd-bf2c3163690c@web.de","threadId":"49478","inReplyTo":null,"subject":"[PATCH v2 0/2] oidset: use khash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-03T13:11:06Z","receivedAt":"2018-10-03T13:11:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Continue the discussion of speeding up oidset started in [1] here in\nits own thread.\n\n[1] https://public-inbox.org/git/20180811172350.GA2689@sigill.intra.peff.net/\n\nThe first patch does a mild refactoring to support khash structures\non the stack, and the second one converts oidset to khash.\n\n  khash: factor out kh_release_*\n  oidset: use khash\n\n fetch-pack.c |  2 +-\n khash.h      |  9 +++++++--\n oidset.c     | 34 ++++++++++++----------------------\n oidset.h     | 36 ++++++++++++++++++++++++++++--------\n 4 files changed, 48 insertions(+), 33 deletions(-)\n\n-- \n2.19.0\n"},{"id":"359516","messageId":"054cf3b9-e915-2669-0e24-a08f7dd1f35d@web.de","threadId":"49478","inReplyTo":"64911aec-71cd-d990-5dfd-bf2c3163690c@web.de","subject":"[PATCH v2 1/2] khash: factor out kh_release_*","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-03T13:12:49Z","receivedAt":"2018-10-03T13:13:01Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a function for releasing the khash-internal allocations, but not the\nkhash structure itself.  It can be used with on-stack khash structs.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n1 tab = 4 spaces here.\n\n khash.h | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/khash.h b/khash.h\nindex 07b4cc2e67..d10caa0c35 100644\n--- a/khash.h\n+++ b/khash.h\n@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;\n \tSCOPE kh_##name##_t *kh_init_##name(void) {\t\t\t\t\t\t\t\\\n \t\treturn (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));\t\t\\\n \t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\tSCOPE void kh_release_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n+\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree(h->flags);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree((void *)h->keys);\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \tSCOPE void kh_destroy_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n \t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t\tif (h) {\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tfree((void *)h->keys); free(h->flags);\t\t\t\t\t\\\n-\t\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\\\n+\t\t\tkh_release_##name(h);\t\t\t\t\t\t\t\t\t\t\\\n \t\t\tfree(h);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-- \n2.19.0\n"},{"id":"359517","messageId":"5efe6695-2e82-786c-1170-7874978cb534@web.de","threadId":"49478","inReplyTo":"64911aec-71cd-d990-5dfd-bf2c3163690c@web.de","subject":"[PATCH v2 2/2] oidset: use khash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-03T13:16:39Z","receivedAt":"2018-10-03T13:16:50Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Reimplement oidset using khash.h in order to reduce its memory footprint\nand make it faster.\n\nPerformance of a command that mainly checks for duplicate objects using\nan oidset, with master and Clang 6.0.1:\n\n  $ cmd=\"./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\"\n\n  $ /usr/bin/time $cmd >/dev/null\n  0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k\n  0inputs+0outputs (0major+11204minor)pagefaults 0swaps\n\n  $ hyperfine \"$cmd\"\n  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n\n    Time (mean ± σ):     250.0 ms ±   6.0 ms    [User: 225.9 ms, System: 23.6 ms]\n\n    Range (min … max):   242.0 ms … 261.1 ms\n\nAnd with this patch:\n\n  $ /usr/bin/time $cmd >/dev/null\n  0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k\n  0inputs+0outputs (0major+8318minor)pagefaults 0swaps\n\n  $ hyperfine \"$cmd\"\n  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n\n    Time (mean ± σ):     151.9 ms ±   4.9 ms    [User: 130.5 ms, System: 21.2 ms]\n\n    Range (min … max):   148.2 ms … 170.4 ms\n\nInitial-patch-by: Jeff King <peff@peff.net>\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n fetch-pack.c |  2 +-\n oidset.c     | 34 ++++++++++++----------------------\n oidset.h     | 36 ++++++++++++++++++++++++++++--------\n 3 files changed, 41 insertions(+), 31 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 75047a4b2a..a839315726 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n \t * add to \"newlist\" between calls, the additions will always be for\n \t * oids that are already in the set.\n \t */\n-\tif (!tip_oids->map.map.tablesize) {\n+\tif (!tip_oids->set.n_buckets) {\n \t\tadd_refs_to_oidset(tip_oids, unmatched);\n \t\tadd_refs_to_oidset(tip_oids, newlist);\n \t}\ndiff --git a/oidset.c b/oidset.c\nindex 454c54f933..9836d427ef 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -3,38 +3,28 @@\n \n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n-\tif (!set->map.map.tablesize)\n-\t\treturn 0;\n-\treturn !!oidmap_get(&set->map, oid);\n+\tkhiter_t pos = kh_get_oid(&set->set, *oid);\n+\treturn pos != kh_end(&set->set);\n }\n \n int oidset_insert(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n-\n-\tif (!set->map.map.tablesize)\n-\t\toidmap_init(&set->map, 0);\n-\telse if (oidset_contains(set, oid))\n-\t\treturn 1;\n-\n-\tentry = xmalloc(sizeof(*entry));\n-\toidcpy(&entry->oid, oid);\n-\n-\toidmap_put(&set->map, entry);\n-\treturn 0;\n+\tint added;\n+\tkh_put_oid(&set->set, *oid, &added);\n+\treturn !added;\n }\n \n int oidset_remove(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n-\n-\tentry = oidmap_remove(&set->map, oid);\n-\tfree(entry);\n-\n-\treturn (entry != NULL);\n+\tkhiter_t pos = kh_get_oid(&set->set, *oid);\n+\tif (pos == kh_end(&set->set))\n+\t\treturn 0;\n+\tkh_del_oid(&set->set, pos);\n+\treturn 1;\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\toidmap_free(&set->map, 1);\n+\tkh_release_oid(&set->set);\n+\toidset_init(set, 0);\n }\ndiff --git a/oidset.h b/oidset.h\nindex 40ec5f87fe..4b90540cd4 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -1,7 +1,8 @@\n #ifndef OIDSET_H\n #define OIDSET_H\n \n-#include \"oidmap.h\"\n+#include \"hashmap.h\"\n+#include \"khash.h\"\n \n /**\n  * This API is similar to sha1-array, in that it maintains a set of object ids\n@@ -15,19 +16,33 @@\n  *      table overhead.\n  */\n \n+static inline unsigned int oid_hash(struct object_id oid)\n+{\n+\treturn sha1hash(oid.hash);\n+}\n+\n+static inline int oid_equal(struct object_id a, struct object_id b)\n+{\n+\treturn oideq(&a, &b);\n+}\n+\n+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n+\n /**\n  * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n  */\n struct oidset {\n-\tstruct oidmap map;\n+\tkh_oid_t set;\n };\n \n-#define OIDSET_INIT { OIDMAP_INIT }\n+#define OIDSET_INIT { { 0 } }\n \n \n static inline void oidset_init(struct oidset *set, size_t initial_size)\n {\n-\toidmap_init(&set->map, initial_size);\n+\tmemset(&set->set, 0, sizeof(set->set));\n+\tif (initial_size)\n+\t\tkh_resize_oid(&set->set, initial_size);\n }\n \n /**\n@@ -58,19 +73,24 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);\n void oidset_clear(struct oidset *set);\n \n struct oidset_iter {\n-\tstruct oidmap_iter m_iter;\n+\tkh_oid_t *set;\n+\tkhiter_t iter;\n };\n \n static inline void oidset_iter_init(struct oidset *set,\n \t\t\t\t    struct oidset_iter *iter)\n {\n-\toidmap_iter_init(&set->map, &iter->m_iter);\n+\titer->set = &set->set;\n+\titer->iter = kh_begin(iter->set);\n }\n \n static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)\n {\n-\tstruct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);\n-\treturn e ? &e->oid : NULL;\n+\tfor (; iter->iter != kh_end(iter->set); iter->iter++) {\n+\t\tif (kh_exist(iter->set, iter->iter))\n+\t\t\treturn &kh_key(iter->set, iter->iter++);\n+\t}\n+\treturn NULL;\n }\n \n static inline struct object_id *oidset_iter_first(struct oidset *set,\n-- \n2.19.0\n\n"},{"id":"359572","messageId":"20181003194051.GB20709@sigill.intra.peff.net","threadId":"49478","inReplyTo":"5efe6695-2e82-786c-1170-7874978cb534@web.de","subject":"Re: [PATCH v2 2/2] oidset: use khash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-03T19:40:51Z","receivedAt":"2018-10-03T19:40:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 03, 2018 at 03:16:39PM +0200, René Scharfe wrote:\n\n> Performance of a command that mainly checks for duplicate objects using\n> an oidset, with master and Clang 6.0.1:\n> \n>   $ cmd=\"./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\"\n> \n>   $ /usr/bin/time $cmd >/dev/null\n>   0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k\n>   0inputs+0outputs (0major+11204minor)pagefaults 0swaps\n> \n>   $ hyperfine \"$cmd\"\n>   Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n> \n>     Time (mean ± σ):     250.0 ms ±   6.0 ms    [User: 225.9 ms, System: 23.6 ms]\n> \n>     Range (min … max):   242.0 ms … 261.1 ms\n> \n> And with this patch:\n> \n>   $ /usr/bin/time $cmd >/dev/null\n>   0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k\n>   0inputs+0outputs (0major+8318minor)pagefaults 0swaps\n> \n>   $ hyperfine \"$cmd\"\n>   Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n> \n>     Time (mean ± σ):     151.9 ms ±   4.9 ms    [User: 130.5 ms, System: 21.2 ms]\n> \n>     Range (min … max):   148.2 ms … 170.4 ms\n\nThanks. Just to reinforce these timings, a similar command on linux.git\ndrops from 4.0s to 2.3s.\n\nThe patch itself mostly looks good. A few small comments:\n\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 75047a4b2a..a839315726 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n>  \t * add to \"newlist\" between calls, the additions will always be for\n>  \t * oids that are already in the set.\n>  \t */\n> -\tif (!tip_oids->map.map.tablesize) {\n> +\tif (!tip_oids->set.n_buckets) {\n>  \t\tadd_refs_to_oidset(tip_oids, unmatched);\n>  \t\tadd_refs_to_oidset(tip_oids, newlist);\n>  \t}\n\nThis is a little intimate with the implementation of khash, but I think\nit's probably OK (and really no worse than what was there before).\n\nAs the comment above notes, I think we're really looking at the case\nwhere this gets populated on the first call, but not subsequent ones. It\nmight be less hacky to use a \"static int initialized\" here. Or if we\nwant to avoid hidden globals, put the logic into filter_refs() to decide\nwhen to populate.\n\nI don't think any of that needs to hold up this series, though.\n\n>  int oidset_insert(struct oidset *set, const struct object_id *oid)\n>  {\n> -\tstruct oidmap_entry *entry;\n> -\n> -\tif (!set->map.map.tablesize)\n> -\t\toidmap_init(&set->map, 0);\n> -\telse if (oidset_contains(set, oid))\n> -\t\treturn 1;\n> -\n> -\tentry = xmalloc(sizeof(*entry));\n> -\toidcpy(&entry->oid, oid);\n> -\n> -\toidmap_put(&set->map, entry);\n> -\treturn 0;\n> +\tint added;\n> +\tkh_put_oid(&set->set, *oid, &added);\n> +\treturn !added;\n>  }\n\nThis actually does the check-and-insert in a single lookup, which is\nnice. ;)\n\n> diff --git a/oidset.h b/oidset.h\n> index 40ec5f87fe..4b90540cd4 100644\n> --- a/oidset.h\n> +++ b/oidset.h\n> [...]\n> +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n\nThis will declare these \"static inline\". Our other major \"macros become\ninline functions\" code is commit-slab.h, and there we found it necessary\nto add MAYBE_UNUSED. I wonder if we ought to be doing the same here (I\ndon't get any warnings, but I suspect sparse might complain).\n\nIt might be nice if these functions could hide inside oidset.c (and just\ndeclare the struct here). It looks like we might be able to do that with\n__KHASH_TYPE(), but the double-underscore implies that we're not\nsupposed to. ;)\n\nI guess we also use a few of them in our inlines here. I'm not 100% sure\nthat oidset_* needs to be inlined either, but this is at least a pretty\nfaithful conversion of the original.\n\n-Peff\n"},{"id":"359604","messageId":"d17f104e-7cc2-5e73-78c9-6c268f9ec5b2@web.de","threadId":"49478","inReplyTo":"20181003194051.GB20709@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/2] oidset: use khash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T05:56:44Z","receivedAt":"2018-10-04T05:57:07Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 03.10.2018 um 21:40 schrieb Jeff King:\n> On Wed, Oct 03, 2018 at 03:16:39PM +0200, René Scharfe wrote:\n>> diff --git a/fetch-pack.c b/fetch-pack.c\n>> index 75047a4b2a..a839315726 100644\n>> --- a/fetch-pack.c\n>> +++ b/fetch-pack.c\n>> @@ -536,7 +536,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n>>  \t * add to \"newlist\" between calls, the additions will always be for\n>>  \t * oids that are already in the set.\n>>  \t */\n>> -\tif (!tip_oids->map.map.tablesize) {\n>> +\tif (!tip_oids->set.n_buckets) {\n>>  \t\tadd_refs_to_oidset(tip_oids, unmatched);\n>>  \t\tadd_refs_to_oidset(tip_oids, newlist);\n>>  \t}\n> \n> This is a little intimate with the implementation of khash, but I think\n> it's probably OK (and really no worse than what was there before).\n> \n> As the comment above notes, I think we're really looking at the case\n> where this gets populated on the first call, but not subsequent ones. It\n> might be less hacky to use a \"static int initialized\" here. Or if we\n> want to avoid hidden globals, put the logic into filter_refs() to decide\n> when to populate.\n\nRight.  I'd prefer the latter, but was unable to find a nice way that\nstill populates the oidset lazily.  It's certainly worth another look,\nand a separate series.\n\n>> diff --git a/oidset.h b/oidset.h\n>> index 40ec5f87fe..4b90540cd4 100644\n>> --- a/oidset.h\n>> +++ b/oidset.h\n>> [...]\n>> +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n> \n> This will declare these \"static inline\". Our other major \"macros become\n> inline functions\" code is commit-slab.h, and there we found it necessary\n> to add MAYBE_UNUSED. I wonder if we ought to be doing the same here (I\n> don't get any warnings, but I suspect sparse might complain).\n\nI doubt it (but didn't check) because khash.h defines kh_clear_##name(),\nwhich we don't use it anywhere and there have been no complaints so far.\nAnd if we wanted to add MAYBE_UNUSED then the right place for that would\nbe in KHASH_INIT, no?\n\n> It might be nice if these functions could hide inside oidset.c (and just\n> declare the struct here). It looks like we might be able to do that with\n> __KHASH_TYPE(), but the double-underscore implies that we're not\n> supposed to. ;)\n> \n> I guess we also use a few of them in our inlines here. I'm not 100% sure\n> that oidset_* needs to be inlined either, but this is at least a pretty\n> faithful conversion of the original.\n\nWe could inline all of the oidset functions, following the spirit of\nklib/khash.h.\n\nOr we could uninline all of them and then may be able to clean up\noidset.h by using KHASH_DECLARE.  Perhaps we'd need to guard with an\n\"#ifndef THIS_IS_OIDSET_C\" or similar to avoid a clash with KHASH_INIT.\n\nNot sure if any of that would be a worthwhile improvement..\n\nRené\n"},{"id":"359605","messageId":"20181004064833.GA9051@sigill.intra.peff.net","threadId":"49478","inReplyTo":"d17f104e-7cc2-5e73-78c9-6c268f9ec5b2@web.de","subject":"Re: [PATCH v2 2/2] oidset: use khash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-04T06:48:34Z","receivedAt":"2018-10-04T06:48:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2018 at 07:56:44AM +0200, René Scharfe wrote:\n\n> > As the comment above notes, I think we're really looking at the case\n> > where this gets populated on the first call, but not subsequent ones. It\n> > might be less hacky to use a \"static int initialized\" here. Or if we\n> > want to avoid hidden globals, put the logic into filter_refs() to decide\n> > when to populate.\n> \n> Right.  I'd prefer the latter, but was unable to find a nice way that\n> still populates the oidset lazily.  It's certainly worth another look,\n> and a separate series.\n\nIt's a little awkward because the lazy load happens in a conditional.\nYou can fully encapsulate it like the patch below, but I actually don't\nthink it's really helping readability.\n\n> >> +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n> > \n> > This will declare these \"static inline\". Our other major \"macros become\n> > inline functions\" code is commit-slab.h, and there we found it necessary\n> > to add MAYBE_UNUSED. I wonder if we ought to be doing the same here (I\n> > don't get any warnings, but I suspect sparse might complain).\n> \n> I doubt it (but didn't check) because khash.h defines kh_clear_##name(),\n> which we don't use it anywhere and there have been no complaints so far.\n> And if we wanted to add MAYBE_UNUSED then the right place for that would\n> be in KHASH_INIT, no?\n\nRight, that would be the correct spot. I'm OK to leave it until somebody\ncomplains. Looking at commit-slab again, its functions are straight\nstatics, not static inline. That's probably the important difference.\n\n> > It might be nice if these functions could hide inside oidset.c (and just\n> > declare the struct here). It looks like we might be able to do that with\n> > __KHASH_TYPE(), but the double-underscore implies that we're not\n> > supposed to. ;)\n> > \n> > I guess we also use a few of them in our inlines here. I'm not 100% sure\n> > that oidset_* needs to be inlined either, but this is at least a pretty\n> > faithful conversion of the original.\n> \n> We could inline all of the oidset functions, following the spirit of\n> klib/khash.h.\n> \n> Or we could uninline all of them and then may be able to clean up\n> oidset.h by using KHASH_DECLARE.  Perhaps we'd need to guard with an\n> \"#ifndef THIS_IS_OIDSET_C\" or similar to avoid a clash with KHASH_INIT.\n> \n> Not sure if any of that would be a worthwhile improvement..\n\nUnless we know something is a performance win to inline, I'd generally\nprefer not to.\n\nFor a case like this with auto-generated functions, I'm mostly worried\nabout bloating the compiled code. Either with a bunch of inlined\nnon-trivial functions, or cases where the compiler says \"this is too big\nto inline\" and generates an anonymous file-scope function, but we end up\nwith a bunch of duplicates, because we're generating the same functions\nin a bunch of C files.\n\nI may be worried about nothing, though. I don't know how clever the\ncompiler and linker can be there.\n\n-Peff\n"},{"id":"359606","messageId":"20181004065030.GA15613@sigill.intra.peff.net","threadId":"49478","inReplyTo":"20181004064833.GA9051@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/2] oidset: use khash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-04T06:50:30Z","receivedAt":"2018-10-04T06:50:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2018 at 02:48:33AM -0400, Jeff King wrote:\n\n> On Thu, Oct 04, 2018 at 07:56:44AM +0200, René Scharfe wrote:\n> \n> > > As the comment above notes, I think we're really looking at the case\n> > > where this gets populated on the first call, but not subsequent ones. It\n> > > might be less hacky to use a \"static int initialized\" here. Or if we\n> > > want to avoid hidden globals, put the logic into filter_refs() to decide\n> > > when to populate.\n> > \n> > Right.  I'd prefer the latter, but was unable to find a nice way that\n> > still populates the oidset lazily.  It's certainly worth another look,\n> > and a separate series.\n> \n> It's a little awkward because the lazy load happens in a conditional.\n> You can fully encapsulate it like the patch below, but I actually don't\n> think it's really helping readability.\n\nI forgot the patch, of course. ;)\n\nI'm not really proposing this, just illustrating one direction (that I\nthink is kind of ugly). Notably it doesn't get rid of the tricky comment\nin tip_oids_contain(), because that is explaining why the single load\nworks even on a list we're still adding to.\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex a839315726..a6212c8758 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -526,8 +526,14 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)\n \t\toidset_insert(oids, &refs->old_oid);\n }\n \n-static int tip_oids_contain(struct oidset *tip_oids,\n-\t\t\t    struct ref *unmatched, struct ref *newlist,\n+struct lazy_tip_oids {\n+\tint loaded;\n+\tstruct oidset oids;\n+\tstruct ref *unmatched;\n+\tstruct ref *newlist;\n+};\n+\n+static int tip_oids_contain(struct lazy_tip_oids *tip_oids,\n \t\t\t    const struct object_id *id)\n {\n \t/*\n@@ -536,11 +542,12 @@ static int tip_oids_contain(struct oidset *tip_oids,\n \t * add to \"newlist\" between calls, the additions will always be for\n \t * oids that are already in the set.\n \t */\n-\tif (!tip_oids->set.n_buckets) {\n-\t\tadd_refs_to_oidset(tip_oids, unmatched);\n-\t\tadd_refs_to_oidset(tip_oids, newlist);\n+\tif (!tip_oids->loaded) {\n+\t\tadd_refs_to_oidset(&tip_oids->oids, tip_oids->unmatched);\n+\t\tadd_refs_to_oidset(&tip_oids->oids, tip_oids->newlist);\n+\t\ttip_oids->loaded = 1;\n \t}\n-\treturn oidset_contains(tip_oids, id);\n+\treturn oidset_contains(&tip_oids->oids, id);\n }\n \n static void filter_refs(struct fetch_pack_args *args,\n@@ -551,7 +558,7 @@ static void filter_refs(struct fetch_pack_args *args,\n \tstruct ref **newtail = &newlist;\n \tstruct ref *unmatched = NULL;\n \tstruct ref *ref, *next;\n-\tstruct oidset tip_oids = OIDSET_INIT;\n+\tstruct lazy_tip_oids tip_oids = { 0 };\n \tint i;\n \n \ti = 0;\n@@ -589,6 +596,9 @@ static void filter_refs(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\ttip_oids.unmatched = unmatched;\n+\ttip_oids.newlist = newlist;\n+\n \t/* Append unmatched requests to the list */\n \tfor (i = 0; i < nr_sought; i++) {\n \t\tstruct object_id oid;\n@@ -604,8 +614,7 @@ static void filter_refs(struct fetch_pack_args *args,\n \n \t\tif ((allow_unadvertised_object_request &\n \t\t     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||\n-\t\t    tip_oids_contain(&tip_oids, unmatched, newlist,\n-\t\t\t\t     &ref->old_oid)) {\n+\t\t    tip_oids_contain(&tip_oids, &ref->old_oid)) {\n \t\t\tref->match_status = REF_MATCHED;\n \t\t\t*newtail = copy_ref(ref);\n \t\t\tnewtail = &(*newtail)->next;\n@@ -614,7 +623,7 @@ static void filter_refs(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n-\toidset_clear(&tip_oids);\n+\toidset_clear(&tip_oids.oids);\n \tfor (ref = unmatched; ref; ref = next) {\n \t\tnext = ref->next;\n \t\tfree(ref);\n"},{"id":"359620","messageId":"413fc698-87f8-f1ee-810a-ec9b143db299@web.de","threadId":"49478","inReplyTo":"20181004064833.GA9051@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/2] oidset: use khash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:05:09Z","receivedAt":"2018-10-04T15:05:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 04.10.2018 um 08:48 schrieb Jeff King:\n> On Thu, Oct 04, 2018 at 07:56:44AM +0200, René Scharfe wrote:\n> \n>>> As the comment above notes, I think we're really looking at the case\n>>> where this gets populated on the first call, but not subsequent ones. It\n>>> might be less hacky to use a \"static int initialized\" here. Or if we\n>>> want to avoid hidden globals, put the logic into filter_refs() to decide\n>>> when to populate.\n>>\n>> Right.  I'd prefer the latter, but was unable to find a nice way that\n>> still populates the oidset lazily.  It's certainly worth another look,\n>> and a separate series.\n> \n> It's a little awkward because the lazy load happens in a conditional.\n> You can fully encapsulate it like the patch below, but I actually don't\n> think it's really helping readability.\n\n*Shudder*\n\n>>> It might be nice if these functions could hide inside oidset.c (and just\n>>> declare the struct here). It looks like we might be able to do that with\n>>> __KHASH_TYPE(), but the double-underscore implies that we're not\n>>> supposed to. ;)\n>>>\n>>> I guess we also use a few of them in our inlines here. I'm not 100% sure\n>>> that oidset_* needs to be inlined either, but this is at least a pretty\n>>> faithful conversion of the original.\n>>\n>> We could inline all of the oidset functions, following the spirit of\n>> klib/khash.h.\n>>\n>> Or we could uninline all of them and then may be able to clean up\n>> oidset.h by using KHASH_DECLARE.  Perhaps we'd need to guard with an\n>> \"#ifndef THIS_IS_OIDSET_C\" or similar to avoid a clash with KHASH_INIT.\n>>\n>> Not sure if any of that would be a worthwhile improvement..\n> \n> Unless we know something is a performance win to inline, I'd generally\n> prefer not to.\n\nAgreed.\n\n> For a case like this with auto-generated functions, I'm mostly worried\n> about bloating the compiled code. Either with a bunch of inlined\n> non-trivial functions, or cases where the compiler says \"this is too big\n> to inline\" and generates an anonymous file-scope function, but we end up\n> with a bunch of duplicates, because we're generating the same functions\n> in a bunch of C files.\n\nThe _iter_ functions look harmless in this regard, as the only use small\nfunctions that are not even type-specific.\n\noidset_init() would better be moved to oidset.c, as the code for resizing\nis quite big.\n\nRené\n"},{"id":"359622","messageId":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","threadId":"49478","inReplyTo":"64911aec-71cd-d990-5dfd-bf2c3163690c@web.de","subject":"[PATCH v3 0/5] oidset: use khash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:05:37Z","receivedAt":"2018-10-04T15:05:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Two new patches to avoid using oidset internals in fetch-pack:\n\n  fetch-pack: factor out is_unmatched_ref()\n  fetch-pack: load tip_oids eagerly iff needed\n\nUnchanged patch:\n\n  khash: factor out kh_release_*\n\nUnchanged, except it doesn't touch fetch-pack anymore:\n\n  oidset: use khash\n\nA new patch, to reduce object text size:\n\n  oidset: uninline oidset_init()\n\n fetch-pack.c | 49 +++++++++++++++++++++++--------------------------\n khash.h      |  9 +++++++--\n oidset.c     | 41 +++++++++++++++++++----------------------\n oidset.h     | 43 ++++++++++++++++++++++++++++++++-----------\n 4 files changed, 81 insertions(+), 61 deletions(-)\n\n-- \n2.19.0\n\n"},{"id":"359623","messageId":"9a7ab468-8d6e-c3d0-3960-b05f06534de5@web.de","threadId":"49478","inReplyTo":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","subject":"[PATCH v3 1/5] fetch-pack: factor out is_unmatched_ref()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:09:06Z","receivedAt":"2018-10-04T15:09:20Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Move the code to determine if a request is unmatched to its own little\nhelper.  This allows us to reuse it in a subsequent patch.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n fetch-pack.c | 19 +++++++++++--------\n 1 file changed, 11 insertions(+), 8 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 75047a4b2a..3b317952f0 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -543,6 +543,16 @@ static int tip_oids_contain(struct oidset *tip_oids,\n \treturn oidset_contains(tip_oids, id);\n }\n \n+static int is_unmatched_ref(const struct ref *ref)\n+{\n+\tstruct object_id oid;\n+\tconst char *p;\n+\treturn\tref->match_status == REF_NOT_MATCHED &&\n+\t\t!parse_oid_hex(ref->name, &oid, &p) &&\n+\t\t*p == '\\0' &&\n+\t\toideq(&oid, &ref->old_oid);\n+}\n+\n static void filter_refs(struct fetch_pack_args *args,\n \t\t\tstruct ref **refs,\n \t\t\tstruct ref **sought, int nr_sought)\n@@ -591,15 +601,8 @@ static void filter_refs(struct fetch_pack_args *args,\n \n \t/* Append unmatched requests to the list */\n \tfor (i = 0; i < nr_sought; i++) {\n-\t\tstruct object_id oid;\n-\t\tconst char *p;\n-\n \t\tref = sought[i];\n-\t\tif (ref->match_status != REF_NOT_MATCHED)\n-\t\t\tcontinue;\n-\t\tif (parse_oid_hex(ref->name, &oid, &p) ||\n-\t\t    *p != '\\0' ||\n-\t\t    !oideq(&oid, &ref->old_oid))\n+\t\tif (!is_unmatched_ref(ref))\n \t\t\tcontinue;\n \n \t\tif ((allow_unadvertised_object_request &\n-- \n2.19.0\n"},{"id":"359624","messageId":"9f51ac28-73e9-2855-c650-7d695945e286@web.de","threadId":"49478","inReplyTo":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","subject":"[PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:09:39Z","receivedAt":"2018-10-04T15:09:50Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"tip_oids_contain() lazily loads refs into an oidset at its first call.\nIt abuses the internal (sub)member .map.tablesize of that oidset to\ncheck if it has done that already.\n\nDetermine if the oidset needs to be populated upfront and then do that\ninstead.  This duplicates a loop, but simplifies the existing one by\nseparating concerns between the two.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n fetch-pack.c | 36 +++++++++++++++---------------------\n 1 file changed, 15 insertions(+), 21 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 3b317952f0..53914563b5 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)\n \t\toidset_insert(oids, &refs->old_oid);\n }\n \n-static int tip_oids_contain(struct oidset *tip_oids,\n-\t\t\t    struct ref *unmatched, struct ref *newlist,\n-\t\t\t    const struct object_id *id)\n-{\n-\t/*\n-\t * Note that this only looks at the ref lists the first time it's\n-\t * called. This works out in filter_refs() because even though it may\n-\t * add to \"newlist\" between calls, the additions will always be for\n-\t * oids that are already in the set.\n-\t */\n-\tif (!tip_oids->map.map.tablesize) {\n-\t\tadd_refs_to_oidset(tip_oids, unmatched);\n-\t\tadd_refs_to_oidset(tip_oids, newlist);\n-\t}\n-\treturn oidset_contains(tip_oids, id);\n-}\n-\n static int is_unmatched_ref(const struct ref *ref)\n {\n \tstruct object_id oid;\n@@ -563,6 +546,8 @@ static void filter_refs(struct fetch_pack_args *args,\n \tstruct ref *ref, *next;\n \tstruct oidset tip_oids = OIDSET_INIT;\n \tint i;\n+\tint strict = !(allow_unadvertised_object_request &\n+\t\t       (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));\n \n \ti = 0;\n \tfor (ref = *refs; ref; ref = next) {\n@@ -599,16 +584,25 @@ static void filter_refs(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\tif (strict) {\n+\t\tfor (i = 0; i < nr_sought; i++) {\n+\t\t\tref = sought[i];\n+\t\t\tif (!is_unmatched_ref(ref))\n+\t\t\t\tcontinue;\n+\n+\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n+\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n \t/* Append unmatched requests to the list */\n \tfor (i = 0; i < nr_sought; i++) {\n \t\tref = sought[i];\n \t\tif (!is_unmatched_ref(ref))\n \t\t\tcontinue;\n \n-\t\tif ((allow_unadvertised_object_request &\n-\t\t     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||\n-\t\t    tip_oids_contain(&tip_oids, unmatched, newlist,\n-\t\t\t\t     &ref->old_oid)) {\n+\t\tif (!strict || oidset_contains(&tip_oids, &ref->old_oid)) {\n \t\t\tref->match_status = REF_MATCHED;\n \t\t\t*newtail = copy_ref(ref);\n \t\t\tnewtail = &(*newtail)->next;\n-- \n2.19.0\n"},{"id":"359625","messageId":"46f34917-eafd-2970-17f4-c2df92a00352@web.de","threadId":"49478","inReplyTo":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","subject":"[PATCH v3 3/5] khash: factor out kh_release_*","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:10:54Z","receivedAt":"2018-10-04T15:11:06Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a function for releasing the khash-internal allocations, but not the\nkhash structure itself.  It can be used with on-stack khash structs.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n1 tab = 4 spaces here.\n\n khash.h | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/khash.h b/khash.h\nindex 07b4cc2e67..d10caa0c35 100644\n--- a/khash.h\n+++ b/khash.h\n@@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77;\n \tSCOPE kh_##name##_t *kh_init_##name(void) {\t\t\t\t\t\t\t\\\n \t\treturn (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));\t\t\\\n \t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\tSCOPE void kh_release_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n+\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree(h->flags);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree((void *)h->keys);\t\t\t\t\t\t\t\t\t\t\t\\\n+\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \tSCOPE void kh_destroy_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n \t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t\tif (h) {\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tfree((void *)h->keys); free(h->flags);\t\t\t\t\t\\\n-\t\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\\\n+\t\t\tkh_release_##name(h);\t\t\t\t\t\t\t\t\t\t\\\n \t\t\tfree(h);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n \t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-- \n2.19.0\n"},{"id":"359626","messageId":"3651262f-dec2-16d4-fc77-346ed74c6ffa@web.de","threadId":"49478","inReplyTo":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","subject":"[PATCH v3 4/5] oidset: use khash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:13:06Z","receivedAt":"2018-10-04T15:13:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Reimplement oidset using khash.h in order to reduce its memory footprint\nand make it faster.\n\nPerformance of a command that mainly checks for duplicate objects using\nan oidset, with master and Clang 6.0.1:\n\n  $ cmd=\"./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\"\n\n  $ /usr/bin/time $cmd >/dev/null\n  0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k\n  0inputs+0outputs (0major+11204minor)pagefaults 0swaps\n\n  $ hyperfine \"$cmd\"\n  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n\n    Time (mean ± σ):     250.0 ms ±   6.0 ms    [User: 225.9 ms, System: 23.6 ms]\n\n    Range (min … max):   242.0 ms … 261.1 ms\n\nAnd with this patch:\n\n  $ /usr/bin/time $cmd >/dev/null\n  0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k\n  0inputs+0outputs (0major+8318minor)pagefaults 0swaps\n\n  $ hyperfine \"$cmd\"\n  Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'\n\n    Time (mean ± σ):     151.9 ms ±   4.9 ms    [User: 130.5 ms, System: 21.2 ms]\n\n    Range (min … max):   148.2 ms … 170.4 ms\n\nInitial-patch-by: Jeff King <peff@peff.net>\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n oidset.c | 34 ++++++++++++----------------------\n oidset.h | 36 ++++++++++++++++++++++++++++--------\n 2 files changed, 40 insertions(+), 30 deletions(-)\n\ndiff --git a/oidset.c b/oidset.c\nindex 454c54f933..9836d427ef 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -3,38 +3,28 @@\n \n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n-\tif (!set->map.map.tablesize)\n-\t\treturn 0;\n-\treturn !!oidmap_get(&set->map, oid);\n+\tkhiter_t pos = kh_get_oid(&set->set, *oid);\n+\treturn pos != kh_end(&set->set);\n }\n \n int oidset_insert(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n-\n-\tif (!set->map.map.tablesize)\n-\t\toidmap_init(&set->map, 0);\n-\telse if (oidset_contains(set, oid))\n-\t\treturn 1;\n-\n-\tentry = xmalloc(sizeof(*entry));\n-\toidcpy(&entry->oid, oid);\n-\n-\toidmap_put(&set->map, entry);\n-\treturn 0;\n+\tint added;\n+\tkh_put_oid(&set->set, *oid, &added);\n+\treturn !added;\n }\n \n int oidset_remove(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidmap_entry *entry;\n-\n-\tentry = oidmap_remove(&set->map, oid);\n-\tfree(entry);\n-\n-\treturn (entry != NULL);\n+\tkhiter_t pos = kh_get_oid(&set->set, *oid);\n+\tif (pos == kh_end(&set->set))\n+\t\treturn 0;\n+\tkh_del_oid(&set->set, pos);\n+\treturn 1;\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\toidmap_free(&set->map, 1);\n+\tkh_release_oid(&set->set);\n+\toidset_init(set, 0);\n }\ndiff --git a/oidset.h b/oidset.h\nindex 40ec5f87fe..4b90540cd4 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -1,7 +1,8 @@\n #ifndef OIDSET_H\n #define OIDSET_H\n \n-#include \"oidmap.h\"\n+#include \"hashmap.h\"\n+#include \"khash.h\"\n \n /**\n  * This API is similar to sha1-array, in that it maintains a set of object ids\n@@ -15,19 +16,33 @@\n  *      table overhead.\n  */\n \n+static inline unsigned int oid_hash(struct object_id oid)\n+{\n+\treturn sha1hash(oid.hash);\n+}\n+\n+static inline int oid_equal(struct object_id a, struct object_id b)\n+{\n+\treturn oideq(&a, &b);\n+}\n+\n+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)\n+\n /**\n  * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n  */\n struct oidset {\n-\tstruct oidmap map;\n+\tkh_oid_t set;\n };\n \n-#define OIDSET_INIT { OIDMAP_INIT }\n+#define OIDSET_INIT { { 0 } }\n \n \n static inline void oidset_init(struct oidset *set, size_t initial_size)\n {\n-\toidmap_init(&set->map, initial_size);\n+\tmemset(&set->set, 0, sizeof(set->set));\n+\tif (initial_size)\n+\t\tkh_resize_oid(&set->set, initial_size);\n }\n \n /**\n@@ -58,19 +73,24 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);\n void oidset_clear(struct oidset *set);\n \n struct oidset_iter {\n-\tstruct oidmap_iter m_iter;\n+\tkh_oid_t *set;\n+\tkhiter_t iter;\n };\n \n static inline void oidset_iter_init(struct oidset *set,\n \t\t\t\t    struct oidset_iter *iter)\n {\n-\toidmap_iter_init(&set->map, &iter->m_iter);\n+\titer->set = &set->set;\n+\titer->iter = kh_begin(iter->set);\n }\n \n static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)\n {\n-\tstruct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);\n-\treturn e ? &e->oid : NULL;\n+\tfor (; iter->iter != kh_end(iter->set); iter->iter++) {\n+\t\tif (kh_exist(iter->set, iter->iter))\n+\t\t\treturn &kh_key(iter->set, iter->iter++);\n+\t}\n+\treturn NULL;\n }\n \n static inline struct object_id *oidset_iter_first(struct oidset *set,\n-- \n2.19.0\n"},{"id":"359627","messageId":"f3d21da8-ae3a-6483-1d61-f25ad238df1e@web.de","threadId":"49478","inReplyTo":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","subject":"[PATCH 5/5] oidset: uninline oidset_init()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T15:14:37Z","receivedAt":"2018-10-04T15:14:49Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"There is no need to inline oidset_init(), as it's typically only called\ntwice in the lifetime of an oidset (once at the beginning and at the end\nby oidset_clear()) and kh_resize_* is quite big, so move its definition\nto oidset.c.  Document it while we're at it.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n oidset.c |  7 +++++++\n oidset.h | 13 +++++++------\n 2 files changed, 14 insertions(+), 6 deletions(-)\n\ndiff --git a/oidset.c b/oidset.c\nindex 9836d427ef..fe4eb921df 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -1,6 +1,13 @@\n #include \"cache.h\"\n #include \"oidset.h\"\n \n+void oidset_init(struct oidset *set, size_t initial_size)\n+{\n+\tmemset(&set->set, 0, sizeof(set->set));\n+\tif (initial_size)\n+\t\tkh_resize_oid(&set->set, initial_size);\n+}\n+\n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n \tkhiter_t pos = kh_get_oid(&set->set, *oid);\ndiff --git a/oidset.h b/oidset.h\nindex 4b90540cd4..c9d0f6d3cc 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -38,12 +38,13 @@ struct oidset {\n #define OIDSET_INIT { { 0 } }\n \n \n-static inline void oidset_init(struct oidset *set, size_t initial_size)\n-{\n-\tmemset(&set->set, 0, sizeof(set->set));\n-\tif (initial_size)\n-\t\tkh_resize_oid(&set->set, initial_size);\n-}\n+/**\n+ * Initialize the oidset structure `set`.\n+ *\n+ * If `initial_size` is bigger than 0 then preallocate to allow inserting\n+ * the specified number of elements without further allocations.\n+ */\n+void oidset_init(struct oidset *set, size_t initial_size);\n \n /**\n  * Returns true iff `set` contains `oid`.\n-- \n2.19.0\n"},{"id":"359635","messageId":"20181004213813.158688-1-jonathantanmy@google.com","threadId":"49478","inReplyTo":"9f51ac28-73e9-2855-c650-7d695945e286@web.de","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-10-04T21:38:13Z","receivedAt":"2018-10-04T21:38:19Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Determine if the oidset needs to be populated upfront and then do that\n> instead.  This duplicates a loop, but simplifies the existing one by\n> separating concerns between the two.\n\n[snip]\n\n> +\tif (strict) {\n> +\t\tfor (i = 0; i < nr_sought; i++) {\n> +\t\t\tref = sought[i];\n> +\t\t\tif (!is_unmatched_ref(ref))\n> +\t\t\t\tcontinue;\n> +\n> +\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n> +\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n> +\t\t\tbreak;\n> +\t\t}\n> +\t}\n> +\n>  \t/* Append unmatched requests to the list */\n>  \tfor (i = 0; i < nr_sought; i++) {\n>  \t\tref = sought[i];\n>  \t\tif (!is_unmatched_ref(ref))\n>  \t\t\tcontinue;\n>  \n> -\t\tif ((allow_unadvertised_object_request &\n> -\t\t     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||\n> -\t\t    tip_oids_contain(&tip_oids, unmatched, newlist,\n> -\t\t\t\t     &ref->old_oid)) {\n> +\t\tif (!strict || oidset_contains(&tip_oids, &ref->old_oid)) {\n>  \t\t\tref->match_status = REF_MATCHED;\n>  \t\t\t*newtail = copy_ref(ref);\n>  \t\t\tnewtail = &(*newtail)->next;\n\nI don't think the concerns are truly separated - the first loop quoted\nneeds to know that in the second loop, tip_oids is accessed only if\nthere is at least one unmatched ref. Would it be better to expose the\nsize of the oidset and then use it in place of\n\"tip_oids->map.map.tablesize\"? Checking for initialization (using\n\"tablesize\") is conceptually different from checking the size, but in\nthis code, both initialization and the first increase in size occur upon\nthe first oidset_insert(), so we should still get the same result.\n\nBut if we do end up going with the approach in this patch, then this\npatch is obviously correct.\n\nI also looked at patch 1 of this patch set and it is obviously correct.\nI didn't look at the other patches.\n"},{"id":"359638","messageId":"20181004220711.GA28287@sigill.intra.peff.net","threadId":"49478","inReplyTo":"9f51ac28-73e9-2855-c650-7d695945e286@web.de","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-04T22:07:11Z","receivedAt":"2018-10-04T22:07:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2018 at 05:09:39PM +0200, René Scharfe wrote:\n\n> tip_oids_contain() lazily loads refs into an oidset at its first call.\n> It abuses the internal (sub)member .map.tablesize of that oidset to\n> check if it has done that already.\n> \n> Determine if the oidset needs to be populated upfront and then do that\n> instead.  This duplicates a loop, but simplifies the existing one by\n> separating concerns between the two.\n\nI like this approach much better than what I showed earlier. But...\n\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 3b317952f0..53914563b5 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)\n>  \t\toidset_insert(oids, &refs->old_oid);\n>  }\n>  \n> -static int tip_oids_contain(struct oidset *tip_oids,\n> -\t\t\t    struct ref *unmatched, struct ref *newlist,\n> -\t\t\t    const struct object_id *id)\n> -{\n> -\t/*\n> -\t * Note that this only looks at the ref lists the first time it's\n> -\t * called. This works out in filter_refs() because even though it may\n> -\t * add to \"newlist\" between calls, the additions will always be for\n> -\t * oids that are already in the set.\n> -\t */\n\nI don't think the subtle point this comment is making goes away. We're\nstill growing the list in the loop that calls tip_oids_contain() (and\nwhich now calls just oidset_contains). That's OK for the reasons given\nhere, but I think that would need to be moved down to this code:\n\n> +\tif (strict) {\n> +\t\tfor (i = 0; i < nr_sought; i++) {\n> +\t\t\tref = sought[i];\n> +\t\t\tif (!is_unmatched_ref(ref))\n> +\t\t\t\tcontinue;\n> +\n> +\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n> +\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n> +\t\t\tbreak;\n> +\t\t}\n> +\t}\n\nI.e., we need to say here why it's OK to summarize newlist in the\noidset, even though we're adding to it later.\n\n-Peff\n"},{"id":"359639","messageId":"a82bf622-8ef8-5525-c3a8-b983d0cfe662@web.de","threadId":"49478","inReplyTo":"20181004213813.158688-1-jonathantanmy@google.com","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-04T22:11:14Z","receivedAt":"2018-10-04T22:11:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 04.10.2018 um 23:38 schrieb Jonathan Tan:\n>> Determine if the oidset needs to be populated upfront and then do that\n>> instead.  This duplicates a loop, but simplifies the existing one by\n>> separating concerns between the two.\n> \n> [snip]\n> \n>> +\tif (strict) {\n>> +\t\tfor (i = 0; i < nr_sought; i++) {\n>> +\t\t\tref = sought[i];\n>> +\t\t\tif (!is_unmatched_ref(ref))\n>> +\t\t\t\tcontinue;\n>> +\n>> +\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n>> +\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n>> +\t\t\tbreak;\n>> +\t\t}\n>> +\t}\n>> +\n>>  \t/* Append unmatched requests to the list */\n>>  \tfor (i = 0; i < nr_sought; i++) {\n>>  \t\tref = sought[i];\n>>  \t\tif (!is_unmatched_ref(ref))\n>>  \t\t\tcontinue;\n>>  \n>> -\t\tif ((allow_unadvertised_object_request &\n>> -\t\t     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||\n>> -\t\t    tip_oids_contain(&tip_oids, unmatched, newlist,\n>> -\t\t\t\t     &ref->old_oid)) {\n>> +\t\tif (!strict || oidset_contains(&tip_oids, &ref->old_oid)) {\n>>  \t\t\tref->match_status = REF_MATCHED;\n>>  \t\t\t*newtail = copy_ref(ref);\n>>  \t\t\tnewtail = &(*newtail)->next;\n> \n> I don't think the concerns are truly separated - the first loop quoted\n> needs to know that in the second loop, tip_oids is accessed only if\n> there is at least one unmatched ref.\n\nRight, the two loops are still closely related, but only the first one\nis concerned with loading refs.\n\nFor a true separation we could first build a list of unmatched refs and\nthen loop through that instead of `sought`.  Not sure if that's better,\nbut maybe the overhead I imagine it would introduce isn't all that big.\n\n> Would it be better to expose the\n> size of the oidset and then use it in place of\n> \"tip_oids->map.map.tablesize\"? Checking for initialization (using\n> \"tablesize\") is conceptually different from checking the size, but in\n> this code, both initialization and the first increase in size occur upon\n> the first oidset_insert(), so we should still get the same result.\n\nIt would work in practice.  If there are no refs to load then it would\ntry to load those zero refs for each unmatched ref, which shouldn't\nreally be a problem, but I still find it a wee bit sloppy.  Too\ntheoretical?\n\nRené\n"},{"id":"359640","messageId":"20181004221406.GB28287@sigill.intra.peff.net","threadId":"49478","inReplyTo":"20181004213813.158688-1-jonathantanmy@google.com","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-04T22:14:06Z","receivedAt":"2018-10-04T22:14:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2018 at 02:38:13PM -0700, Jonathan Tan wrote:\n\n> > -\t\tif ((allow_unadvertised_object_request &\n> > -\t\t     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||\n> > -\t\t    tip_oids_contain(&tip_oids, unmatched, newlist,\n> > -\t\t\t\t     &ref->old_oid)) {\n> > +\t\tif (!strict || oidset_contains(&tip_oids, &ref->old_oid)) {\n> >  \t\t\tref->match_status = REF_MATCHED;\n> >  \t\t\t*newtail = copy_ref(ref);\n> >  \t\t\tnewtail = &(*newtail)->next;\n> \n> I don't think the concerns are truly separated - the first loop quoted\n> needs to know that in the second loop, tip_oids is accessed only if\n> there is at least one unmatched ref. Would it be better to expose the\n> size of the oidset and then use it in place of\n> \"tip_oids->map.map.tablesize\"? Checking for initialization (using\n> \"tablesize\") is conceptually different from checking the size, but in\n> this code, both initialization and the first increase in size occur upon\n> the first oidset_insert(), so we should still get the same result.\n\nYes, I agree with you that the loops are still entwined. They're at\nleast now in a single function, though, which IMHO is a slight\nimprovement.\n\nI agree with you that just checking:\n\n  if (oidset_count() != 0)\n\nwould be fine, too. Or I am even OK with leaving the existing tablesize\ncheck. It is a little intimate with the implementation details, but I\nsuspect that if oidset were to change (e.g., to initialize the buckets\nimmediately), the problem would be pretty apparent in the tests.\n\nAnd in fact, we can test by just changing the conditional in\ntip_oid_contains to if(0), which quite clearly fails t5500.60 (along\nwith others).\n\nSo I don't think it's the end of the world to leave it (but I also am\nnot opposed to the other options discussed).\n\n-Peff\n"},{"id":"359641","messageId":"20181004221531.GC28287@sigill.intra.peff.net","threadId":"49478","inReplyTo":"14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de","subject":"Re: [PATCH v3 0/5] oidset: use khash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-04T22:15:32Z","receivedAt":"2018-10-04T22:15:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2018 at 05:05:37PM +0200, René Scharfe wrote:\n\n> Two new patches to avoid using oidset internals in fetch-pack:\n> \n>   fetch-pack: factor out is_unmatched_ref()\n>   fetch-pack: load tip_oids eagerly iff needed\n> \n> Unchanged patch:\n> \n>   khash: factor out kh_release_*\n> \n> Unchanged, except it doesn't touch fetch-pack anymore:\n> \n>   oidset: use khash\n> \n> A new patch, to reduce object text size:\n> \n>   oidset: uninline oidset_init()\n\nI left a few responses to the fetch-pack changes. The rest of it all\nlooks good to me. Certainly it's satisfying for the implementation-swap\nin patch 4 to be able to touch _only_ oidset.[ch].\n\n-Peff\n"},{"id":"359642","messageId":"20181004225205.176593-1-jonathantanmy@google.com","threadId":"49478","inReplyTo":"20181004221406.GB28287@sigill.intra.peff.net","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-10-04T22:52:05Z","receivedAt":"2018-10-04T22:52:11Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Yes, I agree with you that the loops are still entwined. They're at\n> least now in a single function, though, which IMHO is a slight\n> improvement.\n\nHmm...originally, the main functionality was in a single loop in a\nsingle function. But I say that because I consider the lazy loading in\ntip_oids_contain() as something both peripheral and independent (if the\nmain loop's logic changes, the lazy loading most likely does not need to\nbe changed).\n\n> I agree with you that just checking:\n> \n>   if (oidset_count() != 0)\n> \n> would be fine, too.\n\nOK, we're agreed on this :-)\n\n> Or I am even OK with leaving the existing tablesize\n> check. It is a little intimate with the implementation details, but I\n> suspect that if oidset were to change (e.g., to initialize the buckets\n> immediately), the problem would be pretty apparent in the tests.\n\nI am OK with this too, except that (as far as I can tell) the point of\nthis patch set is to replace the internals of oidset, so we no longer\nhave the tablesize check. Unless you meant the khash analog of\ntablesize? I would be OK if all tablesize references are replaced with\nthe khash analog in the same patch that the oidset internals are\nreplaced.\n"},{"id":"359648","messageId":"20181004231805.GA17146@sigill.intra.peff.net","threadId":"49478","inReplyTo":"20181004225205.176593-1-jonathantanmy@google.com","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-04T23:18:05Z","receivedAt":"2018-10-04T23:18:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 04, 2018 at 03:52:05PM -0700, Jonathan Tan wrote:\n\n> > Or I am even OK with leaving the existing tablesize\n> > check. It is a little intimate with the implementation details, but I\n> > suspect that if oidset were to change (e.g., to initialize the buckets\n> > immediately), the problem would be pretty apparent in the tests.\n> \n> I am OK with this too, except that (as far as I can tell) the point of\n> this patch set is to replace the internals of oidset, so we no longer\n> have the tablesize check. Unless you meant the khash analog of\n> tablesize? I would be OK if all tablesize references are replaced with\n> the khash analog in the same patch that the oidset internals are\n> replaced.\n\nYeah, in khash it's n_buckets, but it's basically the same thing. René's\noriginal patch did that update, and we were musing on whether there was\na way to avoid crossing the module boundary so intimately. Hence the\npatch you saw. :)\n\n-Peff\n"},{"id":"359735","messageId":"413be4ec-2473-c971-8545-3b7effbc157e@web.de","threadId":"49478","inReplyTo":"a82bf622-8ef8-5525-c3a8-b983d0cfe662@web.de","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-05T20:13:24Z","receivedAt":"2018-10-05T20:13:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.10.2018 um 00:11 schrieb René Scharfe:\n> Am 04.10.2018 um 23:38 schrieb Jonathan Tan:\n>> I don't think the concerns are truly separated - the first loop quoted\n>> needs to know that in the second loop, tip_oids is accessed only if\n>> there is at least one unmatched ref.\n> \n> Right, the two loops are still closely related, but only the first one\n> is concerned with loading refs.\n> \n> For a true separation we could first build a list of unmatched refs and\n> then loop through that instead of `sought`.  Not sure if that's better,\n> but maybe the overhead I imagine it would introduce isn't all that big.\n\nHere's what I mean, on top of the other two patches:\n\n---\n fetch-pack.c | 27 +++++++++++++--------------\n 1 file changed, 13 insertions(+), 14 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 53914563b5..7f28584bce 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -543,6 +543,8 @@ static void filter_refs(struct fetch_pack_args *args,\n \tstruct ref *newlist = NULL;\n \tstruct ref **newtail = &newlist;\n \tstruct ref *unmatched = NULL;\n+\tstruct ref **unfound;\n+\tint nr_unfound = 0;\n \tstruct ref *ref, *next;\n \tstruct oidset tip_oids = OIDSET_INIT;\n \tint i;\n@@ -584,23 +586,19 @@ static void filter_refs(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n-\tif (strict) {\n-\t\tfor (i = 0; i < nr_sought; i++) {\n-\t\t\tref = sought[i];\n-\t\t\tif (!is_unmatched_ref(ref))\n-\t\t\t\tcontinue;\n-\n-\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n-\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n-\t\t\tbreak;\n-\t\t}\n+\tALLOC_ARRAY(unfound, nr_sought);\n+\tfor (i = 0; i < nr_sought; i++) {\n+\t\tif (is_unmatched_ref(sought[i]))\n+\t\t\tunfound[nr_unfound++] = sought[i];\n+\t}\n+\tif (strict && nr_unfound) {\n+\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n+\t\tadd_refs_to_oidset(&tip_oids, newlist);\n \t}\n \n \t/* Append unmatched requests to the list */\n-\tfor (i = 0; i < nr_sought; i++) {\n-\t\tref = sought[i];\n-\t\tif (!is_unmatched_ref(ref))\n-\t\t\tcontinue;\n+\tfor (i = 0; i < nr_unfound; i++) {\n+\t\tref = unfound[i];\n \n \t\tif (!strict || oidset_contains(&tip_oids, &ref->old_oid)) {\n \t\t\tref->match_status = REF_MATCHED;\n@@ -611,6 +609,7 @@ static void filter_refs(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\tfree(unfound);\n \toidset_clear(&tip_oids);\n \tfor (ref = unmatched; ref; ref = next) {\n \t\tnext = ref->next;\n-- \n2.19.0\n"},{"id":"359736","messageId":"c75fa650-d2b4-9979-a1f2-25d75c6f447b@web.de","threadId":"49478","inReplyTo":"20181004220711.GA28287@sigill.intra.peff.net","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-05T20:13:34Z","receivedAt":"2018-10-05T20:13:45Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.10.2018 um 00:07 schrieb Jeff King:\n> On Thu, Oct 04, 2018 at 05:09:39PM +0200, René Scharfe wrote:\n> \n>> tip_oids_contain() lazily loads refs into an oidset at its first call.\n>> It abuses the internal (sub)member .map.tablesize of that oidset to\n>> check if it has done that already.\n>>\n>> Determine if the oidset needs to be populated upfront and then do that\n>> instead.  This duplicates a loop, but simplifies the existing one by\n>> separating concerns between the two.\n> \n> I like this approach much better than what I showed earlier. But...\n> \n>> diff --git a/fetch-pack.c b/fetch-pack.c\n>> index 3b317952f0..53914563b5 100644\n>> --- a/fetch-pack.c\n>> +++ b/fetch-pack.c\n>> @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)\n>>  \t\toidset_insert(oids, &refs->old_oid);\n>>  }\n>>  \n>> -static int tip_oids_contain(struct oidset *tip_oids,\n>> -\t\t\t    struct ref *unmatched, struct ref *newlist,\n>> -\t\t\t    const struct object_id *id)\n>> -{\n>> -\t/*\n>> -\t * Note that this only looks at the ref lists the first time it's\n>> -\t * called. This works out in filter_refs() because even though it may\n>> -\t * add to \"newlist\" between calls, the additions will always be for\n>> -\t * oids that are already in the set.\n>> -\t */\n> \n> I don't think the subtle point this comment is making goes away. We're\n> still growing the list in the loop that calls tip_oids_contain() (and\n> which now calls just oidset_contains). That's OK for the reasons given\n> here, but I think that would need to be moved down to this code:\n> \n>> +\tif (strict) {\n>> +\t\tfor (i = 0; i < nr_sought; i++) {\n>> +\t\t\tref = sought[i];\n>> +\t\t\tif (!is_unmatched_ref(ref))\n>> +\t\t\t\tcontinue;\n>> +\n>> +\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n>> +\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n>> +\t\t\tbreak;\n>> +\t\t}\n>> +\t}\n> \n> I.e., we need to say here why it's OK to summarize newlist in the\n> oidset, even though we're adding to it later.\n\nThere is already this comment:\n\n\t/* Append unmatched requests to the list */\n\nAnd that's enough in my eyes.  The refs loop at the top splits the list\ninto matched (\"the list\") and unmatched, and the loop below said comment\nadds a few more.  I see no subtlety left -- what do I miss?\n\nRené\n"},{"id":"359737","messageId":"20181005202737.GA22460@sigill.intra.peff.net","threadId":"49478","inReplyTo":"c75fa650-d2b4-9979-a1f2-25d75c6f447b@web.de","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-05T20:27:37Z","receivedAt":"2018-10-05T20:27:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 05, 2018 at 10:13:34PM +0200, René Scharfe wrote:\n\n> >> -{\n> >> -\t/*\n> >> -\t * Note that this only looks at the ref lists the first time it's\n> >> -\t * called. This works out in filter_refs() because even though it may\n> >> -\t * add to \"newlist\" between calls, the additions will always be for\n> >> -\t * oids that are already in the set.\n> >> -\t */\n> > \n> > I don't think the subtle point this comment is making goes away. We're\n> > still growing the list in the loop that calls tip_oids_contain() (and\n> > which now calls just oidset_contains). That's OK for the reasons given\n> > here, but I think that would need to be moved down to this code:\n> > \n> >> +\tif (strict) {\n> >> +\t\tfor (i = 0; i < nr_sought; i++) {\n> >> +\t\t\tref = sought[i];\n> >> +\t\t\tif (!is_unmatched_ref(ref))\n> >> +\t\t\t\tcontinue;\n> >> +\n> >> +\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n> >> +\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n> >> +\t\t\tbreak;\n> >> +\t\t}\n> >> +\t}\n> > \n> > I.e., we need to say here why it's OK to summarize newlist in the\n> > oidset, even though we're adding to it later.\n> \n> There is already this comment:\n> \n> \t/* Append unmatched requests to the list */\n> \n> And that's enough in my eyes.  The refs loop at the top splits the list\n> into matched (\"the list\") and unmatched, and the loop below said comment\n> adds a few more.  I see no subtlety left -- what do I miss?\n\nIt looks like tip_oids is meant as a fast lookup into what's in\nunmatched and newlist. But in the second loop we continue appending to\nnewlist. Why is it OK that we do not update tip_oids when we do so?\n\nI.e., something like this explains it:\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 53914563b5..c0a1b80f4c 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args,\n \t\t\tref->match_status = REF_MATCHED;\n \t\t\t*newtail = copy_ref(ref);\n \t\t\tnewtail = &(*newtail)->next;\n+\t\t\t/*\n+\t\t\t * No need to update tip_oids with ref->old_oid; we got\n+\t\t\t * here because either it was already there, or we are\n+\t\t\t * in !strict mode, in which case we do not use\n+\t\t\t * tip_oids at all.\n+\t\t\t */\n \t\t} else {\n \t\t\tref->match_status = REF_UNADVERTISED_NOT_ALLOWED;\n \t\t}\n"},{"id":"359739","messageId":"a5a5b0c5-cc97-dc50-56dd-25ec64c03e48@web.de","threadId":"49478","inReplyTo":"20181005202737.GA22460@sigill.intra.peff.net","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-05T21:22:31Z","receivedAt":"2018-10-05T21:22:44Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.10.2018 um 22:27 schrieb Jeff King:\n> On Fri, Oct 05, 2018 at 10:13:34PM +0200, René Scharfe wrote:\n> \n>>>> -{\n>>>> -\t/*\n>>>> -\t * Note that this only looks at the ref lists the first time it's\n>>>> -\t * called. This works out in filter_refs() because even though it may\n>>>> -\t * add to \"newlist\" between calls, the additions will always be for\n>>>> -\t * oids that are already in the set.\n>>>> -\t */\n>>>\n>>> I don't think the subtle point this comment is making goes away. We're\n>>> still growing the list in the loop that calls tip_oids_contain() (and\n>>> which now calls just oidset_contains). That's OK for the reasons given\n>>> here, but I think that would need to be moved down to this code:\n>>>\n>>>> +\tif (strict) {\n>>>> +\t\tfor (i = 0; i < nr_sought; i++) {\n>>>> +\t\t\tref = sought[i];\n>>>> +\t\t\tif (!is_unmatched_ref(ref))\n>>>> +\t\t\t\tcontinue;\n>>>> +\n>>>> +\t\t\tadd_refs_to_oidset(&tip_oids, unmatched);\n>>>> +\t\t\tadd_refs_to_oidset(&tip_oids, newlist);\n>>>> +\t\t\tbreak;\n>>>> +\t\t}\n>>>> +\t}\n>>>\n>>> I.e., we need to say here why it's OK to summarize newlist in the\n>>> oidset, even though we're adding to it later.\n>>\n>> There is already this comment:\n>>\n>> \t/* Append unmatched requests to the list */\n>>\n>> And that's enough in my eyes.  The refs loop at the top splits the list\n>> into matched (\"the list\") and unmatched, and the loop below said comment\n>> adds a few more.  I see no subtlety left -- what do I miss?\n> \n> It looks like tip_oids is meant as a fast lookup into what's in\n> unmatched and newlist. But in the second loop we continue appending to\n> newlist. Why is it OK that we do not update tip_oids when we do so?\n\n`tip_oids` contains the object_ids of the all `refs` passed to\nfilter_refs().  Instead of adding them at the top of the function that\nis done only when it has become clear that there are unmatched ones,\nas an optimization.  (That optimization was implemented by lazy-loading\nin tip_oids_contain() earlier.)  At that point the list has been split\ninto `newlist` and `unmatched`, so we load from them instead of `refs`.\n\n> \n> I.e., something like this explains it:\n> \n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 53914563b5..c0a1b80f4c 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args,\n>  \t\t\tref->match_status = REF_MATCHED;\n>  \t\t\t*newtail = copy_ref(ref);\n>  \t\t\tnewtail = &(*newtail)->next;\n> +\t\t\t/*\n> +\t\t\t * No need to update tip_oids with ref->old_oid; we got\n> +\t\t\t * here because either it was already there, or we are\n> +\t\t\t * in !strict mode, in which case we do not use\n> +\t\t\t * tip_oids at all.\n> +\t\t\t */\n>  \t\t} else {\n>  \t\t\tref->match_status = REF_UNADVERTISED_NOT_ALLOWED;\n>  \t\t}\n\nThis comment puzzles me -- why ask the question it answers?\n`tip_oids` has been loaded with all `refs` at that point; adding\nmore seems odd.\n\nI feel the code needs be simplified further; not sure how, though,\nexcept perhaps by using the `unfound` array added in another reply.\n\nRené\n"},{"id":"359749","messageId":"20181005214721.GA12992@sigill.intra.peff.net","threadId":"49478","inReplyTo":"a5a5b0c5-cc97-dc50-56dd-25ec64c03e48@web.de","subject":"Re: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-05T21:47:22Z","receivedAt":"2018-10-05T21:47:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 05, 2018 at 11:22:31PM +0200, René Scharfe wrote:\n\n> > diff --git a/fetch-pack.c b/fetch-pack.c\n> > index 53914563b5..c0a1b80f4c 100644\n> > --- a/fetch-pack.c\n> > +++ b/fetch-pack.c\n> > @@ -606,6 +606,12 @@ static void filter_refs(struct fetch_pack_args *args,\n> >  \t\t\tref->match_status = REF_MATCHED;\n> >  \t\t\t*newtail = copy_ref(ref);\n> >  \t\t\tnewtail = &(*newtail)->next;\n> > +\t\t\t/*\n> > +\t\t\t * No need to update tip_oids with ref->old_oid; we got\n> > +\t\t\t * here because either it was already there, or we are\n> > +\t\t\t * in !strict mode, in which case we do not use\n> > +\t\t\t * tip_oids at all.\n> > +\t\t\t */\n> >  \t\t} else {\n> >  \t\t\tref->match_status = REF_UNADVERTISED_NOT_ALLOWED;\n> >  \t\t}\n> \n> This comment puzzles me -- why ask the question it answers?\n> `tip_oids` has been loaded with all `refs` at that point; adding\n> more seems odd.\n\nIf you think that tip_oids is a fast lookup for what's in newlist, then\nI think it is a reasonable question to ask whether new additions to\nnewlist need the same treatment. That was what the comment in the\noriginal lazy-load was answering.\n\n> I feel the code needs be simplified further; not sure how, though,\n> except perhaps by using the `unfound` array added in another reply.\n\nI agree it's not the most clear code in the world, but we may be\nreaching a point of diminishing returns in discussing it further.\n\n-Peff\n"}]}