{"thread":{"id":"56884","subject":"[PATCH] name-rev: prefer shorter names over following merges","startedAt":"2021-11-13T00:14:19Z","lastAt":"2021-12-08T11:38:42Z","messageCount":7,"participants":["Elijah Newren via GitGitGadget","Ævar Arnfjörð Bjarmason","Elijah Newren","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"441040","messageId":"pull.1119.git.git.1636762454792.gitgitgadget@gmail.com","threadId":"56884","inReplyTo":null,"subject":"[PATCH] name-rev: prefer shorter names over following merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-11-13T00:14:14Z","receivedAt":"2021-11-13T00:14:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nname-rev has a MERGE_TRAVERSAL_WEIGHT to say that traversing a second or\nlater parent of a merge should be 65535 times more expensive than a\nfirst-parent traversal, as per ac076c29ae8d (name-rev: Fix non-shortest\ndescription, 2007-08-27). The point of this weight is to prefer names\nlike\n\n v2.32.0~1471^2\n\nover names like\n\n v2.32.0~43^2~15^2~11^2~20^2~31^2\n\nwhich are two equally valid names in git.git for the same commit. Note\nthat the first follows 1472 parent traversals compared to a mere 125 for\nthe second. Weighting all traversals equally would clearly prefer the\nsecond name since it has fewer parent traversals, but humans aren't\ngoing to be traversing commits and they tend to have an easier time\ndigesting names with fewer segments. The fact that the former only has\ntwo segments (~1471, ^2) makes it much simpler than the latter which has\nsix segments (~43, ^2, ~15, etc.). Since name-rev is meant to \"find\nsymbolic names suitable for human digestion\", we prefer fewer segments.\n\nHowever, the particular rule implemented in name-rev would actually\nprefer\n\n v2.33.0-rc0~11^2~1\n\nover\n\n v2.33.0-rc0~20^2\n\nbecause both have precisely one second parent traversal, and it gives\nthe tie breaker to shortest number of total parent traversals. Fewer\nsegments is more important for human consumption than number of hops, so\nwe'd rather see the latter which has one fewer segment.\n\nInclude the generation in is_better_name() and use a new\neffective_distance() calculation so that we prefer fewer segments in\nthe printed name over fewer total parent traversals performed to get the\nanswer.\n\nSigned-off-by: Elijah Newren \n---\n name-rev: prefer shorter names over following merges\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1119%2Fnewren%2Fprefer-shorter-names-in-name-rev-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1119/newren/prefer-shorter-names-in-name-rev-v1\nPull-Request: https://github.com/git/git/pull/1119\n\n builtin/name-rev.c | 17 +++++++++++++----\n 1 file changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex b221d300147..27f60153a6c 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -44,11 +44,20 @@ static struct rev_name *get_commit_rev_name(const struct commit *commit)\n \treturn is_valid_rev_name(name) ? name : NULL;\n }\n \n+static int effective_distance(int distance, int generation)\n+{\n+\treturn distance + (generation > 0 ? MERGE_TRAVERSAL_WEIGHT : 0);\n+}\n+\n static int is_better_name(struct rev_name *name,\n \t\t\t timestamp_t taggerdate,\n+\t\t\t int generation,\n \t\t\t int distance,\n \t\t\t int from_tag)\n {\n+\tint name_distance = effective_distance(name->distance, name->generation);\n+\tint new_distance = effective_distance(distance, generation);\n+\n \t/*\n \t * When comparing names based on tags, prefer names\n \t * based on the older tag, even if it is farther away.\n@@ -56,7 +65,7 @@ static int is_better_name(struct rev_name *name,\n \tif (from_tag && name->from_tag)\n \t\treturn (name->taggerdate > taggerdate ||\n \t\t\t(name->taggerdate == taggerdate &&\n-\t\t\t name->distance > distance));\n+\t\t\t name_distance > new_distance));\n \n \t/*\n \t * We know that at least one of them is a non-tag at this point.\n@@ -69,8 +78,8 @@ static int is_better_name(struct rev_name *name,\n \t * We are now looking at two non-tags. Tiebreak to favor\n \t * shorter hops.\n \t */\n-\tif (name->distance != distance)\n-\t\treturn name->distance > distance;\n+\tif (name_distance != new_distance)\n+\t\treturn name_distance > new_distance;\n \n \t/* ... or tiebreak to favor older date */\n \tif (name->taggerdate != taggerdate)\n@@ -88,7 +97,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,\n \tstruct rev_name *name = commit_rev_name_at(&rev_names, commit);\n \n \tif (is_valid_rev_name(name)) {\n-\t\tif (!is_better_name(name, taggerdate, distance, from_tag))\n+\t\tif (!is_better_name(name, taggerdate, generation, distance, from_tag))\n \t\t\treturn NULL;\n \n \t\t/*\n\nbase-commit: 9d530dc0024503ab4218fe6c4395b8a0aa245478\n-- \ngitgitgadget\n"},{"id":"441062","messageId":"211113.86pmr4tm7p.gmgdl@evledraar.gmail.com","threadId":"56884","inReplyTo":"pull.1119.git.git.1636762454792.gitgitgadget@gmail.com","subject":"Re: [PATCH] name-rev: prefer shorter names over following merges","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-11-13T09:42:46Z","receivedAt":"2021-11-13T09:54:23Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, Nov 13 2021, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n>\n> name-rev has a MERGE_TRAVERSAL_WEIGHT to say that traversing a second or\n> later parent of a merge should be 65535 times more expensive than a\n> first-parent traversal, as per ac076c29ae8d (name-rev: Fix non-shortest\n> description, 2007-08-27). The point of this weight is to prefer names\n> like\n>\n> v2.32.0~1471^2\n>\n> over names like\n>\n> v2.32.0~43^2~15^2~11^2~20^2~31^2\n>\n> which are two equally valid names in git.git for the same commit. Note\n> that the first follows 1472 parent traversals compared to a mere 125 for\n> the second. Weighting all traversals equally would clearly prefer the\n> second name since it has fewer parent traversals, but humans aren't\n> going to be traversing commits and they tend to have an easier time\n> digesting names with fewer segments. The fact that the former only has\n> two segments (~1471, ^2) makes it much simpler than the latter which has\n> six segments (~43, ^2, ~15, etc.). Since name-rev is meant to \"find\n> symbolic names suitable for human digestion\", we prefer fewer segments.\n>\n> However, the particular rule implemented in name-rev would actually\n> prefer\n>\n> v2.33.0-rc0~11^2~1\n>\n> over\n>\n> v2.33.0-rc0~20^2\n>\n> because both have precisely one second parent traversal, and it gives\n> the tie breaker to shortest number of total parent traversals. Fewer\n> segments is more important for human consumption than number of hops, so\n> we'd rather see the latter which has one fewer segment.\n>\n> Include the generation in is_better_name() and use a new\n> effective_distance() calculation so that we prefer fewer segments in\n> the printed name over fewer total parent traversals performed to get the\n> answer.\n\nSo it's the case that if you were to print out the output of \"git log\n--graph --oneline\" for these ranges and draw the path we'd take for\neither variant of these examples we'd take different path, i.e. the\nfirst version takes the ^1 parent every time, and the second traverses\nvarious ^2 parents.\n\nI think this change looks good in the context of name-rev, but I wonder\nif longer names wouldn't be easier to understand in some cases,\ni.e. you'd more clearly get an idea of how this change was tangled up\nwith other topics.\n\nDoes one or the other of these versions provide a better hint for the\n\"this branch is used by\" relationships in What's Cooking?\n"},{"id":"441072","messageId":"CABPp-BEeUM+3NLKDVdak90_UUeNghYCx=Dgir6=8ixvYmvyq3Q@mail.gmail.com","threadId":"56884","inReplyTo":"211113.86pmr4tm7p.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH] name-rev: prefer shorter names over following merges","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-11-13T19:35:53Z","receivedAt":"2021-11-13T19:36:08Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Ævar,\n\nOn Sat, Nov 13, 2021 at 1:54 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Sat, Nov 13 2021, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n> > name-rev has a MERGE_TRAVERSAL_WEIGHT to say that traversing a second or\n> > later parent of a merge should be 65535 times more expensive than a\n> > first-parent traversal, as per ac076c29ae8d (name-rev: Fix non-shortest\n> > description, 2007-08-27). The point of this weight is to prefer names\n> > like\n> >\n> > v2.32.0~1471^2\n> >\n> > over names like\n> >\n> > v2.32.0~43^2~15^2~11^2~20^2~31^2\n> >\n> > which are two equally valid names in git.git for the same commit. Note\n> > that the first follows 1472 parent traversals compared to a mere 125 for\n> > the second. Weighting all traversals equally would clearly prefer the\n> > second name since it has fewer parent traversals, but humans aren't\n> > going to be traversing commits and they tend to have an easier time\n> > digesting names with fewer segments. The fact that the former only has\n> > two segments (~1471, ^2) makes it much simpler than the latter which has\n> > six segments (~43, ^2, ~15, etc.). Since name-rev is meant to \"find\n> > symbolic names suitable for human digestion\", we prefer fewer segments.\n> >\n> > However, the particular rule implemented in name-rev would actually\n> > prefer\n> >\n> > v2.33.0-rc0~11^2~1\n> >\n> > over\n> >\n> > v2.33.0-rc0~20^2\n> >\n> > because both have precisely one second parent traversal, and it gives\n> > the tie breaker to shortest number of total parent traversals. Fewer\n> > segments is more important for human consumption than number of hops, so\n> > we'd rather see the latter which has one fewer segment.\n\nSince you bring up semantic meaning of the names with more second\nparents (which I'll address below), let me add an aside here on\nsemantic meaning of the names that prefer first-parent traversals:\n\nIn addition to shorter names just being easier for humans to consume,\nfor many repositories the first-parent-traversal-preferred names also\nanswer the question: \"How or when did this commit get merged?\"\n\nFor example, let's look at commit cbdca289fb -- the second to last\ncommit of en/ort-perf-batch-11.\n\nPrior to my changes:\n\n* `git name-rev cbdca289fb` used to report tags/v2.33.0-rc0~57^2~5\n* v2.33.0-rc0~57^2 is en/ort-perf-batch-12\n* v2.33.0-rc0~57 is \"Merge branch 'en/ort-perf-batch-12'\"\n* None of this tells us when cbdca289fb was merged into master.\n\nAfter my changes:\n\n* `git name-rev cbdca289fb` reports tags/v2.33.0-rc0~112^2~1 [*]\n* v2.33.0-rc0~112^2 is the tip of en/ort-perf-batch-11\n* v2.33.0-rc0~112 is \"Merge branch 'en/ort-perf-batch-11'\"\n* The commit above identifies exactly when cbdca289fb was merged into master.\n\nGranted, this semantic meaning isn't guaranteed since it is possible\nfor multiple folks to merge each other's work. So I didn't mention\nthis auxiliary advantage in my commit message, instead just focusing\non the primary advantage of \"easier for human consumption\". However,\nfor many common repositories (I can only think of a couple\ncounter-examples out of the hundreds of repositories I have worked\nwith), the shorter names do have this extra semantic meaning.\n\n\n[*] If you're curious why my changes provide this alternate name\ndespite having the same number of segments as the old name: (a)\ncbdca289fb is the parent of 25e65b6dd5 -- thus the name for cbdca289fb\nis the first parent of the preferred name for 25e65b6dd5, (b)\n25e65b6dd5 could be named either v2.33.0-rc0~112^2 or\nv2.33.0-rc0~57^2~4, but the former is preferred over the latter due to\nfewer segments, (c) combine the two previous facts, and we get the\nname \"v2.33.0-rc0~112^2~1\" rather than \"v2.33.0-rc0~57^2~5\".\n\n> >\n> > Include the generation in is_better_name() and use a new\n> > effective_distance() calculation so that we prefer fewer segments in\n> > the printed name over fewer total parent traversals performed to get the\n> > answer.\n>\n> So it's the case that if you were to print out the output of \"git log\n> --graph --oneline\" for these ranges and draw the path we'd take for\n> either variant of these examples we'd take different path, i.e. the\n> first version takes the ^1 parent every time, and the second traverses\n> various ^2 parents.\n\nNot quite, no. The shorter names do not exclude second parent\ntraversals (both of the shorter names had one second parent traversal\nat the end, because the commits in question are unreachable solely by\nfirst parent traversals). But I think your intended point was that\nthe shorter names _prefer_ first parent traversals when possible.\nThat is certainly true.\n\n> I think this change looks good in the context of name-rev\n\nAwesome, thanks for reviewing. :-)\n\n>, but I wonder\n> if longer names wouldn't be easier to understand in some cases,\n> i.e. you'd more clearly get an idea of how this change was tangled up\n> with other topics.\n\nInteresting thought, but no. You'd have to perform a much different\nkind of search to find that info.\n\nI think these longer names following more second parents only give you\na quasi-random selection of topics and what commit was \"recently\nstable as a base\" at the time they were applied. We can see this by\nusing the example from the commit message; the name\n\"v2.32.0~43^2~15^2~11^2~20^2~31^2\" gives us five chances to look for\ntangling or dependencies. Let's see how many of them show some:\n\n== 1st example ==\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2~11^2~20^2~31^2\n062a309d36,René Scharfe,remote-curl: use argv_array in parse_push()\n\nNow let's trim off the \"~31^2\" portion of the above and we see:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2~11^2~20^2\n63020f175f,Derrick Stolee,commit-graph: prefer default size_mult when given zero\n\nWas Stolee's patch based on Rene's? No, just following its first parent we see:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2~11^2~20^2~1\n53a06cf39b,Johannes Schindelin,Git 2.24.1\n\n\n== 2nd example ==\n\nTrimming off the trailing \"~20^2\" portion from the name for Stolee's\ncommit, we see:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2~11^2\n70e24186c0,Elijah Newren,t6022, t6046: fix flaky files-are-updated checks\n\nThat was not tangled or dependent upon Stolee's commit, rather it was a\n6-patch series that just happened to be rooted at:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2~11^2~6\nd0654dc308,Junio C Hamano,Git 2.25\n\n\n== 3rd example ==\n\nTrimming off the trailing \"~11^2\" portion from the name for my commit, we see:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2\n173cb08d5b,Carlo Marcelo Arenas Belón,bisect: avoid tailing CR\ncharacters from revision in replay\n\nBut that commit wasn't tangled with or dependent on mine. It was a\n2-patch series based on:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~15^2~2\naf6b65d45e,Jonathan Nieder,Git 2.26.2\n\n\n== 4th example ==\n\nTrimming off the trailing \"~15^2\" portion from the name for Carlo's\ncommit, we see:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2\n3a7f0908b6,Matheus Tavares,clean: remove unnecessary variable\n\nThat series didn't depend on Carlo's commit; it was a single\nstandalone patch that depended on\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~43^2~1\n6ff7f46039,Johannes Schindelin,Git 2.27.1\n\n\n== 5th example ==\n\nTrimming off the trailing \"~43^2\" portion from the name for Matheus's\ncommit, we see:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0\nebf3c04b26,Junio C Hamano,Git 2.32\n\nPretty obvious. Should be clear this didn't depend on Matheus's\ncommit; in fact, it was just a commit on top of:\n\n$ git log -1 --format='%h,%an,%s' v2.32.0~1\n15664a5f35,Junio C Hamano,Merge tag 'l10n-2.32.0-rnd1.1' of\ngit://github.com/git-l10n/git-po\n\n\nSo 0 of the 5 showed any kind of tangling or dependencies. This\ncommit dates back nearly to the 2.24.1 era and we've had lots of\ntopics that depended on other topics in the meantime, but it clearly\nmissed all of them. I see it as five random topics between v2.32.0\nand v2.24.1. The odds of those hitting a tangled topic are slim since\nmost of our topics are standalone; but even if it does hit one, it's\nalmost certainly going to miss all the other dependent topics between\nthe commit and relevant tag used as the basis of the name.\n\n> Does one or the other of these versions provide a better hint for the\n> \"this branch is used by\" relationships in What's Cooking?\n\nIt can, but it's rather unlikely to be very helpful. Most of the time\nit won't provide any hint, and even if it does provide an interesting\nname that suggests there might be a relationship, you'd have to double\ncheck it to make sure it's not a false positive (as per the five\nexamples above). But, let's put it to the test. I had to do two\nthings to try this out:\n\n* name-rev normally fails on topics in \"What's Cooking\" becasue none\nof them are tagged yet, but we can force the issue by telling name-rev\nto use \"seen\" for naming things.\n* I modified builtin/name-rev.c to change the MERGE_TRAVERSAL_WEIGHT\nfrom 65535 to 1 (so that shortest distance is preferred rather than\nfewest name segments, causing it to be much more likely to follow\nsecond parents).\n\nWith those changes, let's look at all three examples from the most\nrecent \"What's cooking\":\n\n1. ld/sparse-diff-blame uses vd/sparse-reset\n\n$ git name-rev --refs=refs/remotes/origin/seen gitster/ld/sparse-diff-blame\ngitster/ld/sparse-diff-blame remotes/origin/seen~6^2\n$ git name-rev --refs=refs/remotes/origin/seen gitster/vd/sparse-reset\ngitster/vd/sparse-reset remotes/origin/seen~7^2\n\nDoesn't hint at the relationship at all.\n\n2. ns/batched-fsync uses ns/tmp-objdir\n\n$ git name-rev --refs=refs/remotes/origin/seen gitster/ns/batched-fsync\ngitster/ns/batched-fsync remotes/origin/seen~50^2\n$ git name-rev --refs=refs/remotes/origin/seen gitster/ns/tmp-objdir\ngitster/ns/tmp-objdir remotes/origin/seen~8^2~7^2\n\nDoesn't hint at the relationship between the two at all.\n\n3. ns/remerge-diff uses ns/tmp-objdir\n\n$ git name-rev --refs=refs/remotes/origin/seen gitster/ns/remerge-diff\ngitster/ns/remerge-diff remotes/origin/seen~8^2\n$ git name-rev --refs=refs/remotes/origin/seen gitster/ns/tmp-objdir\ngitster/ns/tmp-objdir remotes/origin/seen~8^2~7^2\n\nAhah, there we actually see what might be a relationship. As noted\nabove, though, one would have to first check whether ns/remerge-diff\nwas actually a 7 patch series (turns out that it is) in order to\nverify that one is based directly on the other; otherwise it's just a\nfalse positive like the five we looked at above.\n\n\nI also repeated this with the Sept. 20 \"What's cooking email\". In\nthat case, only 1 out of 6 of the generated names hinted at a\nrelationship. That's few enough to not be useful, especially when\nthere's also risk of false positives that would need to be double\nchecked by a different means anyway. So, in short, the longer names\nthat follow second parents generally don't seem to provide any useful\nsemantic meaning I can think of beyond \"what's the fewest parent\ntraversals I can use from my base tag to get to the commit in\nquestion\". If you can think of one, perhaps it would be useful to add\na flag to request the alternate name. I just can't think of any.\n"},{"id":"441319","messageId":"nycvar.QRO.7.76.6.2111161227090.21127@tvgsbejvaqbjf.bet","threadId":"56884","inReplyTo":"pull.1119.git.git.1636762454792.gitgitgadget@gmail.com","subject":"Re: [PATCH] name-rev: prefer shorter names over following merges","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-16T12:13:03Z","receivedAt":"2021-11-16T12:13:29Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Elijah,\n\nOn Sat, 13 Nov 2021, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n>\n> name-rev has a MERGE_TRAVERSAL_WEIGHT to say that traversing a second or\n> later parent of a merge should be 65535 times more expensive than a\n> first-parent traversal, as per ac076c29ae8d (name-rev: Fix non-shortest\n> description, 2007-08-27). The point of this weight is to prefer names\n> like\n>\n> v2.32.0~1471^2\n>\n> over names like\n>\n> v2.32.0~43^2~15^2~11^2~20^2~31^2\n>\n> which are two equally valid names in git.git for the same commit. Note\n> that the first follows 1472 parent traversals compared to a mere 125 for\n> the second. Weighting all traversals equally would clearly prefer the\n> second name since it has fewer parent traversals, but humans aren't\n> going to be traversing commits and they tend to have an easier time\n> digesting names with fewer segments. The fact that the former only has\n> two segments (~1471, ^2) makes it much simpler than the latter which has\n> six segments (~43, ^2, ~15, etc.). Since name-rev is meant to \"find\n> symbolic names suitable for human digestion\", we prefer fewer segments.\n>\n> However, the particular rule implemented in name-rev would actually\n> prefer\n>\n> v2.33.0-rc0~11^2~1\n>\n> over\n>\n> v2.33.0-rc0~20^2\n>\n> because both have precisely one second parent traversal, and it gives\n> the tie breaker to shortest number of total parent traversals. Fewer\n> segments is more important for human consumption than number of hops, so\n> we'd rather see the latter which has one fewer segment.\n>\n> Include the generation in is_better_name() and use a new\n> effective_distance() calculation so that we prefer fewer segments in\n> the printed name over fewer total parent traversals performed to get the\n> answer.\n\nThank you. As you most likely figured out, that magic weight was\nintroduced by me, in ac076c29ae8 (name-rev: Fix non-shortest description,\n2007-08-27). And indeed the motivation was to keep the name as short as\npossible.\n\nTechnically, your solution does not fix the problem fully, as we still do\nnot determine the _shortest possible_ name. Having said that, I think your\npatch improves the situation dramatically, so: ACK!\n\nThanks,\nDscho\n\n>\n> Signed-off-by: Elijah Newren \n> ---\n> name-rev: prefer shorter names over following merges\n>\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1119%2Fnewren%2Fprefer-shorter-names-in-name-rev-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1119/newren/prefer-shorter-names-in-name-rev-v1\n> Pull-Request: https://github.com/git/git/pull/1119\n>\n> builtin/name-rev.c | 17 +++++++++++++----\n> 1 file changed, 13 insertions(+), 4 deletions(-)\n>\n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index b221d300147..27f60153a6c 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -44,11 +44,20 @@ static struct rev_name *get_commit_rev_name(const struct commit *commit)\n> \treturn is_valid_rev_name(name) ? name : NULL;\n> }\n>\n> +static int effective_distance(int distance, int generation)\n> +{\n> +\treturn distance + (generation > 0 ? MERGE_TRAVERSAL_WEIGHT : 0);\n> +}\n> +\n> static int is_better_name(struct rev_name *name,\n> \t\t\t timestamp_t taggerdate,\n> +\t\t\t int generation,\n> \t\t\t int distance,\n> \t\t\t int from_tag)\n> {\n> +\tint name_distance = effective_distance(name->distance, name->generation);\n> +\tint new_distance = effective_distance(distance, generation);\n> +\n> \t/*\n> \t * When comparing names based on tags, prefer names\n> \t * based on the older tag, even if it is farther away.\n> @@ -56,7 +65,7 @@ static int is_better_name(struct rev_name *name,\n> \tif (from_tag && name->from_tag)\n> \t\treturn (name->taggerdate > taggerdate ||\n> \t\t\t(name->taggerdate == taggerdate &&\n> -\t\t\t name->distance > distance));\n> +\t\t\t name_distance > new_distance));\n>\n> \t/*\n> \t * We know that at least one of them is a non-tag at this point.\n> @@ -69,8 +78,8 @@ static int is_better_name(struct rev_name *name,\n> \t * We are now looking at two non-tags. Tiebreak to favor\n> \t * shorter hops.\n> \t */\n> -\tif (name->distance != distance)\n> -\t\treturn name->distance > distance;\n> +\tif (name_distance != new_distance)\n> +\t\treturn name_distance > new_distance;\n>\n> \t/* ... or tiebreak to favor older date */\n> \tif (name->taggerdate != taggerdate)\n> @@ -88,7 +97,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,\n> \tstruct rev_name *name = commit_rev_name_at(&rev_names, commit);\n>\n> \tif (is_valid_rev_name(name)) {\n> -\t\tif (!is_better_name(name, taggerdate, distance, from_tag))\n> +\t\tif (!is_better_name(name, taggerdate, generation, distance, from_tag))\n> \t\t\treturn NULL;\n>\n> \t\t/*\n>\n> base-commit: 9d530dc0024503ab4218fe6c4395b8a0aa245478\n> --\n> gitgitgadget\n>\n"},{"id":"441416","messageId":"xmqq35nv416j.fsf@gitster.g","threadId":"56884","inReplyTo":"nycvar.QRO.7.76.6.2111161227090.21127@tvgsbejvaqbjf.bet","subject":"Re: [PATCH] name-rev: prefer shorter names over following merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-11-17T08:49:08Z","receivedAt":"2021-11-17T08:49:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Thank you. As you most likely figured out, that magic weight was\n> introduced by me, in ac076c29ae8 (name-rev: Fix non-shortest description,\n> 2007-08-27). And indeed the motivation was to keep the name as short as\n> possible.\n>\n> Technically, your solution does not fix the problem fully, as we still do\n> not determine the _shortest possible_ name. Having said that, I think your\n> patch improves the situation dramatically, so: ACK!\n\nIt really depends on how you define \"short\". Is v1.0~11 and v1.0~99\nthe same length and v1.0~100 a bit longer than these two?\n\nI wonder what happens if we counted what the proposed commit log\ncalls \"segments\" and nothing else, e.g.\n\n v2.32.0~1471^2\t\t\thas 2 segments (\"~1471\", \"^2\")\n v2.32.0~43^2~15^2~11^2~20^2~31^2 has 10 segments\n\nand use number of hops only for breaking ties, instead of giving a\nmagic weight and trying to count both hops and segments.\n\nIn any case, this seems to give us a much better results than the\ncurrent code, so let's take it and leave further futzing outside the\nscope.\n\nThanks.\n"},{"id":"443063","messageId":"pull.1119.v2.git.git.1638596152340.gitgitgadget@gmail.com","threadId":"56884","inReplyTo":"pull.1119.git.git.1636762454792.gitgitgadget@gmail.com","subject":"[PATCH v2] name-rev: prefer shorter names over following merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-12-04T05:35:52Z","receivedAt":"2021-12-04T05:35:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nname-rev has a MERGE_TRAVERSAL_WEIGHT to say that traversing a second or\nlater parent of a merge should be 65535 times more expensive than a\nfirst-parent traversal, as per ac076c29ae8d (name-rev: Fix non-shortest\ndescription, 2007-08-27). The point of this weight is to prefer names\nlike\n\n v2.32.0~1471^2\n\nover names like\n\n v2.32.0~43^2~15^2~11^2~20^2~31^2\n\nwhich are two equally valid names in git.git for the same commit. Note\nthat the first follows 1472 parent traversals compared to a mere 125 for\nthe second. Weighting all traversals equally would clearly prefer the\nsecond name since it has fewer parent traversals, but humans aren't\ngoing to be traversing commits and they tend to have an easier time\ndigesting names with fewer segments. The fact that the former only has\ntwo segments (~1471, ^2) makes it much simpler than the latter which has\nsix segments (~43, ^2, ~15, etc.). Since name-rev is meant to \"find\nsymbolic names suitable for human digestion\", we prefer fewer segments.\n\nHowever, the particular rule implemented in name-rev would actually\nprefer\n\n v2.33.0-rc0~11^2~1\n\nover\n\n v2.33.0-rc0~20^2\n\nbecause both have precisely one second parent traversal, and it gives\nthe tie breaker to shortest number of total parent traversals. Fewer\nsegments is more important for human consumption than number of hops, so\nwe'd rather see the latter which has one fewer segment.\n\nInclude the generation in is_better_name() and use a new\neffective_distance() calculation so that we prefer fewer segments in\nthe printed name over fewer total parent traversals performed to get the\nanswer.\n\n== Side-note on tie-breakers ==\n\nWhen there are the same number of segments for two different names, we\nactually use the name of an ancestor commit as a tie-breaker as well.\nFor example, for the commit cbdca289fb in the git.git repository, we\nprefer the name v2.33.0-rc0~112^2~1 over v2.33.0-rc0~57^2~5. This is\nbecause:\n\n * cbdca289fb is the parent of 25e65b6dd5, which implies the name for\n cbdca289fb should be the first parent of the preferred name for\n 25e65b6dd5\n * 25e65b6dd5 could be named either v2.33.0-rc0~112^2 or\n v2.33.0-rc0~57^2~4, but the former is preferred over the latter due\n to fewer segments\n * combine the two previous facts, and the name we get for cbdca289fb\n is \"v2.33.0-rc0~112^2~1\" rather than \"v2.33.0-rc0~57^2~5\".\n\nTechnically, we get this for free out of the implementation since we\nonly keep track of one name for each commit as we walk history (and\nre-add parents to the queue if we find a better name for those parents),\nbut the first bullet point above ensures users get results that feel\nmore consistent.\n\n== Alternative Ideas and Meanings Discussed ==\n\nOne suggestion that came up during review was that shortest\nstring-length might be easiest for users to consume. However, such a\nscheme would be rather computationally expensive (we'd have to track all\nnames for each commit as we traversed the graph) and would additionally\ncome with the possibly perplexing result that on a linear segment of\nhistory we could rapidly swap back and forth on names:\n MYTAG~3^2 would be preferred over MYTAG~9998\n MYTAG~3^2~1 would NOT be preferred over MYTAG~9999\n MYTAG~3^2~2 might be preferred over MYTAG~10000\n\nAnother item that came up was possible auxiliary semantic meanings for\nname-rev results either before or after this patch. The basic answer\nwas that the previous implementation had no known useful auxiliary\nsemantics, but that for many repositories (most in my experience), the\nnew scheme does. In particular, the new name-rev output can often be\nused to answer the question, \"How or when did this commit get merged?\"\nSince that usefulness depends on how merges happen within the repository\nand thus isn't universally applicable, details are omitted here but you\ncan see them at [1].\n\n[1] https://lore.kernel.org/git/CABPp-BEeUM+3NLKDVdak90_UUeNghYCx=Dgir6=8ixvYmvyq3Q@mail.gmail.com/\n\nFinally, it was noted that the algorithm could be improved by just\nexplicitly tracking the number of segments and using both it and\ndistance in the comparison, instead of giving a magic number that tries\nto blend the two (and which therefore might give suboptimal results in\nrepositories with really huge numbers of commits that periodically merge\nolder code). However, \"[this patch] seems to give us a much better\nresults than the current code, so let's take it and leave further\nfutzing outside the scope.\"\n\nSigned-off-by: Elijah Newren \nAcked-by: Ævar Arnfjörð Bjarmason \nAcked-by: Johannes Schindelin \n---\n name-rev: prefer shorter names over following merges\n \n Changes since v1:\n \n * Include acks from Ævar and Dscho\n * To aid future readers, added a few comments to the commit message\n from the mailing list discussion about tie-breakers and other\n possible improvements\n * The 2.35 cycle has started and it's been weeks since I sent v1, so\n it's time to resend. :-)\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1119%2Fnewren%2Fprefer-shorter-names-in-name-rev-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1119/newren/prefer-shorter-names-in-name-rev-v2\nPull-Request: https://github.com/git/git/pull/1119\n\nRange-diff vs v1:\n\n 1: 50812ed6fdf ! 1: 5d068486f9f name-rev: prefer shorter names over following merges\n @@ Commit message\n the printed name over fewer total parent traversals performed to get the\n answer.\n \n + == Side-note on tie-breakers ==\n +\n + When there are the same number of segments for two different names, we\n + actually use the name of an ancestor commit as a tie-breaker as well.\n + For example, for the commit cbdca289fb in the git.git repository, we\n + prefer the name v2.33.0-rc0~112^2~1 over v2.33.0-rc0~57^2~5. This is\n + because:\n +\n + * cbdca289fb is the parent of 25e65b6dd5, which implies the name for\n + cbdca289fb should be the first parent of the preferred name for\n + 25e65b6dd5\n + * 25e65b6dd5 could be named either v2.33.0-rc0~112^2 or\n + v2.33.0-rc0~57^2~4, but the former is preferred over the latter due\n + to fewer segments\n + * combine the two previous facts, and the name we get for cbdca289fb\n + is \"v2.33.0-rc0~112^2~1\" rather than \"v2.33.0-rc0~57^2~5\".\n +\n + Technically, we get this for free out of the implementation since we\n + only keep track of one name for each commit as we walk history (and\n + re-add parents to the queue if we find a better name for those parents),\n + but the first bullet point above ensures users get results that feel\n + more consistent.\n +\n + == Alternative Ideas and Meanings Discussed ==\n +\n + One suggestion that came up during review was that shortest\n + string-length might be easiest for users to consume. However, such a\n + scheme would be rather computationally expensive (we'd have to track all\n + names for each commit as we traversed the graph) and would additionally\n + come with the possibly perplexing result that on a linear segment of\n + history we could rapidly swap back and forth on names:\n + MYTAG~3^2 would be preferred over MYTAG~9998\n + MYTAG~3^2~1 would NOT be preferred over MYTAG~9999\n + MYTAG~3^2~2 might be preferred over MYTAG~10000\n +\n + Another item that came up was possible auxiliary semantic meanings for\n + name-rev results either before or after this patch. The basic answer\n + was that the previous implementation had no known useful auxiliary\n + semantics, but that for many repositories (most in my experience), the\n + new scheme does. In particular, the new name-rev output can often be\n + used to answer the question, \"How or when did this commit get merged?\"\n + Since that usefulness depends on how merges happen within the repository\n + and thus isn't universally applicable, details are omitted here but you\n + can see them at [1].\n +\n + [1] https://lore.kernel.org/git/CABPp-BEeUM+3NLKDVdak90_UUeNghYCx=Dgir6=8ixvYmvyq3Q@mail.gmail.com/\n +\n + Finally, it was noted that the algorithm could be improved by just\n + explicitly tracking the number of segments and using both it and\n + distance in the comparison, instead of giving a magic number that tries\n + to blend the two (and which therefore might give suboptimal results in\n + repositories with really huge numbers of commits that periodically merge\n + older code). However, \"[this patch] seems to give us a much better\n + results than the current code, so let's take it and leave further\n + futzing outside the scope.\"\n +\n Signed-off-by: Elijah Newren \n + Acked-by: Ævar Arnfjörð Bjarmason \n + Acked-by: Johannes Schindelin \n \n ## builtin/name-rev.c ##\n @@ builtin/name-rev.c: static struct rev_name *get_commit_rev_name(const struct commit *commit)\n\n\n builtin/name-rev.c | 17 +++++++++++++----\n 1 file changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex b221d300147..27f60153a6c 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -44,11 +44,20 @@ static struct rev_name *get_commit_rev_name(const struct commit *commit)\n \treturn is_valid_rev_name(name) ? name : NULL;\n }\n \n+static int effective_distance(int distance, int generation)\n+{\n+\treturn distance + (generation > 0 ? MERGE_TRAVERSAL_WEIGHT : 0);\n+}\n+\n static int is_better_name(struct rev_name *name,\n \t\t\t timestamp_t taggerdate,\n+\t\t\t int generation,\n \t\t\t int distance,\n \t\t\t int from_tag)\n {\n+\tint name_distance = effective_distance(name->distance, name->generation);\n+\tint new_distance = effective_distance(distance, generation);\n+\n \t/*\n \t * When comparing names based on tags, prefer names\n \t * based on the older tag, even if it is farther away.\n@@ -56,7 +65,7 @@ static int is_better_name(struct rev_name *name,\n \tif (from_tag && name->from_tag)\n \t\treturn (name->taggerdate > taggerdate ||\n \t\t\t(name->taggerdate == taggerdate &&\n-\t\t\t name->distance > distance));\n+\t\t\t name_distance > new_distance));\n \n \t/*\n \t * We know that at least one of them is a non-tag at this point.\n@@ -69,8 +78,8 @@ static int is_better_name(struct rev_name *name,\n \t * We are now looking at two non-tags. Tiebreak to favor\n \t * shorter hops.\n \t */\n-\tif (name->distance != distance)\n-\t\treturn name->distance > distance;\n+\tif (name_distance != new_distance)\n+\t\treturn name_distance > new_distance;\n \n \t/* ... or tiebreak to favor older date */\n \tif (name->taggerdate != taggerdate)\n@@ -88,7 +97,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,\n \tstruct rev_name *name = commit_rev_name_at(&rev_names, commit);\n \n \tif (is_valid_rev_name(name)) {\n-\t\tif (!is_better_name(name, taggerdate, distance, from_tag))\n+\t\tif (!is_better_name(name, taggerdate, generation, distance, from_tag))\n \t\t\treturn NULL;\n \n \t\t/*\n\nbase-commit: abe6bb3905392d5eb6b01fa6e54d7e784e0522aa\n-- \ngitgitgadget\n"},{"id":"443419","messageId":"nycvar.QRO.7.76.6.2112081237310.90@tvgsbejvaqbjf.bet","threadId":"56884","inReplyTo":"pull.1119.v2.git.git.1638596152340.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] name-rev: prefer shorter names over following merges","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-12-08T11:38:19Z","receivedAt":"2021-12-08T11:38:42Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Elijah,\n\nOn Sat, 4 Dec 2021, Elijah Newren via GitGitGadget wrote:\n\n> Range-diff vs v1:\n>\n> 1: 50812ed6fdf ! 1: 5d068486f9f name-rev: prefer shorter names over following merges\n> @@ Commit message\n> the printed name over fewer total parent traversals performed to get the\n> answer.\n>\n> + == Side-note on tie-breakers ==\n> +\n> + When there are the same number of segments for two different names, we\n> + actually use the name of an ancestor commit as a tie-breaker as well.\n> + For example, for the commit cbdca289fb in the git.git repository, we\n> + prefer the name v2.33.0-rc0~112^2~1 over v2.33.0-rc0~57^2~5. This is\n> + because:\n> +\n> + * cbdca289fb is the parent of 25e65b6dd5, which implies the name for\n> + cbdca289fb should be the first parent of the preferred name for\n> + 25e65b6dd5\n> + * 25e65b6dd5 could be named either v2.33.0-rc0~112^2 or\n> + v2.33.0-rc0~57^2~4, but the former is preferred over the latter due\n> + to fewer segments\n> + * combine the two previous facts, and the name we get for cbdca289fb\n> + is \"v2.33.0-rc0~112^2~1\" rather than \"v2.33.0-rc0~57^2~5\".\n> +\n> + Technically, we get this for free out of the implementation since we\n> + only keep track of one name for each commit as we walk history (and\n> + re-add parents to the queue if we find a better name for those parents),\n> + but the first bullet point above ensures users get results that feel\n> + more consistent.\n> +\n> + == Alternative Ideas and Meanings Discussed ==\n> +\n> + One suggestion that came up during review was that shortest\n> + string-length might be easiest for users to consume. However, such a\n> + scheme would be rather computationally expensive (we'd have to track all\n> + names for each commit as we traversed the graph) and would additionally\n> + come with the possibly perplexing result that on a linear segment of\n> + history we could rapidly swap back and forth on names:\n> + MYTAG~3^2 would be preferred over MYTAG~9998\n> + MYTAG~3^2~1 would NOT be preferred over MYTAG~9999\n> + MYTAG~3^2~2 might be preferred over MYTAG~10000\n> +\n> + Another item that came up was possible auxiliary semantic meanings for\n> + name-rev results either before or after this patch. The basic answer\n> + was that the previous implementation had no known useful auxiliary\n> + semantics, but that for many repositories (most in my experience), the\n> + new scheme does. In particular, the new name-rev output can often be\n> + used to answer the question, \"How or when did this commit get merged?\"\n> + Since that usefulness depends on how merges happen within the repository\n> + and thus isn't universally applicable, details are omitted here but you\n> + can see them at [1].\n> +\n> + [1] https://lore.kernel.org/git/CABPp-BEeUM+3NLKDVdak90_UUeNghYCx=Dgir6=8ixvYmvyq3Q@mail.gmail.com/\n> +\n> + Finally, it was noted that the algorithm could be improved by just\n> + explicitly tracking the number of segments and using both it and\n> + distance in the comparison, instead of giving a magic number that tries\n> + to blend the two (and which therefore might give suboptimal results in\n> + repositories with really huge numbers of commits that periodically merge\n> + older code). However, \"[this patch] seems to give us a much better\n> + results than the current code, so let's take it and leave further\n> + futzing outside the scope.\"\n> +\n> Signed-off-by: Elijah Newren \n\nVery nice addition!\n\nAnd obviously, I am still in favor of moving this patch along in the\ndirection of `main`.\n\nThank you,\nDscho\n"}]}