{"thread":{"id":"64022","subject":"[PATCH] describe: use khash in finish_depth_computation()","startedAt":"2025-08-24T08:37:36Z","lastAt":"2025-09-04T11:22:56Z","messageCount":21,"participants":["René Scharfe","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"524804","messageId":"9110f085-aec0-42e9-9774-b153ece6284f@web.de","threadId":"64022","inReplyTo":null,"subject":"[PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-24T08:37:28Z","receivedAt":"2025-08-24T08:37:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Depth computation can end early if all remaining commits are flagged.\nThe current code determines if that's the case by checking all queue\nitems each time it dequeues a flagged commit. This can cause\nquadratic complexity.\n\nWe could simply count the flagged items in the queue and then update\nthat number as we add and remove items. That would provide a general\nspeedup, but leave one case where we have to scan the whole queue: When\nwe flag a previously seen, but unflagged commit. It could be on the\nqueue and then we'd have to decrease our count.\n\nWe could dedicate an object flag to track queue membership, but that\nwould leave less for candidate tags, affecting the results. So use a\nhash table, specifically a khash set of commit pointers, to track that.\nThis avoids quadratic behaviour in all cases and provides a nice\nperformance boost over the previous commit, 08bb69d70f (describe: use\nprio_queue_replace(), 2025-08-03):\n\nBenchmark 1: ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 851.7 ms ± 1.1 ms [User: 788.7 ms, System: 49.2 ms]\n Range (min … max): 849.4 ms … 852.8 ms 10 runs\n\nBenchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 607.1 ms ± 0.9 ms [User: 544.6 ms, System: 48.6 ms]\n Range (min … max): 606.1 ms … 608.3 ms 10 runs\n\nSummary\n ./git describe $(git rev-list v2.41.0..v2.47.0) ran\n 1.40 ± 0.00 times faster than ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n\nUse the commit index value as a hash because it is unique, has the\nright size and needs no computation. We could also derive the hash\ndirectly from the pointer value, but that requires slightly more effort.\n\nSigned-off-by: René Scharfe \n---\n builtin/describe.c | 57 ++++++++++++++++++++++++++++++++++++++--------\n 1 file changed, 47 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 0540976210..edb4dec79d 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -24,6 +24,7 @@\n #include \"commit-slab.h\"\n #include \"wildmatch.h\"\n #include \"prio-queue.h\"\n+#include \"khash.h\"\n \n #define MAX_TAGS\t(FLAG_BITS - 1)\n #define DEFAULT_CANDIDATES 10\n@@ -286,38 +287,74 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n \tqueue->get_pending = false;\n }\n \n-static bool all_have_flag(const struct lazy_queue *queue, unsigned flag)\n+static inline unsigned int commit_index(const struct commit *commit)\n {\n-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n-\t\tstruct commit *commit = queue->queue.array[i].data;\n-\t\tif (!(commit->object.flags & flag))\n-\t\t\treturn false;\n-\t}\n-\treturn true;\n+\treturn commit->index;\n+}\n+\n+static inline int ptr_eq(const void *a, const void *b)\n+{\n+\treturn a == b;\n+}\n+\n+KHASH_INIT(commit_set, struct commit *, int, 0, commit_index, ptr_eq)\n+\n+static void commit_set_insert(kh_commit_set_t *set, struct commit *commit)\n+{\n+\tint added;\n+\tkh_put_commit_set(set, commit, &added);\n+}\n+\n+static void commit_set_remove(kh_commit_set_t *set, struct commit *commit)\n+{\n+\tkhiter_t pos = kh_get_commit_set(set, commit);\n+\tif (pos != kh_end(set))\n+\t\tkh_del_commit_set(set, pos);\n }\n \n static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\t\t\t struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n+\tkh_commit_set_t unflagged = { 0 };\n+\n+\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n+\t\tstruct commit *commit = queue->queue.array[i].data;\n+\t\tif (!(commit->object.flags & best->flag_within))\n+\t\t\tcommit_set_insert(&unflagged, commit);\n+\t}\n+\n \twhile (!lazy_queue_empty(queue)) {\n \t\tstruct commit *c = lazy_queue_get(queue);\n \t\tstruct commit_list *parents = c->parents;\n+\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n-\t\t\tif (all_have_flag(queue, best->flag_within))\n+\t\t\tif (!kh_size(&unflagged))\n \t\t\t\tbreak;\n-\t\t} else\n+\t\t} else {\n+\t\t\tcommit_set_remove(&unflagged, c);\n \t\t\tbest->depth++;\n+\t\t}\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n+\t\t\tunsigned seen, flag_before, flag_after;\n+\n \t\t\trepo_parse_commit(the_repository, p);\n-\t\t\tif (!(p->object.flags & SEEN))\n+\t\t\tseen = p->object.flags & SEEN;\n+\t\t\tif (!seen)\n \t\t\t\tlazy_queue_put(queue, p);\n+\t\t\tflag_before = p->object.flags & best->flag_within;\n \t\t\tp->object.flags |= c->object.flags;\n+\t\t\tflag_after = p->object.flags & best->flag_within;\n+\t\t\tif (!seen && !flag_after)\n+\t\t\t\tcommit_set_insert(&unflagged, p);\n+\t\t\tif (seen && !flag_before && flag_after)\n+\t\t\t\tcommit_set_remove(&unflagged, p);\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n+\tkh_release_commit_set(&unflagged);\n \treturn seen_commits;\n }\n \n-- \n2.51.0\n"},{"id":"524805","messageId":"20250824103117.GA250458@coredump.intra.peff.net","threadId":"64022","inReplyTo":"9110f085-aec0-42e9-9774-b153ece6284f@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-08-24T10:31:17Z","receivedAt":"2025-08-24T10:31:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 24, 2025 at 10:37:28AM +0200, René Scharfe wrote:\n\n> We could dedicate an object flag to track queue membership, but that\n> would leave less for candidate tags, affecting the results. So use a\n> hash table, specifically a khash set of commit pointers, to track that.\n> This avoids quadratic behaviour in all cases and provides a nice\n> performance boost over the previous commit, 08bb69d70f (describe: use\n> prio_queue_replace(), 2025-08-03):\n> \n> Benchmark 1: ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 851.7 ms ± 1.1 ms [User: 788.7 ms, System: 49.2 ms]\n> Range (min … max): 849.4 ms … 852.8 ms 10 runs\n> \n> Benchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 607.1 ms ± 0.9 ms [User: 544.6 ms, System: 48.6 ms]\n> Range (min … max): 606.1 ms … 608.3 ms 10 runs\n> \n> Summary\n> ./git describe $(git rev-list v2.41.0..v2.47.0) ran\n> 1.40 ± 0.00 times faster than ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n> \n> Use the commit index value as a hash because it is unique, has the\n> right size and needs no computation. We could also derive the hash\n> directly from the pointer value, but that requires slightly more effort.\n\nInteresting. This is exactly what commit-slabs were created for (and are\nwhy the convenient index value is there in the first place!).\n\nThe idea of commit-slab was to have a zero-cost lookup, which is done by\nindexing into an array (well, really an array-of-arrays). The biggest\ndownside of commit-slabs is that they allocate one element per commit.\nSo for a sparse set you end up over-allocating and possibly suffering\ncache woes due to requests being far apart.\n\nWhereas in your technique we are trading a little bit of computation\n(indexing a bucket and then probing for the match) to get a table that\nscales with the number of elements actually added to it.\n\nIt should be easy to convert between the two and time it. On top of your\npatch, I think this works:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex edb4dec79d..f1d1ce8c8e 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -287,36 +287,38 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n \tqueue->get_pending = false;\n }\n \n-static inline unsigned int commit_index(const struct commit *commit)\n-{\n-\treturn commit->index;\n-}\n-\n-static inline int ptr_eq(const void *a, const void *b)\n-{\n-\treturn a == b;\n-}\n+define_commit_slab(commit_counter, int);\n \n-KHASH_INIT(commit_set, struct commit *, int, 0, commit_index, ptr_eq)\n+struct commit_set {\n+\tint nr;\n+\tstruct commit_counter present;\n+};\n \n-static void commit_set_insert(kh_commit_set_t *set, struct commit *commit)\n+static void commit_set_insert(struct commit_set *set, struct commit *commit)\n {\n-\tint added;\n-\tkh_put_commit_set(set, commit, &added);\n+\tint *v = commit_counter_at(&set->present, commit);\n+\tif (!*v) {\n+\t\tset->nr++;\n+\t\t*v = 1;\n+\t}\n }\n \n-static void commit_set_remove(kh_commit_set_t *set, struct commit *commit)\n+static void commit_set_remove(struct commit_set *set, struct commit *commit)\n {\n-\tkhiter_t pos = kh_get_commit_set(set, commit);\n-\tif (pos != kh_end(set))\n-\t\tkh_del_commit_set(set, pos);\n+\tint *v = commit_counter_peek(&set->present, commit);\n+\tif (*v) {\n+\t\tset->nr--;\n+\t\t*v = 0;\n+\t}\n }\n \n static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\t\t\t struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n-\tkh_commit_set_t unflagged = { 0 };\n+\tstruct commit_set unflagged = { 0 };\n+\n+\tinit_commit_counter(&unflagged.present);\n \n \tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n \t\tstruct commit *commit = queue->queue.array[i].data;\n@@ -330,7 +332,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n-\t\t\tif (!kh_size(&unflagged))\n+\t\t\tif (!unflagged.nr)\n \t\t\t\tbreak;\n \t\t} else {\n \t\t\tcommit_set_remove(&unflagged, c);\n@@ -354,7 +356,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n-\tkh_release_commit_set(&unflagged);\n+\tclear_commit_counter(&unflagged.present);\n \treturn seen_commits;\n }\n \n\nHere's what I get for timing:\n\n Benchmark 1: ./git.orig describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 1.195 s ± 0.012 s [User: 1.152 s, System: 0.045 s]\n Range (min … max): 1.175 s … 1.220 s 10 runs\n \n Benchmark 2: ./git.khash describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 912.4 ms ± 5.7 ms [User: 867.7 ms, System: 46.3 ms]\n Range (min … max): 901.1 ms … 921.2 ms 10 runs\n \n Benchmark 3: ./git.slab describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 937.9 ms ± 7.6 ms [User: 896.1 ms, System: 43.5 ms]\n Range (min … max): 924.8 ms … 947.9 ms 10 runs\n \n Summary\n ./git.khash describe $(git rev-list v2.41.0..v2.47.0) ran\n 1.03 ± 0.01 times faster than ./git.slab describe $(git rev-list v2.41.0..v2.47.0)\n 1.31 ± 0.02 times faster than ./git.orig describe $(git rev-list v2.41.0..v2.47.0)\n\nSo I see similar speedups vs stock Git using your patch, but the\ncommit-slab version is just slightly slower. That of course makes me\nwonder if we could or should replace the guts of commit-slab with a hash\nmore like this. Some obvious questions:\n\n 1. Does the hash always perform better? For a dense set, might the\n commit-slab do better (probably something like topo-sort would be a\n good test there).\n\n 2. Can the hash version handle strides of different sizes? One of the\n points of commit-slab is that the fixed size of the value type can\n be set at runtime (so you could have a slab of 32 bits per commit,\n or 132, depending on your traversal needs).\n\n 3. How does it perform if we swap the commit->index field for using\n the pointer? If it's similar or faster, we could get rid of the\n commit->index field entirely. Besides saving a few bytes and being\n simpler, that would also mean that we could start to use the same\n slab techniques for non-commit objects. There are several cases\n where we use a few custom bits in object.flags because we need to\n cover both commits and other objects. But those are error prone if\n two sub-systems of Git use the same bits and happen to run at the\n same time without clearing in between. It would be great if each\n algorithm could declare its own unique flag space (and discard them\n in one action without iterating yet again to clear the bits).\n\n-Peff\n"},{"id":"524814","messageId":"6402268d-bc80-4bfe-abb8-edec9e1b8417@web.de","threadId":"64022","inReplyTo":"20250824103117.GA250458@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-24T16:32:47Z","receivedAt":"2025-08-24T16:32:56Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 8/24/25 12:31 PM, Jeff King wrote:\n> On Sun, Aug 24, 2025 at 10:37:28AM +0200, René Scharfe wrote:\n> \n>> We could dedicate an object flag to track queue membership, but that\n>> would leave less for candidate tags, affecting the results. So use a\n>> hash table, specifically a khash set of commit pointers, to track that.\n>> This avoids quadratic behaviour in all cases and provides a nice\n>> performance boost over the previous commit, 08bb69d70f (describe: use\n>> prio_queue_replace(), 2025-08-03):\n>>\n>> Benchmark 1: ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n>> Time (mean ± σ): 851.7 ms ± 1.1 ms [User: 788.7 ms, System: 49.2 ms]\n>> Range (min … max): 849.4 ms … 852.8 ms 10 runs\n>>\n>> Benchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)\n>> Time (mean ± σ): 607.1 ms ± 0.9 ms [User: 544.6 ms, System: 48.6 ms]\n>> Range (min … max): 606.1 ms … 608.3 ms 10 runs\n>>\n>> Summary\n>> ./git describe $(git rev-list v2.41.0..v2.47.0) ran\n>> 1.40 ± 0.00 times faster than ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n>>\n>> Use the commit index value as a hash because it is unique, has the\n>> right size and needs no computation. We could also derive the hash\n>> directly from the pointer value, but that requires slightly more effort.\n> \n> Interesting. This is exactly what commit-slabs were created for (and are\n> why the convenient index value is there in the first place!).\n\nKinda -- they have a payload value, while a khash set only stores keys.\nA commit slab with an int payload would still be smaller than a khash\nset with 64-bit pointers as keys -- IF we were to add all commits. Here\nwe typically add just a few, but a pathological history could add a lot;\nnot sure if there's a boundary. Hmm. So you might be able to find\nexamples where commit-slabs win.\n\n> The idea of commit-slab was to have a zero-cost lookup, which is done by\n> indexing into an array (well, really an array-of-arrays). The biggest\n> downside of commit-slabs is that they allocate one element per commit.\n> So for a sparse set you end up over-allocating and possibly suffering\n> cache woes due to requests being far apart.\n\nRight, and it doesn't support removal.\n\n> Whereas in your technique we are trading a little bit of computation\n> (indexing a bucket and then probing for the match) to get a table that\n> scales with the number of elements actually added to it.\n> \n> It should be easy to convert between the two and time it. On top of your\n> patch, I think this works:\n> \n> diff --git a/builtin/describe.c b/builtin/describe.c\n> index edb4dec79d..f1d1ce8c8e 100644\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -287,36 +287,38 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n> \tqueue->get_pending = false;\n> }\n> \n> -static inline unsigned int commit_index(const struct commit *commit)\n> -{\n> -\treturn commit->index;\n> -}\n> -\n> -static inline int ptr_eq(const void *a, const void *b)\n> -{\n> -\treturn a == b;\n> -}\n> +define_commit_slab(commit_counter, int);\n\nWe only need one bit, so a uint8_t or char would suffice.\n\n> \n> -KHASH_INIT(commit_set, struct commit *, int, 0, commit_index, ptr_eq)\n> +struct commit_set {\n> +\tint nr;\n> +\tstruct commit_counter present;\n> +};\n> \n> -static void commit_set_insert(kh_commit_set_t *set, struct commit *commit)\n> +static void commit_set_insert(struct commit_set *set, struct commit *commit)\n> {\n> -\tint added;\n> -\tkh_put_commit_set(set, commit, &added);\n> +\tint *v = commit_counter_at(&set->present, commit);\n> +\tif (!*v) {\n> +\t\tset->nr++;\n> +\t\t*v = 1;\n> +\t}\n> }\n> \n> -static void commit_set_remove(kh_commit_set_t *set, struct commit *commit)\n> +static void commit_set_remove(struct commit_set *set, struct commit *commit)\n> {\n> -\tkhiter_t pos = kh_get_commit_set(set, commit);\n> -\tif (pos != kh_end(set))\n> -\t\tkh_del_commit_set(set, pos);\n> +\tint *v = commit_counter_peek(&set->present, commit);\n> +\tif (*v) {\n> +\t\tset->nr--;\n> +\t\t*v = 0;\n> +\t}\n> }\n> \n> static unsigned long finish_depth_computation(struct lazy_queue *queue,\n> \t\t\t\t\t struct possible_tag *best)\n> {\n> \tunsigned long seen_commits = 0;\n> -\tkh_commit_set_t unflagged = { 0 };\n> +\tstruct commit_set unflagged = { 0 };\n> +\n> +\tinit_commit_counter(&unflagged.present);\n> \n> \tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n> \t\tstruct commit *commit = queue->queue.array[i].data;\n> @@ -330,7 +332,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n> \n> \t\tseen_commits++;\n> \t\tif (c->object.flags & best->flag_within) {\n> -\t\t\tif (!kh_size(&unflagged))\n> +\t\t\tif (!unflagged.nr)\n> \t\t\t\tbreak;\n> \t\t} else {\n> \t\t\tcommit_set_remove(&unflagged, c);\n> @@ -354,7 +356,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n> \t\t\tparents = parents->next;\n> \t\t}\n> \t}\n> -\tkh_release_commit_set(&unflagged);\n> +\tclear_commit_counter(&unflagged.present);\n> \treturn seen_commits;\n> }\n> \n> \n> Here's what I get for timing:\n> \n> Benchmark 1: ./git.orig describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 1.195 s ± 0.012 s [User: 1.152 s, System: 0.045 s]\n> Range (min … max): 1.175 s … 1.220 s 10 runs\n> \n> Benchmark 2: ./git.khash describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 912.4 ms ± 5.7 ms [User: 867.7 ms, System: 46.3 ms]\n> Range (min … max): 901.1 ms … 921.2 ms 10 runs\n> \n> Benchmark 3: ./git.slab describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 937.9 ms ± 7.6 ms [User: 896.1 ms, System: 43.5 ms]\n> Range (min … max): 924.8 ms … 947.9 ms 10 runs\n> \n> Summary\n> ./git.khash describe $(git rev-list v2.41.0..v2.47.0) ran\n> 1.03 ± 0.01 times faster than ./git.slab describe $(git rev-list v2.41.0..v2.47.0)\n> 1.31 ± 0.02 times faster than ./git.orig describe $(git rev-list v2.41.0..v2.47.0)\n> \n\nI didn't even consider them a contender due to the memory overhead. The\ndifference is surprisingly small. I also got 3%:\n\nBenchmark 1: ./git_khash describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 608.4 ms ± 0.6 ms [User: 544.6 ms, System: 49.2 ms]\n Range (min … max): 607.5 ms … 609.3 ms 10 runs\n\nBenchmark 2: ./git_slab describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 624.4 ms ± 1.0 ms [User: 560.6 ms, System: 49.3 ms]\n Range (min … max): 623.3 ms … 626.5 ms 10 runs\n\nSummary\n ./git_khash describe $(git rev-list v2.41.0..v2.47.0) ran\n 1.03 ± 0.00 times faster than ./git_slab describe $(git rev-list v2.41.0..v2.47.0)\n\nI guess hash tables are just fast, even the slower ones. Provided they\nfit into memory.\n\n> So I see similar speedups vs stock Git using your patch, but the\n> commit-slab version is just slightly slower. That of course makes me\n> wonder if we could or should replace the guts of commit-slab with a hash\n> more like this. Some obvious questions:\n> \n> 1. Does the hash always perform better? For a dense set, might the\n> commit-slab do better (probably something like topo-sort would be a\n> good test there).\n\nWith dense you mean that most commits get some data value assigned that\nis kept for longer? That's when commit-slabs should shine.\n\n> 2. Can the hash version handle strides of different sizes? One of the\n> points of commit-slab is that the fixed size of the value type can\n> be set at runtime (so you could have a slab of 32 bits per commit,\n> or 132, depending on your traversal needs).\n\nDynamic value sizes require an indirection via a pointer, or at least I\ndon't see any other way. What would be a possible use case? (Don't see\nany in-tree.)\n\n> 3. How does it perform if we swap the commit->index field for using\n> the pointer? If it's similar or faster, we could get rid of the\n> commit->index field entirely. Besides saving a few bytes and being\n> simpler, that would also mean that we could start to use the same\n> slab techniques for non-commit objects. There are several cases\n> where we use a few custom bits in object.flags because we need to\n> cover both commits and other objects. But those are error prone if\n> two sub-systems of Git use the same bits and happen to run at the\n> same time without clearing in between. It would be great if each\n> algorithm could declare its own unique flag space (and discard them\n> in one action without iterating yet again to clear the bits).\nWith \"commit\" being the pointer, returning \"(uintptr_t)commit / 8\" in the\nhash function for the khash set gets me the same performance. This\nassumes an eight-byte alignment and that pointer values are flat indexes\ninto memory, which might be too much. A portable solution would probably\nhave to mix and spread out all bits evenly?\n\nThe nice thing about commit-slabs is the lack of required maintenance.\nThey just allocate as needed and never give anything back, never need to\nrehash. And they don't need to store the keys anywhere. They should be\ngood alternatives to object flags used during full history traversal\nwithout flagging non-commits.\n\nOff-the-shelf hash tables like khash might be slower in these cases,\nthough not far off, I expect.\n\nRené\n\n"},{"id":"524855","messageId":"20250825073403.GA332447@coredump.intra.peff.net","threadId":"64022","inReplyTo":"6402268d-bc80-4bfe-abb8-edec9e1b8417@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-08-25T07:34:03Z","receivedAt":"2025-08-25T07:34:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 24, 2025 at 06:32:47PM +0200, René Scharfe wrote:\n\n> >> Use the commit index value as a hash because it is unique, has the\n> >> right size and needs no computation. We could also derive the hash\n> >> directly from the pointer value, but that requires slightly more effort.\n> > \n> > Interesting. This is exactly what commit-slabs were created for (and are\n> > why the convenient index value is there in the first place!).\n> \n> Kinda -- they have a payload value, while a khash set only stores keys.\n> A commit slab with an int payload would still be smaller than a khash\n> set with 64-bit pointers as keys -- IF we were to add all commits. Here\n> we typically add just a few, but a pathological history could add a lot;\n> not sure if there's a boundary. Hmm. So you might be able to find\n> examples where commit-slabs win.\n\nA khash set doesn't have a \"vals\" array, but I think it does always keep\nthe flags array, which is a uint32_t per bucket. That's how it knows\nwhich buckets have a value in them (since it does not otherwise assume\nthere is a sentinel value like NULL). So even though its API is that of\na set, you can think of it as a mapping of keys to flags. So a mapping\nto an int (or even a char) should cost the same.\n\n> > The idea of commit-slab was to have a zero-cost lookup, which is done by\n> > indexing into an array (well, really an array-of-arrays). The biggest\n> > downside of commit-slabs is that they allocate one element per commit.\n> > So for a sparse set you end up over-allocating and possibly suffering\n> > cache woes due to requests being far apart.\n> \n> Right, and it doesn't support removal.\n\nTrue. And I think that is the big downfall for what I was suggesting\nearlier (backing a slab with a hash table). If you have a slab that\nholds only a few items at one time, but which cycles through a larger\nset of items, it will grow to match that larger set. That is a waste of\nmemory with a traditional slab, but if you back the slab with a hash\ntable you also waste computation doing lookups on a hash table with lots\nof elements, when most of them are not interesting (but the slab code\nhas no way to say \"this is not interesting any more\"; you can only\ntake the address and assign to it).\n\nSo probably the slab API is not so great for many cases. But what I was\nmostly getting at is: should we be using hashes in more places if their\naccess time is cost-competitive with the slab arrays?\n\nMore on that in a moment...\n\n> > +define_commit_slab(commit_counter, int);\n> \n> We only need one bit, so a uint8_t or char would suffice.\n\nTrue, though that doesn't seem to change timings much for me (I used\n\"int\" because that's what your khash used, but I think the type is a\ndummy value in \"set\" mode).\n\n> I didn't even consider them a contender due to the memory overhead. The\n> difference is surprisingly small. I also got 3%:\n> \n> Benchmark 1: ./git_khash describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 608.4 ms ± 0.6 ms [User: 544.6 ms, System: 49.2 ms]\n> Range (min … max): 607.5 ms … 609.3 ms 10 runs\n> \n> Benchmark 2: ./git_slab describe $(git rev-list v2.41.0..v2.47.0)\n> Time (mean ± σ): 624.4 ms ± 1.0 ms [User: 560.6 ms, System: 49.3 ms]\n> Range (min … max): 623.3 ms … 626.5 ms 10 runs\n> \n> Summary\n> ./git_khash describe $(git rev-list v2.41.0..v2.47.0) ran\n> 1.03 ± 0.00 times faster than ./git_slab describe $(git rev-list v2.41.0..v2.47.0)\n> \n> I guess hash tables are just fast, even the slower ones. Provided they\n> fit into memory.\n\nYeah. Thinking on it more, how much benefit are we getting from the use\nof commit->index in your patch? In other contexts where we store oids or\nobjects in hash tables, we use the low bits of the oid directly. So it's\nsimilarly cheap. If I do this tweak on top of your patch:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex edb4dec79d..e024feb080 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -289,7 +289,7 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n \n static inline unsigned int commit_index(const struct commit *commit)\n {\n-\treturn commit->index;\n+\treturn oidhash(&commit->object.oid);\n }\n \n static inline int ptr_eq(const void *a, const void *b)\n\nI get similar results (actually faster, but I think within the noise).\n\nWhich made me think more (always a danger). We already have an oidset\ndata structure, which is backed by a khash. It's not _quite_ the same\nthing, because it's going to store an actual 36-byte oid struct as the\nhash key, rather than an 8-byte pointer to a \"struct object\" (which\ncontains that same oid). And likewise when we do a lookup, the bucket\nsearch requires a larger memcmp() than the pointer equality. But how\nmuch difference does that make?\n\nIf I instead do this on top of your patch:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex edb4dec79d..38ce0c1978 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -287,41 +287,16 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n \tqueue->get_pending = false;\n }\n \n-static inline unsigned int commit_index(const struct commit *commit)\n-{\n-\treturn commit->index;\n-}\n-\n-static inline int ptr_eq(const void *a, const void *b)\n-{\n-\treturn a == b;\n-}\n-\n-KHASH_INIT(commit_set, struct commit *, int, 0, commit_index, ptr_eq)\n-\n-static void commit_set_insert(kh_commit_set_t *set, struct commit *commit)\n-{\n-\tint added;\n-\tkh_put_commit_set(set, commit, &added);\n-}\n-\n-static void commit_set_remove(kh_commit_set_t *set, struct commit *commit)\n-{\n-\tkhiter_t pos = kh_get_commit_set(set, commit);\n-\tif (pos != kh_end(set))\n-\t\tkh_del_commit_set(set, pos);\n-}\n-\n static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\t\t\t struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n-\tkh_commit_set_t unflagged = { 0 };\n+\tstruct oidset unflagged = OIDSET_INIT;\n \n \tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n \t\tstruct commit *commit = queue->queue.array[i].data;\n \t\tif (!(commit->object.flags & best->flag_within))\n-\t\t\tcommit_set_insert(&unflagged, commit);\n+\t\t\toidset_insert(&unflagged, &commit->object.oid);\n \t}\n \n \twhile (!lazy_queue_empty(queue)) {\n@@ -330,10 +305,10 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n-\t\t\tif (!kh_size(&unflagged))\n+\t\t\tif (!oidset_size(&unflagged))\n \t\t\t\tbreak;\n \t\t} else {\n-\t\t\tcommit_set_remove(&unflagged, c);\n+\t\t\toidset_remove(&unflagged, &c->object.oid);\n \t\t\tbest->depth++;\n \t\t}\n \t\twhile (parents) {\n@@ -348,13 +323,13 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tflag_after = p->object.flags & best->flag_within;\n \t\t\tif (!seen && !flag_after)\n-\t\t\t\tcommit_set_insert(&unflagged, p);\n+\t\t\t\toidset_insert(&unflagged, &p->object.oid);\n \t\t\tif (seen && !flag_before && flag_after)\n-\t\t\t\tcommit_set_remove(&unflagged, p);\n+\t\t\t\toidset_remove(&unflagged, &p->object.oid);\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n-\tkh_release_commit_set(&unflagged);\n+\toidset_clear(&unflagged);\n \treturn seen_commits;\n }\n \n\nthen I likewise get very similar timings. Your version seems to be\nconsistently a little bit faster, but within the run-to-run noise of\n~1%. But the bonus here is that we didn't need to define a new hash\ntype, nor do any tricks with the commit->index field.\n\nNow if we really are worried about those extra bytes in storing a fresh\noid, is there room for new data types? I.e., A \"struct objset\" that\nstores object pointers, hashes based on the oid, and uses pointer\nequality to find a match? And likewise a \"struct objmap\" that could\nperhaps compete with commit-slab (but be more pleasant to use).\n\n> > 1. Does the hash always perform better? For a dense set, might the\n> > commit-slab do better (probably something like topo-sort would be a\n> > good test there).\n> \n> With dense you mean that most commits get some data value assigned that\n> is kept for longer? That's when commit-slabs should shine.\n\nYes, that's what I meant. And yeah, I'd expect commit slabs to be more\ncompetitive with hashes in those cases. But I wonder if a good hash\ntable could come close enough to obsolete slabs.\n\n> > 2. Can the hash version handle strides of different sizes? One of the\n> > points of commit-slab is that the fixed size of the value type can\n> > be set at runtime (so you could have a slab of 32 bits per commit,\n> > or 132, depending on your traversal needs).\n> \n> Dynamic value sizes require an indirection via a pointer, or at least I\n> don't see any other way. What would be a possible use case? (Don't see\n> any in-tree.)\n\nThe value isn't totally dynamic; it's static for a single instantiation\nof a slab. I don't think khash supports that (it has a value type and\nlets the compiler take care of indexing into an array of that value).\nBut you could imagine a world where khash (or some custom hash code)\nonly knows that it's storing N bytes per item, and does the indexing\nmultiplication itself.\n\nBut yes, I don't think we are even using that feature of commit-slab\ncurrently. I used it in a series for fast --contains long ago:\n\n https://lore.kernel.org/git/20140625233429.GA20457@sigill.intra.peff.net/\n\nbut can't remember why I never got back to it. It would also be useful\nfor show-branch, which wants to paint down for each starting tip. But\ngiven that we haven't used it, it may just not be that useful a feature.\n\n> > 3. How does it perform if we swap the commit->index field for using\n> > the pointer? If it's similar or faster, we could get rid of the\n> > commit->index field entirely. Besides saving a few bytes and being\n> > simpler, that would also mean that we could start to use the same\n> > slab techniques for non-commit objects. There are several cases\n> > where we use a few custom bits in object.flags because we need to\n> > cover both commits and other objects. But those are error prone if\n> > two sub-systems of Git use the same bits and happen to run at the\n> > same time without clearing in between. It would be great if each\n> > algorithm could declare its own unique flag space (and discard them\n> > in one action without iterating yet again to clear the bits).\n> With \"commit\" being the pointer, returning \"(uintptr_t)commit / 8\" in the\n> hash function for the khash set gets me the same performance. This\n> assumes an eight-byte alignment and that pointer values are flat indexes\n> into memory, which might be too much. A portable solution would probably\n> have to mix and spread out all bits evenly?\n\nI'd think there would be more entropy in the low bits in general, so\njust \"(uintptr_t)commit & 0xffffffff\". But probably just using oidhash()\nis better still.\n\n> The nice thing about commit-slabs is the lack of required maintenance.\n> They just allocate as needed and never give anything back, never need to\n> rehash. And they don't need to store the keys anywhere. They should be\n> good alternatives to object flags used during full history traversal\n> without flagging non-commits.\n> \n> Off-the-shelf hash tables like khash might be slower in these cases,\n> though not far off, I expect.\n\nYeah, maybe. I've never really loved the drawbacks of commit-slab, and\nyour numbers made me wonder if we could be getting away with hashes in\nmore places. Though one of the drawbacks I find with commit-slab is the\ngrossness of instantiating a giant mess of macros. That is not much\nbetter with khash. ;) And certainly oidmap, though it does not use\nmacros, is no picnic to use either.\n\n-Peff\n"},{"id":"524857","messageId":"20250825081345.GA352784@coredump.intra.peff.net","threadId":"64022","inReplyTo":"20250825073403.GA332447@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-08-25T08:13:45Z","receivedAt":"2025-08-25T08:13:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 25, 2025 at 03:34:03AM -0400, Jeff King wrote:\n\n> > The nice thing about commit-slabs is the lack of required maintenance.\n> > They just allocate as needed and never give anything back, never need to\n> > rehash. And they don't need to store the keys anywhere. They should be\n> > good alternatives to object flags used during full history traversal\n> > without flagging non-commits.\n> > \n> > Off-the-shelf hash tables like khash might be slower in these cases,\n> > though not far off, I expect.\n> \n> Yeah, maybe. I've never really loved the drawbacks of commit-slab, and\n> your numbers made me wonder if we could be getting away with hashes in\n> more places. Though one of the drawbacks I find with commit-slab is the\n> grossness of instantiating a giant mess of macros. That is not much\n> better with khash. ;) And certainly oidmap, though it does not use\n> macros, is no picnic to use either.\n\nSo out of curiosity I tried replacing a slab that should be pretty\ndensely filled, using a khash based on oidhash/ptr along with some\nquality-of-life wrappers. Patch is below.\n\nIt performs...very badly. Not sure if I've screwed something up, but\nit's about 7x slower to run \"git rev-list --author-date-order HEAD\" in\nthe kernel. So maybe slabs really are worth it overall.\n\n-Peff\n\n---\ndiff --git a/commit.c b/commit.c\nindex 16d91b2bfc..0678932ab8 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -822,9 +822,7 @@ struct commit *pop_commit(struct commit_list **stack)\n /* count number of children that have not been emitted */\n define_commit_slab(indegree_slab, int);\n \n-define_commit_slab(author_date_slab, timestamp_t);\n-\n-void record_author_date(struct author_date_slab *author_date,\n+void record_author_date(kh_obj_timestamp_t *author_date,\n \t\t\tstruct commit *commit)\n {\n \tconst char *buffer = repo_get_commit_buffer(the_repository, commit,\n@@ -845,7 +843,7 @@ void record_author_date(struct author_date_slab *author_date,\n \tdate = parse_timestamp(ident.date_begin, &date_end, 10);\n \tif (date_end != ident.date_end)\n \t\tgoto fail_exit; /* malformed date */\n-\t*(author_date_slab_at(author_date, commit)) = date;\n+\tobj_timestamp_put(author_date, &commit->object, date);\n \n fail_exit:\n \trepo_unuse_commit_buffer(the_repository, commit, buffer);\n@@ -855,9 +853,9 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n \t\t\t\t void *cb_data)\n {\n \tconst struct commit *a = a_, *b = b_;\n-\tstruct author_date_slab *author_date = cb_data;\n-\ttimestamp_t a_date = *(author_date_slab_at(author_date, a));\n-\ttimestamp_t b_date = *(author_date_slab_at(author_date, b));\n+\tkh_obj_timestamp_t *author_date = cb_data;\n+\ttimestamp_t a_date = obj_timestamp_get(author_date, &a->object);\n+\ttimestamp_t b_date = obj_timestamp_get(author_date, &b->object);\n \n \t/* newer commits with larger date first */\n \tif (a_date < b_date)\n@@ -910,7 +908,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tstruct indegree_slab indegree;\n \tstruct prio_queue queue;\n \tstruct commit *commit;\n-\tstruct author_date_slab author_date;\n+\tkh_obj_timestamp_t author_date;\n \n \tif (!orig)\n \t\treturn;\n@@ -927,7 +925,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t\tqueue.compare = compare_commits_by_commit_date;\n \t\tbreak;\n \tcase REV_SORT_BY_AUTHOR_DATE:\n-\t\tinit_author_date_slab(&author_date);\n+\t\tmemset(&author_date, 0, sizeof(author_date));\n \t\tqueue.compare = compare_commits_by_author_date;\n \t\tqueue.cb_data = &author_date;\n \t\tbreak;\n@@ -1011,7 +1009,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tclear_indegree_slab(&indegree);\n \tclear_prio_queue(&queue);\n \tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n-\t\tclear_author_date_slab(&author_date);\n+\t\tkh_release_obj_timestamp(&author_date);\n }\n \n struct rev_collect {\ndiff --git a/commit.h b/commit.h\nindex 1d6e0c7518..f49531ab8b 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -334,8 +334,8 @@ int remove_signature(struct strbuf *buf);\n int check_commit_signature(const struct commit *commit, struct signature_check *sigc);\n \n /* record author-date for each commit object */\n-struct author_date_slab;\n-void record_author_date(struct author_date_slab *author_date,\n+struct kh_obj_timestamp_t;\n+void record_author_date(kh_obj_timestamp_t *author_date,\n \t\t\tstruct commit *commit);\n \n int compare_commits_by_author_date(const void *a_, const void *b_, void *unused);\ndiff --git a/object.h b/object.h\nindex 8c3c1c46e1..14718051f2 100644\n--- a/object.h\n+++ b/object.h\n@@ -2,6 +2,7 @@\n #define OBJECT_H\n \n #include \"hash.h\"\n+#include \"khash.h\"\n \n struct buffer_slab;\n struct repository;\n@@ -340,4 +341,33 @@ void clear_object_flags(struct repository *repo, unsigned flags);\n */\n void repo_clear_commit_marks(struct repository *r, unsigned int flags);\n \n+/*\n+ * This would all probably go into its own header file...\n+ */\n+static inline unsigned int obj_ptr_hash(const struct object *obj)\n+{\n+\treturn oidhash(&obj->oid);\n+}\n+\n+static inline int obj_ptr_eq(const struct object *a, const struct object *b)\n+{\n+\treturn a == b;\n+}\n+\n+#define OBJHASH_INIT(name, value_type, sentinel) \\\n+KHASH_INIT(name, const struct object *, value_type, 1, obj_ptr_hash, obj_ptr_eq); \\\n+static inline void name##_put(kh_##name##_t *map, const struct object *obj, value_type v) \\\n+{ \\\n+\tint hash_ret; \\\n+\tkhiter_t pos = kh_put_##name(map, obj, &hash_ret); \\\n+\tkh_value(map, pos) = v; \\\n+} \\\n+static inline value_type name##_get(kh_##name##_t *map, const struct object *obj) \\\n+{ \\\n+\tkhiter_t pos = kh_get_##name(map, obj); \\\n+\treturn pos == kh_end(map) ? sentinel : kh_value(map, pos); \\\n+}\n+\n+OBJHASH_INIT(obj_timestamp, timestamp_t, 0);\n+\n #endif /* OBJECT_H */\ndiff --git a/revision.c b/revision.c\nindex 6ba8f67054..e67cf2249a 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3622,15 +3622,14 @@ static int mark_uninteresting(const struct object_id *oid,\n }\n \n define_commit_slab(indegree_slab, int);\n-define_commit_slab(author_date_slab, timestamp_t);\n \n struct topo_walk_info {\n \ttimestamp_t min_generation;\n \tstruct prio_queue explore_queue;\n \tstruct prio_queue indegree_queue;\n \tstruct prio_queue topo_queue;\n \tstruct indegree_slab indegree;\n-\tstruct author_date_slab author_date;\n+\tkh_obj_timestamp_t author_date;\n };\n \n static int topo_walk_atexit_registered;\n@@ -3755,7 +3754,7 @@ static void release_revisions_topo_walk_info(struct topo_walk_info *info)\n \tclear_prio_queue(&info->indegree_queue);\n \tclear_prio_queue(&info->topo_queue);\n \tclear_indegree_slab(&info->indegree);\n-\tclear_author_date_slab(&info->author_date);\n+\tkh_release_obj_timestamp(&info->author_date);\n \tfree(info);\n }\n \n@@ -3789,7 +3788,7 @@ static void init_topo_walk(struct rev_info *revs)\n \t\tinfo->topo_queue.compare = compare_commits_by_commit_date;\n \t\tbreak;\n \tcase REV_SORT_BY_AUTHOR_DATE:\n-\t\tinit_author_date_slab(&info->author_date);\n+\t\tmemset(&info->author_date, 0, sizeof(info->author_date));\n \t\tinfo->topo_queue.compare = compare_commits_by_author_date;\n \t\tinfo->topo_queue.cb_data = &info->author_date;\n \t\tbreak;\n"},{"id":"524877","messageId":"xmqqcy8jqlue.fsf@gitster.g","threadId":"64022","inReplyTo":"20250825081345.GA352784@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-25T18:48:09Z","receivedAt":"2025-08-25T18:48:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So out of curiosity I tried replacing a slab that should be pretty\n> densely filled, using a khash based on oidhash/ptr along with some\n> quality-of-life wrappers. Patch is below.\n>\n> It performs...very badly. Not sure if I've screwed something up, but\n> it's about 7x slower to run \"git rev-list --author-date-order HEAD\" in\n> the kernel. So maybe slabs really are worth it overall.\n\nHmph. It is the best case scenario for the slab code, as you'd need\nauthor date for each and every commit object in this use case, and\nthe comparison function called by prio-queue would be called for the\nsame object many times.\n\nBut the hash function being oidhash(), I am a bit surprised. It\nshouldn't be so much more expensive to peek at the first 4 bytes and\nthen do the usual hashtable thing than looking at the in-object\ncommit->index. Is it a sign that the range of oidhash() is a bit\ntoo small for a real workload?\n\nNah, 4 byte unsigned integer should be sufficient for the number of\nobjects in the kernel.\n\n"},{"id":"524915","messageId":"20250826033920.GA388997@coredump.intra.peff.net","threadId":"64022","inReplyTo":"xmqqcy8jqlue.fsf@gitster.g","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-08-26T03:39:20Z","receivedAt":"2025-08-26T03:39:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 25, 2025 at 11:48:09AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > So out of curiosity I tried replacing a slab that should be pretty\n> > densely filled, using a khash based on oidhash/ptr along with some\n> > quality-of-life wrappers. Patch is below.\n> >\n> > It performs...very badly. Not sure if I've screwed something up, but\n> > it's about 7x slower to run \"git rev-list --author-date-order HEAD\" in\n> > the kernel. So maybe slabs really are worth it overall.\n> \n> Hmph. It is the best case scenario for the slab code, as you'd need\n> author date for each and every commit object in this use case, and\n> the comparison function called by prio-queue would be called for the\n> same object many times.\n> \n> But the hash function being oidhash(), I am a bit surprised. It\n> shouldn't be so much more expensive to peek at the first 4 bytes and\n> then do the usual hashtable thing than looking at the in-object\n> commit->index. Is it a sign that the range of oidhash() is a bit\n> too small for a real workload?\n> \n> Nah, 4 byte unsigned integer should be sufficient for the number of\n> objects in the kernel.\n\nI was surprised, too. I expected it be maybe 20% slower or something.\nWhich really makes me think I've managed to screw up the patch, but if\nso, I don't see it. I tried profiling the result, expecting to see a\nbunch of extra time spent in obj_timestamp_put() or obj_timestamp_get().\nBut I don't. They account together for only a few percent of the\nrun-time, according to perf.\n\nSo I dunno. I am confused by the results, but I am not sure if I am\nholding it wrong.\n\n-Peff\n"},{"id":"524917","messageId":"20250826042607.GA995491@coredump.intra.peff.net","threadId":"64022","inReplyTo":"20250826033920.GA388997@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-08-26T04:26:07Z","receivedAt":"2025-08-26T04:26:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 25, 2025 at 11:39:20PM -0400, Jeff King wrote:\n\n> > But the hash function being oidhash(), I am a bit surprised. It\n> > shouldn't be so much more expensive to peek at the first 4 bytes and\n> > then do the usual hashtable thing than looking at the in-object\n> > commit->index. Is it a sign that the range of oidhash() is a bit\n> > too small for a real workload?\n> > \n> > Nah, 4 byte unsigned integer should be sufficient for the number of\n> > objects in the kernel.\n> \n> I was surprised, too. I expected it be maybe 20% slower or something.\n> Which really makes me think I've managed to screw up the patch, but if\n> so, I don't see it. I tried profiling the result, expecting to see a\n> bunch of extra time spent in obj_timestamp_put() or obj_timestamp_get().\n> But I don't. They account together for only a few percent of the\n> run-time, according to perf.\n> \n> So I dunno. I am confused by the results, but I am not sure if I am\n> holding it wrong.\n\nOK, maybe I am just holding it wrong. I think I may have mistakenly been\nusing the wrong timing for my baseline (maybe --date-order instead of\n--author-date-order; the latter is _way_ more expensive because we have\nto open the commits to parse the author date).\n\nHere's a more apples-to-apples comparison using hyperfine. On git.git:\n\n Benchmark 1: ./git.slab rev-list --author-date-order HEAD\n Time (mean ± σ): 547.3 ms ± 12.2 ms [User: 535.8 ms, System: 11.3 ms]\n Range (min … max): 536.1 ms … 566.4 ms 10 runs\n \n Benchmark 2: ./git.hash rev-list --author-date-order HEAD\n Time (mean ± σ): 558.6 ms ± 11.2 ms [User: 542.4 ms, System: 16.0 ms]\n Range (min … max): 544.4 ms … 572.6 ms 10 runs\n \n Summary\n ./git.slab rev-list --author-date-order HEAD ran\n 1.02 ± 0.03 times faster than ./git.hash rev-list --author-date-order HEAD\n\nSo a little slowdown, but within the run-to-run noise. And on linux.git:\n\n Benchmark 1: ~/compile/git/git.slab rev-list --author-date-order HEAD\n Time (mean ± σ): 11.020 s ± 0.131 s [User: 10.764 s, System: 0.254 s]\n Range (min … max): 10.886 s … 11.262 s 10 runs\n \n Benchmark 2: ~/compile/git/git.hash rev-list --author-date-order HEAD\n Time (mean ± σ): 11.682 s ± 0.204 s [User: 11.398 s, System: 0.282 s]\n Range (min … max): 11.424 s … 12.139 s 10 runs\n \n Summary\n ~/compile/git/git.slab rev-list --author-date-order HEAD ran\n 1.06 ± 0.02 times faster than ~/compile/git/git.hash rev-list --author-date-order HEAD\n\n\nA little more measurable there. Those numbers are more in line with what\nI was expecting. I'm not sure what it all means, though. 6% is enough\nthat it is probably worth keeping a custom data type like slab around.\nThough it would be nice to have a data type that worked on all object\ntypes and didn't necessarily use a ton of memory.\n\nThis particular case may not be representative, either. I picked it\nbecause it was easy to convert. But I wonder how bad it would be to put\nthe object flags for a traversal into a hash. Right now those are in the\noriginal struct, not even in a commit-slab. So I'd guess it's an even\nbigger slowdown.\n\n-Peff\n"},{"id":"524920","messageId":"20250826055210.GA1031277@coredump.intra.peff.net","threadId":"64022","inReplyTo":"20250826042607.GA995491@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-08-26T05:52:10Z","receivedAt":"2025-08-26T05:52:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 26, 2025 at 12:26:07AM -0400, Jeff King wrote:\n\n> This particular case may not be representative, either. I picked it\n> because it was easy to convert. But I wonder how bad it would be to put\n> the object flags for a traversal into a hash. Right now those are in the\n> original struct, not even in a commit-slab. So I'd guess it's an even\n> bigger slowdown.\n\nJust for fun, and because I hadn't tortured myself with coccinelle\nsyntax in a while, I tried removing object.flags entirely. Apply the\npatch below, then:\n\n make SPATCH_USE_O_DEPENDENCIES= contrib/coccinelle/flags.cocci.patch\n git apply contrib/coccinelle/flags.cocci.patch\n\nThat misses a few stragglers, which I'll include fixes for below.\nAnyway, the result is a system that does hash lookups for every access\nof the \"flags\" field. I added a few helpers to do |= and &= without\ndoing two lookups. Probably this could go a little further with some\nkind of test-and-set (e.g., you want to know if SEEN is set and if not,\nset it and do some other stuff). But it gives a general idea.\n\nI tried timing merge-base which I know will need to paint flags, using\nan old commit (so that we have to walk almost down to the root). Here\nare the results:\n\n Benchmark 1: ./git.orig merge-base HEAD 19b2860cba574\n Time (mean ± σ): 31.7 ms ± 0.7 ms [User: 26.1 ms, System: 5.5 ms]\n Range (min … max): 30.5 ms … 34.0 ms 89 runs\n \n Benchmark 2: ./git.hash merge-base HEAD 19b2860cba574\n Time (mean ± σ): 39.7 ms ± 0.7 ms [User: 33.9 ms, System: 5.8 ms]\n Range (min … max): 38.5 ms … 42.6 ms 75 runs\n \n Summary\n ./git.orig merge-base HEAD 19b2860cba574 ran\n 1.25 ± 0.03 times faster than ./git.hash merge-base HEAD 19b2860cba574\n\nAnd here's a rev-list which needs to set SEEN on a lot of objects (but\nalso has to actually inflate a lot of trees, too):\n\n $ hyperfine -L v orig,hash './git.{v} rev-list --objects --all'\n Benchmark 1: ./git.orig rev-list --objects --all\n Time (mean ± σ): 2.875 s ± 0.050 s [User: 2.799 s, System: 0.075 s]\n Range (min … max): 2.803 s … 2.973 s 10 runs\n \n Benchmark 2: ./git.hash rev-list --objects --all\n Time (mean ± σ): 5.547 s ± 0.069 s [User: 5.477 s, System: 0.070 s]\n Range (min … max): 5.396 s … 5.671 s 10 runs\n \n Summary\n ./git.orig rev-list --objects --all ran\n 1.93 ± 0.04 times faster than ./git.hash rev-list --objects --all\n\n\nI expected the merge-base to fare much worse, since it's otherwise\nmostly just pulling commit data from the commit-graph file and walking\nthe pointers. But I guess we check a lot of SEEN flags for rev-list.\n\nAnyway, I think the numbers there demonstrate that it's probably not\nthat interesting a direction. I'm a little curious how a slab would\nfare. It shouldn't be _too_ hard to slot it in with a similar API (the\nreal work was adjusting all the callers via cocci). But I'm not sure I\nhave the stomach to waste more time on this. ;)\n\nPatches below for reference. This is the one that rips out the flags\nfield:\n\n---\n contrib/coccinelle/flags.cocci | 59 ++++++++++++++++++++++++++++++++++\n object.c | 5 ++-\n object.h | 29 ++++++++++++++++-\n 3 files changed, 91 insertions(+), 2 deletions(-)\n create mode 100644 contrib/coccinelle/flags.cocci\n\ndiff --git a/contrib/coccinelle/flags.cocci b/contrib/coccinelle/flags.cocci\nnew file mode 100644\nindex 0000000000..5dae0054d6\n--- /dev/null\n+++ b/contrib/coccinelle/flags.cocci\n@@ -0,0 +1,59 @@\n+@@\n+struct object *OBJPTR;\n+expression FLAGS;\n+@@\n+- OBJPTR->flags |= FLAGS\n++ objflags_set(OBJPTR, FLAGS)\n+\n+@@\n+struct object *OBJPTR;\n+expression FLAGS;\n+@@\n+- OBJPTR->flags &= FLAGS\n++ objflags_clear(OBJPTR, FLAGS)\n+\n+@@\n+struct object *OBJPTR;\n+@@\n+- OBJPTR->flags\n++ objflags_get(OBJPTR)\n+\n+@@\n+expression TYPEDOBJ;\n+expression FLAGS;\n+@@\n+- TYPEDOBJ->object.flags |= FLAGS\n++ objflags_set(&TYPEDOBJ->object, FLAGS)\n+\n+@@\n+expression TYPEDOBJ;\n+expression FLAGS;\n+@@\n+- TYPEDOBJ->object.flags &= FLAGS\n++ objflags_clear(&TYPEDOBJ->object, FLAGS)\n+\n+@@\n+expression TYPEDOBJ;\n+@@\n+- TYPEDOBJ->object.flags\n++ objflags_get(&TYPEDOBJ->object)\n+\n+@@\n+struct object_array_entry *ENTRY;\n+expression FLAGS;\n+@@\n+- ENTRY->item->flags |= FLAGS\n++ objflags_set(ENTRY->item, FLAGS)\n+\n+@@\n+struct object_array_entry *ENTRY;\n+expression FLAGS;\n+@@\n+- ENTRY->item->flags &= FLAGS\n++ objflags_clear(ENTRY->item, FLAGS)\n+\n+@@\n+struct object_array_entry *ENTRY;\n+@@\n+- ENTRY->item->flags\n++ objflags_get(ENTRY->item)\ndiff --git a/object.c b/object.c\nindex c1553ee433..679aadbd7b 100644\n--- a/object.c\n+++ b/object.c\n@@ -14,6 +14,9 @@\n #include \"alloc.h\"\n #include \"commit-graph.h\"\n \n+static kh_obj_flags_t objflags_data;\n+kh_obj_flags_t *objflags = &objflags_data;\n+\n unsigned int get_max_object_index(const struct repository *repo)\n {\n \treturn repo->parsed_objects->obj_hash_size;\n@@ -149,7 +152,7 @@ void *create_object(struct repository *r, const struct object_id *oid, void *o)\n \tstruct object *obj = o;\n \n \tobj->parsed = 0;\n-\tobj->flags = 0;\n+\t/* flags default to 0 via flags hash */\n \toidcpy(&obj->oid, oid);\n \n \tif (r->parsed_objects->obj_hash_size - 1 <= r->parsed_objects->nr_objs * 2)\ndiff --git a/object.h b/object.h\nindex 14718051f2..50d1d0e65f 100644\n--- a/object.h\n+++ b/object.h\n@@ -159,7 +159,6 @@ static inline unsigned int canon_mode(unsigned int mode)\n struct object {\n \tunsigned parsed : 1;\n \tunsigned type : TYPE_BITS;\n-\tunsigned flags : FLAG_BITS;\n \tstruct object_id oid;\n };\n \n@@ -369,5 +368,33 @@ static inline value_type name##_get(kh_##name##_t *map, const struct object *obj\n }\n \n OBJHASH_INIT(obj_timestamp, timestamp_t, 0);\n+OBJHASH_INIT(obj_flags, unsigned, 0);\n+\n+extern kh_obj_flags_t *objflags;\n+\n+static inline unsigned objflags_get(const struct object *obj)\n+{\n+\treturn obj_flags_get(objflags, obj);\n+}\n+\n+static inline void objflags_set(const struct object *obj, unsigned flags)\n+{\n+\tint hash_ret;\n+\tkhiter_t pos = kh_put_obj_flags(objflags, obj, &hash_ret);\n+\tif (!hash_ret)\n+\t\tkh_value(objflags, pos) |= flags;\n+\telse\n+\t\tkh_value(objflags, pos) = flags;\n+}\n+\n+static inline void objflags_clear(const struct object *obj, unsigned flags)\n+{\n+\tint hash_ret;\n+\tkhiter_t pos = kh_put_obj_flags(objflags, obj, &hash_ret);\n+\tif (!hash_ret)\n+\t\tkh_value(objflags, pos) &= flags;\n+\telse\n+\t\tkh_value(objflags, pos) = 0;\n+}\n \n #endif /* OBJECT_H */\n\nAnd then this one gives you the fixups on top of applying the cocci\npatch:\n\n---\n builtin/describe.c | 5 +++--\n builtin/fsck.c | 2 +-\n builtin/log.c | 10 +++++-----\n commit-graph.c | 2 +-\n commit-reach.c | 2 +-\n http-push.c | 2 +-\n range-diff.c | 2 +-\n reflog.c | 6 +++---\n revision.c | 4 ++--\n 9 files changed, 18 insertions(+), 17 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex b9ebdb9a3d..aeb3b3344f 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -290,7 +290,7 @@ static bool all_have_flag(const struct lazy_queue *queue, unsigned flag)\n {\n \tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n \t\tstruct commit *commit = queue->queue.array[i].data;\n-\t\tif (!(commit->object.flags & flag))\n+\t\tif (!(objflags_get(&commit->object) & flag))\n \t\t\treturn false;\n \t}\n \treturn true;\n@@ -398,7 +398,8 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\thave_util = 1;\n \t}\n \n-\tobjflags_get(&cmit->object) = SEEN;\n+\t/* weird, this assigns SEEN instead of OR-ing it? */\n+\tobj_flags_put(objflags, &cmit->object, SEEN);\n \tlazy_queue_put(&queue, cmit);\n \twhile (!lazy_queue_empty(&queue)) {\n \t\tstruct commit *c = lazy_queue_get(&queue);\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex c2a3df8c1d..c5d5a4ea75 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -214,7 +214,7 @@ static int mark_used(struct object *obj, enum object_type type UNUSED,\n {\n \tif (!obj)\n \t\treturn 1;\n-\tobj->flags |= USED;\n+\tobjflags_set(obj, USED);\n \treturn 0;\n }\n \ndiff --git a/builtin/log.c b/builtin/log.c\nindex 9ceeace9c3..34ba1ff782 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1164,8 +1164,8 @@ static void get_patch_ids(struct rev_info *rev, struct patch_ids *ids)\n \t/* given a range a..b get all patch ids for b..a */\n \trepo_init_revisions(the_repository, &check_rev, rev->prefix);\n \tcheck_rev.max_parents = 1;\n-\tobjflags_get(o1) ^= UNINTERESTING;\n-\tobjflags_get(o2) ^= UNINTERESTING;\n+\tobj_flags_put(objflags, o1, objflags_get(o1) ^ UNINTERESTING);\n+\tobj_flags_put(objflags, o2, objflags_get(o2) ^ UNINTERESTING);\n \tadd_pending_object(&check_rev, o1, \"o1\");\n \tadd_pending_object(&check_rev, o2, \"o2\");\n \tif (prepare_revision_walk(&check_rev))\n@@ -1178,8 +1178,8 @@ static void get_patch_ids(struct rev_info *rev, struct patch_ids *ids)\n \t/* reset for next revision walk */\n \tclear_commit_marks(c1, SEEN | UNINTERESTING | SHOWN | ADDED);\n \tclear_commit_marks(c2, SEEN | UNINTERESTING | SHOWN | ADDED);\n-\tobjflags_get(o1) = flags1;\n-\tobjflags_get(o2) = flags2;\n+\tobj_flags_put(objflags, o1, flags1);\n+\tobj_flags_put(objflags, o2, flags2);\n }\n \n static void gen_message_id(struct rev_info *info, const char *base)\n@@ -2224,7 +2224,7 @@ int cmd_format_patch(int argc,\n \t\t\t * origin\" that prepares what the origin side still\n \t\t\t * does not have.\n \t\t\t */\n-\t\t\trev.pending.objects[0].item->flags |= UNINTERESTING;\n+\t\t\tobjflags_set(rev.pending.objects[0].item, UNINTERESTING);\n \t\t\tadd_head_to_pending(&rev);\n \t\t\tcheck_head = 1;\n \t\t}\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 89a48171e4..a29f716523 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1568,7 +1568,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (commit)\n-\t\t\tcommit->object.flags &= ~REACHABLE;\n+\t\t\tobjflags_clear(&commit->object, ~REACHABLE);\n \t}\n \tstop_progress(&ctx->progress);\n }\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 329c61d559..3189aee0db 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -812,7 +812,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t * leave a note to ourselves not to worry about\n \t\t\t * this object anymore.\n \t\t\t */\n-\t\t\tfrom->objects[i].item->flags |= assign_flag;\n+\t\t\tobjflags_set(from->objects[i].item, assign_flag);\n \t\t\tcontinue;\n \t\t}\n \ndiff --git a/http-push.c b/http-push.c\nindex 0706929cac..5d7635988e 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1377,7 +1377,7 @@ static int get_delta(struct rev_info *revs, struct remote_lock *lock)\n \twhile (objects) {\n \t\tstruct object_list *next = objects->next;\n \n-\t\tif (!(objects->item->flags & UNINTERESTING))\n+\t\tif (!(objflags_get(objects->item) & UNINTERESTING))\n \t\t\tcount += add_send_request(objects->item, lock);\n \n \t\tfree(objects);\ndiff --git a/range-diff.c b/range-diff.c\nindex 8a2dcbee32..2774720615 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -611,7 +611,7 @@ int is_range_diff_range(const char *arg)\n \trepo_init_revisions(the_repository, &revs, NULL);\n \tif (setup_revisions(3, argv, &revs, NULL) == 1) {\n \t\tfor (i = 0; i < revs.pending.nr; i++)\n-\t\t\tif (revs.pending.objects[i].item->flags & UNINTERESTING)\n+\t\t\tif (objflags_get(revs.pending.objects[i].item) & UNINTERESTING)\n \t\t\t\tnegative++;\n \t\t\telse\n \t\t\t\tpositive++;\ndiff --git a/reflog.c b/reflog.c\nindex 879e802228..ff99a8353c 100644\n--- a/reflog.c\n+++ b/reflog.c\n@@ -244,12 +244,12 @@ static int commit_is_complete(struct commit *commit)\n \t\tif (!is_incomplete) {\n \t\t\t/* mark all found commits as complete, iow SEEN */\n \t\t\tfor (i = 0; i < found.nr; i++)\n-\t\t\t\tfound.objects[i].item->flags |= SEEN;\n+\t\t\t\tobjflags_set(found.objects[i].item, SEEN);\n \t\t}\n \t}\n \t/* clear flags from the objects we traversed */\n \tfor (i = 0; i < found.nr; i++)\n-\t\tfound.objects[i].item->flags &= ~STUDYING;\n+\t\tobjflags_clear(found.objects[i].item, ~STUDYING);\n \tif (is_incomplete)\n \t\tobjflags_set(&commit->object, INCOMPLETE);\n \telse {\n@@ -262,7 +262,7 @@ static int commit_is_complete(struct commit *commit)\n \t\t * we have seen during this process are complete.\n \t\t */\n \t\tfor (i = 0; i < found.nr; i++)\n-\t\t\tfound.objects[i].item->flags |= SEEN;\n+\t\t\tobjflags_set(found.objects[i].item, SEEN);\n \t}\n \t/* free object arrays */\n \tobject_array_clear(&study);\ndiff --git a/revision.c b/revision.c\nindex 90e3ee30d5..4fd4b96eb1 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3656,10 +3656,10 @@ static void trace2_topo_walk_statistics_atexit(void)\n \n static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag)\n {\n-\tif (c->object.flags & flag)\n+\tif (objflags_get(&c->object) & flag)\n \t\treturn;\n \n-\tc->object.flags |= flag;\n+\tobjflags_set(&c->object, flag);\n \tprio_queue_put(q, c);\n }\n \n-- \n2.51.0.382.g68ff637df6\n\n\n"},{"id":"524966","messageId":"xmqqwm6qksgn.fsf@gitster.g","threadId":"64022","inReplyTo":"20250826042607.GA995491@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-26T15:34:00Z","receivedAt":"2025-08-26T15:34:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> OK, maybe I am just holding it wrong. I think I may have mistakenly been\n> using the wrong timing for my baseline (maybe --date-order instead of\n> --author-date-order; the latter is _way_ more expensive because we have\n> to open the commits to parse the author date).\n\nTrue. And the numbers below are much more believable ;-)\n\n> Here's a more apples-to-apples comparison using hyperfine. On git.git:\n> ...\n> So a little slowdown, but within the run-to-run noise. And on linux.git:\n> ...\n> A little more measurable there. Those numbers are more in line with what\n> I was expecting.\n> ...\n> I'm not sure what it all means, though. 6% is enough that it is\n> probably worth keeping a custom data type like slab around.\n> Though it would be nice to have a data type that worked on all\n> object types and didn't necessarily use a ton of memory.\n\nYup, a short version of it is \"assume that we still live in the old\nworld where 'you want to compute X? spawn a process, work in-core\nand compute and spew out your result, then exit(3) will clean up\nafter you' was the norm. And our codebase has an easy way to tell\nthe object API to allocate N extra bytes for app specific per object\nbookkeeping purpose. Now, would you use that facility to store your\ndata there because you'd need that data for all objects you touch in\nyour application?\" and if the answer is yes, it belongs to slab,\notherwise you are better off with a separate hashtable indexed via\nobject names populated only for few selected objects you care about.\n\nFor example, the slab is something I would have used to rewrite\n\"show-branch\", since it would have been really handy to have more\nbits in per-object \"flags\", and the most natural way to write that\napplication is to keep one bit in all objects it slurps in core for\nevery starting ref.\n\n> This particular case may not be representative, either. I picked it\n> because it was easy to convert. But I wonder how bad it would be to put\n> the object flags for a traversal into a hash. Right now those are in the\n> original struct, not even in a commit-slab. So I'd guess it's an even\n> bigger slowdown.\n\nTrue, too.\n"},{"id":"525264","messageId":"cb192b28-d85a-4866-a312-df4408cae93e@web.de","threadId":"64022","inReplyTo":"20250825073403.GA332447@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-08-31T17:25:13Z","receivedAt":"2025-08-31T17:30:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 8/25/25 9:34 AM, Jeff King wrote:\n> On Sun, Aug 24, 2025 at 06:32:47PM +0200, René Scharfe wrote:\n> \n>>>> Use the commit index value as a hash because it is unique, has the\n>>>> right size and needs no computation. We could also derive the hash\n>>>> directly from the pointer value, but that requires slightly more effort.\n>>>\n>>> Interesting. This is exactly what commit-slabs were created for (and are\n>>> why the convenient index value is there in the first place!).\n>>\n>> Kinda -- they have a payload value, while a khash set only stores keys.\n>> A commit slab with an int payload would still be smaller than a khash\n>> set with 64-bit pointers as keys -- IF we were to add all commits. Here\n>> we typically add just a few, but a pathological history could add a lot;\n>> not sure if there's a boundary. Hmm. So you might be able to find\n>> examples where commit-slabs win.\n> \n> A khash set doesn't have a \"vals\" array, but I think it does always keep\n> the flags array, which is a uint32_t per bucket. That's how it knows\n> which buckets have a value in them (since it does not otherwise assume\n> there is a sentinel value like NULL). So even though its API is that of\n> a set, you can think of it as a mapping of keys to flags. So a mapping\n> to an int (or even a char) should cost the same.\n\nAdmittedly I *did* ignore the flags and they *are* stored in an array of\nuint32_t, but they occupy only two bits per bucket (see __ac_isempty,\n__ac_isdel, __ac_fsize).\n\n>>> +define_commit_slab(commit_counter, int);\n>>\n>> We only need one bit, so a uint8_t or char would suffice.\n> \n> True, though that doesn't seem to change timings much for me (I used\n> \"int\" because that's what your khash used, but I think the type is a\n> dummy value in \"set\" mode).\nI also saw no significant change. Yes, the second type is not actually\nused in a khash set.\n\n> Thinking on it more, how much benefit are we getting from the use\n> of commit->index in your patch? In other contexts where we store oids or\n> objects in hash tables, we use the low bits of the oid directly. So it's\n> similarly cheap. If I do this tweak on top of your patch:\n> \n> diff --git a/builtin/describe.c b/builtin/describe.c\n> index edb4dec79d..e024feb080 100644\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -289,7 +289,7 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n> \n> static inline unsigned int commit_index(const struct commit *commit)\n> {\n> -\treturn commit->index;\n> +\treturn oidhash(&commit->object.oid);\n> }\n> \n> static inline int ptr_eq(const void *a, const void *b)\n> \n> I get similar results (actually faster, but I think within the noise).\n\nSure. I'm not comfortable with oidhash() though, because it allows\nattackers to influence the hash value, cause collisions and thus\nincrease the cost of lookups and inserts to O(N), leading to quadratic\ncomplexity overall.\n\nThey \"just\" need to construct commits with a common hash prefix. I\nguess that's easy for two bytes and hard for four bytes. Not sure how\nwhat an attacker would get out of planting such performance traps, but\nI guess some people would do it just for the heck of it.\n\nLetting oidhash() XOR in another word would close that line of attack\nfor quite a while, I assume.\n\n> Which made me think more (always a danger). We already have an oidset\n> data structure, which is backed by a khash. It's not _quite_ the same\n> thing, because it's going to store an actual 36-byte oid struct as the\n> hash key, rather than an 8-byte pointer to a \"struct object\" (which\n> contains that same oid). And likewise when we do a lookup, the bucket\n> search requires a larger memcmp() than the pointer equality. But how\n> much difference does that make?\n> \n> If I instead do this on top of your patch:\n> \n> diff --git a/builtin/describe.c b/builtin/describe.c\n> index edb4dec79d..38ce0c1978 100644\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -287,41 +287,16 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n> \tqueue->get_pending = false;\n> }\n> \n> -static inline unsigned int commit_index(const struct commit *commit)\n> -{\n> -\treturn commit->index;\n> -}\n> -\n> -static inline int ptr_eq(const void *a, const void *b)\n> -{\n> -\treturn a == b;\n> -}\n> -\n> -KHASH_INIT(commit_set, struct commit *, int, 0, commit_index, ptr_eq)\n> -\n> -static void commit_set_insert(kh_commit_set_t *set, struct commit *commit)\n> -{\n> -\tint added;\n> -\tkh_put_commit_set(set, commit, &added);\n> -}\n> -\n> -static void commit_set_remove(kh_commit_set_t *set, struct commit *commit)\n> -{\n> -\tkhiter_t pos = kh_get_commit_set(set, commit);\n> -\tif (pos != kh_end(set))\n> -\t\tkh_del_commit_set(set, pos);\n> -}\n> -\n> static unsigned long finish_depth_computation(struct lazy_queue *queue,\n> \t\t\t\t\t struct possible_tag *best)\n> {\n> \tunsigned long seen_commits = 0;\n> -\tkh_commit_set_t unflagged = { 0 };\n> +\tstruct oidset unflagged = OIDSET_INIT;\n> \n> \tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n> \t\tstruct commit *commit = queue->queue.array[i].data;\n> \t\tif (!(commit->object.flags & best->flag_within))\n> -\t\t\tcommit_set_insert(&unflagged, commit);\n> +\t\t\toidset_insert(&unflagged, &commit->object.oid);\n> \t}\n> \n> \twhile (!lazy_queue_empty(queue)) {\n> @@ -330,10 +305,10 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n> \n> \t\tseen_commits++;\n> \t\tif (c->object.flags & best->flag_within) {\n> -\t\t\tif (!kh_size(&unflagged))\n> +\t\t\tif (!oidset_size(&unflagged))\n> \t\t\t\tbreak;\n> \t\t} else {\n> -\t\t\tcommit_set_remove(&unflagged, c);\n> +\t\t\toidset_remove(&unflagged, &c->object.oid);\n> \t\t\tbest->depth++;\n> \t\t}\n> \t\twhile (parents) {\n> @@ -348,13 +323,13 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n> \t\t\tp->object.flags |= c->object.flags;\n> \t\t\tflag_after = p->object.flags & best->flag_within;\n> \t\t\tif (!seen && !flag_after)\n> -\t\t\t\tcommit_set_insert(&unflagged, p);\n> +\t\t\t\toidset_insert(&unflagged, &p->object.oid);\n> \t\t\tif (seen && !flag_before && flag_after)\n> -\t\t\t\tcommit_set_remove(&unflagged, p);\n> +\t\t\t\toidset_remove(&unflagged, &p->object.oid);\n> \t\t\tparents = parents->next;\n> \t\t}\n> \t}\n> -\tkh_release_commit_set(&unflagged);\n> +\toidset_clear(&unflagged);\n> \treturn seen_commits;\n> }\n> \n> \n> then I likewise get very similar timings. Your version seems to be\n> consistently a little bit faster, but within the run-to-run noise of\n> ~1%. But the bonus here is that we didn't need to define a new hash\n> type, nor do any tricks with the commit->index field.\n\nI don't see any performance difference at all. Using the existing\noidset structure is clearly better under these circumstances.\n\n> Now if we really are worried about those extra bytes in storing a fresh\n> oid, is there room for new data types? I.e., A \"struct objset\" that\n> stores object pointers, hashes based on the oid, and uses pointer\n> equality to find a match? And likewise a \"struct objmap\" that could\n> perhaps compete with commit-slab (but be more pleasant to use).\n\nMaybe. It's a matter of measuring the performance difference, though,\nand that's hard.\n\n>>> 2. Can the hash version handle strides of different sizes? One of the\n>>> points of commit-slab is that the fixed size of the value type can\n>>> be set at runtime (so you could have a slab of 32 bits per commit,\n>>> or 132, depending on your traversal needs).\n>>\n>> Dynamic value sizes require an indirection via a pointer, or at least I\n>> don't see any other way. What would be a possible use case? (Don't see\n>> any in-tree.)\n> \n> The value isn't totally dynamic; it's static for a single instantiation\n> of a slab. I don't think khash supports that (it has a value type and\n> lets the compiler take care of indexing into an array of that value).\n> But you could imagine a world where khash (or some custom hash code)\n> only knows that it's storing N bytes per item, and does the indexing\n> multiplication itself.\n> \n> But yes, I don't think we are even using that feature of commit-slab\n> currently. I used it in a series for fast --contains long ago:\n> \n> https://lore.kernel.org/git/20140625233429.GA20457@sigill.intra.peff.net/\n> \n> but can't remember why I never got back to it. It would also be useful\n> for show-branch, which wants to paint down for each starting tip. But\n> given that we haven't used it, it may just not be that useful a feature.\n\nOr for describe, actually, to allow an arbitrarily large --max-candidates\nvalue.\n\nRené\n\n"},{"id":"525286","messageId":"84fb48b3-17ae-405c-b7a9-6d48a3c57a36@web.de","threadId":"64022","inReplyTo":"cb192b28-d85a-4866-a312-df4408cae93e@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-09-01T19:06:19Z","receivedAt":"2025-09-01T19:06:28Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 8/31/25 7:25 PM, René Scharfe wrote:\n> Sure. I'm not comfortable with oidhash() though, because it allows\n> attackers to influence the hash value, cause collisions and thus\n> increase the cost of lookups and inserts to O(N), leading to quadratic\n> complexity overall.\n> \n> They \"just\" need to construct commits with a common hash prefix. I\n> guess that's easy for two bytes and hard for four bytes. Not sure how\n> what an attacker would get out of planting such performance traps, but\n> I guess some people would do it just for the heck of it.\n\nThere's https://github.com/not-an-aardvark/lucky-commit, which claims to\ntake a quarter of a second on a four year old laptop to give a commit a\nchosen 28-bit hash prefix by adjusting whitespace in its message.\nConstructing a history with a common 32-bit prefix that would\neffectively turn any oidhash()-based hash table into an unordered list\nseems within easy reach.\n\nRené\n\n"},{"id":"525338","messageId":"20250902123834.GA711442@coredump.intra.peff.net","threadId":"64022","inReplyTo":"cb192b28-d85a-4866-a312-df4408cae93e@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-09-02T12:38:34Z","receivedAt":"2025-09-02T12:38:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 31, 2025 at 07:25:13PM +0200, René Scharfe wrote:\n\n> > diff --git a/builtin/describe.c b/builtin/describe.c\n> > index edb4dec79d..e024feb080 100644\n> > --- a/builtin/describe.c\n> > +++ b/builtin/describe.c\n> > @@ -289,7 +289,7 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n> > \n> > static inline unsigned int commit_index(const struct commit *commit)\n> > {\n> > -\treturn commit->index;\n> > +\treturn oidhash(&commit->object.oid);\n> > }\n> > \n> > static inline int ptr_eq(const void *a, const void *b)\n> > \n> > I get similar results (actually faster, but I think within the noise).\n> \n> Sure. I'm not comfortable with oidhash() though, because it allows\n> attackers to influence the hash value, cause collisions and thus\n> increase the cost of lookups and inserts to O(N), leading to quadratic\n> complexity overall.\n>\n> They \"just\" need to construct commits with a common hash prefix. I\n> guess that's easy for two bytes and hard for four bytes. Not sure how\n> what an attacker would get out of planting such performance traps, but\n> I guess some people would do it just for the heck of it.\n\nI doubt that commit->index is any better in that regard. If I can\ninfluence the order in which Git loads the commits (e.g., by creating a\nbunch of refs which get loaded when we walk over for_each_ref), I can\nchoose the index for each. They'll be unique, but I can still cause\ncollisions modulo the number of buckets.\n\nLikewise for oidhash(), I'd guess that colliding 4 bytes is not even\nnecessary to cause trouble, since probing starts by throwing away\neverything mod n_buckets. So really you just need to collide however\nmany low bits you need to make your desired N, and then get O(N^2)\nbehavior.\n\nI'm not super worried about it, because in my experience Git is already\na perfectly tuned device for convincing other people to waste CPU. ;)\nBut if we want to address it, I'd rather do so by improving oidhash()\nthan avoiding it. Specifically...\n\n> Letting oidhash() XOR in another word would close that line of attack\n> for quite a while, I assume.\n\nYeah. We have at least 160 bits in an object hash, and we only bother\nwith the low 32. We could XOR up to 5 times, but I agree that even a\nsingle extra word would probably be plenty. Might be an interesting\nexperiment to time something like the patch below on a hash-heavy\nworkload.\n\ndiff --git a/hash.h b/hash.h\nindex fae966b23c..c9d21f589e 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -457,7 +457,10 @@ static inline unsigned int oidhash(const struct object_id *oid)\n \t * platforms that don't support unaligned reads.\n \t */\n \tunsigned int hash;\n+\tunsigned int entropy;\n \tmemcpy(&hash, oid->hash, sizeof(hash));\n+\tmemcpy(&entropy, oid->hash + sizeof(hash), sizeof(entropy));\n+\thash ^= entropy;\n \treturn hash;\n }\n \n\nI suspect it won't make a big time difference. The old code should have\nbeen optimized down to a single word load, and now we have two word\nloads and an xor. That probably isn't important compared to the actual\n5-word memcmp() we have to do in order to verify that we found the right\nbucket anyway.\n\n-Peff\n"},{"id":"525365","messageId":"b16aa099-b683-4a66-acd9-603cc9f0935c@web.de","threadId":"64022","inReplyTo":"9110f085-aec0-42e9-9774-b153ece6284f@web.de","subject":"[PATCH v2] describe: use oidset in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-09-02T18:24:52Z","receivedAt":"2025-09-02T18:24:54Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Depth computation can end early if all remaining commits are flagged.\nThe current code determines if that's the case by checking all queue\nitems each time it dequeues a flagged commit. This can cause\nquadratic complexity.\n\nWe could simply count the flagged items in the queue and then update\nthat number as we add and remove items. That would provide a general\nspeedup, but leave one case where we have to scan the whole queue: When\nwe flag a previously seen, but unflagged commit. It could be on the\nqueue and then we'd have to decrease our count.\n\nWe could dedicate an object flag to track queue membership, but that\nwould leave less for candidate tags, affecting the results. So use a\nhash table, specifically an oidset of commit hashes, to track that.\nThis avoids quadratic behaviour in all cases and provides a nice\nperformance boost over the previous commit, 08bb69d70f (describe: use\nprio_queue_replace(), 2025-08-03):\n\nBenchmark 1: ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 855.3 ms ± 1.3 ms [User: 790.8 ms, System: 49.9 ms]\n Range (min … max): 853.7 ms … 857.8 ms 10 runs\n\nBenchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)\n Time (mean ± σ): 610.8 ms ± 1.7 ms [User: 546.9 ms, System: 49.3 ms]\n Range (min … max): 608.9 ms … 613.3 ms 10 runs\n\nSummary\n ./git describe $(git rev-list v2.41.0..v2.47.0) ran\n 1.40 ± 0.00 times faster than ./git_08bb69d70f describe $(git rev-list v2.41.0..v2.47.0)\n\nHelped-by: Jeff King \nSigned-off-by: René Scharfe \n---\nChanges:\n- Use oidset instead of a custom khash set for simplicity.\n- Removed spurious whitespace changes.\n- Formatted with --patience to better see the function removal.\n\n builtin/describe.c | 36 +++++++++++++++++++++++-------------\n 1 file changed, 23 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex fbe78ace66..9f4e26d7ff 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -24,6 +24,7 @@\n #include \"commit-slab.h\"\n #include \"wildmatch.h\"\n #include \"prio-queue.h\"\n+#include \"oidset.h\"\n \n #define MAX_TAGS\t(FLAG_BITS - 1)\n #define DEFAULT_CANDIDATES 10\n@@ -286,38 +287,47 @@ static void lazy_queue_clear(struct lazy_queue *queue)\n \tqueue->get_pending = false;\n }\n \n-static bool all_have_flag(const struct lazy_queue *queue, unsigned flag)\n-{\n-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n-\t\tstruct commit *commit = queue->queue.array[i].data;\n-\t\tif (!(commit->object.flags & flag))\n-\t\t\treturn false;\n-\t}\n-\treturn true;\n-}\n-\n static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\t\t\t struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n+\tstruct oidset unflagged = OIDSET_INIT;\n+\n+\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n+\t\tstruct commit *commit = queue->queue.array[i].data;\n+\t\tif (!(commit->object.flags & best->flag_within))\n+\t\t\toidset_insert(&unflagged, &commit->object.oid);\n+\t}\n+\n \twhile (!lazy_queue_empty(queue)) {\n \t\tstruct commit *c = lazy_queue_get(queue);\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n-\t\t\tif (all_have_flag(queue, best->flag_within))\n+\t\t\tif (!oidset_size(&unflagged))\n \t\t\t\tbreak;\n-\t\t} else\n+\t\t} else {\n+\t\t\toidset_remove(&unflagged, &c->object.oid);\n \t\t\tbest->depth++;\n+\t\t}\n \t\twhile (parents) {\n+\t\t\tunsigned seen, flag_before, flag_after;\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n-\t\t\tif (!(p->object.flags & SEEN))\n+\t\t\tseen = p->object.flags & SEEN;\n+\t\t\tif (!seen)\n \t\t\t\tlazy_queue_put(queue, p);\n+\t\t\tflag_before = p->object.flags & best->flag_within;\n \t\t\tp->object.flags |= c->object.flags;\n+\t\t\tflag_after = p->object.flags & best->flag_within;\n+\t\t\tif (!seen && !flag_after)\n+\t\t\t\toidset_insert(&unflagged, &p->object.oid);\n+\t\t\tif (seen && !flag_before && flag_after)\n+\t\t\t\toidset_remove(&unflagged, &p->object.oid);\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n+\toidset_clear(&unflagged);\n \treturn seen_commits;\n }\n \n-- \n2.51.0\n"},{"id":"525368","messageId":"05b8e161-9087-4eb8-b049-6e99ff288af7@web.de","threadId":"64022","inReplyTo":"20250902123834.GA711442@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-09-02T18:51:37Z","receivedAt":"2025-09-02T18:51:42Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 9/2/25 2:38 PM, Jeff King wrote:\n> \n> I doubt that commit->index is any better in that regard. If I can\n> influence the order in which Git loads the commits (e.g., by creating a\n> bunch of refs which get loaded when we walk over for_each_ref), I can\n> choose the index for each. They'll be unique, but I can still cause\n> collisions modulo the number of buckets.\n\nHmm, sounds tricky, but feasible. :-O\n> Likewise for oidhash(), I'd guess that colliding 4 bytes is not even\n> necessary to cause trouble, since probing starts by throwing away\n> everything mod n_buckets. So really you just need to collide however\n> many low bits you need to make your desired N, and then get O(N^2)\n> behavior.\n\nOh, right.\n\n>> Letting oidhash() XOR in another word would close that line of attack\n>> for quite a while, I assume.\n> \n> Yeah. We have at least 160 bits in an object hash, and we only bother\n> with the low 32. We could XOR up to 5 times, but I agree that even a\n> single extra word would probably be plenty. Might be an interesting\n> experiment to time something like the patch below on a hash-heavy\n> workload.\n> \n> diff --git a/hash.h b/hash.h\n> index fae966b23c..c9d21f589e 100644\n> --- a/hash.h\n> +++ b/hash.h\n> @@ -457,7 +457,10 @@ static inline unsigned int oidhash(const struct object_id *oid)\n> \t * platforms that don't support unaligned reads.\n> \t */\n> \tunsigned int hash;\n> +\tunsigned int entropy;\n> \tmemcpy(&hash, oid->hash, sizeof(hash));\n> +\tmemcpy(&entropy, oid->hash + sizeof(hash), sizeof(entropy));\n> +\thash ^= entropy;\n> \treturn hash;\n> }\n> \n> \n> I suspect it won't make a big time difference. The old code should have\n> been optimized down to a single word load, and now we have two word\n> loads and an xor. That probably isn't important compared to the actual\n> 5-word memcmp() we have to do in order to verify that we found the right\n> bucket anyway.\nI see slightly worse performance, but within the noise.\n\nHowever, just stacking two words won't do if only a few bits of the\nresulting hash will be used to find a bucket. We could mix in more bits\nand smear them all over, but if that's done by a deterministic function\nthen it could be applied during the construction of manipulated object\nhash values as well, no?\n\nPerhaps salting with a random value determined at runtime would help.\nNot XORing it in (pointless if the other value is controlled by the\nattacker, as the result would still collide), but using it as a mask to\nchoose the bits to take from the object hash?\n\nRené\n\n"},{"id":"525432","messageId":"20250903143134.GA1884731@coredump.intra.peff.net","threadId":"64022","inReplyTo":"05b8e161-9087-4eb8-b049-6e99ff288af7@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-09-03T14:31:34Z","receivedAt":"2025-09-03T14:31:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 02, 2025 at 08:51:37PM +0200, René Scharfe wrote:\n\n> > I suspect it won't make a big time difference. The old code should have\n> > been optimized down to a single word load, and now we have two word\n> > loads and an xor. That probably isn't important compared to the actual\n> > 5-word memcmp() we have to do in order to verify that we found the right\n> > bucket anyway.\n>\n> I see slightly worse performance, but within the noise.\n> \n> However, just stacking two words won't do if only a few bits of the\n> resulting hash will be used to find a bucket. We could mix in more bits\n> and smear them all over, but if that's done by a deterministic function\n> then it could be applied during the construction of manipulated object\n> hash values as well, no?\n\nI think the difficulty in manipulating scales as the number of bits\nincreases. So yeah, if you are worried about the low 8 bits, then\nXOR-ing in another 8 bits is not going to do much. But your table is\nonly 256 items long, so you don't care much either way.\n\nAt even 16 bits, it gets hard for the attacker to choose the low 16 bits\n_and_ the low 16 bits of the next word (you mentioned a project earlier\nwhich claims 28 bits). If you XOR in a third word, now your 16-bit hash\nis using 48 bits that the attacker has to control. And so on.\n\n> Perhaps salting with a random value determined at runtime would help.\n> Not XORing it in (pointless if the other value is controlled by the\n> attacker, as the result would still collide), but using it as a mask to\n> choose the bits to take from the object hash?\n\nI think that would work, but XOR-ing the higher order bits is easier to\ndo and I think produces a similar effect. Let's shrink the problem for a\nsecond. Imagine sha1 was 16 bits, and we wanted to create an 8-bit hash\nto use in our table. The attacker creates two objects with binary\nhashes:\n\n object a: 10111001 11110111\n object b: 01001000 11110111\n\nThey collide in the lower 8 bits, but we don't want them to. In your\nscheme, as I understand it, we'd come up with a 16-bit mask that has\nexactly 8 bits set, like:\n\n 11010110 01011000\n\nand then picking only the bits where the mask is \"1\", we get:\n\n object a: 10111001 11110111\n mask: 11010110 01011000\n hash a: 10100110\n\n object b: 01001000 11110111\n mask: 11010110 01011000\n hash b: 01000110\n\nSo I agree that is hard to foil without the attacker knowing which bits\nyou'll pick. You've made their job 8 bits harder, because they now have\nto control all 16 bits to get their collision.\n\nBut if we instead XOR the words of the object hashes together, we get:\n\n object a[hi]: 10111001\n object a[lo]: 11110111\n hash a: 01001110\n\n object b[hi]: 01001000\n object b[lo]: 11110111\n hash b: 10111111\n\nSo you're flipping bits \"randomly\". It's not truly random, but is coming\nfrom the rest of the hash the attacker provided. But for any bit they\nwant to control, they have to control that position in both words. So\nthey're back to needing to control all 16 bits to get their desired\nhash.\n\nAnd as somebody who just hand-computed those answers, I can tell you\nthat the XOR one is much simpler to do. ;)\n\n-Peff\n"},{"id":"525433","messageId":"20250903143634.GB1884731@coredump.intra.peff.net","threadId":"64022","inReplyTo":"b16aa099-b683-4a66-acd9-603cc9f0935c@web.de","subject":"Re: [PATCH v2] describe: use oidset in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-09-03T14:36:34Z","receivedAt":"2025-09-03T14:36:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 02, 2025 at 08:24:52PM +0200, René Scharfe wrote:\n\n> Changes:\n> - Use oidset instead of a custom khash set for simplicity.\n> - Removed spurious whitespace changes.\n> - Formatted with --patience to better see the function removal.\n\nThanks, this version looks good to me.\n\n-Peff\n"},{"id":"525437","messageId":"f6b4c1fb-9f59-4072-a796-e2971524ffa5@web.de","threadId":"64022","inReplyTo":"20250903143134.GA1884731@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-09-03T15:41:49Z","receivedAt":"2025-09-03T15:55:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 9/3/25 4:31 PM, Jeff King wrote:\n> On Tue, Sep 02, 2025 at 08:51:37PM +0200, René Scharfe wrote:\n> \n>>> I suspect it won't make a big time difference. The old code should have\n>>> been optimized down to a single word load, and now we have two word\n>>> loads and an xor. That probably isn't important compared to the actual\n>>> 5-word memcmp() we have to do in order to verify that we found the right\n>>> bucket anyway.\n>>\n>> I see slightly worse performance, but within the noise.\n>>\n>> However, just stacking two words won't do if only a few bits of the\n>> resulting hash will be used to find a bucket. We could mix in more bits\n>> and smear them all over, but if that's done by a deterministic function\n>> then it could be applied during the construction of manipulated object\n>> hash values as well, no?\n> \n> I think the difficulty in manipulating scales as the number of bits\n> increases. So yeah, if you are worried about the low 8 bits, then\n> XOR-ing in another 8 bits is not going to do much. But your table is\n> only 256 items long, so you don't care much either way.\n> \n> At even 16 bits, it gets hard for the attacker to choose the low 16 bits\n> _and_ the low 16 bits of the next word (you mentioned a project earlier\n> which claims 28 bits). If you XOR in a third word, now your 16-bit hash\n> is using 48 bits that the attacker has to control. And so on.\n> \n>> Perhaps salting with a random value determined at runtime would help.\n>> Not XORing it in (pointless if the other value is controlled by the\n>> attacker, as the result would still collide), but using it as a mask to\n>> choose the bits to take from the object hash?\n> \n> I think that would work, but XOR-ing the higher order bits is easier to\n> do and I think produces a similar effect. Let's shrink the problem for a\n> second. Imagine sha1 was 16 bits, and we wanted to create an 8-bit hash\n> to use in our table. The attacker creates two objects with binary\n> hashes:\n> \n> object a: 10111001 11110111\n> object b: 01001000 11110111\n> \n> They collide in the lower 8 bits, but we don't want them to. In your\n> scheme, as I understand it, we'd come up with a 16-bit mask that has\n> exactly 8 bits set, like:\n> \n> 11010110 01011000\n> \n> and then picking only the bits where the mask is \"1\", we get:\n> \n> object a: 10111001 11110111\n> mask: 11010110 01011000\n> hash a: 10100110\n> \n> object b: 01001000 11110111\n> mask: 11010110 01011000\n> hash b: 01000110\n> \n> So I agree that is hard to foil without the attacker knowing which bits\n> you'll pick. You've made their job 8 bits harder, because they now have\n> to control all 16 bits to get their collision.\n> \n> But if we instead XOR the words of the object hashes together, we get:\n> \n> object a[hi]: 10111001\n> object a[lo]: 11110111\n> hash a: 01001110\n> \n> object b[hi]: 01001000\n> object b[lo]: 11110111\n> hash b: 10111111\n> \n> So you're flipping bits \"randomly\". It's not truly random, but is coming\n> from the rest of the hash the attacker provided. But for any bit they\n> want to control, they have to control that position in both words. So\n> they're back to needing to control all 16 bits to get their desired\n> hash.\n> \n> And as somebody who just hand-computed those answers, I can tell you\n> that the XOR one is much simpler to do. ;)\nNo doubt. :) Using a deterministic function is easier, but also allows\nan attacker to use it for finding object hash values that yield\ncolliding hash table hashes.\n\nHow does an attacker control object hashes? Hash it, check if it fits\nthe criteria, if it doesn't then make some inconsequential changes like\nadding whitespace to a commit message and repeat. That criteria can be\n\"bits 1-16 are all zero\", but it can just as well be \"bits 1-8 XORed\nwith bits 9-16 are all zero\". For the former they'd have to roll the\ndice in the order of 2^16 times, for the latter just 2^8 times.\n\nThe attacker in our scenario doesn't have to care about the individual\nbits of object hashes, just the resulting hash table hashes, which\nreduces their search space a lot. Making the deterministic function\nmore complicated or using more attacker-supplied input bits doesn't\nchange that.\n\nRené\n\n"},{"id":"525438","messageId":"aeb6aa64-c2f8-4b28-a2cf-9662907b5feb@web.de","threadId":"64022","inReplyTo":"20250825073403.GA332447@coredump.intra.peff.net","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-09-03T16:30:57Z","receivedAt":"2025-09-03T16:31:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 8/25/25 9:34 AM, Jeff King wrote:\n> \n> [oidset instead of khash]\n> But the bonus here is that we didn't need to define a new hash\n> type, nor do any tricks with the commit->index field.\n\nIt took me a while to notice what's tricky, or rather inconsistent,\nabout the khash set of commit objects with commit index as hash: We\ncould just as well go all in and use an uint32_t khash set of commit\nindexes. That would reduce the memory footprint further. No pointers\nneeded here. Didn't measure a meaningful performance difference\nthough, so that's that..\nRené\n\n"},{"id":"525489","messageId":"20250904111619.GA2474144@coredump.intra.peff.net","threadId":"64022","inReplyTo":"f6b4c1fb-9f59-4072-a796-e2971524ffa5@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-09-04T11:16:19Z","receivedAt":"2025-09-04T11:16:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 03, 2025 at 05:41:49PM +0200, René Scharfe wrote:\n\n> How does an attacker control object hashes? Hash it, check if it fits\n> the criteria, if it doesn't then make some inconsequential changes like\n> adding whitespace to a commit message and repeat. That criteria can be\n> \"bits 1-16 are all zero\", but it can just as well be \"bits 1-8 XORed\n> with bits 9-16 are all zero\". For the former they'd have to roll the\n> dice in the order of 2^16 times, for the latter just 2^8 times.\n\nHmm, yeah, you're right. I was counting the wrong thing. It is not one\nexpensive action to generate a byte (or word) of sha1 hash. It is one\naction to generate the whole hash. And then cheap to XOR it and find out\nwhat the result would be in our XOR-bucket scheme. So if you are just\nbrute-forcing anyway, it is the same number of hash attempts, which is\nwhat the attacker cares about minimizing. My proposal adds nothing\nthere.\n\n> The attacker in our scenario doesn't have to care about the individual\n> bits of object hashes, just the resulting hash table hashes, which\n> reduces their search space a lot. Making the deterministic function\n> more complicated or using more attacker-supplied input bits doesn't\n> change that.\n\nYep. Thanks for a dose of sanity.\n\n-Peff\n"},{"id":"525490","messageId":"20250904112255.GB2474144@coredump.intra.peff.net","threadId":"64022","inReplyTo":"aeb6aa64-c2f8-4b28-a2cf-9662907b5feb@web.de","subject":"Re: [PATCH] describe: use khash in finish_depth_computation()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-09-04T11:22:55Z","receivedAt":"2025-09-04T11:22:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 03, 2025 at 06:30:57PM +0200, René Scharfe wrote:\n\n> On 8/25/25 9:34 AM, Jeff King wrote:\n> > \n> > [oidset instead of khash]\n> > But the bonus here is that we didn't need to define a new hash\n> > type, nor do any tricks with the commit->index field.\n> \n> It took me a while to notice what's tricky, or rather inconsistent,\n> about the khash set of commit objects with commit index as hash: We\n> could just as well go all in and use an uint32_t khash set of commit\n> indexes. That would reduce the memory footprint further. No pointers\n> needed here. Didn't measure a meaningful performance difference\n> though, so that's that..\n\nHeh, yes, that's true. I didn't even think about that. Conceptually we\ncould replace \"struct object\" with just an index value, and then all\ncode could just allocate arrays and index them. And the commit-slab code\nis essentially a slightly more dynamic version of that. And a hash of\nints is a good way of handling a sparsely populated set of data.\n\nIt's less crazy than it sounds because we allocate objects sequentially\nand never free them anyway. But it would still be a pretty big change\n(and each data access would involve a few extra instructions to compute\nthe address).\n\nAnyway, I'm happy enough with the oidset solution you landed on.\n\n-Peff\n"}]}