{"thread":{"id":"55069","subject":"[PATCH 0/3] Speed up remove_redundant()","startedAt":"2021-01-28T16:25:58Z","lastAt":"2021-02-20T03:32:51Z","messageCount":35,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","René Scharfe","Derrick Stolee","René Scharfe.","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"415511","messageId":"pull.852.git.1611851095.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":null,"subject":"[PATCH 0/3] Speed up remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-28T16:24:51Z","receivedAt":"2021-01-28T16:25:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Michael Haggerty pointed out that git merge-base --independent is quite slow\nwhen many commits are provided in the input. This boils down to some\nquadratic behavior in remove_redundant() because it calls\npaint_down_to_common() in a loop.\n\nThis series avoids that by using a single commit walk, pushing a flag that\nmeans \"this commit is reachable from a parent of a commit in the list.\" At\nthe end of the walk, the input commits without that flag are independent.\n\nThere is an extra performance enhancement using the first-parent history as\na heuristic. This helps only when there is a single independent result, as\nwe can short circuit the walk when all other inputs are found to be\nreachable from the top one.\n\nMy tests were on the Linux kernel repository, testing this command:\n\n git merge-base --independent $(git for-each-ref refs/tags --format=\"%(refname)\")\n\n Before: 16.4s\nAfter Patch 1: 1.1s\nAfter Patch 2: 0.1s\n\nThis does not change the correctness of the function. It is tested carefully\nin t6600-test-reach.c, among existing merge-base tests.\n\nThanks, -Stolee\n\nDerrick Stolee (3):\n commit-reach: use one walk in remove_redundant()\n commit-reach: move compare_commits_by_gen\n commit-reach: use heuristic in remove_redundant()\n\n commit-reach.c | 178 +++++++++++++++++++++++++++++++++----------------\n 1 file changed, 120 insertions(+), 58 deletions(-)\n\n\nbase-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/852\n-- \ngitgitgadget\n"},{"id":"415512","messageId":"4c58877a7095f3509df0dda52b4110758aaf3201.1611851095.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.git.1611851095.gitgitgadget@gmail.com","subject":"[PATCH 2/3] commit-reach: move compare_commits_by_gen","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-28T16:24:53Z","receivedAt":"2021-01-28T16:25:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nMove this earlier in the file so it can be used by more methods.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 30 +++++++++++++++---------------\n 1 file changed, 15 insertions(+), 15 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 677f6f7c3f3..783c604a405 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -17,6 +17,21 @@\n \n static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n \n+static int compare_commits_by_gen(const void *_a, const void *_b)\n+{\n+\tconst struct commit *a = *(const struct commit * const *)_a;\n+\tconst struct commit *b = *(const struct commit * const *)_b;\n+\n+\ttimestamp_t generation_a = commit_graph_generation(a);\n+\ttimestamp_t generation_b = commit_graph_generation(b);\n+\n+\tif (generation_a < generation_b)\n+\t\treturn -1;\n+\tif (generation_a > generation_b)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n static int queue_has_nonstale(struct prio_queue *queue)\n {\n \tint i;\n@@ -583,21 +598,6 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\n \n-static int compare_commits_by_gen(const void *_a, const void *_b)\n-{\n-\tconst struct commit *a = *(const struct commit * const *)_a;\n-\tconst struct commit *b = *(const struct commit * const *)_b;\n-\n-\ttimestamp_t generation_a = commit_graph_generation(a);\n-\ttimestamp_t generation_b = commit_graph_generation(b);\n-\n-\tif (generation_a < generation_b)\n-\t\treturn -1;\n-\tif (generation_a > generation_b)\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t\t unsigned int with_flag,\n \t\t\t\t unsigned int assign_flag,\n-- \ngitgitgadget\n\n"},{"id":"415513","messageId":"3fe74e339fc5b7083398f2df51baae5a4a008060.1611851095.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.git.1611851095.gitgitgadget@gmail.com","subject":"[PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-28T16:24:52Z","receivedAt":"2021-01-28T16:26:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe current implementation of remove_redundant() uses several calls to\npaint_down_to_common() to determine that commits are independent of each\nother. This leads to quadratic behavior when many inputs are passed to\ncommands such as 'git merge-base'.\n\nFor example, in the Linux kernel repository, I tested the performance\nby passing all tags:\n\n git merge-base --independent $(git for-each-ref refs/tags --format=\"$(refname)\")\n\n(Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do\nnot point to commits.)\n\nHere is the performance improvement introduced by this change:\n\n Before: 16.4s\n After: 1.1s\n\nThe basic approach is to do one commit walk instead of many. First, scan\nall commits in the list and mark their _parents_ with the STALE flag.\nThis flag will indicate commits that are reachable from one of the\ninputs, except not including themselves. Then, walk commits until\ncovering all commits up to the minimum generation number pushing the\nSTALE flag throughout.\n\nAt the end of the walk, commits in the input list that have the STALE\nflag are reachable from a _different_ commit in the list. These should\nbe moved to the end of the array while the others are shifted to the\nfront.\n\nThis logic is covered by tests in t6600-test-reach.sh, so the behavior\ndoes not change.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 108 +++++++++++++++++++++++++++++--------------------\n 1 file changed, 65 insertions(+), 43 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex e38771ca5a1..677f6f7c3f3 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -164,58 +164,80 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t * the array, and return the number of commits that\n \t * are independent from each other.\n \t */\n-\tstruct commit **work;\n-\tunsigned char *redundant;\n-\tint *filled_index;\n-\tint i, j, filled;\n+\tint i, count_non_stale = 0;\n+\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tstruct commit **dup;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \n-\twork = xcalloc(cnt, sizeof(*work));\n-\tredundant = xcalloc(cnt, 1);\n-\tALLOC_ARRAY(filled_index, cnt - 1);\n+\t/* Mark all parents of the input as STALE */\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tstruct commit_list *parents;\n+\t\ttimestamp_t generation;\n \n-\tfor (i = 0; i < cnt; i++)\n \t\trepo_parse_commit(r, array[i]);\n-\tfor (i = 0; i < cnt; i++) {\n-\t\tstruct commit_list *common;\n-\t\ttimestamp_t min_generation = commit_graph_generation(array[i]);\n+\t\tparents = array[i]->parents;\n+\n+\t\twhile (parents) {\n+\t\t\trepo_parse_commit(r, parents->item);\n+\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n+\t\t\tparents = parents->next;\n+\t\t}\n+\n+\t\tgeneration = commit_graph_generation(array[i]);\n+\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n+\t}\n+\n+\t/* push the STALE bits up to min generation */\n+\twhile (queue.nr) {\n+\t\tstruct commit_list *parents;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\n+\t\trepo_parse_commit(r, c);\n \n-\t\tif (redundant[i])\n+\t\tif (commit_graph_generation(c) < min_generation)\n \t\t\tcontinue;\n-\t\tfor (j = filled = 0; j < cnt; j++) {\n-\t\t\ttimestamp_t curr_generation;\n-\t\t\tif (i == j || redundant[j])\n-\t\t\t\tcontinue;\n-\t\t\tfilled_index[filled] = j;\n-\t\t\twork[filled++] = array[j];\n \n-\t\t\tcurr_generation = commit_graph_generation(array[j]);\n-\t\t\tif (curr_generation < min_generation)\n-\t\t\t\tmin_generation = curr_generation;\n+\t\tparents = c->parents;\n+\t\twhile (parents) {\n+\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n+\t\t\tparents = parents->next;\n+\t\t}\n+\t}\n+\n+\t/* rearrange array */\n+\tdup = xcalloc(cnt, sizeof(struct commit *));\n+\tCOPY_ARRAY(dup, array, cnt);\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tif (dup[i]->object.flags & STALE) {\n+\t\t\tint insert = cnt - 1 - (i - count_non_stale);\n+\t\t\tarray[insert] = dup[i];\n+\t\t} else {\n+\t\t\tarray[count_non_stale] = dup[i];\n+\t\t\tcount_non_stale++;\n+\t\t}\n+\t}\n+\tfree(dup);\n+\n+\t/* clear marks */\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tstruct commit_list *parents;\n+\t\tparents = array[i]->parents;\n+\n+\t\twhile (parents) {\n+\t\t\tclear_commit_marks(parents->item, STALE);\n+\t\t\tparents = parents->next;\n \t\t}\n-\t\tcommon = paint_down_to_common(r, array[i], filled,\n-\t\t\t\t\t work, min_generation);\n-\t\tif (array[i]->object.flags & PARENT2)\n-\t\t\tredundant[i] = 1;\n-\t\tfor (j = 0; j < filled; j++)\n-\t\t\tif (work[j]->object.flags & PARENT1)\n-\t\t\t\tredundant[filled_index[j]] = 1;\n-\t\tclear_commit_marks(array[i], all_flags);\n-\t\tclear_commit_marks_many(filled, work, all_flags);\n-\t\tfree_commit_list(common);\n \t}\n \n-\t/* Now collect the result */\n-\tCOPY_ARRAY(work, array, cnt);\n-\tfor (i = filled = 0; i < cnt; i++)\n-\t\tif (!redundant[i])\n-\t\t\tarray[filled++] = work[i];\n-\tfor (j = filled, i = 0; i < cnt; i++)\n-\t\tif (redundant[i])\n-\t\t\tarray[j++] = work[i];\n-\tfree(work);\n-\tfree(redundant);\n-\tfree(filled_index);\n-\treturn filled;\n+\treturn count_non_stale;\n }\n \n static struct commit_list *get_merge_bases_many_0(struct repository *r,\n-- \ngitgitgadget\n\n"},{"id":"415514","messageId":"fbe7bdc1ec2ba6014dacc3a7ffa626b24c9aa7a5.1611851095.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.git.1611851095.gitgitgadget@gmail.com","subject":"[PATCH 3/3] commit-reach: use heuristic in remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-28T16:24:54Z","receivedAt":"2021-01-28T16:26:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nReachability algorithms in commit-reach.c frequently benefit from using\nthe first-parent history as a heuristic for satisfying reachability\nqueries. The most obvious example was implemented in 4fbcca4e\n(commit-reach: make can_all_from_reach... linear, 2018-07-20).\n\nUpdate the walk in remove_redundant() to use this same heuristic. Here,\nwe are walking starting at the parents of the input commits. Sort those\nparents and walk from the highest generation to lower. Each time, use\nthe heuristic of searching the first parent history before continuing to\nexpand the walk.\n\nThe important piece is to ensure we short-circuit the walk when we find\nthat there is a single non-redundant commit. This happens frequently\nwhen looking for merge-bases or comparing several tags with 'git\nmerge-base --independent'. Use a new count 'count_still_independent' and\nif that hits 1 we can stop walking.\n\nTo update 'count_still_independent' properly, we add use of the RESULT\nflag on the input commits. Then we can detect when we reach one of these\ncommits and decrease the count. We need to remove the RESULT flag at\nthat moment because we might re-visit that commit when popping the\nstack.\n\nWe use the STALE flag to mark parents that have been added to the new\nwalk_start list, but we need to clear that flag before we start walking\nso those flags don't halt our depth-first-search walk.\n\nOn my copy of the Linux kernel repository, the performance of 'git\nmerge-base --independent ' goes from 1.1 seconds to 0.11\nseconds.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 56 insertions(+), 16 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 783c604a405..6032624282e 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -179,10 +179,13 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t * the array, and return the number of commits that\n \t * are independent from each other.\n \t */\n-\tint i, count_non_stale = 0;\n+\tint i, count_non_stale = 0, count_still_independent = cnt;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n \tstruct commit **dup;\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct commit **walk_start;\n+\tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n+\n+\tALLOC_ARRAY(walk_start, walk_start_alloc);\n \n \t/* Mark all parents of the input as STALE */\n \tfor (i = 0; i < cnt; i++) {\n@@ -190,13 +193,15 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\ttimestamp_t generation;\n \n \t\trepo_parse_commit(r, array[i]);\n+\t\tarray[i]->object.flags |= RESULT;\n \t\tparents = array[i]->parents;\n \n \t\twhile (parents) {\n \t\t\trepo_parse_commit(r, parents->item);\n \t\t\tif (!(parents->item->object.flags & STALE)) {\n \t\t\t\tparents->item->object.flags |= STALE;\n-\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n+\t\t\t\twalk_start[walk_start_nr++] = parents->item;\n \t\t\t}\n \t\t\tparents = parents->next;\n \t\t}\n@@ -207,30 +212,65 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\t\tmin_generation = generation;\n \t}\n \n-\t/* push the STALE bits up to min generation */\n-\twhile (queue.nr) {\n-\t\tstruct commit_list *parents;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\tQSORT(walk_start, walk_start_nr, compare_commits_by_gen);\n \n-\t\trepo_parse_commit(r, c);\n+\t/* remove STALE bit for now to allow walking through parents */\n+\tfor (i = 0; i < walk_start_nr; i++)\n+\t\twalk_start[i]->object.flags &= ~STALE;\n \n-\t\tif (commit_graph_generation(c) < min_generation)\n-\t\t\tcontinue;\n+\t/*\n+\t * Start walking from the highest generation. Hopefully, it will\n+\t * find all other items during the first-parent walk, and we can\n+\t * terminate early. Otherwise, we will do the same amount of work\n+\t * as before.\n+\t */\n+\tfor (i = walk_start_nr - 1; i >= 0 && count_still_independent > 1; i--) {\n+\t\t/* push the STALE bits up to min generation */\n+\t\tstruct commit_list *stack = NULL;\n \n-\t\tparents = c->parents;\n-\t\twhile (parents) {\n-\t\t\tif (!(parents->item->object.flags & STALE)) {\n-\t\t\t\tparents->item->object.flags |= STALE;\n-\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\tcommit_list_insert(walk_start[i], &stack);\n+\t\twalk_start[i]->object.flags |= STALE;\n+\n+\t\twhile (stack) {\n+\t\t\tstruct commit_list *parents;\n+\t\t\tstruct commit *c = stack->item;\n+\n+\t\t\trepo_parse_commit(r, c);\n+\n+\t\t\tif (c->object.flags & RESULT) {\n+\t\t\t\tc->object.flags &= ~RESULT;\n+\t\t\t\tif (--count_still_independent <= 1)\n+\t\t\t\t\tbreak;\n \t\t\t}\n-\t\t\tparents = parents->next;\n+\n+\t\t\tif (commit_graph_generation(c) < min_generation) {\n+\t\t\t\tpop_commit(&stack);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tparents = c->parents;\n+\t\t\twhile (parents) {\n+\t\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\t\tcommit_list_insert(parents->item, &stack);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t\tparents = parents->next;\n+\t\t\t}\n+\n+\t\t\t/* pop if all parents have been visited already */\n+\t\t\tif (!parents)\n+\t\t\t\tpop_commit(&stack);\n \t\t}\n+\t\tfree_commit_list(stack);\n \t}\n+\tfree(walk_start);\n \n \t/* rearrange array */\n \tdup = xcalloc(cnt, sizeof(struct commit *));\n \tCOPY_ARRAY(dup, array, cnt);\n \tfor (i = 0; i < cnt; i++) {\n+\t\tdup[i]->object.flags &= ~RESULT;\n \t\tif (dup[i]->object.flags & STALE) {\n \t\t\tint insert = cnt - 1 - (i - count_non_stale);\n \t\t\tarray[insert] = dup[i];\n-- \ngitgitgadget\n"},{"id":"415524","messageId":"xmqqzh0svmnj.fsf@gitster.c.googlers.com","threadId":"55069","inReplyTo":"pull.852.git.1611851095.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] Speed up remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-28T20:20:32Z","receivedAt":"2021-01-28T20:21:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> Michael Haggerty pointed out that git merge-base --independent is quite slow\n> when many commits are provided in the input. This boils down to some\n> quadratic behavior in remove_redundant() because it calls\n> paint_down_to_common() in a loop.\n>\n> This series avoids that by using a single commit walk, pushing a flag that\n> means \"this commit is reachable from a parent of a commit in the list.\" At\n> the end of the walk, the input commits without that flag are independent.\n\nYay. I've been quite unhappy with the loop ever since I wrote it\nback in 2012.\n\nThanks for cleaning it up.\n"},{"id":"415525","messageId":"xmqqtur0vl7i.fsf@gitster.c.googlers.com","threadId":"55069","inReplyTo":"3fe74e339fc5b7083398f2df51baae5a4a008060.1611851095.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-28T20:51:45Z","receivedAt":"2021-01-28T20:54:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> +\t/* Mark all parents of the input as STALE */\n> +\tfor (i = 0; i < cnt; i++) {\n> +\t\tstruct commit_list *parents;\n> +\t\ttimestamp_t generation;\n> \n> \t\trepo_parse_commit(r, array[i]);\n> +\t\tparents = array[i]->parents;\n> +\n> +\t\twhile (parents) {\n> +\t\t\trepo_parse_commit(r, parents->item);\n> +\t\t\tif (!(parents->item->object.flags & STALE)) {\n> +\t\t\t\tparents->item->object.flags |= STALE;\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n> +\t\t\t}\n> +\t\t\tparents = parents->next;\n> +\t\t}\n> +\n> +\t\tgeneration = commit_graph_generation(array[i]);\n> +\n> +\t\tif (generation < min_generation)\n> +\t\t\tmin_generation = generation;\n> +\t}\n> +\n> +\t/* push the STALE bits up to min generation */\n> +\twhile (queue.nr) {\n> +\t\tstruct commit_list *parents;\n> +\t\tstruct commit *c = prio_queue_get(&queue);\n> +\n> +\t\trepo_parse_commit(r, c);\n> \n> +\t\tif (commit_graph_generation(c) < min_generation)\n> \t\t\tcontinue;\n> \n> +\t\tparents = c->parents;\n> +\t\twhile (parents) {\n> +\t\t\tif (!(parents->item->object.flags & STALE)) {\n> +\t\t\t\tparents->item->object.flags |= STALE;\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n> +\t\t\t}\n> +\t\t\tparents = parents->next;\n> +\t\t}\n> +\t}\n\nSo, the inner loop makes sure we won't revisit STALE parent, but\nkeep digging parents we haven't seen, and stop when the generation\nis old enough. What happens when there is no generation number\ncomputed yet, I wonder... We'll keep getting infinity and dig all\nthe way down to root?\n\n> +\t/* rearrange array */\n> +\tdup = xcalloc(cnt, sizeof(struct commit *));\n> +\tCOPY_ARRAY(dup, array, cnt);\n> +\tfor (i = 0; i < cnt; i++) {\n> +\t\tif (dup[i]->object.flags & STALE) {\n> +\t\t\tint insert = cnt - 1 - (i - count_non_stale);\n> +\t\t\tarray[insert] = dup[i];\n> +\t\t} else {\n> +\t\t\tarray[count_non_stale] = dup[i];\n> +\t\t\tcount_non_stale++;\n> +\t\t}\n> +\t}\n> +\tfree(dup);\n\nThe \"fill stale ones from the end, non-stale ones from the\nbeginning\" in the loop looks unnecessarily complex to me. I wonder\nif we can do only the \"fill non-stale ones from the beginning\" half,\ni.e.\n\n\tfor (i = count_non_stale = 0; i < cnt; i++) {\n\t\tif (dup[i] is not stale)\n\t\t\tarray[count_non_stale++] = dup[i];\n\t}\n\nwithout the \"keep the stale one at the end of array[]\", and clear\nmarks using what is in dup[] as starting points before discarding\ndup[]?\n\nOr do the callers still look at the entries beyond count_non_stale?\n\nOther than that, nicely done.\n\n> +\t/* clear marks */\n> +\tfor (i = 0; i < cnt; i++) {\n> +\t\tstruct commit_list *parents;\n> +\t\tparents = array[i]->parents;\n> +\n> +\t\twhile (parents) {\n> +\t\t\tclear_commit_marks(parents->item, STALE);\n> +\t\t\tparents = parents->next;\n> \t\t}\n> -\t\tcommon = paint_down_to_common(r, array[i], filled,\n> -\t\t\t\t\t work, min_generation);\n> -\t\tif (array[i]->object.flags & PARENT2)\n> -\t\t\tredundant[i] = 1;\n> -\t\tfor (j = 0; j < filled; j++)\n> -\t\t\tif (work[j]->object.flags & PARENT1)\n> -\t\t\t\tredundant[filled_index[j]] = 1;\n> -\t\tclear_commit_marks(array[i], all_flags);\n> -\t\tclear_commit_marks_many(filled, work, all_flags);\n> -\t\tfree_commit_list(common);\n> \t}\n> \n> -\t/* Now collect the result */\n> -\tCOPY_ARRAY(work, array, cnt);\n> -\tfor (i = filled = 0; i < cnt; i++)\n> -\t\tif (!redundant[i])\n> -\t\t\tarray[filled++] = work[i];\n> -\tfor (j = filled, i = 0; i < cnt; i++)\n> -\t\tif (redundant[i])\n> -\t\t\tarray[j++] = work[i];\n> -\tfree(work);\n> -\tfree(redundant);\n> -\tfree(filled_index);\n> -\treturn filled;\n> +\treturn count_non_stale;\n> }\n> \n> static struct commit_list *get_merge_bases_many_0(struct repository *r,\n"},{"id":"415568","messageId":"d1c7b530-f1ef-8aee-32d3-6ac6707bad37@web.de","threadId":"55069","inReplyTo":"3fe74e339fc5b7083398f2df51baae5a4a008060.1611851095.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-01-29T17:10:20Z","receivedAt":"2021-01-29T17:14:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.01.21 um 17:24 schrieb Derrick Stolee via GitGitGadget:\n> +\t/* rearrange array */\n> +\tdup = xcalloc(cnt, sizeof(struct commit *));\n\nYou could use CALLOC_ARRAY instead here, which is shorter and uses the\ncorrect type automatically. Or -- seeing that the next line overwrites\nall items anyway -- ALLOC_ARRAY.\n\n> +\tCOPY_ARRAY(dup, array, cnt);\n\nRené\n"},{"id":"415569","messageId":"198f7766-190d-d361-d6f4-23adefedaf6c@web.de","threadId":"55069","inReplyTo":"xmqqtur0vl7i.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-01-29T17:11:23Z","receivedAt":"2021-01-29T17:15:54Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.01.21 um 21:51 schrieb Junio C Hamano:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>> +\t/* rearrange array */\n>> +\tdup = xcalloc(cnt, sizeof(struct commit *));\n>> +\tCOPY_ARRAY(dup, array, cnt);\n>> +\tfor (i = 0; i < cnt; i++) {\n>> +\t\tif (dup[i]->object.flags & STALE) {\n>> +\t\t\tint insert = cnt - 1 - (i - count_non_stale);\n>> +\t\t\tarray[insert] = dup[i];\n>> +\t\t} else {\n>> +\t\t\tarray[count_non_stale] = dup[i];\n>> +\t\t\tcount_non_stale++;\n>> +\t\t}\n>> +\t}\n>> +\tfree(dup);\n>\n> The \"fill stale ones from the end, non-stale ones from the\n> beginning\" in the loop looks unnecessarily complex to me. I wonder\n> if we can do only the \"fill non-stale ones from the beginning\" half,\n> i.e.\n>\n> \tfor (i = count_non_stale = 0; i < cnt; i++) {\n> \t\tif (dup[i] is not stale)\n> \t\t\tarray[count_non_stale++] = dup[i];\n> \t}\n>\n> without the \"keep the stale one at the end of array[]\", and clear\n> marks using what is in dup[] as starting points before discarding\n> dup[]?\n>\n> Or do the callers still look at the entries beyond count_non_stale?\n\nHad the same reaction. Both callers ignore the stale entries.\n\n> Other than that, nicely done.\n>\n>> +\t/* clear marks */\n>> +\tfor (i = 0; i < cnt; i++) {\n>> +\t\tstruct commit_list *parents;\n>> +\t\tparents = array[i]->parents;\n>> +\n>> +\t\twhile (parents) {\n>> +\t\t\tclear_commit_marks(parents->item, STALE);\n>> +\t\t\tparents = parents->next;\n>> \t\t}\n\nThis loop clears STALE from the parents of both the non-stale and\nstale entries. OK. Should it also clear it from the stale entries\nthemselves?\n\n>> -\t\tcommon = paint_down_to_common(r, array[i], filled,\n>> -\t\t\t\t\t work, min_generation);\n>> -\t\tif (array[i]->object.flags & PARENT2)\n>> -\t\t\tredundant[i] = 1;\n>> -\t\tfor (j = 0; j < filled; j++)\n>> -\t\t\tif (work[j]->object.flags & PARENT1)\n>> -\t\t\t\tredundant[filled_index[j]] = 1;\n>> -\t\tclear_commit_marks(array[i], all_flags);\n>> -\t\tclear_commit_marks_many(filled, work, all_flags);\n>> -\t\tfree_commit_list(common);\n>> \t}\n>>\n>> -\t/* Now collect the result */\n>> -\tCOPY_ARRAY(work, array, cnt);\n>> -\tfor (i = filled = 0; i < cnt; i++)\n>> -\t\tif (!redundant[i])\n>> -\t\t\tarray[filled++] = work[i];\n>> -\tfor (j = filled, i = 0; i < cnt; i++)\n>> -\t\tif (redundant[i])\n>> -\t\t\tarray[j++] = work[i];\n>> -\tfree(work);\n>> -\tfree(redundant);\n>> -\tfree(filled_index);\n>> -\treturn filled;\n>> +\treturn count_non_stale;\n>> }\n>>\n>> static struct commit_list *get_merge_bases_many_0(struct repository *r,\n\n"},{"id":"415682","messageId":"75225d59-877e-92ad-1370-632d40af71cf@gmail.com","threadId":"55069","inReplyTo":"198f7766-190d-d361-d6f4-23adefedaf6c@web.de","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-31T03:52:59Z","receivedAt":"2021-01-31T03:53:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/29/2021 12:11 PM, René Scharfe wrote:\n> Am 28.01.21 um 21:51 schrieb Junio C Hamano:\n>> \"Derrick Stolee via GitGitGadget\" writes:\n>>> +\t/* rearrange array */\n>>> +\tdup = xcalloc(cnt, sizeof(struct commit *));\n>>> +\tCOPY_ARRAY(dup, array, cnt);\n>>> +\tfor (i = 0; i < cnt; i++) {\n>>> +\t\tif (dup[i]->object.flags & STALE) {\n>>> +\t\t\tint insert = cnt - 1 - (i - count_non_stale);\n>>> +\t\t\tarray[insert] = dup[i];\n>>> +\t\t} else {\n>>> +\t\t\tarray[count_non_stale] = dup[i];\n>>> +\t\t\tcount_non_stale++;\n>>> +\t\t}\n>>> +\t}\n>>> +\tfree(dup);\n>>\n>> The \"fill stale ones from the end, non-stale ones from the\n>> beginning\" in the loop looks unnecessarily complex to me. I wonder\n>> if we can do only the \"fill non-stale ones from the beginning\" half,\n>> i.e.\n>>\n>> \tfor (i = count_non_stale = 0; i < cnt; i++) {\n>> \t\tif (dup[i] is not stale)\n>> \t\t\tarray[count_non_stale++] = dup[i];\n>> \t}\n>>\n>> without the \"keep the stale one at the end of array[]\", and clear\n>> marks using what is in dup[] as starting points before discarding\n>> dup[]?\n>>\n>> Or do the callers still look at the entries beyond count_non_stale?\n> \n> Had the same reaction. Both callers ignore the stale entries.\n\nOk, I can update that logic accordingly. I wanted to keep consistent\nwith the comment at the start of the method:\n\n\t/*\n\t * Some commit in the array may be an ancestor of\n\t * another commit. Move such commit to the end of\n\t * the array, and return the number of commits that\n\t * are independent from each other.\n\t */\n\nbut if no caller actually needs that, then I can remove this\nbehavior. Anyone mind if it is a follow-up patch to change this\npart of the behavior?\n\n>> Other than that, nicely done.\n>>\n>>> +\t/* clear marks */\n>>> +\tfor (i = 0; i < cnt; i++) {\n>>> +\t\tstruct commit_list *parents;\n>>> +\t\tparents = array[i]->parents;\n>>> +\n>>> +\t\twhile (parents) {\n>>> +\t\t\tclear_commit_marks(parents->item, STALE);\n>>> +\t\t\tparents = parents->next;\n>>> \t\t}\n> \n> This loop clears STALE from the parents of both the non-stale and\n> stale entries. OK. Should it also clear it from the stale entries\n> themselves?\n\nclear_commit_marks() walks commits starting from the input commit\n(parents->item in this case) and clears the STALE bit as long as\nit is present. This way, the accumulated clear_commit_marks() will\nwalk each commit only once _and_ will visit any of the commits from\n'array' that received the STALE bit during the above walk.\n\nThanks,\n-Stolee\n"},{"id":"415683","messageId":"e5863616-ff74-88f2-3d6a-c8dbe03477fe@gmail.com","threadId":"55069","inReplyTo":"xmqqtur0vl7i.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-31T03:59:08Z","receivedAt":"2021-01-31T04:00:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/28/2021 3:51 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>> +\t\tparents = c->parents;\n>> +\t\twhile (parents) {\n>> +\t\t\tif (!(parents->item->object.flags & STALE)) {\n>> +\t\t\t\tparents->item->object.flags |= STALE;\n>> +\t\t\t\tprio_queue_put(&queue, parents->item);\n>> +\t\t\t}\n>> +\t\t\tparents = parents->next;\n>> +\t\t}\n>> +\t}\n> \n> So, the inner loop makes sure we won't revisit STALE parent, but\n> keep digging parents we haven't seen, and stop when the generation\n> is old enough. What happens when there is no generation number\n> computed yet, I wonder... We'll keep getting infinity and dig all\n> the way down to root?\n\nIf we are on commits that have no generation number yet, then we\nwill walk until reaching commits in the commit-graph file that have\na computed generation (or in the heuristic case, when we have reached\nall but one of the commits).\n\nIn the case of the commit-graph, all commits will have generation\nnumber \"infinity\". In such a case, perhaps the old algorithm _is_\nthe best we can do, at least for now.\n\nThe trade-off is that we might walk more commits in unusual cases\nwith few input commits. That quadratic behavior will take over as\nthe input size grows, no matter if there is a commit-graph or not.\n\nI can do a big more digging into these unusual cases, especially\nwhen we cannot rely on commit-graphs being present.\n\nOne way to ensure we do not regress from the current behavior\nwould be to condition the new algorithm with\n\n\tif (generation_numbers_enabled(the_repository))\n\t\tnew_algorithm();\n\telse\n\t\told_algorithm();\n\nmuch like in repo_is_descendant_of().\n\nIs that a good plan?\n\nThanks,\n-Stolee\n"},{"id":"415691","messageId":"1c99bd13-13a8-1c06-6b40-70722d685f5c@gmail.com","threadId":"55069","inReplyTo":"e5863616-ff74-88f2-3d6a-c8dbe03477fe@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-31T20:13:38Z","receivedAt":"2021-01-31T20:25:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/30/2021 10:59 PM, Derrick Stolee wrote:\n> On 1/28/2021 3:51 PM, Junio C Hamano wrote:\n>> \"Derrick Stolee via GitGitGadget\" writes:\n>>> +\t\tparents = c->parents;\n>>> +\t\twhile (parents) {\n>>> +\t\t\tif (!(parents->item->object.flags & STALE)) {\n>>> +\t\t\t\tparents->item->object.flags |= STALE;\n>>> +\t\t\t\tprio_queue_put(&queue, parents->item);\n>>> +\t\t\t}\n>>> +\t\t\tparents = parents->next;\n>>> +\t\t}\n>>> +\t}\n>>\n>> So, the inner loop makes sure we won't revisit STALE parent, but\n>> keep digging parents we haven't seen, and stop when the generation\n>> is old enough. What happens when there is no generation number\n>> computed yet, I wonder... We'll keep getting infinity and dig all\n>> the way down to root?\n> \n> If we are on commits that have no generation number yet, then we\n> will walk until reaching commits in the commit-graph file that have\n> a computed generation (or in the heuristic case, when we have reached\n> all but one of the commits).\n> \n> In the case of the commit-graph, all commits will have generation\n> number \"infinity\". In such a case, perhaps the old algorithm _is_\n> the best we can do, at least for now.\n> \n> The trade-off is that we might walk more commits in unusual cases\n> with few input commits. That quadratic behavior will take over as\n> the input size grows, no matter if there is a commit-graph or not.\n> \n> I can do a big more digging into these unusual cases, especially\n> when we cannot rely on commit-graphs being present.\n\nIndeed, the old algorithm is better for cases where generation\nnumbers do not help and there are multiple independent commits.\n\nFor example, this command in the Linux kernel repo changes from\n0.047s in the old algorithm to 6.6s with the new algorithm:\n\ngit -c core.commitGraph=false merge-base --independent 2ecedd756908 d2360a398f0b >/dev/null\n\n> One way to ensure we do not regress from the current behavior\n> would be to condition the new algorithm with\n> \n> \tif (generation_numbers_enabled(the_repository))\n> \t\tnew_algorithm();\n> \telse\n> \t\told_algorithm();\n> \n> much like in repo_is_descendant_of().\n\nI will include this in a v2.\n\nThanks,\n-Stolee\n\n"},{"id":"415694","messageId":"xmqqft2gonuh.fsf@gitster.c.googlers.com","threadId":"55069","inReplyTo":"e5863616-ff74-88f2-3d6a-c8dbe03477fe@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-31T20:25:42Z","receivedAt":"2021-01-31T20:28:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> So, the inner loop makes sure we won't revisit STALE parent, but\n>> keep digging parents we haven't seen, and stop when the generation\n>> is old enough. What happens when there is no generation number\n>> computed yet, I wonder... We'll keep getting infinity and dig all\n>> the way down to root?\n>\n> If we are on commits that have no generation number yet, then we\n> will walk until reaching commits in the commit-graph file that have\n> a computed generation (or in the heuristic case, when we have reached\n> all but one of the commits).\n>\n> In the case of the commit-graph, all commits will have generation\n> number \"infinity\". In such a case, perhaps the old algorithm _is_\n> the best we can do, at least for now.\n\nHmph, I am afraid that such is life X-<.\n\n> One way to ensure we do not regress from the current behavior\n> would be to condition the new algorithm with\n>\n> \tif (generation_numbers_enabled(the_repository))\n> \t\tnew_algorithm();\n> \telse\n> \t\told_algorithm();\n>\n> much like in repo_is_descendant_of().\n>\n> Is that a good plan?\n\nIt would certainly avoid one particular form of regression, so it is\nbetter than nothing.\n\nBut at the same time, we'd probably want to encourage people to\nenable and maintain generation numbers for the majority of commits\nin their repository, but unless you \"gc\" twice a day or something,\nyou'd inevitably have a mixture, say, all commits that are more than\ntwo weeks old are covered by commit-graph, but more recent ones are\nnot yet enumerated, and you have to traverse at runtime.\n\nAnd the performance characteristics we would care the most in the\nlonger term is to make sure that we perform well in such a mixed\nenvironment for the parts of the history that are not old enough.\n\nMany things can be sped up by precomputing and storing the result in\nthe commit-graph file and that is not all that interesting or\nsurprising part of the story, I would think. Rather, we want to\nensure that we do not perform on the youngest part of the history\nany worse---that way, people will have strong incentive to enable\ncommit-graph, as things will work superbly for older parts of the\nhistory, while not doing any worse than the original system for the\nnewest parts of the history.\n\nThere was a side thread where somebody wished if they can remove\nsupport for all the codepaths that do not use commit-graph, but\nwould this be an example of how such a wish is impractical, I have\nto wonder?\n\nThanks.\n"},{"id":"415706","messageId":"5d1e909e-b2e2-afda-d8ee-a3c32d25b01d@gmail.com","threadId":"55069","inReplyTo":"xmqqft2gonuh.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-02-01T03:55:52Z","receivedAt":"2021-02-01T03:56:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/31/2021 3:25 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n> \n>>> So, the inner loop makes sure we won't revisit STALE parent, but\n>>> keep digging parents we haven't seen, and stop when the generation\n>>> is old enough. What happens when there is no generation number\n>>> computed yet, I wonder... We'll keep getting infinity and dig all\n>>> the way down to root?\n>>\n>> If we are on commits that have no generation number yet, then we\n>> will walk until reaching commits in the commit-graph file that have\n>> a computed generation (or in the heuristic case, when we have reached\n>> all but one of the commits).\n>>\n>> In the case of the commit-graph, all commits will have generation\n>> number \"infinity\". In such a case, perhaps the old algorithm _is_\n>> the best we can do, at least for now.\n> \n> Hmph, I am afraid that such is life X-<.\n> \n>> One way to ensure we do not regress from the current behavior\n>> would be to condition the new algorithm with\n>>\n>> \tif (generation_numbers_enabled(the_repository))\n>> \t\tnew_algorithm();\n>> \telse\n>> \t\told_algorithm();\n>>\n>> much like in repo_is_descendant_of().\n>>\n>> Is that a good plan?\n> \n> It would certainly avoid one particular form of regression, so it is\n> better than nothing.\n> \n> But at the same time, we'd probably want to encourage people to\n> enable and maintain generation numbers for the majority of commits\n> in their repository, but unless you \"gc\" twice a day or something,\n> you'd inevitably have a mixture, say, all commits that are more than\n> two weeks old are covered by commit-graph, but more recent ones are\n> not yet enumerated, and you have to traverse at runtime.\n> \n> And the performance characteristics we would care the most in the\n> longer term is to make sure that we perform well in such a mixed\n> environment for the parts of the history that are not old enough.\n\nYou're right, that in the mixed case of \"all of these input commits\nhave infinite generation number\" is the worst possible case for\nthis algorithm. However, if even a single commit has a finite\ngeneration number, then this new algorithm should out-perform the\none using paint_down_to_common() in all cases.\n\nI tested the painful case of\n\n\tgit merge-base --independent 2ecedd756908 d2360a398f0b\n\nin the Linux kernel repository with different commit-graph files.\nI found that the new algorithm performed worse than the old\nalgorithm until there were fewer than 2,500 commits reachable\nfrom these two but not in the commit-graph file. That's probably\ntoo small of a gap to expect of a typical user.\n\nI will modify my check\n\n\tif (generation_numbers_enabled(r)) {\n\t\tint i;\n\n\t\t/*\n\t\t * If we have a single commit with finite generation\n\t\t * number, then the _with_gen algorithm is preferred.\n\t\t */\n\t\tfor (i = 0; i < cnt; i++) {\n\t\t\tif (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)\n\t\t\t\treturn remove_redundant_with_gen(r, array, cnt);\n\t\t}\n\t}\n\n\treturn remove_redundant_no_gen(r, array, cnt);\n\n> Many things can be sped up by precomputing and storing the result in\n> the commit-graph file and that is not all that interesting or\n> surprising part of the story, I would think. Rather, we want to\n> ensure that we do not perform on the youngest part of the history\n> any worse---that way, people will have strong incentive to enable\n> commit-graph, as things will work superbly for older parts of the\n> history, while not doing any worse than the original system for the\n> newest parts of the history.\n\nI'm definitely biased to a case where there is an up-to-date\ncommit-graph file, since I care most about server-side performance\nor users with background maintenance enabled (and computing the\ncommit-graph frequently). You are right to call out that that is\nnot always the case.\n \n> There was a side thread where somebody wished if they can remove\n> support for all the codepaths that do not use commit-graph, but\n> would this be an example of how such a wish is impractical, I have\n> to wonder?\n\nSome cases might allow de-duplication, such as\nsort_in_topological_order(), that would have roughly the same\nperformance, give or take some overhead. It takes time to check\nand see if that is the case, however.\n\nThanks,\n-Stolee\n"},{"id":"415742","messageId":"649f6799e6bfa0662ed5a4debf915053598fe142.1612183647.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"[PATCH v2 1/5] commit-reach: reduce requirements for remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-01T12:47:23Z","receivedAt":"2021-02-01T12:48:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nRemove a comment at the beggining of remove_redundant() that mentions a\nreordering of the input array to have the initial segment be the\nindependent commits and the final segment be the redundant commits.\nWhile this behavior is followed in remove_redundant(), no callers rely\non that behavior.\n\nRemove the final loop that copies this final segment and update the\ncomment to match the new behavior.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 10 ++++------\n 1 file changed, 4 insertions(+), 6 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex e38771ca5a1..9af51fe7e07 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -160,9 +160,10 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n {\n \t/*\n \t * Some commit in the array may be an ancestor of\n-\t * another commit. Move such commit to the end of\n-\t * the array, and return the number of commits that\n-\t * are independent from each other.\n+\t * another commit. Move the independent commits to the\n+\t * beginning of 'array' and return their number. Callers\n+\t * should not rely upon the contents of 'array' after\n+\t * that number.\n \t */\n \tstruct commit **work;\n \tunsigned char *redundant;\n@@ -209,9 +210,6 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \tfor (i = filled = 0; i < cnt; i++)\n \t\tif (!redundant[i])\n \t\t\tarray[filled++] = work[i];\n-\tfor (j = filled, i = 0; i < cnt; i++)\n-\t\tif (redundant[i])\n-\t\t\tarray[j++] = work[i];\n \tfree(work);\n \tfree(redundant);\n \tfree(filled_index);\n-- \ngitgitgadget\n\n"},{"id":"415743","messageId":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.git.1611851095.gitgitgadget@gmail.com","subject":"[PATCH v2 0/5] Speed up remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-01T12:47:22Z","receivedAt":"2021-02-01T12:48:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Michael Haggerty pointed out that git merge-base --independent is quite slow\nwhen many commits are provided in the input. This boils down to some\nquadratic behavior in remove_redundant() because it calls\npaint_down_to_common() in a loop.\n\nThis series avoids that by using a single commit walk, pushing a flag that\nmeans \"this commit is reachable from a parent of a commit in the list.\" At\nthe end of the walk, the input commits without that flag are independent.\n\nThere is an extra performance enhancement using the first-parent history as\na heuristic. This helps only when there is a single independent result, as\nwe can short circuit the walk when all other inputs are found to be\nreachable from the top one. It also gets faster when we discover the commit\nwith lowest generation and can restrict our walk further to the next-lowest\ngeneration number.\n\nMy tests were on the Linux kernel repository, testing this command:\n\n git merge-base --independent $(git for-each-ref refs/tags --format=\"%(refname)\")\n\n Before: 16.4s\nAfter Patch 1: 1.1s\nAfter Patch 2: 0.1s\n\nThis does not change the correctness of the function. It is tested carefully\nin t6600-test-reach.c, among existing merge-base tests. There are also more\ntests in scripts like t6012-rev-list-simplify.sh that trigger the new logic\nunder GIT_TEST_COMMIT_GRAPH=1.\n\n\nUpdates in V2\n=============\n\n * The old algorithm is not entirely removed. It is still faster than the\n new algorithm if all input commits are not in the commit-graph file\n (unless the commit-graph file is really close to the input commits, but\n that is an unreasonable expectation). Now, the new logic only happens if\n there is an input commit with finite generation number.\n\n * There was a copy of 'array' being used for the final reorder which is now\n removed. We still need to be careful about the RESULT bit.\n\n * The final patch is new, adding yet another speedup in the form of\n increasing the min_generation cutoff when we find the input commit of\n smallest generation. This can reduce the time significantly when given\n many inputs. This does require copying the 'array' again, so we can sort\n by generation number while preserving the original order of 'array' which\n is required by some callers.\n\nThanks, -Stolee\n\nDerrick Stolee (5):\n commit-reach: reduce requirements for remove_redundant()\n commit-reach: use one walk in remove_redundant()\n commit-reach: move compare_commits_by_gen\n commit-reach: use heuristic in remove_redundant()\n commit-reach: stale commits may prune generation further\n\n commit-reach.c | 188 +++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 166 insertions(+), 22 deletions(-)\n\n\nbase-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/852\n\nRange-diff vs v1:\n\n -: ----------- > 1: 649f6799e6b commit-reach: reduce requirements for remove_redundant()\n 1: 3fe74e339fc ! 2: 2f80ae5fcb0 commit-reach: use one walk in remove_redundant()\n @@ Commit message\n Before: 16.4s\n After: 1.1s\n \n + This performance improvement requires the commit-graph file to be\n + present. We keep the old algorithm around as remove_redundant_no_gen()\n + and use it when generation_numbers_enabled() is false. This is similar\n + to other algorithms within commit-reach.c. The new algorithm is\n + implemented in remove_redundant_with_gen().\n +\n The basic approach is to do one commit walk instead of many. First, scan\n all commits in the list and mark their _parents_ with the STALE flag.\n This flag will indicate commits that are reachable from one of the\n @@ Commit message\n covering all commits up to the minimum generation number pushing the\n STALE flag throughout.\n \n - At the end of the walk, commits in the input list that have the STALE\n - flag are reachable from a _different_ commit in the list. These should\n - be moved to the end of the array while the others are shifted to the\n - front.\n + At the end, we need to clear the STALE bit from all of the commits\n + we walked. We move the non-stale commits in 'array' to the beginning of\n + the list, and this might overwrite stale commits. However, we store an\n + array of commits that started the walk, and use clear_commit_marks() on\n + each of those starting commits. That method will walk the reachable\n + commits with the STALE bit and clear them all. This makes the algorithm\n + safe for re-entry or for other uses of those commits after this walk.\n \n This logic is covered by tests in t6600-test-reach.sh, so the behavior\n - does not change.\n + does not change. This is tested both in the case with a commit-graph and\n + without.\n \n Signed-off-by: Derrick Stolee \n \n ## commit-reach.c ##\n +@@ commit-reach.c: struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n + \treturn ret;\n + }\n + \n +-static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n ++static int remove_redundant_no_gen(struct repository *r,\n ++\t\t\t\t struct commit **array, int cnt)\n + {\n +-\t/*\n +-\t * Some commit in the array may be an ancestor of\n +-\t * another commit. Move the independent commits to the\n +-\t * beginning of 'array' and return their number. Callers\n +-\t * should not rely upon the contents of 'array' after\n +-\t * that number.\n +-\t */\n + \tstruct commit **work;\n + \tunsigned char *redundant;\n + \tint *filled_index;\n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt\n - \t * the array, and return the number of commits that\n - \t * are independent from each other.\n - \t */\n --\tstruct commit **work;\n --\tunsigned char *redundant;\n --\tint *filled_index;\n --\tint i, j, filled;\n + \tfor (i = filled = 0; i < cnt; i++)\n + \t\tif (!redundant[i])\n + \t\t\tarray[filled++] = work[i];\n ++\tfor (j = filled, i = 0; i < cnt; i++)\n ++\t\tif (redundant[i])\n ++\t\t\tarray[j++] = work[i];\n + \tfree(work);\n + \tfree(redundant);\n + \tfree(filled_index);\n + \treturn filled;\n + }\n + \n ++static int remove_redundant_with_gen(struct repository *r,\n ++\t\t\t\t struct commit **array, int cnt)\n ++{\n +\tint i, count_non_stale = 0;\n +\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n -+\tstruct commit **dup;\n ++\tstruct commit **walk_start;\n ++\tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n - \n --\twork = xcalloc(cnt, sizeof(*work));\n --\tredundant = xcalloc(cnt, 1);\n --\tALLOC_ARRAY(filled_index, cnt - 1);\n ++\n ++\tALLOC_ARRAY(walk_start, walk_start_alloc);\n ++\n +\t/* Mark all parents of the input as STALE */\n +\tfor (i = 0; i < cnt; i++) {\n +\t\tstruct commit_list *parents;\n +\t\ttimestamp_t generation;\n - \n --\tfor (i = 0; i < cnt; i++)\n - \t\trepo_parse_commit(r, array[i]);\n --\tfor (i = 0; i < cnt; i++) {\n --\t\tstruct commit_list *common;\n --\t\ttimestamp_t min_generation = commit_graph_generation(array[i]);\n ++\n ++\t\trepo_parse_commit(r, array[i]);\n +\t\tparents = array[i]->parents;\n +\n +\t\twhile (parents) {\n +\t\t\trepo_parse_commit(r, parents->item);\n +\t\t\tif (!(parents->item->object.flags & STALE)) {\n +\t\t\t\tparents->item->object.flags |= STALE;\n ++\t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n ++\t\t\t\twalk_start[walk_start_nr++] = parents->item;\n +\t\t\t\tprio_queue_put(&queue, parents->item);\n +\t\t\t}\n +\t\t\tparents = parents->next;\n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit\n +\t\tstruct commit *c = prio_queue_get(&queue);\n +\n +\t\trepo_parse_commit(r, c);\n - \n --\t\tif (redundant[i])\n ++\n +\t\tif (commit_graph_generation(c) < min_generation)\n - \t\t\tcontinue;\n --\t\tfor (j = filled = 0; j < cnt; j++) {\n --\t\t\ttimestamp_t curr_generation;\n --\t\t\tif (i == j || redundant[j])\n --\t\t\t\tcontinue;\n --\t\t\tfilled_index[filled] = j;\n --\t\t\twork[filled++] = array[j];\n - \n --\t\t\tcurr_generation = commit_graph_generation(array[j]);\n --\t\t\tif (curr_generation < min_generation)\n --\t\t\t\tmin_generation = curr_generation;\n ++\t\t\tcontinue;\n ++\n +\t\tparents = c->parents;\n +\t\twhile (parents) {\n +\t\t\tif (!(parents->item->object.flags & STALE)) {\n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit\n +\t}\n +\n +\t/* rearrange array */\n -+\tdup = xcalloc(cnt, sizeof(struct commit *));\n -+\tCOPY_ARRAY(dup, array, cnt);\n -+\tfor (i = 0; i < cnt; i++) {\n -+\t\tif (dup[i]->object.flags & STALE) {\n -+\t\t\tint insert = cnt - 1 - (i - count_non_stale);\n -+\t\t\tarray[insert] = dup[i];\n -+\t\t} else {\n -+\t\t\tarray[count_non_stale] = dup[i];\n -+\t\t\tcount_non_stale++;\n -+\t\t}\n ++\tfor (i = count_non_stale = 0; i < cnt; i++) {\n ++\t\tif (!(array[i]->object.flags & STALE))\n ++\t\t\tarray[count_non_stale++] = array[i];\n +\t}\n -+\tfree(dup);\n +\n +\t/* clear marks */\n -+\tfor (i = 0; i < cnt; i++) {\n -+\t\tstruct commit_list *parents;\n -+\t\tparents = array[i]->parents;\n ++\tfor (i = 0; i < walk_start_nr; i++)\n ++\t\tclear_commit_marks(walk_start[i], STALE);\n ++\tfree(walk_start);\n +\n -+\t\twhile (parents) {\n -+\t\t\tclear_commit_marks(parents->item, STALE);\n -+\t\t\tparents = parents->next;\n - \t\t}\n --\t\tcommon = paint_down_to_common(r, array[i], filled,\n --\t\t\t\t\t work, min_generation);\n --\t\tif (array[i]->object.flags & PARENT2)\n --\t\t\tredundant[i] = 1;\n --\t\tfor (j = 0; j < filled; j++)\n --\t\t\tif (work[j]->object.flags & PARENT1)\n --\t\t\t\tredundant[filled_index[j]] = 1;\n --\t\tclear_commit_marks(array[i], all_flags);\n --\t\tclear_commit_marks_many(filled, work, all_flags);\n --\t\tfree_commit_list(common);\n - \t}\n - \n --\t/* Now collect the result */\n --\tCOPY_ARRAY(work, array, cnt);\n --\tfor (i = filled = 0; i < cnt; i++)\n --\t\tif (!redundant[i])\n --\t\t\tarray[filled++] = work[i];\n --\tfor (j = filled, i = 0; i < cnt; i++)\n --\t\tif (redundant[i])\n --\t\t\tarray[j++] = work[i];\n --\tfree(work);\n --\tfree(redundant);\n --\tfree(filled_index);\n --\treturn filled;\n +\treturn count_non_stale;\n - }\n - \n ++}\n ++\n ++static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n ++{\n ++\t/*\n ++\t * Some commit in the array may be an ancestor of\n ++\t * another commit. Move the independent commits to the\n ++\t * beginning of 'array' and return their number. Callers\n ++\t * should not rely upon the contents of 'array' after\n ++\t * that number.\n ++\t */\n ++\tif (generation_numbers_enabled(r)) {\n ++\t\tint i;\n ++\n ++\t\t/*\n ++\t\t * If we have a single commit with finite generation\n ++\t\t * number, then the _with_gen algorithm is preferred.\n ++\t\t */\n ++\t\tfor (i = 0; i < cnt; i++) {\n ++\t\t\tif (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)\n ++\t\t\t\treturn remove_redundant_with_gen(r, array, cnt);\n ++\t\t}\n ++\t}\n ++\n ++\treturn remove_redundant_no_gen(r, array, cnt);\n ++}\n ++\n static struct commit_list *get_merge_bases_many_0(struct repository *r,\n + \t\t\t\t\t\t struct commit *one,\n + \t\t\t\t\t\t int n,\n 2: 4c58877a709 = 3: 009f64b53c9 commit-reach: move compare_commits_by_gen\n 3: fbe7bdc1ec2 ! 4: 83feabeebb5 commit-reach: use heuristic in remove_redundant()\n @@ Commit message\n the heuristic of searching the first parent history before continuing to\n expand the walk.\n \n + The order in which we explore the commits matters, so update\n + compare_commits_by_gen to break generation number ties with commit date.\n + This has no effect when the commits are in a commit-graph file with\n + corrected commit dates computed, but it will assist when the commits are\n + in the region \"above\" the commit-graph with \"infinite\" generation\n + number. Note that we cannot shift to use\n + compare_commits_by_gen_then_commit_date as the method prototype is\n + different. We use compare_commits_by_gen for QSORT() as opposed to as a\n + priority function.\n +\n The important piece is to ensure we short-circuit the walk when we find\n that there is a single non-redundant commit. This happens frequently\n when looking for merge-bases or comparing several tags with 'git\n @@ Commit message\n Signed-off-by: Derrick Stolee \n \n ## commit-reach.c ##\n -@@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt\n - \t * the array, and return the number of commits that\n - \t * are independent from each other.\n - \t */\n +@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)\n + \t\treturn -1;\n + \tif (generation_a > generation_b)\n + \t\treturn 1;\n ++\tif (a->date < b->date)\n ++\t\treturn -1;\n ++\tif (a->date > b->date)\n ++\t\treturn 1;\n + \treturn 0;\n + }\n + \n +@@ commit-reach.c: static int remove_redundant_no_gen(struct repository *r,\n + static int remove_redundant_with_gen(struct repository *r,\n + \t\t\t\t struct commit **array, int cnt)\n + {\n -\tint i, count_non_stale = 0;\n +\tint i, count_non_stale = 0, count_still_independent = cnt;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n - \tstruct commit **dup;\n + \tstruct commit **walk_start;\n + \tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n -\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n -+\tstruct commit **walk_start;\n -+\tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n -+\n -+\tALLOC_ARRAY(walk_start, walk_start_alloc);\n \n - \t/* Mark all parents of the input as STALE */\n - \tfor (i = 0; i < cnt; i++) {\n -@@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt\n + \tALLOC_ARRAY(walk_start, walk_start_alloc);\n + \n +@@ commit-reach.c: static int remove_redundant_with_gen(struct repository *r,\n \t\ttimestamp_t generation;\n \n \t\trepo_parse_commit(r, array[i]);\n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit\n \t\tparents = array[i]->parents;\n \n \t\twhile (parents) {\n - \t\t\trepo_parse_commit(r, parents->item);\n - \t\t\tif (!(parents->item->object.flags & STALE)) {\n +@@ commit-reach.c: static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\tparents->item->object.flags |= STALE;\n + \t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n + \t\t\t\twalk_start[walk_start_nr++] = parents->item;\n -\t\t\t\tprio_queue_put(&queue, parents->item);\n -+\t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n -+\t\t\t\twalk_start[walk_start_nr++] = parents->item;\n \t\t\t}\n \t\t\tparents = parents->next;\n \t\t}\n -@@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt\n +@@ commit-reach.c: static int remove_redundant_with_gen(struct repository *r,\n \t\t\tmin_generation = generation;\n \t}\n \n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit\n \t\t}\n +\t\tfree_commit_list(stack);\n \t}\n -+\tfree(walk_start);\n \n ++\t/* clear result */\n ++\tfor (i = 0; i < cnt; i++)\n ++\t\tarray[i]->object.flags &= ~RESULT;\n ++\n \t/* rearrange array */\n - \tdup = xcalloc(cnt, sizeof(struct commit *));\n - \tCOPY_ARRAY(dup, array, cnt);\n - \tfor (i = 0; i < cnt; i++) {\n -+\t\tdup[i]->object.flags &= ~RESULT;\n - \t\tif (dup[i]->object.flags & STALE) {\n - \t\t\tint insert = cnt - 1 - (i - count_non_stale);\n - \t\t\tarray[insert] = dup[i];\n + \tfor (i = count_non_stale = 0; i < cnt; i++) {\n + \t\tif (!(array[i]->object.flags & STALE))\n -: ----------- > 5: 14f0974c987 commit-reach: stale commits may prune generation further\n\n-- \ngitgitgadget\n"},{"id":"415744","messageId":"009f64b53c9567a94a52d1607e3ea0456776c9e1.1612183647.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"[PATCH v2 3/5] commit-reach: move compare_commits_by_gen","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-01T12:47:25Z","receivedAt":"2021-02-01T12:48:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nMove this earlier in the file so it can be used by more methods.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 30 +++++++++++++++---------------\n 1 file changed, 15 insertions(+), 15 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 053676e51d0..7bf52e94429 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -17,6 +17,21 @@\n \n static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n \n+static int compare_commits_by_gen(const void *_a, const void *_b)\n+{\n+\tconst struct commit *a = *(const struct commit * const *)_a;\n+\tconst struct commit *b = *(const struct commit * const *)_b;\n+\n+\ttimestamp_t generation_a = commit_graph_generation(a);\n+\ttimestamp_t generation_b = commit_graph_generation(b);\n+\n+\tif (generation_a < generation_b)\n+\t\treturn -1;\n+\tif (generation_a > generation_b)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n static int queue_has_nonstale(struct prio_queue *queue)\n {\n \tint i;\n@@ -651,21 +666,6 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\n \n-static int compare_commits_by_gen(const void *_a, const void *_b)\n-{\n-\tconst struct commit *a = *(const struct commit * const *)_a;\n-\tconst struct commit *b = *(const struct commit * const *)_b;\n-\n-\ttimestamp_t generation_a = commit_graph_generation(a);\n-\ttimestamp_t generation_b = commit_graph_generation(b);\n-\n-\tif (generation_a < generation_b)\n-\t\treturn -1;\n-\tif (generation_a > generation_b)\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t\t unsigned int with_flag,\n \t\t\t\t unsigned int assign_flag,\n-- \ngitgitgadget\n\n"},{"id":"415745","messageId":"2f80ae5fcb00d9d5c1b0502af45921cb20ebdf94.1612183647.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"[PATCH v2 2/5] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-01T12:47:24Z","receivedAt":"2021-02-01T12:48:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe current implementation of remove_redundant() uses several calls to\npaint_down_to_common() to determine that commits are independent of each\nother. This leads to quadratic behavior when many inputs are passed to\ncommands such as 'git merge-base'.\n\nFor example, in the Linux kernel repository, I tested the performance\nby passing all tags:\n\n git merge-base --independent $(git for-each-ref refs/tags --format=\"$(refname)\")\n\n(Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do\nnot point to commits.)\n\nHere is the performance improvement introduced by this change:\n\n Before: 16.4s\n After: 1.1s\n\nThis performance improvement requires the commit-graph file to be\npresent. We keep the old algorithm around as remove_redundant_no_gen()\nand use it when generation_numbers_enabled() is false. This is similar\nto other algorithms within commit-reach.c. The new algorithm is\nimplemented in remove_redundant_with_gen().\n\nThe basic approach is to do one commit walk instead of many. First, scan\nall commits in the list and mark their _parents_ with the STALE flag.\nThis flag will indicate commits that are reachable from one of the\ninputs, except not including themselves. Then, walk commits until\ncovering all commits up to the minimum generation number pushing the\nSTALE flag throughout.\n\nAt the end, we need to clear the STALE bit from all of the commits\nwe walked. We move the non-stale commits in 'array' to the beginning of\nthe list, and this might overwrite stale commits. However, we store an\narray of commits that started the walk, and use clear_commit_marks() on\neach of those starting commits. That method will walk the reachable\ncommits with the STALE bit and clear them all. This makes the algorithm\nsafe for re-entry or for other uses of those commits after this walk.\n\nThis logic is covered by tests in t6600-test-reach.sh, so the behavior\ndoes not change. This is tested both in the case with a commit-graph and\nwithout.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 108 +++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 100 insertions(+), 8 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9af51fe7e07..053676e51d0 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -156,15 +156,9 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n \treturn ret;\n }\n \n-static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n+static int remove_redundant_no_gen(struct repository *r,\n+\t\t\t\t struct commit **array, int cnt)\n {\n-\t/*\n-\t * Some commit in the array may be an ancestor of\n-\t * another commit. Move the independent commits to the\n-\t * beginning of 'array' and return their number. Callers\n-\t * should not rely upon the contents of 'array' after\n-\t * that number.\n-\t */\n \tstruct commit **work;\n \tunsigned char *redundant;\n \tint *filled_index;\n@@ -210,12 +204,110 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \tfor (i = filled = 0; i < cnt; i++)\n \t\tif (!redundant[i])\n \t\t\tarray[filled++] = work[i];\n+\tfor (j = filled, i = 0; i < cnt; i++)\n+\t\tif (redundant[i])\n+\t\t\tarray[j++] = work[i];\n \tfree(work);\n \tfree(redundant);\n \tfree(filled_index);\n \treturn filled;\n }\n \n+static int remove_redundant_with_gen(struct repository *r,\n+\t\t\t\t struct commit **array, int cnt)\n+{\n+\tint i, count_non_stale = 0;\n+\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tstruct commit **walk_start;\n+\tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\n+\tALLOC_ARRAY(walk_start, walk_start_alloc);\n+\n+\t/* Mark all parents of the input as STALE */\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tstruct commit_list *parents;\n+\t\ttimestamp_t generation;\n+\n+\t\trepo_parse_commit(r, array[i]);\n+\t\tparents = array[i]->parents;\n+\n+\t\twhile (parents) {\n+\t\t\trepo_parse_commit(r, parents->item);\n+\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n+\t\t\t\twalk_start[walk_start_nr++] = parents->item;\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n+\t\t\tparents = parents->next;\n+\t\t}\n+\n+\t\tgeneration = commit_graph_generation(array[i]);\n+\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n+\t}\n+\n+\t/* push the STALE bits up to min generation */\n+\twhile (queue.nr) {\n+\t\tstruct commit_list *parents;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\n+\t\trepo_parse_commit(r, c);\n+\n+\t\tif (commit_graph_generation(c) < min_generation)\n+\t\t\tcontinue;\n+\n+\t\tparents = c->parents;\n+\t\twhile (parents) {\n+\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n+\t\t\tparents = parents->next;\n+\t\t}\n+\t}\n+\n+\t/* rearrange array */\n+\tfor (i = count_non_stale = 0; i < cnt; i++) {\n+\t\tif (!(array[i]->object.flags & STALE))\n+\t\t\tarray[count_non_stale++] = array[i];\n+\t}\n+\n+\t/* clear marks */\n+\tfor (i = 0; i < walk_start_nr; i++)\n+\t\tclear_commit_marks(walk_start[i], STALE);\n+\tfree(walk_start);\n+\n+\treturn count_non_stale;\n+}\n+\n+static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n+{\n+\t/*\n+\t * Some commit in the array may be an ancestor of\n+\t * another commit. Move the independent commits to the\n+\t * beginning of 'array' and return their number. Callers\n+\t * should not rely upon the contents of 'array' after\n+\t * that number.\n+\t */\n+\tif (generation_numbers_enabled(r)) {\n+\t\tint i;\n+\n+\t\t/*\n+\t\t * If we have a single commit with finite generation\n+\t\t * number, then the _with_gen algorithm is preferred.\n+\t\t */\n+\t\tfor (i = 0; i < cnt; i++) {\n+\t\t\tif (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)\n+\t\t\t\treturn remove_redundant_with_gen(r, array, cnt);\n+\t\t}\n+\t}\n+\n+\treturn remove_redundant_no_gen(r, array, cnt);\n+}\n+\n static struct commit_list *get_merge_bases_many_0(struct repository *r,\n \t\t\t\t\t\t struct commit *one,\n \t\t\t\t\t\t int n,\n-- \ngitgitgadget\n\n"},{"id":"415746","messageId":"83feabeebb5f035059758fba1ca5cf74f3a22c91.1612183647.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"[PATCH v2 4/5] commit-reach: use heuristic in remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-01T12:47:26Z","receivedAt":"2021-02-01T12:48:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nReachability algorithms in commit-reach.c frequently benefit from using\nthe first-parent history as a heuristic for satisfying reachability\nqueries. The most obvious example was implemented in 4fbcca4e\n(commit-reach: make can_all_from_reach... linear, 2018-07-20).\n\nUpdate the walk in remove_redundant() to use this same heuristic. Here,\nwe are walking starting at the parents of the input commits. Sort those\nparents and walk from the highest generation to lower. Each time, use\nthe heuristic of searching the first parent history before continuing to\nexpand the walk.\n\nThe order in which we explore the commits matters, so update\ncompare_commits_by_gen to break generation number ties with commit date.\nThis has no effect when the commits are in a commit-graph file with\ncorrected commit dates computed, but it will assist when the commits are\nin the region \"above\" the commit-graph with \"infinite\" generation\nnumber. Note that we cannot shift to use\ncompare_commits_by_gen_then_commit_date as the method prototype is\ndifferent. We use compare_commits_by_gen for QSORT() as opposed to as a\npriority function.\n\nThe important piece is to ensure we short-circuit the walk when we find\nthat there is a single non-redundant commit. This happens frequently\nwhen looking for merge-bases or comparing several tags with 'git\nmerge-base --independent'. Use a new count 'count_still_independent' and\nif that hits 1 we can stop walking.\n\nTo update 'count_still_independent' properly, we add use of the RESULT\nflag on the input commits. Then we can detect when we reach one of these\ncommits and decrease the count. We need to remove the RESULT flag at\nthat moment because we might re-visit that commit when popping the\nstack.\n\nWe use the STALE flag to mark parents that have been added to the new\nwalk_start list, but we need to clear that flag before we start walking\nso those flags don't halt our depth-first-search walk.\n\nOn my copy of the Linux kernel repository, the performance of 'git\nmerge-base --independent ' goes from 1.1 seconds to 0.11\nseconds.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 56 insertions(+), 16 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 7bf52e94429..d3a6e2bdd04 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -29,6 +29,10 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \t\treturn -1;\n \tif (generation_a > generation_b)\n \t\treturn 1;\n+\tif (a->date < b->date)\n+\t\treturn -1;\n+\tif (a->date > b->date)\n+\t\treturn 1;\n \treturn 0;\n }\n \n@@ -231,11 +235,10 @@ static int remove_redundant_no_gen(struct repository *r,\n static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\t struct commit **array, int cnt)\n {\n-\tint i, count_non_stale = 0;\n+\tint i, count_non_stale = 0, count_still_independent = cnt;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n \tstruct commit **walk_start;\n \tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \n \tALLOC_ARRAY(walk_start, walk_start_alloc);\n \n@@ -245,6 +248,7 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\ttimestamp_t generation;\n \n \t\trepo_parse_commit(r, array[i]);\n+\t\tarray[i]->object.flags |= RESULT;\n \t\tparents = array[i]->parents;\n \n \t\twhile (parents) {\n@@ -253,7 +257,6 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\tparents->item->object.flags |= STALE;\n \t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n \t\t\t\twalk_start[walk_start_nr++] = parents->item;\n-\t\t\t\tprio_queue_put(&queue, parents->item);\n \t\t\t}\n \t\t\tparents = parents->next;\n \t\t}\n@@ -264,26 +267,63 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\tmin_generation = generation;\n \t}\n \n-\t/* push the STALE bits up to min generation */\n-\twhile (queue.nr) {\n-\t\tstruct commit_list *parents;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\tQSORT(walk_start, walk_start_nr, compare_commits_by_gen);\n \n-\t\trepo_parse_commit(r, c);\n+\t/* remove STALE bit for now to allow walking through parents */\n+\tfor (i = 0; i < walk_start_nr; i++)\n+\t\twalk_start[i]->object.flags &= ~STALE;\n \n-\t\tif (commit_graph_generation(c) < min_generation)\n-\t\t\tcontinue;\n+\t/*\n+\t * Start walking from the highest generation. Hopefully, it will\n+\t * find all other items during the first-parent walk, and we can\n+\t * terminate early. Otherwise, we will do the same amount of work\n+\t * as before.\n+\t */\n+\tfor (i = walk_start_nr - 1; i >= 0 && count_still_independent > 1; i--) {\n+\t\t/* push the STALE bits up to min generation */\n+\t\tstruct commit_list *stack = NULL;\n \n-\t\tparents = c->parents;\n-\t\twhile (parents) {\n-\t\t\tif (!(parents->item->object.flags & STALE)) {\n-\t\t\t\tparents->item->object.flags |= STALE;\n-\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\tcommit_list_insert(walk_start[i], &stack);\n+\t\twalk_start[i]->object.flags |= STALE;\n+\n+\t\twhile (stack) {\n+\t\t\tstruct commit_list *parents;\n+\t\t\tstruct commit *c = stack->item;\n+\n+\t\t\trepo_parse_commit(r, c);\n+\n+\t\t\tif (c->object.flags & RESULT) {\n+\t\t\t\tc->object.flags &= ~RESULT;\n+\t\t\t\tif (--count_still_independent <= 1)\n+\t\t\t\t\tbreak;\n \t\t\t}\n-\t\t\tparents = parents->next;\n+\n+\t\t\tif (commit_graph_generation(c) < min_generation) {\n+\t\t\t\tpop_commit(&stack);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tparents = c->parents;\n+\t\t\twhile (parents) {\n+\t\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\t\tcommit_list_insert(parents->item, &stack);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t\tparents = parents->next;\n+\t\t\t}\n+\n+\t\t\t/* pop if all parents have been visited already */\n+\t\t\tif (!parents)\n+\t\t\t\tpop_commit(&stack);\n \t\t}\n+\t\tfree_commit_list(stack);\n \t}\n \n+\t/* clear result */\n+\tfor (i = 0; i < cnt; i++)\n+\t\tarray[i]->object.flags &= ~RESULT;\n+\n \t/* rearrange array */\n \tfor (i = count_non_stale = 0; i < cnt; i++) {\n \t\tif (!(array[i]->object.flags & STALE))\n-- \ngitgitgadget\n\n"},{"id":"415747","messageId":"14f0974c987215bd36e91450c1a6ebc6d5732121.1612183647.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"[PATCH v2 5/5] commit-reach: stale commits may prune generation further","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-01T12:47:27Z","receivedAt":"2021-02-01T12:49:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe remove_redundant_with_gen() algorithm performs a depth-first-search\nto find commits in the 'array' list, starting at the parents of each\ncommit in 'array'. The result is that commits in 'array' are marked\nSTALE when they are reachable from another commit in 'array'.\n\nThis depth-first-search is fast when commits lie on or near the\nfirst-parent history of the higher commits. The search terminates early\nif all but one commit becomes marked STALE.\n\nHowever, it is possible that there are two independent commits with high\ngeneration number. In that case, the depth-first-search might languish\nby searching in lower generations due to the fixed min_generation used\nthroughout the method.\n\nWith the expectation that commits with lower generation are expected to\nbecome STALE more often, we can optimize further by increasing that\nmin_generation boundary upon discovery of the commit with minimum\ngeneration.\n\nWe must first sort the commits in 'array' by generation. We cannot sort\n'array' itself since it must preserve relative order among the returned\nresults (see revision.c:mark_redundant_parents() for an example).\n\nThis simplifies the initialization of min_generation, but it also allows\nus to increase the new min_generation when we find the commit with\nsmallest generation remaining.\n\nThis requires more than two commits in order to test, so I used the\nLinux kernel repository with a few commits that are slightly off of the\nfirst-parent history. I timed the following command:\n\n git merge-base --independent 2ecedd756908 d2360a398f0b \\\n\t1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e\n\nThe first two commits have similar generation and are near the v5.10\ntag. Commit 160bab43419e is off of the first-parent history behind v5.5,\nwhile the others are scattered somewhere reachable from v5.9. This is\ndesigned to demonstrate the optimization, as that commit within v5.5\nwould normally cause a lot of extra commit walking.\n\nSince remove_redundant_with_alg() is called only when at least one of\nthe input commits has a finite generation number, this algorithm is\ntested with a commit-graph generated starting at a number of different\ntags, the earliest being v5.5.\n\ncommit-graph at v5.5:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 864ms |\n | *_with_gen() (before) | 858ms |\n | *_with_gen() (after) | 810ms |\n\ncommit-graph at v5.7:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 625ms |\n | *_with_gen() (before) | 572ms |\n | *_with_gen() (after) | 517ms |\n\ncommit-graph at v5.9:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 268ms |\n | *_with_gen() (before) | 224ms |\n | *_with_gen() (after) | 202ms |\n\ncommit-graph at v5.10:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 72ms |\n | *_with_gen() (before) | 37ms |\n | *_with_gen() (after) | 9ms |\n\nNote that these are only modest improvements for the case where the two\nindependent commits are not in the commit-graph (not until v5.10). All\nalgorithms get faster as more commits are indexed, which is not a\nsurprise. However, the cost of walking extra commits is more and more\nprevalent in relative terms as more commits are indexed. Finally, the\nlast case allows us to jump to the minimum generation between the last\ntwo commits (that are actually independent) so we greatly reduce the\ncost in that case.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 28 +++++++++++++++++++++-------\n 1 file changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a6e2bdd04..c2e0747fea4 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -237,15 +237,27 @@ static int remove_redundant_with_gen(struct repository *r,\n {\n \tint i, count_non_stale = 0, count_still_independent = cnt;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n-\tstruct commit **walk_start;\n+\tstruct commit **walk_start, **sorted;\n \tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n+\tint min_gen_pos = 0;\n+\n+\t/*\n+\t * Sort the input by generation number, ascending. This allows\n+\t * us to increase the \"min_generation\" limit when we discover\n+\t * the commit with lowest generation is STALE. The index\n+\t * min_gen_pos points to the current position within 'array'\n+\t * that is not yet known to be STALE.\n+\t */\n+\tALLOC_ARRAY(sorted, cnt);\n+\tCOPY_ARRAY(sorted, array, cnt);\n+\tQSORT(sorted, cnt, compare_commits_by_gen);\n+\tmin_generation = commit_graph_generation(sorted[0]);\n \n \tALLOC_ARRAY(walk_start, walk_start_alloc);\n \n \t/* Mark all parents of the input as STALE */\n \tfor (i = 0; i < cnt; i++) {\n \t\tstruct commit_list *parents;\n-\t\ttimestamp_t generation;\n \n \t\trepo_parse_commit(r, array[i]);\n \t\tarray[i]->object.flags |= RESULT;\n@@ -260,11 +272,6 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\t}\n \t\t\tparents = parents->next;\n \t\t}\n-\n-\t\tgeneration = commit_graph_generation(array[i]);\n-\n-\t\tif (generation < min_generation)\n-\t\t\tmin_generation = generation;\n \t}\n \n \tQSORT(walk_start, walk_start_nr, compare_commits_by_gen);\n@@ -296,6 +303,12 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\tc->object.flags &= ~RESULT;\n \t\t\t\tif (--count_still_independent <= 1)\n \t\t\t\t\tbreak;\n+\t\t\t\tif (oideq(&c->object.oid, &sorted[min_gen_pos]->object.oid)) {\n+\t\t\t\t\twhile (min_gen_pos < cnt - 1 &&\n+\t\t\t\t\t (sorted[min_gen_pos]->object.flags & STALE))\n+\t\t\t\t\t\tmin_gen_pos++;\n+\t\t\t\t\tmin_generation = commit_graph_generation(sorted[min_gen_pos]);\n+\t\t\t\t}\n \t\t\t}\n \n \t\t\tif (commit_graph_generation(c) < min_generation) {\n@@ -319,6 +332,7 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t}\n \t\tfree_commit_list(stack);\n \t}\n+\tfree(sorted);\n \n \t/* clear result */\n \tfor (i = 0; i < cnt; i++)\n-- \ngitgitgadget\n"},{"id":"415761","messageId":"7a1a8990-59e7-d538-d382-446fdc270810@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/5] Speed up remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-02-01T15:48:02Z","receivedAt":"2021-02-01T15:48:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/1/2021 7:47 AM, Derrick Stolee via GitGitGadget wrote:\n> My tests were on the Linux kernel repository, testing this command:\n> \n> git merge-base --independent $(git for-each-ref refs/tags --format=\"%(refname)\")\n> \n> Before: 16.4s\n> After Patch 1: 1.1s\n> After Patch 2: 0.1s\n\nDuring my testing of v2, I discovered how remove_redundant()\nis being used as part of 'git log --simplify-merges'. So, here\nare some performance numbers for the Linux kernel repository\nwith a full commit-graph and changed-path Bloom filters running\n\n git log --oneline -n10 --simplify-merges -- kernel/\n\nBenchmark #1: old\n Time (mean ± σ): 5.770 s ± 0.030 s [User: 5.551 s, System: 0.219 s]\n Range (min … max): 5.728 s … 5.827 s 10 runs\n \nBenchmark #2: new\n Time (mean ± σ): 5.030 s ± 0.017 s [User: 4.805 s, System: 0.224 s]\n Range (min … max): 4.999 s … 5.054 s 10 runs\n \nSummary\n 'new' ran\n 1.15 ± 0.01 times faster than 'old'\n\nThanks,\n-Stolee\n"},{"id":"415764","messageId":"419ddcca-8534-8dc5-bcd8-1e244414bcf1@web.de","threadId":"55069","inReplyTo":"2f80ae5fcb00d9d5c1b0502af45921cb20ebdf94.1612183647.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/5] commit-reach: use one walk in remove_redundant()","fromName":"René Scharfe.","fromEmail":"l.s.r@web.de","sentAt":"2021-02-01T16:12:37Z","receivedAt":"2021-02-01T16:23:02Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 01.02.21 um 13:47 schrieb Derrick Stolee via GitGitGadget:\n> @@ -210,12 +204,110 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n> \tfor (i = filled = 0; i < cnt; i++)\n> \t\tif (!redundant[i])\n> \t\t\tarray[filled++] = work[i];\n> +\tfor (j = filled, i = 0; i < cnt; i++)\n> +\t\tif (redundant[i])\n> +\t\t\tarray[j++] = work[i];\n\nThis puts the loop back in that you removed in the previous commit.\nIntentionally?\n\n> \tfree(work);\n> \tfree(redundant);\n> \tfree(filled_index);\n> \treturn filled;\n> }\n>\n> +static int remove_redundant_with_gen(struct repository *r,\n> +\t\t\t\t struct commit **array, int cnt)\n> +{\n> +\tint i, count_non_stale = 0;\n> +\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n> +\tstruct commit **walk_start;\n> +\tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> +\n> +\tALLOC_ARRAY(walk_start, walk_start_alloc);\n> +\n> +\t/* Mark all parents of the input as STALE */\n> +\tfor (i = 0; i < cnt; i++) {\n> +\t\tstruct commit_list *parents;\n> +\t\ttimestamp_t generation;\n> +\n> +\t\trepo_parse_commit(r, array[i]);\n> +\t\tparents = array[i]->parents;\n> +\n> +\t\twhile (parents) {\n> +\t\t\trepo_parse_commit(r, parents->item);\n> +\t\t\tif (!(parents->item->object.flags & STALE)) {\n> +\t\t\t\tparents->item->object.flags |= STALE;\n> +\t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n> +\t\t\t\twalk_start[walk_start_nr++] = parents->item;\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n> +\t\t\t}\n> +\t\t\tparents = parents->next;\n> +\t\t}\n> +\n> +\t\tgeneration = commit_graph_generation(array[i]);\n> +\n> +\t\tif (generation < min_generation)\n> +\t\t\tmin_generation = generation;\n> +\t}\n> +\n> +\t/* push the STALE bits up to min generation */\n> +\twhile (queue.nr) {\n> +\t\tstruct commit_list *parents;\n> +\t\tstruct commit *c = prio_queue_get(&queue);\n> +\n> +\t\trepo_parse_commit(r, c);\n> +\n> +\t\tif (commit_graph_generation(c) < min_generation)\n> +\t\t\tcontinue;\n> +\n> +\t\tparents = c->parents;\n> +\t\twhile (parents) {\n> +\t\t\tif (!(parents->item->object.flags & STALE)) {\n> +\t\t\t\tparents->item->object.flags |= STALE;\n> +\t\t\t\tprio_queue_put(&queue, parents->item);\n> +\t\t\t}\n> +\t\t\tparents = parents->next;\n> +\t\t}\n> +\t}\n> +\n> +\t/* rearrange array */\n> +\tfor (i = count_non_stale = 0; i < cnt; i++) {\n> +\t\tif (!(array[i]->object.flags & STALE))\n\nHere I would have added another condition, count_non_stale != i, to\navoid self-assignment (array[x] = array[x]). The code works without\nit, though. Not sure if there is a performance benefit to be had --\nbranch vs. pointer copy. Probably not worth it..\n\n> +\t\t\tarray[count_non_stale++] = array[i];\n> +\t}\n> +\n> +\t/* clear marks */\n> +\tfor (i = 0; i < walk_start_nr; i++)\n> +\t\tclear_commit_marks(walk_start[i], STALE);\n\nYou can replace this loop with a call to clear_commit_marks_many().\n\n> +\tfree(walk_start);\n> +\n> +\treturn count_non_stale;\n> +}\n> +\n> +static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n> +{\n> +\t/*\n> +\t * Some commit in the array may be an ancestor of\n> +\t * another commit. Move the independent commits to the\n> +\t * beginning of 'array' and return their number. Callers\n> +\t * should not rely upon the contents of 'array' after\n> +\t * that number.\n> +\t */\n> +\tif (generation_numbers_enabled(r)) {\n> +\t\tint i;\n> +\n> +\t\t/*\n> +\t\t * If we have a single commit with finite generation\n> +\t\t * number, then the _with_gen algorithm is preferred.\n> +\t\t */\n> +\t\tfor (i = 0; i < cnt; i++) {\n> +\t\t\tif (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)\n> +\t\t\t\treturn remove_redundant_with_gen(r, array, cnt);\n> +\t\t}\n> +\t}\n> +\n> +\treturn remove_redundant_no_gen(r, array, cnt);\n> +}\n> +\n> static struct commit_list *get_merge_bases_many_0(struct repository *r,\n> \t\t\t\t\t\t struct commit *one,\n> \t\t\t\t\t\t int n,\n>\n"},{"id":"415765","messageId":"5236b427-d10c-acaf-e8c4-97011bc68c49@gmail.com","threadId":"55069","inReplyTo":"419ddcca-8534-8dc5-bcd8-1e244414bcf1@web.de","subject":"Re: [PATCH v2 2/5] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-02-01T16:31:11Z","receivedAt":"2021-02-01T16:32:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/1/2021 11:12 AM, René Scharfe. wrote:\n> Am 01.02.21 um 13:47 schrieb Derrick Stolee via GitGitGadget:\n>> @@ -210,12 +204,110 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n>> \tfor (i = filled = 0; i < cnt; i++)\n>> \t\tif (!redundant[i])\n>> \t\t\tarray[filled++] = work[i];\n>> +\tfor (j = filled, i = 0; i < cnt; i++)\n>> +\t\tif (redundant[i])\n>> +\t\t\tarray[j++] = work[i];\n> \n> This puts the loop back in that you removed in the previous commit.\n> Intentionally?\n\nNot intentional. Thanks for noticing.\n\n>> +\t/* rearrange array */\n>> +\tfor (i = count_non_stale = 0; i < cnt; i++) {\n>> +\t\tif (!(array[i]->object.flags & STALE))\n> \n> Here I would have added another condition, count_non_stale != i, to\n> avoid self-assignment (array[x] = array[x]). The code works without\n> it, though. Not sure if there is a performance benefit to be had --> branch vs. pointer copy. Probably not worth it..\n\nYou are correct, but I'm going to go on the side of not worth it.\n\n>> +\t\t\tarray[count_non_stale++] = array[i];\n>> +\t}\n>> +\n>> +\t/* clear marks */\n>> +\tfor (i = 0; i < walk_start_nr; i++)\n>> +\t\tclear_commit_marks(walk_start[i], STALE);\n> \n> You can replace this loop with a call to clear_commit_marks_many().\n\nRight! Earlier I was using a 'struct commit_list *' which would not\nwork, but this 'struct commit ** walk_start' does work. Thanks.\n\n-Stolee\n"},{"id":"415806","messageId":"xmqqmtwnlg6f.fsf@gitster.c.googlers.com","threadId":"55069","inReplyTo":"649f6799e6bfa0662ed5a4debf915053598fe142.1612183647.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/5] commit-reach: reduce requirements for remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-01T19:51:52Z","receivedAt":"2021-02-01T19:52:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> Remove a comment at the beggining of remove_redundant() that mentions a\n> reordering of the input array to have the initial segment be the\n> independent commits and the final segment be the redundant commits.\n> While this behavior is followed in remove_redundant(), no callers rely\n> on that behavior.\n>\n> Remove the final loop that copies this final segment and update the\n> comment to match the new behavior.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n\nMakes sense, especially since this is a file-local/static helper\nfunction, we have reasonably tight control over its callers.\n\nWill queue. Thanks.\n\n> commit-reach.c | 10 ++++------\n> 1 file changed, 4 insertions(+), 6 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index e38771ca5a1..9af51fe7e07 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -160,9 +160,10 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n> {\n> \t/*\n> \t * Some commit in the array may be an ancestor of\n> -\t * another commit. Move such commit to the end of\n> -\t * the array, and return the number of commits that\n> -\t * are independent from each other.\n> +\t * another commit. Move the independent commits to the\n> +\t * beginning of 'array' and return their number. Callers\n> +\t * should not rely upon the contents of 'array' after\n> +\t * that number.\n> \t */\n> \tstruct commit **work;\n> \tunsigned char *redundant;\n> @@ -209,9 +210,6 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n> \tfor (i = filled = 0; i < cnt; i++)\n> \t\tif (!redundant[i])\n> \t\t\tarray[filled++] = work[i];\n> -\tfor (j = filled, i = 0; i < cnt; i++)\n> -\t\tif (redundant[i])\n> -\t\t\tarray[j++] = work[i];\n> \tfree(work);\n> \tfree(redundant);\n> \tfree(filled_index);\n"},{"id":"415808","messageId":"xmqqczxjlfj1.fsf@gitster.c.googlers.com","threadId":"55069","inReplyTo":"83feabeebb5f035059758fba1ca5cf74f3a22c91.1612183647.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-01T20:05:54Z","receivedAt":"2021-02-01T20:07:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> The important piece is to ensure we short-circuit the walk when we find\n> that there is a single non-redundant commit. This happens frequently\n> when looking for merge-bases or comparing several tags with 'git\n> merge-base --independent'. Use a new count 'count_still_independent' and\n> if that hits 1 we can stop walking.\n\nThat is because when you are left one single thing, it may be able\nto reach many other things, but the fact that it by itself won't be\nreachable by remaining independent things will not change (because,\nthat sole remaining independent thing is itself)?\n\n> To update 'count_still_independent' properly, we add use of the RESULT\n> flag on the input commits. Then we can detect when we reach one of these\n> commits and decrease the count. We need to remove the RESULT flag at\n> that moment because we might re-visit that commit when popping the\n> stack.\n>\n> We use the STALE flag to mark parents that have been added to the new\n> walk_start list, but we need to clear that flag before we start walking\n> so those flags don't halt our depth-first-search walk.\n>\n> On my copy of the Linux kernel repository, the performance of 'git\n> merge-base --independent ' goes from 1.1 seconds to 0.11\n> seconds.\n\nThese two numbers are with commit-graph fully populated with usable\ngeneration numbers, I presume, and it is quite impressive.\n\n"},{"id":"415815","messageId":"bd00470c-59d6-52a8-9b2c-dc9e3a0beb82@gmail.com","threadId":"55069","inReplyTo":"xmqqczxjlfj1.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-02-01T21:02:32Z","receivedAt":"2021-02-01T21:03:34Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/1/2021 3:05 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> The important piece is to ensure we short-circuit the walk when we find\n>> that there is a single non-redundant commit. This happens frequently\n>> when looking for merge-bases or comparing several tags with 'git\n>> merge-base --independent'. Use a new count 'count_still_independent' and\n>> if that hits 1 we can stop walking.\n> \n> That is because when you are left one single thing, it may be able\n> to reach many other things, but the fact that it by itself won't be\n> reachable by remaining independent things will not change (because,\n> that sole remaining independent thing is itself)?\n\nRight. If there is only one non-STALE input commit left, then it will\nbe the only returned result. We will never find that all commits are\nredundant because the commit graph is acyclic. The performance\nimprovement comes from halting the DFS walk: there might be more\ncommits to walk but they won't change the result.\n\n>> To update 'count_still_independent' properly, we add use of the RESULT\n>> flag on the input commits. Then we can detect when we reach one of these\n>> commits and decrease the count. We need to remove the RESULT flag at\n>> that moment because we might re-visit that commit when popping the\n>> stack.\n>>\n>> We use the STALE flag to mark parents that have been added to the new\n>> walk_start list, but we need to clear that flag before we start walking\n>> so those flags don't halt our depth-first-search walk.\n>>\n>> On my copy of the Linux kernel repository, the performance of 'git\n>> merge-base --independent ' goes from 1.1 seconds to 0.11\n>> seconds.\n> \n> These two numbers are with commit-graph fully populated with usable\n> generation numbers, I presume, and it is quite impressive.\n \nYes, these numbers are with a full commit-graph.\n\nThanks,\n-Stolee\n"},{"id":"416058","messageId":"YBrISQ/5/pJKgGGZ@nand.local","threadId":"55069","inReplyTo":"14f0974c987215bd36e91450c1a6ebc6d5732121.1612183647.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 5/5] commit-reach: stale commits may prune generation further","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-02-03T15:59:05Z","receivedAt":"2021-02-03T16:00:26Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Feb 01, 2021 at 12:47:27PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> Note that these are only modest improvements for the case where the two\n> independent commits are not in the commit-graph (not until v5.10). All\n> algorithms get faster as more commits are indexed, which is not a\n> surprise. However, the cost of walking extra commits is more and more\n> prevalent in relative terms as more commits are indexed. Finally, the\n> last case allows us to jump to the minimum generation between the last\n> two commits (that are actually independent) so we greatly reduce the\n> cost in that case.\n\nVery nice. The explanation and implementation makes sense to me.\n\n> Signed-off-by: Derrick Stolee \n> ---\n> commit-reach.c | 28 +++++++++++++++++++++-------\n> 1 file changed, 21 insertions(+), 7 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index d3a6e2bdd04..c2e0747fea4 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -237,15 +237,27 @@ static int remove_redundant_with_gen(struct repository *r,\n> {\n> \tint i, count_non_stale = 0, count_still_independent = cnt;\n> \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n> -\tstruct commit **walk_start;\n> +\tstruct commit **walk_start, **sorted;\n> \tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n> +\tint min_gen_pos = 0;\n> +\n> +\t/*\n> +\t * Sort the input by generation number, ascending. This allows\n> +\t * us to increase the \"min_generation\" limit when we discover\n> +\t * the commit with lowest generation is STALE. The index\n> +\t * min_gen_pos points to the current position within 'array'\n> +\t * that is not yet known to be STALE.\n> +\t */\n> +\tALLOC_ARRAY(sorted, cnt);\n> +\tCOPY_ARRAY(sorted, array, cnt);\n> +\tQSORT(sorted, cnt, compare_commits_by_gen);\n> +\tmin_generation = commit_graph_generation(sorted[0]);\n\nThis line caught my eye, but we return early in\ncommit-reach.c:reduce_heads() before even calling remove_redundant()\n(which itself calls remove_redundant_with_gen()), so it's always OK to\nassume that we have at least one element in 'array'.\n\nThis patch and the others in v2 all look good to me.\n\nThanks,\nTaylor\n"},{"id":"417372","messageId":"xmqq8s7lc61j.fsf@gitster.g","threadId":"55069","inReplyTo":"7a1a8990-59e7-d538-d382-446fdc270810@gmail.com","subject":"Re: [PATCH v2 0/5] Speed up remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-18T23:25:28Z","receivedAt":"2021-02-18T23:26:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 2/1/2021 7:47 AM, Derrick Stolee via GitGitGadget wrote:\n>> My tests were on the Linux kernel repository, testing this command:\n>> \n>> git merge-base --independent $(git for-each-ref refs/tags --format=\"%(refname)\")\n>> \n>> Before: 16.4s\n>> After Patch 1: 1.1s\n>> After Patch 2: 0.1s\n>\n> During my testing of v2, I discovered how remove_redundant()\n> is being used as part of 'git log --simplify-merges'. So, here\n> are some performance numbers for the Linux kernel repository\n> with a full commit-graph and changed-path Bloom filters running\n>\n> git log --oneline -n10 --simplify-merges -- kernel/\n>\n> Benchmark #1: old\n> Time (mean ± σ): 5.770 s ± 0.030 s [User: 5.551 s, System: 0.219 s]\n> Range (min … max): 5.728 s … 5.827 s 10 runs\n> \n> Benchmark #2: new\n> Time (mean ± σ): 5.030 s ± 0.017 s [User: 4.805 s, System: 0.224 s]\n> Range (min … max): 4.999 s … 5.054 s 10 runs\n> \n> Summary\n> 'new' ran\n> 1.15 ± 0.01 times faster than 'old'\n\n\nThis topic seems to have been forgotten? Is the only thing missing\nis an updated 2/5 or is there anything more that is needed?\n"},{"id":"417395","messageId":"4ca2931f-3e3c-12d5-e12a-6c63699a98d7@gmail.com","threadId":"55069","inReplyTo":"xmqq8s7lc61j.fsf@gitster.g","subject":"Re: [PATCH v2 0/5] Speed up remove_redundant()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-02-19T12:17:32Z","receivedAt":"2021-02-19T12:18:34Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/18/2021 6:25 PM, Junio C Hamano wrote:\n> This topic seems to have been forgotten? Is the only thing missing\n> is an updated 2/5 or is there anything more that is needed?\n \nI had forgotten about the comments on patch 2/5, sorry. That explains\nwhy it hasn't merged yet...\n\nI'll get right on it.\n\nThanks,\n-Stolee\n"},{"id":"417396","messageId":"649f6799e6bfa0662ed5a4debf915053598fe142.1613738051.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v3.git.1613738051.gitgitgadget@gmail.com","subject":"[PATCH v3 1/5] commit-reach: reduce requirements for remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-19T12:34:06Z","receivedAt":"2021-02-19T12:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nRemove a comment at the beggining of remove_redundant() that mentions a\nreordering of the input array to have the initial segment be the\nindependent commits and the final segment be the redundant commits.\nWhile this behavior is followed in remove_redundant(), no callers rely\non that behavior.\n\nRemove the final loop that copies this final segment and update the\ncomment to match the new behavior.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 10 ++++------\n 1 file changed, 4 insertions(+), 6 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex e38771ca5a1f..9af51fe7e078 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -160,9 +160,10 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n {\n \t/*\n \t * Some commit in the array may be an ancestor of\n-\t * another commit. Move such commit to the end of\n-\t * the array, and return the number of commits that\n-\t * are independent from each other.\n+\t * another commit. Move the independent commits to the\n+\t * beginning of 'array' and return their number. Callers\n+\t * should not rely upon the contents of 'array' after\n+\t * that number.\n \t */\n \tstruct commit **work;\n \tunsigned char *redundant;\n@@ -209,9 +210,6 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \tfor (i = filled = 0; i < cnt; i++)\n \t\tif (!redundant[i])\n \t\t\tarray[filled++] = work[i];\n-\tfor (j = filled, i = 0; i < cnt; i++)\n-\t\tif (redundant[i])\n-\t\t\tarray[j++] = work[i];\n \tfree(work);\n \tfree(redundant);\n \tfree(filled_index);\n-- \ngitgitgadget\n\n"},{"id":"417397","messageId":"pull.852.v3.git.1613738051.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v2.git.1612183647.gitgitgadget@gmail.com","subject":"[PATCH v3 0/5] Speed up remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-19T12:34:05Z","receivedAt":"2021-02-19T12:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Michael Haggerty pointed out that git merge-base --independent is quite slow\nwhen many commits are provided in the input. This boils down to some\nquadratic behavior in remove_redundant() because it calls\npaint_down_to_common() in a loop.\n\nThis series avoids that by using a single commit walk, pushing a flag that\nmeans \"this commit is reachable from a parent of a commit in the list.\" At\nthe end of the walk, the input commits without that flag are independent.\n\nThere is an extra performance enhancement using the first-parent history as\na heuristic. This helps only when there is a single independent result, as\nwe can short circuit the walk when all other inputs are found to be\nreachable from the top one. It also gets faster when we discover the commit\nwith lowest generation and can restrict our walk further to the next-lowest\ngeneration number.\n\nMy tests were on the Linux kernel repository, testing this command:\n\n git merge-base --independent $(git for-each-ref refs/tags --format=\"%(refname)\")\n\n Before: 16.4s\nAfter Patch 1: 1.1s\nAfter Patch 2: 0.1s\n\n\nThis does not change the correctness of the function. It is tested carefully\nin t6600-test-reach.c, among existing merge-base tests. There are also more\ntests in scripts like t6012-rev-list-simplify.sh that trigger the new logic\nunder GIT_TEST_COMMIT_GRAPH=1.\n\n\nUpdates in V3\n=============\n\n * Patch 2 is updated to René's comments. Sorry I dropped the ball on this.\n I had the changes locally, but never pushed them until now.\n\n\nUpdates in V2\n=============\n\n * The old algorithm is not entirely removed. It is still faster than the\n new algorithm if all input commits are not in the commit-graph file\n (unless the commit-graph file is really close to the input commits, but\n that is an unreasonable expectation). Now, the new logic only happens if\n there is an input commit with finite generation number.\n\n * There was a copy of 'array' being used for the final reorder which is now\n removed. We still need to be careful about the RESULT bit.\n\n * The final patch is new, adding yet another speedup in the form of\n increasing the min_generation cutoff when we find the input commit of\n smallest generation. This can reduce the time significantly when given\n many inputs. This does require copying the 'array' again, so we can sort\n by generation number while preserving the original order of 'array' which\n is required by some callers.\n\nThanks, -Stolee\n\nDerrick Stolee (5):\n commit-reach: reduce requirements for remove_redundant()\n commit-reach: use one walk in remove_redundant()\n commit-reach: move compare_commits_by_gen\n commit-reach: use heuristic in remove_redundant()\n commit-reach: stale commits may prune generation further\n\n commit-reach.c | 190 ++++++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 165 insertions(+), 25 deletions(-)\n\n\nbase-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/852\n\nRange-diff vs v2:\n\n 1: 649f6799e6bf = 1: 649f6799e6bf commit-reach: reduce requirements for remove_redundant()\n 2: 2f80ae5fcb00 ! 2: c2c08989ce60 commit-reach: use one walk in remove_redundant()\n @@ commit-reach.c: struct commit_list *get_octopus_merge_bases(struct commit_list *\n \tunsigned char *redundant;\n \tint *filled_index;\n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt\n - \tfor (i = filled = 0; i < cnt; i++)\n - \t\tif (!redundant[i])\n - \t\t\tarray[filled++] = work[i];\n -+\tfor (j = filled, i = 0; i < cnt; i++)\n -+\t\tif (redundant[i])\n -+\t\t\tarray[j++] = work[i];\n - \tfree(work);\n - \tfree(redundant);\n - \tfree(filled_index);\n \treturn filled;\n }\n \n @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit\n +\t}\n +\n +\t/* clear marks */\n -+\tfor (i = 0; i < walk_start_nr; i++)\n -+\t\tclear_commit_marks(walk_start[i], STALE);\n ++\tclear_commit_marks_many(walk_start_nr, walk_start, STALE);\n +\tfree(walk_start);\n +\n +\treturn count_non_stale;\n 3: 009f64b53c95 = 3: 1d3c5ebbb632 commit-reach: move compare_commits_by_gen\n 4: 83feabeebb5f = 4: c1fc174d42aa commit-reach: use heuristic in remove_redundant()\n 5: 14f0974c9872 = 5: 539db83bd735 commit-reach: stale commits may prune generation further\n\n-- \ngitgitgadget\n"},{"id":"417398","messageId":"539db83bd7355d8b3a474ed7b577f4112e3ce1e0.1613738051.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v3.git.1613738051.gitgitgadget@gmail.com","subject":"[PATCH v3 5/5] commit-reach: stale commits may prune generation further","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-19T12:34:10Z","receivedAt":"2021-02-19T12:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe remove_redundant_with_gen() algorithm performs a depth-first-search\nto find commits in the 'array' list, starting at the parents of each\ncommit in 'array'. The result is that commits in 'array' are marked\nSTALE when they are reachable from another commit in 'array'.\n\nThis depth-first-search is fast when commits lie on or near the\nfirst-parent history of the higher commits. The search terminates early\nif all but one commit becomes marked STALE.\n\nHowever, it is possible that there are two independent commits with high\ngeneration number. In that case, the depth-first-search might languish\nby searching in lower generations due to the fixed min_generation used\nthroughout the method.\n\nWith the expectation that commits with lower generation are expected to\nbecome STALE more often, we can optimize further by increasing that\nmin_generation boundary upon discovery of the commit with minimum\ngeneration.\n\nWe must first sort the commits in 'array' by generation. We cannot sort\n'array' itself since it must preserve relative order among the returned\nresults (see revision.c:mark_redundant_parents() for an example).\n\nThis simplifies the initialization of min_generation, but it also allows\nus to increase the new min_generation when we find the commit with\nsmallest generation remaining.\n\nThis requires more than two commits in order to test, so I used the\nLinux kernel repository with a few commits that are slightly off of the\nfirst-parent history. I timed the following command:\n\n git merge-base --independent 2ecedd756908 d2360a398f0b \\\n\t1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e\n\nThe first two commits have similar generation and are near the v5.10\ntag. Commit 160bab43419e is off of the first-parent history behind v5.5,\nwhile the others are scattered somewhere reachable from v5.9. This is\ndesigned to demonstrate the optimization, as that commit within v5.5\nwould normally cause a lot of extra commit walking.\n\nSince remove_redundant_with_alg() is called only when at least one of\nthe input commits has a finite generation number, this algorithm is\ntested with a commit-graph generated starting at a number of different\ntags, the earliest being v5.5.\n\ncommit-graph at v5.5:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 864ms |\n | *_with_gen() (before) | 858ms |\n | *_with_gen() (after) | 810ms |\n\ncommit-graph at v5.7:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 625ms |\n | *_with_gen() (before) | 572ms |\n | *_with_gen() (after) | 517ms |\n\ncommit-graph at v5.9:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 268ms |\n | *_with_gen() (before) | 224ms |\n | *_with_gen() (after) | 202ms |\n\ncommit-graph at v5.10:\n\n | Method | Time |\n |-----------------------+-------|\n | *_no_gen() | 72ms |\n | *_with_gen() (before) | 37ms |\n | *_with_gen() (after) | 9ms |\n\nNote that these are only modest improvements for the case where the two\nindependent commits are not in the commit-graph (not until v5.10). All\nalgorithms get faster as more commits are indexed, which is not a\nsurprise. However, the cost of walking extra commits is more and more\nprevalent in relative terms as more commits are indexed. Finally, the\nlast case allows us to jump to the minimum generation between the last\ntwo commits (that are actually independent) so we greatly reduce the\ncost in that case.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 28 +++++++++++++++++++++-------\n 1 file changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 399f2a8673e0..2ea84d3dc074 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -234,15 +234,27 @@ static int remove_redundant_with_gen(struct repository *r,\n {\n \tint i, count_non_stale = 0, count_still_independent = cnt;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n-\tstruct commit **walk_start;\n+\tstruct commit **walk_start, **sorted;\n \tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n+\tint min_gen_pos = 0;\n+\n+\t/*\n+\t * Sort the input by generation number, ascending. This allows\n+\t * us to increase the \"min_generation\" limit when we discover\n+\t * the commit with lowest generation is STALE. The index\n+\t * min_gen_pos points to the current position within 'array'\n+\t * that is not yet known to be STALE.\n+\t */\n+\tALLOC_ARRAY(sorted, cnt);\n+\tCOPY_ARRAY(sorted, array, cnt);\n+\tQSORT(sorted, cnt, compare_commits_by_gen);\n+\tmin_generation = commit_graph_generation(sorted[0]);\n \n \tALLOC_ARRAY(walk_start, walk_start_alloc);\n \n \t/* Mark all parents of the input as STALE */\n \tfor (i = 0; i < cnt; i++) {\n \t\tstruct commit_list *parents;\n-\t\ttimestamp_t generation;\n \n \t\trepo_parse_commit(r, array[i]);\n \t\tarray[i]->object.flags |= RESULT;\n@@ -257,11 +269,6 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\t}\n \t\t\tparents = parents->next;\n \t\t}\n-\n-\t\tgeneration = commit_graph_generation(array[i]);\n-\n-\t\tif (generation < min_generation)\n-\t\t\tmin_generation = generation;\n \t}\n \n \tQSORT(walk_start, walk_start_nr, compare_commits_by_gen);\n@@ -293,6 +300,12 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\tc->object.flags &= ~RESULT;\n \t\t\t\tif (--count_still_independent <= 1)\n \t\t\t\t\tbreak;\n+\t\t\t\tif (oideq(&c->object.oid, &sorted[min_gen_pos]->object.oid)) {\n+\t\t\t\t\twhile (min_gen_pos < cnt - 1 &&\n+\t\t\t\t\t (sorted[min_gen_pos]->object.flags & STALE))\n+\t\t\t\t\t\tmin_gen_pos++;\n+\t\t\t\t\tmin_generation = commit_graph_generation(sorted[min_gen_pos]);\n+\t\t\t\t}\n \t\t\t}\n \n \t\t\tif (commit_graph_generation(c) < min_generation) {\n@@ -316,6 +329,7 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t}\n \t\tfree_commit_list(stack);\n \t}\n+\tfree(sorted);\n \n \t/* clear result */\n \tfor (i = 0; i < cnt; i++)\n-- \ngitgitgadget\n"},{"id":"417399","messageId":"c1fc174d42aa591b86a243edbb6a950e095daec4.1613738051.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v3.git.1613738051.gitgitgadget@gmail.com","subject":"[PATCH v3 4/5] commit-reach: use heuristic in remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-19T12:34:09Z","receivedAt":"2021-02-19T12:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nReachability algorithms in commit-reach.c frequently benefit from using\nthe first-parent history as a heuristic for satisfying reachability\nqueries. The most obvious example was implemented in 4fbcca4e\n(commit-reach: make can_all_from_reach... linear, 2018-07-20).\n\nUpdate the walk in remove_redundant() to use this same heuristic. Here,\nwe are walking starting at the parents of the input commits. Sort those\nparents and walk from the highest generation to lower. Each time, use\nthe heuristic of searching the first parent history before continuing to\nexpand the walk.\n\nThe order in which we explore the commits matters, so update\ncompare_commits_by_gen to break generation number ties with commit date.\nThis has no effect when the commits are in a commit-graph file with\ncorrected commit dates computed, but it will assist when the commits are\nin the region \"above\" the commit-graph with \"infinite\" generation\nnumber. Note that we cannot shift to use\ncompare_commits_by_gen_then_commit_date as the method prototype is\ndifferent. We use compare_commits_by_gen for QSORT() as opposed to as a\npriority function.\n\nThe important piece is to ensure we short-circuit the walk when we find\nthat there is a single non-redundant commit. This happens frequently\nwhen looking for merge-bases or comparing several tags with 'git\nmerge-base --independent'. Use a new count 'count_still_independent' and\nif that hits 1 we can stop walking.\n\nTo update 'count_still_independent' properly, we add use of the RESULT\nflag on the input commits. Then we can detect when we reach one of these\ncommits and decrease the count. We need to remove the RESULT flag at\nthat moment because we might re-visit that commit when popping the\nstack.\n\nWe use the STALE flag to mark parents that have been added to the new\nwalk_start list, but we need to clear that flag before we start walking\nso those flags don't halt our depth-first-search walk.\n\nOn my copy of the Linux kernel repository, the performance of 'git\nmerge-base --independent ' goes from 1.1 seconds to 0.11\nseconds.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 56 insertions(+), 16 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex a34c5ba09e81..399f2a8673e0 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -29,6 +29,10 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \t\treturn -1;\n \tif (generation_a > generation_b)\n \t\treturn 1;\n+\tif (a->date < b->date)\n+\t\treturn -1;\n+\tif (a->date > b->date)\n+\t\treturn 1;\n \treturn 0;\n }\n \n@@ -228,11 +232,10 @@ static int remove_redundant_no_gen(struct repository *r,\n static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\t struct commit **array, int cnt)\n {\n-\tint i, count_non_stale = 0;\n+\tint i, count_non_stale = 0, count_still_independent = cnt;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n \tstruct commit **walk_start;\n \tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \n \tALLOC_ARRAY(walk_start, walk_start_alloc);\n \n@@ -242,6 +245,7 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\ttimestamp_t generation;\n \n \t\trepo_parse_commit(r, array[i]);\n+\t\tarray[i]->object.flags |= RESULT;\n \t\tparents = array[i]->parents;\n \n \t\twhile (parents) {\n@@ -250,7 +254,6 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\t\tparents->item->object.flags |= STALE;\n \t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n \t\t\t\twalk_start[walk_start_nr++] = parents->item;\n-\t\t\t\tprio_queue_put(&queue, parents->item);\n \t\t\t}\n \t\t\tparents = parents->next;\n \t\t}\n@@ -261,26 +264,63 @@ static int remove_redundant_with_gen(struct repository *r,\n \t\t\tmin_generation = generation;\n \t}\n \n-\t/* push the STALE bits up to min generation */\n-\twhile (queue.nr) {\n-\t\tstruct commit_list *parents;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\tQSORT(walk_start, walk_start_nr, compare_commits_by_gen);\n \n-\t\trepo_parse_commit(r, c);\n+\t/* remove STALE bit for now to allow walking through parents */\n+\tfor (i = 0; i < walk_start_nr; i++)\n+\t\twalk_start[i]->object.flags &= ~STALE;\n \n-\t\tif (commit_graph_generation(c) < min_generation)\n-\t\t\tcontinue;\n+\t/*\n+\t * Start walking from the highest generation. Hopefully, it will\n+\t * find all other items during the first-parent walk, and we can\n+\t * terminate early. Otherwise, we will do the same amount of work\n+\t * as before.\n+\t */\n+\tfor (i = walk_start_nr - 1; i >= 0 && count_still_independent > 1; i--) {\n+\t\t/* push the STALE bits up to min generation */\n+\t\tstruct commit_list *stack = NULL;\n \n-\t\tparents = c->parents;\n-\t\twhile (parents) {\n-\t\t\tif (!(parents->item->object.flags & STALE)) {\n-\t\t\t\tparents->item->object.flags |= STALE;\n-\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\tcommit_list_insert(walk_start[i], &stack);\n+\t\twalk_start[i]->object.flags |= STALE;\n+\n+\t\twhile (stack) {\n+\t\t\tstruct commit_list *parents;\n+\t\t\tstruct commit *c = stack->item;\n+\n+\t\t\trepo_parse_commit(r, c);\n+\n+\t\t\tif (c->object.flags & RESULT) {\n+\t\t\t\tc->object.flags &= ~RESULT;\n+\t\t\t\tif (--count_still_independent <= 1)\n+\t\t\t\t\tbreak;\n \t\t\t}\n-\t\t\tparents = parents->next;\n+\n+\t\t\tif (commit_graph_generation(c) < min_generation) {\n+\t\t\t\tpop_commit(&stack);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tparents = c->parents;\n+\t\t\twhile (parents) {\n+\t\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\t\tcommit_list_insert(parents->item, &stack);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t\tparents = parents->next;\n+\t\t\t}\n+\n+\t\t\t/* pop if all parents have been visited already */\n+\t\t\tif (!parents)\n+\t\t\t\tpop_commit(&stack);\n \t\t}\n+\t\tfree_commit_list(stack);\n \t}\n \n+\t/* clear result */\n+\tfor (i = 0; i < cnt; i++)\n+\t\tarray[i]->object.flags &= ~RESULT;\n+\n \t/* rearrange array */\n \tfor (i = count_non_stale = 0; i < cnt; i++) {\n \t\tif (!(array[i]->object.flags & STALE))\n-- \ngitgitgadget\n\n"},{"id":"417400","messageId":"1d3c5ebbb632b33c6623c3c5ad120f1ec9884756.1613738051.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v3.git.1613738051.gitgitgadget@gmail.com","subject":"[PATCH v3 3/5] commit-reach: move compare_commits_by_gen","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-19T12:34:08Z","receivedAt":"2021-02-19T12:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nMove this earlier in the file so it can be used by more methods.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 30 +++++++++++++++---------------\n 1 file changed, 15 insertions(+), 15 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 7a3a1eb1a26e..a34c5ba09e81 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -17,6 +17,21 @@\n \n static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n \n+static int compare_commits_by_gen(const void *_a, const void *_b)\n+{\n+\tconst struct commit *a = *(const struct commit * const *)_a;\n+\tconst struct commit *b = *(const struct commit * const *)_b;\n+\n+\ttimestamp_t generation_a = commit_graph_generation(a);\n+\ttimestamp_t generation_b = commit_graph_generation(b);\n+\n+\tif (generation_a < generation_b)\n+\t\treturn -1;\n+\tif (generation_a > generation_b)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n static int queue_has_nonstale(struct prio_queue *queue)\n {\n \tint i;\n@@ -647,21 +662,6 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\n \n-static int compare_commits_by_gen(const void *_a, const void *_b)\n-{\n-\tconst struct commit *a = *(const struct commit * const *)_a;\n-\tconst struct commit *b = *(const struct commit * const *)_b;\n-\n-\ttimestamp_t generation_a = commit_graph_generation(a);\n-\ttimestamp_t generation_b = commit_graph_generation(b);\n-\n-\tif (generation_a < generation_b)\n-\t\treturn -1;\n-\tif (generation_a > generation_b)\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t\t unsigned int with_flag,\n \t\t\t\t unsigned int assign_flag,\n-- \ngitgitgadget\n\n"},{"id":"417401","messageId":"c2c08989ce60ef6892eb1c206483834d750a70c6.1613738051.git.gitgitgadget@gmail.com","threadId":"55069","inReplyTo":"pull.852.v3.git.1613738051.gitgitgadget@gmail.com","subject":"[PATCH v3 2/5] commit-reach: use one walk in remove_redundant()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-19T12:34:07Z","receivedAt":"2021-02-19T12:35:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe current implementation of remove_redundant() uses several calls to\npaint_down_to_common() to determine that commits are independent of each\nother. This leads to quadratic behavior when many inputs are passed to\ncommands such as 'git merge-base'.\n\nFor example, in the Linux kernel repository, I tested the performance\nby passing all tags:\n\n git merge-base --independent $(git for-each-ref refs/tags --format=\"$(refname)\")\n\n(Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do\nnot point to commits.)\n\nHere is the performance improvement introduced by this change:\n\n Before: 16.4s\n After: 1.1s\n\nThis performance improvement requires the commit-graph file to be\npresent. We keep the old algorithm around as remove_redundant_no_gen()\nand use it when generation_numbers_enabled() is false. This is similar\nto other algorithms within commit-reach.c. The new algorithm is\nimplemented in remove_redundant_with_gen().\n\nThe basic approach is to do one commit walk instead of many. First, scan\nall commits in the list and mark their _parents_ with the STALE flag.\nThis flag will indicate commits that are reachable from one of the\ninputs, except not including themselves. Then, walk commits until\ncovering all commits up to the minimum generation number pushing the\nSTALE flag throughout.\n\nAt the end, we need to clear the STALE bit from all of the commits\nwe walked. We move the non-stale commits in 'array' to the beginning of\nthe list, and this might overwrite stale commits. However, we store an\narray of commits that started the walk, and use clear_commit_marks() on\neach of those starting commits. That method will walk the reachable\ncommits with the STALE bit and clear them all. This makes the algorithm\nsafe for re-entry or for other uses of those commits after this walk.\n\nThis logic is covered by tests in t6600-test-reach.sh, so the behavior\ndoes not change. This is tested both in the case with a commit-graph and\nwithout.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 104 +++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 96 insertions(+), 8 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9af51fe7e078..7a3a1eb1a26e 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -156,15 +156,9 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n \treturn ret;\n }\n \n-static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n+static int remove_redundant_no_gen(struct repository *r,\n+\t\t\t\t struct commit **array, int cnt)\n {\n-\t/*\n-\t * Some commit in the array may be an ancestor of\n-\t * another commit. Move the independent commits to the\n-\t * beginning of 'array' and return their number. Callers\n-\t * should not rely upon the contents of 'array' after\n-\t * that number.\n-\t */\n \tstruct commit **work;\n \tunsigned char *redundant;\n \tint *filled_index;\n@@ -216,6 +210,100 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \treturn filled;\n }\n \n+static int remove_redundant_with_gen(struct repository *r,\n+\t\t\t\t struct commit **array, int cnt)\n+{\n+\tint i, count_non_stale = 0;\n+\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tstruct commit **walk_start;\n+\tsize_t walk_start_nr = 0, walk_start_alloc = cnt;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\n+\tALLOC_ARRAY(walk_start, walk_start_alloc);\n+\n+\t/* Mark all parents of the input as STALE */\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tstruct commit_list *parents;\n+\t\ttimestamp_t generation;\n+\n+\t\trepo_parse_commit(r, array[i]);\n+\t\tparents = array[i]->parents;\n+\n+\t\twhile (parents) {\n+\t\t\trepo_parse_commit(r, parents->item);\n+\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\tALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);\n+\t\t\t\twalk_start[walk_start_nr++] = parents->item;\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n+\t\t\tparents = parents->next;\n+\t\t}\n+\n+\t\tgeneration = commit_graph_generation(array[i]);\n+\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n+\t}\n+\n+\t/* push the STALE bits up to min generation */\n+\twhile (queue.nr) {\n+\t\tstruct commit_list *parents;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\n+\t\trepo_parse_commit(r, c);\n+\n+\t\tif (commit_graph_generation(c) < min_generation)\n+\t\t\tcontinue;\n+\n+\t\tparents = c->parents;\n+\t\twhile (parents) {\n+\t\t\tif (!(parents->item->object.flags & STALE)) {\n+\t\t\t\tparents->item->object.flags |= STALE;\n+\t\t\t\tprio_queue_put(&queue, parents->item);\n+\t\t\t}\n+\t\t\tparents = parents->next;\n+\t\t}\n+\t}\n+\n+\t/* rearrange array */\n+\tfor (i = count_non_stale = 0; i < cnt; i++) {\n+\t\tif (!(array[i]->object.flags & STALE))\n+\t\t\tarray[count_non_stale++] = array[i];\n+\t}\n+\n+\t/* clear marks */\n+\tclear_commit_marks_many(walk_start_nr, walk_start, STALE);\n+\tfree(walk_start);\n+\n+\treturn count_non_stale;\n+}\n+\n+static int remove_redundant(struct repository *r, struct commit **array, int cnt)\n+{\n+\t/*\n+\t * Some commit in the array may be an ancestor of\n+\t * another commit. Move the independent commits to the\n+\t * beginning of 'array' and return their number. Callers\n+\t * should not rely upon the contents of 'array' after\n+\t * that number.\n+\t */\n+\tif (generation_numbers_enabled(r)) {\n+\t\tint i;\n+\n+\t\t/*\n+\t\t * If we have a single commit with finite generation\n+\t\t * number, then the _with_gen algorithm is preferred.\n+\t\t */\n+\t\tfor (i = 0; i < cnt; i++) {\n+\t\t\tif (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)\n+\t\t\t\treturn remove_redundant_with_gen(r, array, cnt);\n+\t\t}\n+\t}\n+\n+\treturn remove_redundant_no_gen(r, array, cnt);\n+}\n+\n static struct commit_list *get_merge_bases_many_0(struct repository *r,\n \t\t\t\t\t\t struct commit *one,\n \t\t\t\t\t\t int n,\n-- \ngitgitgadget\n\n"},{"id":"417431","messageId":"xmqqeehb9zyg.fsf@gitster.g","threadId":"55069","inReplyTo":"4ca2931f-3e3c-12d5-e12a-6c63699a98d7@gmail.com","subject":"Re: [PATCH v2 0/5] Speed up remove_redundant()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-20T03:32:07Z","receivedAt":"2021-02-20T03:32:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 2/18/2021 6:25 PM, Junio C Hamano wrote:\n>> This topic seems to have been forgotten? Is the only thing missing\n>> is an updated 2/5 or is there anything more that is needed?\n> \n> I had forgotten about the comments on patch 2/5, sorry. That explains\n> why it hasn't merged yet...\n>\n> I'll get right on it.\n\nThanks.\n"}]}