{"thread":{"id":"62962","subject":"[GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","startedAt":"2025-02-17T05:51:17Z","lastAt":"2025-03-02T12:56:58Z","messageCount":6,"participants":["Meet Soni","Junio C Hamano","Jeff King","Ghanshyam Thakkar"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"512497","messageId":"20250217055049.9217-1-meetsoni3017@gmail.com","threadId":"62962","inReplyTo":null,"subject":"[GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-17T05:50:49Z","receivedAt":"2025-02-17T05:51:17Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"Replace direct accesses to commit->object.flags with the commit-slab\nmechanism. Introduce `get_commit_flags()` and `set_commit_flags()` to\nretrieve and update flags, respectively, and include `revision.h` so that\nthe canonical UNINTERESTING definition is used.\n\nSigned-off-by: Meet Soni <meetsoni3017@gmail.com>\n---\nI'm not entirely sure what the TODO comment meant by storing a pointer to\nthe \"ref name\" directly, so I've assumed that the intent was to store\nflags (of type int) directly in the commit-slab instead of commit->object.\n\nI've tested these changes using:\n - test suite -- they passed.\n - github ci result -- https://github.com/inosmeet/git/actions/runs/13355488433\n\nThe review from Junio that led to this TODO comment [1]:\n> Another place we could use commit-slab in this program, which I\n> think is a more interesting application, is to use it to store a\n> bitmask with runtime-computed width to replace those object->flags\n> bits, which will allow us to lift the MAX_REVS limitation.\n\nUltimately, I'm interested in implementing this change and would appreciate\nsome guidance. Specifically, does this mean I should define the commit-slab\nusing a struct containing both an int and a size, instead of just an int?\n\n[1]: https://lore.kernel.org/git/xmqq36yud9bp.fsf@gitster-ct.c.googlers.com/\n\n builtin/show-branch.c | 59 +++++++++++++++++++++++++------------------\n 1 file changed, 34 insertions(+), 25 deletions(-)\n\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex fce6b404e9..909a22990d 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -9,6 +9,7 @@\n #include \"hex.h\"\n #include \"pretty.h\"\n #include \"refs.h\"\n+#include \"revision.h\"\n #include \"color.h\"\n #include \"strvec.h\"\n #include \"object-name.h\"\n@@ -33,18 +34,25 @@ static int showbranch_use_color = -1;\n \n static struct strvec default_args = STRVEC_INIT;\n \n-/*\n- * TODO: convert this use of commit->object.flags to commit-slab\n- * instead to store a pointer to ref name directly. Then use the same\n- * UNINTERESTING definition from revision.h here.\n- */\n-#define UNINTERESTING\t01\n-\n #define REV_SHIFT\t 2\n #define MAX_REVS\t(FLAG_BITS - REV_SHIFT) /* should not exceed bits_per_int - REV_SHIFT */\n \n #define DEFAULT_REFLOG\t4\n \n+define_commit_slab(commit_flags, int);\n+static struct commit_flags commit_flags;\n+\n+static int get_commit_flags(struct commit *commit)\n+{\n+\tint *result = commit_flags_peek(&commit_flags, commit);\n+\treturn result ? *result : 0;\n+}\n+\n+static void set_commit_flags(struct commit *commit, int flags)\n+{\n+\t*commit_flags_at(&commit_flags, commit) = flags;\n+}\n+\n static const char *get_color_code(int idx)\n {\n \tif (want_color(showbranch_use_color))\n@@ -64,7 +72,7 @@ static struct commit *interesting(struct commit_list *list)\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n \t\tlist = list->next;\n-\t\tif (commit->object.flags & UNINTERESTING)\n+\t\tif (get_commit_flags(commit) & UNINTERESTING)\n \t\t\tcontinue;\n \t\treturn commit;\n \t}\n@@ -215,7 +223,7 @@ static void name_commits(struct commit_list *list,\n \n static int mark_seen(struct commit *commit, struct commit_list **seen_p)\n {\n-\tif (!commit->object.flags) {\n+\tif (!get_commit_flags(commit)) {\n \t\tcommit_list_insert(commit, seen_p);\n \t\treturn 1;\n \t}\n@@ -233,7 +241,7 @@ static void join_revs(struct commit_list **list_p,\n \t\tstruct commit_list *parents;\n \t\tint still_interesting = !!interesting(*list_p);\n \t\tstruct commit *commit = pop_commit(list_p);\n-\t\tint flags = commit->object.flags & all_mask;\n+\t\tint flags = get_commit_flags(commit) & all_mask;\n \n \t\tif (!still_interesting && extra <= 0)\n \t\t\tbreak;\n@@ -245,14 +253,14 @@ static void join_revs(struct commit_list **list_p,\n \n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n-\t\t\tint this_flag = p->object.flags;\n+\t\t\tint this_flag = get_commit_flags(p);\n \t\t\tparents = parents->next;\n \t\t\tif ((this_flag & flags) == flags)\n \t\t\t\tcontinue;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n \t\t\t\textra--;\n-\t\t\tp->object.flags |= flags;\n+\t\t\tset_commit_flags(p, get_commit_flags(p) | flags);\n \t\t\tcommit_list_insert_by_date(p, list_p);\n \t\t}\n \t}\n@@ -271,8 +279,8 @@ static void join_revs(struct commit_list **list_p,\n \t\t\tstruct commit *c = s->item;\n \t\t\tstruct commit_list *parents;\n \n-\t\t\tif (((c->object.flags & all_revs) != all_revs) &&\n-\t\t\t    !(c->object.flags & UNINTERESTING))\n+\t\t\tif (((get_commit_flags(c) & all_revs) != all_revs) &&\n+\t\t\t    !(get_commit_flags(c) & UNINTERESTING))\n \t\t\t\tcontinue;\n \n \t\t\t/* The current commit is either a merge base or\n@@ -285,8 +293,8 @@ static void join_revs(struct commit_list **list_p,\n \t\t\twhile (parents) {\n \t\t\t\tstruct commit *p = parents->item;\n \t\t\t\tparents = parents->next;\n-\t\t\t\tif (!(p->object.flags & UNINTERESTING)) {\n-\t\t\t\t\tp->object.flags |= UNINTERESTING;\n+\t\t\t\tif (!(get_commit_flags(p) & UNINTERESTING)) {\n+\t\t\t\t\tset_commit_flags(p, get_commit_flags(p) | UNINTERESTING);\n \t\t\t\t\tchanged = 1;\n \t\t\t\t}\n \t\t\t}\n@@ -513,12 +521,12 @@ static int show_merge_base(const struct commit_list *seen, int num_rev)\n \n \tfor (const struct commit_list *s = seen; s; s = s->next) {\n \t\tstruct commit *commit = s->item;\n-\t\tint flags = commit->object.flags & all_mask;\n+\t\tint flags = get_commit_flags(commit) & all_mask;\n \t\tif (!(flags & UNINTERESTING) &&\n \t\t    ((flags & all_revs) == all_revs)) {\n \t\t\tputs(oid_to_hex(&commit->object.oid));\n \t\t\texit_status = 0;\n-\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t\tset_commit_flags(commit, get_commit_flags(commit) | UNINTERESTING);\n \t\t}\n \t}\n \treturn exit_status;\n@@ -534,9 +542,9 @@ static int show_independent(struct commit **rev,\n \t\tstruct commit *commit = rev[i];\n \t\tunsigned int flag = rev_mask[i];\n \n-\t\tif (commit->object.flags == flag)\n+\t\tif (get_commit_flags(commit) == flag)\n \t\t\tputs(oid_to_hex(&commit->object.oid));\n-\t\tcommit->object.flags |= UNINTERESTING;\n+\t\tset_commit_flags(commit, get_commit_flags(commit) | UNINTERESTING);\n \t}\n \treturn 0;\n }\n@@ -603,7 +611,7 @@ static int omit_in_dense(struct commit *commit, struct commit **rev, int n)\n \tfor (i = 0; i < n; i++)\n \t\tif (rev[i] == commit)\n \t\t\treturn 0;\n-\tflag = commit->object.flags;\n+\tflag = get_commit_flags(commit);\n \tfor (i = count = 0; i < n; i++) {\n \t\tif (flag & (1u << (i + REV_SHIFT)))\n \t\t\tcount++;\n@@ -702,6 +710,7 @@ int cmd_show_branch(int ac,\n \tint ret;\n \n \tinit_commit_name_slab(&name_slab);\n+\tinit_commit_flags(&commit_flags);\n \n \tgit_config(git_show_branch_config, NULL);\n \n@@ -877,13 +886,13 @@ int cmd_show_branch(int ac,\n \t\t * and so on.  REV_SHIFT bits from bit 0 are used for\n \t\t * internal bookkeeping.\n \t\t */\n-\t\tcommit->object.flags |= flag;\n-\t\tif (commit->object.flags == flag)\n+\t\tset_commit_flags(commit, get_commit_flags(commit) | flag);\n+\t\tif (get_commit_flags(commit) == flag)\n \t\t\tcommit_list_insert_by_date(commit, &list);\n \t\trev[num_rev] = commit;\n \t}\n \tfor (i = 0; i < num_rev; i++)\n-\t\trev_mask[i] = rev[i]->object.flags;\n+\t\trev_mask[i] = get_commit_flags(rev[i]);\n \n \tif (0 <= extra)\n \t\tjoin_revs(&list, &seen, num_rev, extra);\n@@ -951,7 +960,7 @@ int cmd_show_branch(int ac,\n \n \tfor (struct commit_list *l = seen; l; l = l->next) {\n \t\tstruct commit *commit = l->item;\n-\t\tint this_flag = commit->object.flags;\n+\t\tint this_flag = get_commit_flags(commit);\n \t\tint is_merge_point = ((this_flag & all_revs) == all_revs);\n \n \t\tshown_merge_point |= is_merge_point;\n\nbase-commit: e2067b49ecaef9b7f51a17ce251f9207f72ef52d\n-- \n2.34.1\n\n"},{"id":"512630","messageId":"xmqqseobksfe.fsf@gitster.g","threadId":"62962","inReplyTo":"20250217055049.9217-1-meetsoni3017@gmail.com","subject":"Re: [GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-18T18:40:21Z","receivedAt":"2025-02-18T18:40:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Meet Soni <meetsoni3017@gmail.com> writes:\n\n> Replace direct accesses to commit->object.flags with the commit-slab\n> mechanism. Introduce `get_commit_flags()` and `set_commit_flags()` to\n> retrieve and update flags, respectively, and include `revision.h` so that\n> the canonical UNINTERESTING definition is used.\n>\n> Signed-off-by: Meet Soni <meetsoni3017@gmail.com>\n\nOhhhh.  I thought people somehow have \"refactored\" the commit\ntraversal code here to share more with the machinery used by the\n\"log\" family of commands, but the change in this patch being\ncontained within the single \"show-branch\" file indicates that it is\nnot the case, which is good ;-)\n\nAnd the MAX_REVS limitation has been with us from the very beginning\nof the \"show-branch\" command.  Lifting it is very good ;-) ;-).\n\n> ---\n> I'm not entirely sure what the TODO comment meant by storing a pointer to\n> the \"ref name\" directly, so I've assumed that the intent was to store\n> flags (of type int) directly in the commit-slab instead of commit->object.\n\nIt has been forever since I looked at the code around here the last\ntime, but I suspect that it meant the final mapping the code makes\nat the output phase from the bit position in the flags bits to which\nreference the bit (i.e. \"I am reachable from that ref\") could be\nomitted if we make the slab entry a set of (interned) refnames.\n\nBut I think using a slab whose element is still a bag of bits that\nis wider than object.flags word is is the most straight-forward way\nto lift MAX_REVS limitation.  If we can leave everything else\nunchanged, that would be great.\n\n> I've tested these changes using:\n>  - test suite -- they passed.\n>  - github ci result -- https://github.com/inosmeet/git/actions/runs/13355488433\n\nNew tests that traverse from more than historical MAX_REVS would be\nthe most interesting.\n\nIt is not exactly surprising if the existing tests do not exercise\nsuch a case (even though it probably should have been checking that\nthe command refused to accept more than MAX_REVS refs to prevent it\nfrom producing garbage results).\n\nIf there were such a test to illustrate what happens when too many\nrefs are given, we can demonstrate how the behaviour changes, for\nthe better, with this change ;-)\n\nHowever ...\n\n> +static int get_commit_flags(struct commit *commit)\n> +{\n> +\tint *result = commit_flags_peek(&commit_flags, commit);\n> +\treturn result ? *result : 0;\n> +}\n> +\n> +static void set_commit_flags(struct commit *commit, int flags)\n> +{\n> +\t*commit_flags_at(&commit_flags, commit) = flags;\n> +}\n\n... it does not make much sense to use the slab mechanism if we are\nstill limited to bitsizeof(type(flags)).  If your \"int\" is 32 bit,\nand the command line fed 100 revs, we'd want a flags parameter that\ncan house at least 100 bits passed into the \"set\" function, and\nyields the result that can hold at least 100 bits from the \"get\"\nfunction.  I'd expect that the interface would be more like\n\n    static int get_commit_flags(struct commit *commit, unsigned flags[]);\n    static int set_commit_flags(struct commit *commit, unsigned flags[]);\n\nwith a file-scope static variable signaling how many bits we are\ndealing with (allowing these functions to infer how many words\nflags[] array has), and the return values from these helpers to\nindicate success (with 0) and failure (with a negative value).  On a\n32-bit platform, you'd need at least 4 words in flags[] array to\ndeal with 100 revs.  On a 64-bit box, 2 words would be sufficient.\n\nI would imagine that we would need two more helpers\n\n    static int set_flag_bit(unsigned flags[], unsigned n);\n    static int get_flag_bit(unsigned flags[], unsigned n);\n\nto query the n-th bit in a set of bits stored in flags[] array.\n\nThanks.\n"},{"id":"512789","messageId":"20250221063257.GA568823@coredump.intra.peff.net","threadId":"62962","inReplyTo":"xmqqseobksfe.fsf@gitster.g","subject":"Re: [GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-02-21T06:32:57Z","receivedAt":"2025-02-21T06:39:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2025 at 10:40:21AM -0800, Junio C Hamano wrote:\n\n> > +static int get_commit_flags(struct commit *commit)\n> > +{\n> > +\tint *result = commit_flags_peek(&commit_flags, commit);\n> > +\treturn result ? *result : 0;\n> > +}\n> > +\n> > +static void set_commit_flags(struct commit *commit, int flags)\n> > +{\n> > +\t*commit_flags_at(&commit_flags, commit) = flags;\n> > +}\n> \n> ... it does not make much sense to use the slab mechanism if we are\n> still limited to bitsizeof(type(flags)).  If your \"int\" is 32 bit,\n> and the command line fed 100 revs, we'd want a flags parameter that\n> can house at least 100 bits passed into the \"set\" function, and\n> yields the result that can hold at least 100 bits from the \"get\"\n> function.  I'd expect that the interface would be more like\n> \n>     static int get_commit_flags(struct commit *commit, unsigned flags[]);\n>     static int set_commit_flags(struct commit *commit, unsigned flags[]);\n> \n> with a file-scope static variable signaling how many bits we are\n> dealing with (allowing these functions to infer how many words\n> flags[] array has), and the return values from these helpers to\n> indicate success (with 0) and failure (with a negative value).  On a\n> 32-bit platform, you'd need at least 4 words in flags[] array to\n> deal with 100 revs.  On a 64-bit box, 2 words would be sufficient.\n> \n> I would imagine that we would need two more helpers\n> \n>     static int set_flag_bit(unsigned flags[], unsigned n);\n>     static int get_flag_bit(unsigned flags[], unsigned n);\n> \n> to query the n-th bit in a set of bits stored in flags[] array.\n\nYeah. I did not see the word \"stride\" anywhere in your email, so I\nwanted to provide a further hint: the commit-slab \"_with_stride()\"\nvariant is meant to handle this kind of arbitrary-sized data. This was\npart of the original commit-slab implementation in a84b794ad0\n(commit-slab: introduce a macro to define a slab for new type,\n2013-04-13), but AFAIK we've never actually used it in practice. See\nthat commit for some examples.\n\n-Peff\n"},{"id":"512835","messageId":"xmqqy0xzb4o4.fsf@gitster.g","threadId":"62962","inReplyTo":"20250221063257.GA568823@coredump.intra.peff.net","subject":"Re: [GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-21T17:15:07Z","receivedAt":"2025-02-21T17:15:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Yeah. I did not see the word \"stride\" anywhere in your email, so I\n> wanted to provide a further hint: the commit-slab \"_with_stride()\"\n> variant is meant to handle this kind of arbitrary-sized data. This was\n> part of the original commit-slab implementation in a84b794ad0\n> (commit-slab: introduce a macro to define a slab for new type,\n> 2013-04-13), but AFAIK we've never actually used it in practice. See\n> that commit for some examples.\n\nWow, after reading the log message of that commit, I realize that we\nalready were considering that one-bit-per-ref needs dynamic scaling\nand folks must have been thinking hard about it (I do not think the\nauthor of the commit alone thought it---it must have been a group\neffort on the list, which the log message merely explains the motivation\nbehind the design).\n\nThanks for a pointer ;-)\n"},{"id":"512937","messageId":"20250225011757.GA752084@coredump.intra.peff.net","threadId":"62962","inReplyTo":"xmqqy0xzb4o4.fsf@gitster.g","subject":"Re: [GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-02-25T01:17:57Z","receivedAt":"2025-02-25T01:17:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 21, 2025 at 09:15:07AM -0800, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Yeah. I did not see the word \"stride\" anywhere in your email, so I\n> > wanted to provide a further hint: the commit-slab \"_with_stride()\"\n> > variant is meant to handle this kind of arbitrary-sized data. This was\n> > part of the original commit-slab implementation in a84b794ad0\n> > (commit-slab: introduce a macro to define a slab for new type,\n> > 2013-04-13), but AFAIK we've never actually used it in practice. See\n> > that commit for some examples.\n> \n> Wow, after reading the log message of that commit, I realize that we\n> already were considering that one-bit-per-ref needs dynamic scaling\n> and folks must have been thinking hard about it (I do not think the\n> author of the commit alone thought it---it must have been a group\n> effort on the list, which the log message merely explains the motivation\n> behind the design).\n> \n> Thanks for a pointer ;-)\n\nDefinitely one of the use cases we discussed early on was using it in\npaint_down_to_common(). This series:\n\n  https://lore.kernel.org/git/20140625233429.GA20457@sigill.intra.peff.net/\n\nbuilt a fast --contains traversal using the slab stride. I think I\nstalled because I hadn't convinced myself fully that it covered all\ncases. You left some very thoughtful comments, but I guess I just never\ngot back around to it.\n\nWe ended up taking the early parts (like converting quadratic list\naccess to a prio_queue) as a separate series. I don't know how valuable\nthe rest of it is; there has been a lot of work since then in this area\nby Stolee, et al. So it's unclear how much it would help now.\n\nBut the \"bitset\" API from:\n\n  https://lore.kernel.org/git/20140625234000.GD23146@sigill.intra.peff.net/\n\nwould probably be useful if somebody is trying to help show-branch. It\ngives you the arbitrary-sized thing you'd store in the slab.\n\n-Peff\n"},{"id":"513365","messageId":"D85SPKTTT47S.32GQ2NBP9J6I0@gmail.com","threadId":"62962","inReplyTo":"xmqqseobksfe.fsf@gitster.g","subject":"Re: [GSoC][RFC PATCH] show-branch: use commit-slab for flag storage","fromName":"Ghanshyam Thakkar","fromEmail":"shyamthakkar001@gmail.com","sentAt":"2025-03-02T12:56:52Z","receivedAt":"2025-03-02T12:56:58Z","isPatch":true,"sender":{"key":"shyamthakkar001@gmail.com","avatar":"https://avatars.githubusercontent.com/u/72698233?v=4"},"body":"On Wed Feb 19, 2025 at 12:10 AM IST, Junio C Hamano wrote:\n> Meet Soni <meetsoni3017@gmail.com> writes:\n>\n> > Replace direct accesses to commit->object.flags with the commit-slab\n> > mechanism. Introduce `get_commit_flags()` and `set_commit_flags()` to\n> > retrieve and update flags, respectively, and include `revision.h` so that\n> > the canonical UNINTERESTING definition is used.\n> >\n> > Signed-off-by: Meet Soni <meetsoni3017@gmail.com>\n>\n> Ohhhh.  I thought people somehow have \"refactored\" the commit\n> traversal code here to share more with the machinery used by the\n> \"log\" family of commands, but the change in this patch being\n> contained within the single \"show-branch\" file indicates that it is\n> not the case, which is good ;-)\n>\n> And the MAX_REVS limitation has been with us from the very beginning\n> of the \"show-branch\" command.  Lifting it is very good ;-) ;-).\n>\n> > ---\n> > I'm not entirely sure what the TODO comment meant by storing a pointer to\n> > the \"ref name\" directly, so I've assumed that the intent was to store\n> > flags (of type int) directly in the commit-slab instead of commit->object.\n>\n> It has been forever since I looked at the code around here the last\n> time, but I suspect that it meant the final mapping the code makes\n> at the output phase from the bit position in the flags bits to which\n> reference the bit (i.e. \"I am reachable from that ref\") could be\n> omitted if we make the slab entry a set of (interned) refnames.\n>\n> But I think using a slab whose element is still a bag of bits that\n> is wider than object.flags word is is the most straight-forward way\n> to lift MAX_REVS limitation.  If we can leave everything else\n> unchanged, that would be great.\n\nAgreed. Looking at the code, there seems to be two prequisites for\nremoving MAX_REVS limitation:\n\n- Removing dependency on MAX_REVS for allocating arrays (ref_names,\n  revs, etc.)\n  (can convert these to heap allocation)\n\n- Removing dependency on MAX_REVS for storing flags (which can be\n  achieved by using the slab mechanism and using some kind of bitset\n  API or we can use 'bitmap' from ewok.h)\n\nThanks.\n"}]}