{"thread":{"id":"49715","subject":"[PATCH 0/3] Make add_missing_tags() linear","startedAt":"2018-10-30T14:16:07Z","lastAt":"2018-11-02T15:39:00Z","messageCount":22,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Elijah Newren","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"361988","messageId":"pull.60.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":null,"subject":"[PATCH 0/3] Make add_missing_tags() linear","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-10-30T14:16:02Z","receivedAt":"2018-10-30T14:16:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As reported earlier [1], the add_missing_tags() method in remote.c has\nquadratic performance. Some of that performance is curbed due to the\ngeneration-number cutoff in in_merge_bases_many(). However, that fix doesn't\nhelp users without a commit-graph, and it can still be painful if that\ncutoff is sufficiently low compared to the tags we are using for\nreachability testing.\n\nAdd a new method in commit-reach.c called get_reachable_subset() which does\na many-to-many reachability test. Starting at the 'from' commits, walk until\nthe generation is below the smallest generation in the 'to' commits, or all\n'to' commits have been discovered. This performs only one commit walk for\nthe entire add_missing_tags() method, giving linear performance in the worst\ncase.\n\nTests are added in t6600-test-reach.sh to ensure get_reachable_subset()\nworks independently of its application in add_missing_tags().\n\nThanks, -Stolee\n\n[1] \nhttps://public-inbox.org/git/CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com/\n\nDerrick Stolee (3):\n commit-reach: implement get_reachable_subset\n test-reach: test get_reachable_subset\n remote: make add_missing_tags() linear\n\n commit-reach.c | 70 +++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 10 +++++++\n remote.c | 34 ++++++++++++++++++++-\n t/helper/test-reach.c | 34 ++++++++++++++++++---\n t/t6600-test-reach.sh | 52 ++++++++++++++++++++++++++++++++\n 5 files changed, 195 insertions(+), 5 deletions(-)\n\n\nbase-commit: c670b1f876521c9f7cd40184bf7ed05aad843433\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-60%2Fderrickstolee%2Fadd-missing-tags-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-60/derrickstolee/add-missing-tags-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/60\n-- \ngitgitgadget\n"},{"id":"361989","messageId":"4c0c5c9143a757ee5187ae6fca9a76f29b6c6ae2.1540908961.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.git.gitgitgadget@gmail.com","subject":"[PATCH 1/3] commit-reach: implement get_reachable_subset","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-10-30T14:16:04Z","receivedAt":"2018-10-30T14:16:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe existing reachability algorithms in commit-reach.c focus on\nfinding merge-bases or determining if all commits in a set X can\nreach at least one commit in a set Y. However, for two commits sets\nX and Y, we may also care about which commits in Y are reachable\nfrom at least one commit in X.\n\nImplement get_reachable_subset() which answers this question. Given\ntwo arrays of commits, 'from' and 'to', return a commit_list with\nevery commit from the 'to' array that is reachable from at least\none commit in the 'from' array.\n\nThe algorithm is a simple walk starting at the 'from' commits, using\nthe PARENT2 flag to indicate \"this commit has already been added to\nthe walk queue\". By marking the 'to' commits with the PARENT1 flag,\nwe can determine when we see a commit from the 'to' array. We remove\nthe PARENT1 flag as we add that commit to the result list to avoid\nduplicates.\n\nThe order of the resulting list is a reverse of the order that the\ncommits are discovered in the walk.\n\nThere are a couple shortcuts to avoid walking more than we need:\n\n1. We determine the minimum generation number of commits in the\n 'to' array. We do not walk commits with generation number\n below this minimum.\n\n2. We count how many distinct commits are in the 'to' array, and\n decrement this count when we discover a 'to' commit during the\n walk. If this number reaches zero, then we can terminate the\n walk.\n\nTests will be added using the 'test-tool reach' helper in a\nsubsequent commit.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 10 ++++++++\n 2 files changed, 80 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9f79ce0a2..a98532ecc 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \tobject_array_clear(&from_objs);\n \treturn result;\n }\n+\n+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n+\t\t\t\t\t struct commit **to, int nr_to,\n+\t\t\t\t\t int reachable_flag)\n+{\n+\tstruct commit **item;\n+\tstruct commit *current;\n+\tstruct commit_list *found_commits = NULL;\n+\tstruct commit **to_last = to + nr_to;\n+\tstruct commit **from_last = from + nr_from;\n+\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tint num_to_find = 0;\n+\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\n+\tfor (item = to; item < to_last; item++) {\n+\t\tstruct commit *c = *item;\n+\t\t\n+\t\tparse_commit(c);\n+\t\tif (c->generation < min_generation)\n+\t\t\tmin_generation = c->generation;\n+\n+\t\tif (!(c->object.flags & PARENT1)) {\n+\t\t\tc->object.flags |= PARENT1;\n+\t\t\tnum_to_find++;\n+\t\t}\n+\t}\n+\n+\tfor (item = from; item < from_last; item++) {\n+\t\tstruct commit *c = *item;\n+\t\tif (!(c->object.flags & PARENT2)) {\n+\t\t\tc->object.flags |= PARENT2;\n+\t\t\tparse_commit(c);\n+\n+\t\t\tprio_queue_put(&queue, *item);\n+\t\t}\n+\t}\n+\n+\twhile (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n+\t\tstruct commit_list *parents;\n+\n+\t\tif (current->object.flags & PARENT1) {\n+\t\t\tcurrent->object.flags &= ~PARENT1;\n+\t\t\tcurrent->object.flags |= reachable_flag;\n+\t\t\tcommit_list_insert(current, &found_commits);\n+\t\t\tnum_to_find--;\n+\t\t}\n+\n+\t\tfor (parents = current->parents; parents; parents = parents->next) {\n+\t\t\tstruct commit *p = parents->item;\n+\n+\t\t\tparse_commit(p);\n+\n+\t\t\tif (p->generation < min_generation)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (p->object.flags & PARENT2)\n+\t\t\t\tcontinue;\n+\n+\t\t\tp->object.flags |= PARENT2;\n+\t\t\tprio_queue_put(&queue, p);\n+\t\t}\n+\t}\n+\n+\tclear_commit_marks_many(nr_to, to, PARENT1);\n+\tclear_commit_marks_many(nr_from, from, PARENT2);\n+\n+\treturn found_commits;\n+}\n+\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 7d313e297..43bd50a70 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -74,4 +74,14 @@ int can_all_from_reach_with_flag(struct object_array *from,\n int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t int commit_date_cutoff);\n \n+\n+/*\n+ * Return a list of commits containing the commits in the 'to' array\n+ * that are reachable from at least one commit in the 'from' array.\n+ * Also add the given 'flag' to each of the commits in the returned list.\n+ */\n+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n+\t\t\t\t\t struct commit **to, int nr_to,\n+\t\t\t\t\t int reachable_flag);\n+\n #endif\n-- \ngitgitgadget\n\n"},{"id":"361990","messageId":"382f4f4a5b4671307530a34a60f9cc18c3b06443.1540908961.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.git.gitgitgadget@gmail.com","subject":"[PATCH 2/3] test-reach: test get_reachable_subset","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-10-30T14:16:05Z","receivedAt":"2018-10-30T14:16:09Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe get_reachable_subset() method returns the list of commits in\nthe 'to' array that are reachable from at least one commit in the\n'from' array. Add tests that check this method works in a few\ncases:\n\n1. All commits in the 'to' list are reachable. This exercises the\n early-termination condition.\n\n2. Some commits in the 'to' list are reachable. This exercises the\n loop-termination condition.\n\n3. No commits in the 'to' list are reachable. This exercises the\n NULL return condition.\n\nSigned-off-by: Derrick Stolee \n---\n t/helper/test-reach.c | 34 ++++++++++++++++++++++++----\n t/t6600-test-reach.sh | 52 +++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 82 insertions(+), 4 deletions(-)\n\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 08d2ea68e..a0272178b 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -32,8 +32,8 @@ int cmd__reach(int ac, const char **av)\n \tstruct commit *A, *B;\n \tstruct commit_list *X, *Y;\n \tstruct object_array X_obj = OBJECT_ARRAY_INIT;\n-\tstruct commit **X_array;\n-\tint X_nr, X_alloc;\n+\tstruct commit **X_array, **Y_array;\n+\tint X_nr, X_alloc, Y_nr, Y_alloc;\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct repository *r = the_repository;\n \n@@ -44,9 +44,10 @@ int cmd__reach(int ac, const char **av)\n \n \tA = B = NULL;\n \tX = Y = NULL;\n-\tX_nr = 0;\n-\tX_alloc = 16;\n+\tX_nr = Y_nr = 0;\n+\tX_alloc = Y_alloc = 16;\n \tALLOC_ARRAY(X_array, X_alloc);\n+\tALLOC_ARRAY(Y_array, Y_alloc);\n \n \twhile (strbuf_getline(&buf, stdin) != EOF) {\n \t\tstruct object_id oid;\n@@ -92,6 +93,8 @@ int cmd__reach(int ac, const char **av)\n \n \t\t\tcase 'Y':\n \t\t\t\tcommit_list_insert(c, &Y);\n+\t\t\t\tALLOC_GROW(Y_array, Y_nr + 1, Y_alloc);\n+\t\t\t\tY_array[Y_nr++] = c;\n \t\t\t\tbreak;\n \n \t\t\tdefault:\n@@ -136,6 +139,29 @@ int cmd__reach(int ac, const char **av)\n \t\t\tfilter.with_commit_tag_algo = 0;\n \n \t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n+\t} else if (!strcmp(av[1], \"get_reachable_subset\")) {\n+\t\tconst int reachable_flag = 1;\n+\t\tint i, count = 0;\n+\t\tstruct commit_list *current;\n+\t\tstruct commit_list *list = get_reachable_subset(X_array, X_nr,\n+\t\t\t\t\t\t\t\tY_array, Y_nr,\n+\t\t\t\t\t\t\t\treachable_flag);\n+\t\tprintf(\"get_reachable_subset(X,Y)\\n\");\n+\t\tfor (current = list; current; current = current->next) {\n+\t\t\tif (!(list->item->object.flags & reachable_flag))\n+\t\t\t\tdie(_(\"commit %s is not marked reachable\"),\n+\t\t\t\t oid_to_hex(&list->item->object.oid));\n+\t\t\tcount++;\n+\t\t}\n+\t\tfor (i = 0; i < Y_nr; i++) {\n+\t\t\tif (Y_array[i]->object.flags & reachable_flag)\n+\t\t\t\tcount--;\n+\t\t}\n+\n+\t\tif (count < 0)\n+\t\t\tdie(_(\"too many commits marked reachable\"));\n+\n+\t\tprint_sorted_commit_ids(list);\n \t}\n \n \texit(0);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex ae94b27f7..a0c64e617 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -265,4 +265,56 @@ test_expect_success 'commit_contains:miss' '\n \ttest_three_modes commit_contains --tag\n '\n \n+test_expect_success 'get_reachable_subset:all' '\n+\tcat >input <<-\\EOF &&\n+\tX:commit-9-1\n+\tX:commit-8-3\n+\tX:commit-7-5\n+\tX:commit-6-6\n+\tX:commit-1-7\n+\tY:commit-3-3\n+\tY:commit-1-7\n+\tY:commit-5-6\n+\tEOF\n+\t(\n+\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\tgit rev-parse commit-3-3 \\\n+\t\t\t commit-1-7 \\\n+\t\t\t commit-5-6 | sort\n+\t) >expect &&\n+\ttest_three_modes get_reachable_subset\n+'\n+\n+test_expect_success 'get_reachable_subset:some' '\n+\tcat >input <<-\\EOF &&\n+\tX:commit-9-1\n+\tX:commit-8-3\n+\tX:commit-7-5\n+\tX:commit-1-7\n+\tY:commit-3-3\n+\tY:commit-1-7\n+\tY:commit-5-6\n+\tEOF\n+\t(\n+\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\tgit rev-parse commit-3-3 \\\n+\t\t\t commit-1-7 | sort\n+\t) >expect &&\n+\ttest_three_modes get_reachable_subset\n+'\n+\n+test_expect_success 'get_reachable_subset:none' '\n+\tcat >input <<-\\EOF &&\n+\tX:commit-9-1\n+\tX:commit-8-3\n+\tX:commit-7-5\n+\tX:commit-1-7\n+\tY:commit-9-3\n+\tY:commit-7-6\n+\tY:commit-2-8\n+\tEOF\n+\techo \"get_reachable_subset(X,Y)\" >expect &&\n+\ttest_three_modes get_reachable_subset\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"361991","messageId":"ecbed3de5c704a5d54a910a527b60eb79f0d252e.1540908961.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.git.gitgitgadget@gmail.com","subject":"[PATCH 3/3] remote: make add_missing_tags() linear","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-10-30T14:16:07Z","receivedAt":"2018-10-30T14:16:10Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe add_missing_tags() method currently has quadratic behavior.\nThis is due to a linear number (based on number of tags T) of\ncalls to in_merge_bases_many, which has linear performance (based\non number of commits C in the repository).\n\nReplace this O(T * C) algorithm with an O(T + C) algorithm by\nusing get_reachable_subset(). We ignore the return list and focus\ninstead on the reachable_flag assigned to the commits we care\nabout, because we need to interact with the tag ref and not just\nthe commit object.\n\nSigned-off-by: Derrick Stolee \n---\n remote.c | 34 +++++++++++++++++++++++++++++++++-\n 1 file changed, 33 insertions(+), 1 deletion(-)\n\ndiff --git a/remote.c b/remote.c\nindex 81f4f01b0..b850f2feb 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1205,9 +1205,36 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t * sent to the other side.\n \t */\n \tif (sent_tips.nr) {\n+\t\tconst int reachable_flag = 1;\n+\t\tstruct commit_list *found_commits;\n+\t\tstruct commit **src_commits;\n+\t\tint nr_src_commits = 0, alloc_src_commits = 16;\n+\t\tALLOC_ARRAY(src_commits, alloc_src_commits);\n+\n \t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *ref = item->util;\n+\t\t\tstruct commit *commit;\n+\n+\t\t\tif (is_null_oid(&ref->new_oid))\n+\t\t\t\tcontinue;\n+\t\t\tcommit = lookup_commit_reference_gently(the_repository,\n+\t\t\t\t\t\t\t\t&ref->new_oid,\n+\t\t\t\t\t\t\t\t1);\n+\t\t\tif (!commit)\n+\t\t\t\t/* not pushing a commit, which is not an error */\n+\t\t\t\tcontinue;\n+\n+\t\t\tALLOC_GROW(src_commits, nr_src_commits + 1, alloc_src_commits);\n+\t\t\tsrc_commits[nr_src_commits++] = commit;\n+\t\t}\n+\n+\t\tfound_commits = get_reachable_subset(sent_tips.tip, sent_tips.nr,\n+\t\t\t\t\t\t src_commits, nr_src_commits,\n+\t\t\t\t\t\t reachable_flag);\n+\n+\t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *dst_ref;\n+\t\t\tstruct ref *ref = item->util;\n \t\t\tstruct commit *commit;\n \n \t\t\tif (is_null_oid(&ref->new_oid))\n@@ -1223,7 +1250,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\t * Is this tag, which they do not have, reachable from\n \t\t\t * any of the commits we are sending?\n \t\t\t */\n-\t\t\tif (!in_merge_bases_many(commit, sent_tips.nr, sent_tips.tip))\n+\t\t\tif (!(commit->object.flags & reachable_flag))\n \t\t\t\tcontinue;\n \n \t\t\t/* Add it in */\n@@ -1231,7 +1258,12 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\toidcpy(&dst_ref->new_oid, &ref->new_oid);\n \t\t\tdst_ref->peer_ref = copy_ref(ref);\n \t\t}\n+\n+\t\tclear_commit_marks_many(nr_src_commits, src_commits, reachable_flag);\n+\t\tfree(src_commits);\n+\t\tfree_commit_list(found_commits);\n \t}\n+\n \tstring_list_clear(&src_tag, 0);\n \tfree(sent_tips.tip);\n }\n-- \ngitgitgadget\n"},{"id":"362053","messageId":"xmqq7ehyzugy.fsf@gitster-ct.c.googlers.com","threadId":"49715","inReplyTo":"pull.60.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-31T03:05:33Z","receivedAt":"2018-10-31T03:05:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> Add a new method in commit-reach.c called get_reachable_subset() which does\n> a many-to-many reachability test. Starting at the 'from' commits, walk until\n> the generation is below the smallest generation in the 'to' commits, or all\n> 'to' commits have been discovered. This performs only one commit walk for\n> the entire add_missing_tags() method, giving linear performance in the worst\n> case.\n\n;-)\n\nI think in_merge_bases_many() was an attempt to do one half of this\n(i.e. it checks only one 'to' against main 'from' to see if any of\nthem reach). I wonder why we didn't extend it to multiple 'to' back\nwhen we invented it.\n\nIn any case, good to see this code optimized.\n\nThanks.\n"},{"id":"362054","messageId":"xmqqy3aeyehs.fsf@gitster-ct.c.googlers.com","threadId":"49715","inReplyTo":"4c0c5c9143a757ee5187ae6fca9a76f29b6c6ae2.1540908961.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: implement get_reachable_subset","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-31T03:35:59Z","receivedAt":"2018-10-31T03:36:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n> +\t\t\t\t\t struct commit **to, int nr_to,\n> +\t\t\t\t\t int reachable_flag)\n\nThis is OR'ed into object.flags, and I somoehow expected to see it\nas 'unsigned int', not a signed one.\n\n> +{\n> +\tstruct commit **item;\n> +\tstruct commit *current;\n> +\tstruct commit_list *found_commits = NULL;\n> +\tstruct commit **to_last = to + nr_to;\n> +\tstruct commit **from_last = from + nr_from;\n> +\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n> +\tint num_to_find = 0;\n> +\n> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> +\n> +\tfor (item = to; item < to_last; item++) {\n> +\t\tstruct commit *c = *item;\n> +\t\t\n> +\t\tparse_commit(c);\n> +\t\tif (c->generation < min_generation)\n> +\t\t\tmin_generation = c->generation;\n> +\n> +\t\tif (!(c->object.flags & PARENT1)) {\n> +\t\t\tc->object.flags |= PARENT1;\n> +\t\t\tnum_to_find++;\n> +\t\t}\n> +\t}\n> +\n> +\tfor (item = from; item < from_last; item++) {\n> +\t\tstruct commit *c = *item;\n> +\t\tif (!(c->object.flags & PARENT2)) {\n> +\t\t\tc->object.flags |= PARENT2;\n> +\t\t\tparse_commit(c);\n> +\n> +\t\t\tprio_queue_put(&queue, *item);\n> +\t\t}\n> +\t}\n\nOK, we marked \"to\" with PARENT1 and counted them in num_to_find\nwithout dups. We also marked \"from\" with PARENT2 and threw them in\nthe \"queue\" without dups.\n\nMental note: the caller must guarantee that everybody reachable from\n\"to\" and \"from\" have PARENT1 and PARENT2 clear. This might deserve\nto be in the comment before the function.\n\n> +\twhile (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n> +\t\tstruct commit_list *parents;\n> +\n> +\t\tif (current->object.flags & PARENT1) {\n> +\t\t\tcurrent->object.flags &= ~PARENT1;\n> +\t\t\tcurrent->object.flags |= reachable_flag;\n> +\t\t\tcommit_list_insert(current, &found_commits);\n> +\t\t\tnum_to_find--;\n\nWhat is in \"queue\" are all reachable from \"from\" so we found this\nobject in the \"to\" set is reachable. One down.\n\n> +\t\t}\n> +\n> +\t\tfor (parents = current->parents; parents; parents = parents->next) {\n> +\t\t\tstruct commit *p = parents->item;\n> +\n> +\t\t\tparse_commit(p);\n> +\n> +\t\t\tif (p->generation < min_generation)\n> +\t\t\t\tcontinue;\n\nAny commit reachable from \"from\" whose generation is too small\n(i.e. old) can never reach any of \"to\", because all \"to\" are at\ngeneration \"min_generation\" or greater. Makes sense.\n\n> +\t\t\tif (p->object.flags & PARENT2)\n> +\t\t\t\tcontinue;\n\nIf the object is painted with PARENT2, we know we have it in queue\nand traversing to find more of its ancestors. Avoid recursing into\nit twice. Makes sense.\n\n> +\t\t\tp->object.flags |= PARENT2;\n> +\t\t\tprio_queue_put(&queue, p);\n\nOtherwise, explore this parent.\n\n> +\t\t}\n> +\t}\n> +\n> +\tclear_commit_marks_many(nr_to, to, PARENT1);\n\nAmong \"to\", the ones that were not found still have PARENT1.\nBecause we do not propagate this flag down the ancestry chain like\nmerge-base discovery, this only has to clear just one level.\n\n> +\tclear_commit_marks_many(nr_from, from, PARENT2);\n\nAnd then we smudged everything that are reachable from \"from\"\nwith this flag. In the worst case, i.e. when num_to_find is still\npositive here, we would have painted all commits down to the root,\nand we need to clear all of them.\n\n> +\treturn found_commits;\n> +}\n\nOK, this all makes sense. Unlike merge-base traversals, this does\nnot have to traverse from the \"to\" side at all, which makes it quite\nsimpler and straight-forward.\n\nI do wonder if we can now reimplement in_merge_bases_many() in terms\nof this helper, and if that gives us a better performance. It asks\n\"is 'commit', i.e. a single 'to', an ancestor of, i.e. reachable\nfrom, one of the 'references', i.e. 'from'\"?\n\n> diff --git a/commit-reach.h b/commit-reach.h\n> index 7d313e297..43bd50a70 100644\n> --- a/commit-reach.h\n> +++ b/commit-reach.h\n> @@ -74,4 +74,14 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> \t\t int commit_date_cutoff);\n> \n> +\n> +/*\n> + * Return a list of commits containing the commits in the 'to' array\n> + * that are reachable from at least one commit in the 'from' array.\n> + * Also add the given 'flag' to each of the commits in the returned list.\n> + */\n> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n> +\t\t\t\t\t struct commit **to, int nr_to,\n> +\t\t\t\t\t int reachable_flag);\n> +\n> #endif\n"},{"id":"362075","messageId":"CABPp-BFzwphzaMjCWrNxU2V+YeYvRiBOzSV--b13wa7r16dvMQ@mail.gmail.com","threadId":"49715","inReplyTo":"pull.60.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-10-31T06:04:39Z","receivedAt":"2018-10-31T06:04:53Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Oct 30, 2018 at 7:16 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> As reported earlier [1], the add_missing_tags() method in remote.c has\n> quadratic performance. Some of that performance is curbed due to the\n> generation-number cutoff in in_merge_bases_many(). However, that fix doesn't\n> help users without a commit-graph, and it can still be painful if that\n> cutoff is sufficiently low compared to the tags we are using for\n> reachability testing.\n>\n> Add a new method in commit-reach.c called get_reachable_subset() which does\n> a many-to-many reachability test. Starting at the 'from' commits, walk until\n> the generation is below the smallest generation in the 'to' commits, or all\n> 'to' commits have been discovered. This performs only one commit walk for\n> the entire add_missing_tags() method, giving linear performance in the worst\n> case.\n>\n> Tests are added in t6600-test-reach.sh to ensure get_reachable_subset()\n> works independently of its application in add_missing_tags().\n\nOn the original repo where the topic was brought up, with commit-graph\nNOT turned on and using origin/master, I see:\n\n$ time git push --dry-run --follow-tags /home/newren/repo-mirror\nTo /home/newren/repo-mirror\n * [new branch] test5 -> test5\n\nreal 1m20.081s\nuser 1m19.688s\nsys 0m0.292s\n\nMerging this series in, I now get:\n\n$ time git push --dry-run --follow-tags /home/newren/repo-mirror\nTo /home/newren/repo-mirror\n * [new branch] test5 -> test5\n\nreal 0m2.857s\nuser 0m2.580s\nsys 0m0.328s\n\nwhich provides a very nice speedup.\n\nOddly enough, if I _also_ do the following:\n$ git config core.commitgraph true\n$ git config gc.writecommitgraph true\n$ git gc\n\nthen my timing actually slows down just slightly:\n$ time git push --follow-tags --dry-run /home/newren/repo-mirror\nTo /home/newren/repo-mirror\n * [new branch] test5 -> test5\n\nreal 0m3.027s\nuser 0m2.696s\nsys 0m0.400s\n\n(run-to-run variation seems pretty consistent, < .1s variation, so\nthis difference is just enough to notice.) I wouldn't be that\nsurprised if that means there's some really old tags with very small\ngeneration numbers, meaning it's not gaining anything in this special\ncase from the commit-graph, but it does pay the cost of loading the\ncommit-graph.\n\n\nAnyway, looks good in my testing. Thanks much for working on this!\n"},{"id":"362076","messageId":"CABPp-BHbOWXsnUSdcptyQ_Cn_PnqH4On+Q3zWNZQV4QHgYhqpg@mail.gmail.com","threadId":"49715","inReplyTo":"4c0c5c9143a757ee5187ae6fca9a76f29b6c6ae2.1540908961.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: implement get_reachable_subset","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-10-31T06:07:37Z","receivedAt":"2018-10-31T06:07:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Oct 30, 2018 at 7:16 AM Derrick Stolee via GitGitGadget\n wrote:\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> object_array_clear(&from_objs);\n> return result;\n> }\n> +\n> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n> + struct commit **to, int nr_to,\n> + int reachable_flag)\n> +{\n> + struct commit **item;\n> + struct commit *current;\n> + struct commit_list *found_commits = NULL;\n> + struct commit **to_last = to + nr_to;\n> + struct commit **from_last = from + nr_from;\n> + uint32_t min_generation = GENERATION_NUMBER_INFINITY;\n> + int num_to_find = 0;\n> +\n> + struct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> +\n> + for (item = to; item < to_last; item++) {\n> + struct commit *c = *item;\n> +\n> + parse_commit(c);\n> + if (c->generation < min_generation)\n> + min_generation = c->generation;\n\nSo, when we don't have a commit-graph, is c->generation just going to\nbe 0, making min_generation also be 0? (meaning we get no possible\nspeed benefit from the commit-graph, since we just don't have that\ninformation available)?\n\n> +\n> + if (!(c->object.flags & PARENT1)) {\n> + c->object.flags |= PARENT1;\n> + num_to_find++;\n> + }\n> + }\n> +\n> + for (item = from; item < from_last; item++) {\n> + struct commit *c = *item;\n> + if (!(c->object.flags & PARENT2)) {\n> + c->object.flags |= PARENT2;\n> + parse_commit(c);\n> +\n> + prio_queue_put(&queue, *item);\n> + }\n> + }\n> +\n> + while (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n> + struct commit_list *parents;\n> +\n> + if (current->object.flags & PARENT1) {\n> + current->object.flags &= ~PARENT1;\n> + current->object.flags |= reachable_flag;\n> + commit_list_insert(current, &found_commits);\n> + num_to_find--;\n> + }\n> +\n> + for (parents = current->parents; parents; parents = parents->next) {\n> + struct commit *p = parents->item;\n> +\n> + parse_commit(p);\n> +\n> + if (p->generation < min_generation)\n> + continue;\n> +\n> + if (p->object.flags & PARENT2)\n> + continue;\n> +\n> + p->object.flags |= PARENT2;\n> + prio_queue_put(&queue, p);\n> + }\n> + }\n> +\n> + clear_commit_marks_many(nr_to, to, PARENT1);\n> + clear_commit_marks_many(nr_from, from, PARENT2);\n> +\n> + return found_commits;\n> +}\n> +\n> diff --git a/commit-reach.h b/commit-reach.h\n> index 7d313e297..43bd50a70 100644\n> --- a/commit-reach.h\n> +++ b/commit-reach.h\n> @@ -74,4 +74,14 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> int commit_date_cutoff);\n>\n> +\n> +/*\n> + * Return a list of commits containing the commits in the 'to' array\n> + * that are reachable from at least one commit in the 'from' array.\n> + * Also add the given 'flag' to each of the commits in the returned list.\n> + */\n> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n> + struct commit **to, int nr_to,\n> + int reachable_flag);\n> +\n> #endif\n> --\n> gitgitgadget\n>\n"},{"id":"362093","messageId":"d42eceda-0178-ce48-1ccd-7a1842e897ed@gmail.com","threadId":"49715","inReplyTo":"CABPp-BHbOWXsnUSdcptyQ_Cn_PnqH4On+Q3zWNZQV4QHgYhqpg@mail.gmail.com","subject":"Re: [PATCH 1/3] commit-reach: implement get_reachable_subset","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-31T11:54:43Z","receivedAt":"2018-10-31T11:54:45Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/31/2018 2:07 AM, Elijah Newren wrote:\n> On Tue, Oct 30, 2018 at 7:16 AM Derrick Stolee via GitGitGadget\n> wrote:\n>> --- a/commit-reach.c\n>> +++ b/commit-reach.c\n>> @@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n>> object_array_clear(&from_objs);\n>> return result;\n>> }\n>> +\n>> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n>> + struct commit **to, int nr_to,\n>> + int reachable_flag)\n>> +{\n>> + struct commit **item;\n>> + struct commit *current;\n>> + struct commit_list *found_commits = NULL;\n>> + struct commit **to_last = to + nr_to;\n>> + struct commit **from_last = from + nr_from;\n>> + uint32_t min_generation = GENERATION_NUMBER_INFINITY;\n>> + int num_to_find = 0;\n>> +\n>> + struct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n>> +\n>> + for (item = to; item < to_last; item++) {\n>> + struct commit *c = *item;\n>> +\n>> + parse_commit(c);\n>> + if (c->generation < min_generation)\n>> + min_generation = c->generation;\n> So, when we don't have a commit-graph, is c->generation just going to\n> be 0, making min_generation also be 0? (meaning we get no possible\n> speed benefit from the commit-graph, since we just don't have that\n> information available)?\n\nIf we don't have a commit-graph, then we can only terminate the loop early\nif we discover all of the commits (num_to_find == 0).Otherwise, we need to\nwalk the entire graph in order to determine non-reachability. This relates\nto Junio's point about in_merge_bases_many(), which I'll respond to his\nmessage in more detail about that.\n\nThanks,\n-Stolee\n"},{"id":"362094","messageId":"15ef2018-4bb1-430f-32fd-5676a1b5ac1a@gmail.com","threadId":"49715","inReplyTo":"xmqqy3aeyehs.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 1/3] commit-reach: implement get_reachable_subset","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-31T12:01:48Z","receivedAt":"2018-10-31T12:01:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/30/2018 11:35 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>\n>> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n>> +\t\t\t\t\t struct commit **to, int nr_to,\n>> +\t\t\t\t\t int reachable_flag)\n> This is OR'ed into object.flags, and I somoehow expected to see it\n> as 'unsigned int', not a signed one.\n\nWill do. Thanks.\n\n>\n>> +{\n>> +\tstruct commit **item;\n>> +\tstruct commit *current;\n>> +\tstruct commit_list *found_commits = NULL;\n>> +\tstruct commit **to_last = to + nr_to;\n>> +\tstruct commit **from_last = from + nr_from;\n>> +\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n>> +\tint num_to_find = 0;\n>> +\n>> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n>> +\n>> +\tfor (item = to; item < to_last; item++) {\n>> +\t\tstruct commit *c = *item;\n>> +\t\t\n>> +\t\tparse_commit(c);\n>> +\t\tif (c->generation < min_generation)\n>> +\t\t\tmin_generation = c->generation;\n>> +\n>> +\t\tif (!(c->object.flags & PARENT1)) {\n>> +\t\t\tc->object.flags |= PARENT1;\n>> +\t\t\tnum_to_find++;\n>> +\t\t}\n>> +\t}\n>> +\n>> +\tfor (item = from; item < from_last; item++) {\n>> +\t\tstruct commit *c = *item;\n>> +\t\tif (!(c->object.flags & PARENT2)) {\n>> +\t\t\tc->object.flags |= PARENT2;\n>> +\t\t\tparse_commit(c);\n>> +\n>> +\t\t\tprio_queue_put(&queue, *item);\n>> +\t\t}\n>> +\t}\n> OK, we marked \"to\" with PARENT1 and counted them in num_to_find\n> without dups. We also marked \"from\" with PARENT2 and threw them in\n> the \"queue\" without dups.\n>\n> Mental note: the caller must guarantee that everybody reachable from\n> \"to\" and \"from\" have PARENT1 and PARENT2 clear. This might deserve\n> to be in the comment before the function.\n\nI'll put that in the header file.\n\n[snip]\n> OK, this all makes sense. Unlike merge-base traversals, this does\n> not have to traverse from the \"to\" side at all, which makes it quite\n> simpler and straight-forward.\n>\n> I do wonder if we can now reimplement in_merge_bases_many() in terms\n> of this helper, and if that gives us a better performance. It asks\n> \"is 'commit', i.e. a single 'to', an ancestor of, i.e. reachable\n> from, one of the 'references', i.e. 'from'\"?\n\nWe could do this, but it does come with a performance hit when the following\nare all true:\n\n1. 'to' is not reachable from any 'from' commits.\n\n2. The 'to' and 'from' commits are close in commit-date.\n\n3. Generation numbers are not available, or the topology is skewed to have\n    commits with high commit date and low generation number.\n\nSince in_merge_bases_many() calls paint_down_to_common(), it has the same\nissues with the current generation numbers. This can be fixed when we have\nthe next version of generation numbers available.\n\nI'll make a note to have in_merge_bases_many() call get_reachable_subset()\nconditionally (like the generation_numbers_available() trick in the \n--topo-order\nseries) after the generation numbers are settled and implemented.\n\nThanks,\n-Stolee\n"},{"id":"362095","messageId":"20181031120505.237235-1-dstolee@microsoft.com","threadId":"49715","inReplyTo":"CABPp-BFzwphzaMjCWrNxU2V+YeYvRiBOzSV--b13wa7r16dvMQ@mail.gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-31T12:05:05Z","receivedAt":"2018-10-31T12:05:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"\nOn 10/31/2018 2:04 AM, Elijah Newren wrote:\n> On Tue, Oct 30, 2018 at 7:16 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> As reported earlier [1], the add_missing_tags() method in remote.c has\n>> quadratic performance. Some of that performance is curbed due to the\n>> generation-number cutoff in in_merge_bases_many(). However, that fix doesn't\n>> help users without a commit-graph, and it can still be painful if that\n>> cutoff is sufficiently low compared to the tags we are using for\n>> reachability testing.\n>>\n>> Add a new method in commit-reach.c called get_reachable_subset() which does\n>> a many-to-many reachability test. Starting at the 'from' commits, walk until\n>> the generation is below the smallest generation in the 'to' commits, or all\n>> 'to' commits have been discovered. This performs only one commit walk for\n>> the entire add_missing_tags() method, giving linear performance in the worst\n>> case.\n>>\n>> Tests are added in t6600-test-reach.sh to ensure get_reachable_subset()\n>> works independently of its application in add_missing_tags().\n>\n> On the original repo where the topic was brought up, with commit-graph\n> NOT turned on and using origin/master, I see:\n>\n> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> To /home/newren/repo-mirror\n> * [new branch] test5 -> test5\n>\n> real 1m20.081s\n> user 1m19.688s\n> sys 0m0.292s\n>\n> Merging this series in, I now get:\n>\n> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> To /home/newren/repo-mirror\n> * [new branch] test5 -> test5\n>\n> real 0m2.857s\n> user 0m2.580s\n> sys 0m0.328s\n>\n> which provides a very nice speedup.\n>\n> Oddly enough, if I _also_ do the following:\n> $ git config core.commitgraph true\n> $ git config gc.writecommitgraph true\n> $ git gc\n>\n> then my timing actually slows down just slightly:\n> $ time git push --follow-tags --dry-run /home/newren/repo-mirror\n> To /home/newren/repo-mirror\n> * [new branch] test5 -> test5\n>\n> real 0m3.027s\n> user 0m2.696s\n> sys 0m0.400s\n\nSo you say that the commit-graph is off in the 2.8s case, but not here\nin the 3.1s case? I would expect _at minimum_ that the cost of parsing\ncommits would have a speedup in the commit-graph case. There may be\nsomething else going on here, since you are timing a `push` event that\nis doing more than the current walk.\n\n> (run-to-run variation seems pretty consistent, < .1s variation, so\n> this difference is just enough to notice.) I wouldn't be that\n> surprised if that means there's some really old tags with very small\n> generation numbers, meaning it's not gaining anything in this special\n> case from the commit-graph, but it does pay the cost of loading the\n> commit-graph.\n\nWhile you have this test environment, do you mind applying the diff\nbelow and re-running the tests? It will output a count for how many\ncommits are walked by the algorithm. This should help us determine if\nthis is another case where generation numbers are worse than commit-date,\nor if there is something else going on. Thanks!\n\n-->8--\n\nFrom 2115e7dcafb2770455b7b4793f90edc2254bad97 Mon Sep 17 00:00:00 2001\nFrom: Derrick Stolee \nDate: Wed, 31 Oct 2018 11:40:50 +0000\nSubject: [PATCH] DO-NOT-MERGE: count commits in get_reachable_subset\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex a98532ecc8..b512461cf7 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -700,6 +700,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \tstruct commit **from_last = from + nr_from;\n \tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n \tint num_to_find = 0;\n+\tint count = 0;\n \n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \n@@ -729,6 +730,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \twhile (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n \t\tstruct commit_list *parents;\n \n+\t\tcount++;\n+\n \t\tif (current->object.flags & PARENT1) {\n \t\t\tcurrent->object.flags &= ~PARENT1;\n \t\t\tcurrent->object.flags |= reachable_flag;\n@@ -755,6 +758,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \tclear_commit_marks_many(nr_to, to, PARENT1);\n \tclear_commit_marks_many(nr_from, from, PARENT2);\n \n+\tfprintf(stderr, \"count: %d\\n\", count);\n+\n \treturn found_commits;\n }\n \n-- \n2.19.1.542.gc4df23f792\n\n"},{"id":"362151","messageId":"CABPp-BHHG9K0869=4CYkqjN6rwLCzRBiF_Z94KFevSo3_FvYAw@mail.gmail.com","threadId":"49715","inReplyTo":"20181031120505.237235-1-dstolee@microsoft.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-11-01T06:52:01Z","receivedAt":"2018-11-01T06:52:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Oct 31, 2018 at 5:05 AM Derrick Stolee wrote:\n>\n> On 10/31/2018 2:04 AM, Elijah Newren wrote:\n> > On Tue, Oct 30, 2018 at 7:16 AM Derrick Stolee via GitGitGadget\n> > wrote:\n> >>\n> >> As reported earlier [1], the add_missing_tags() method in remote.c has\n> >> quadratic performance. Some of that performance is curbed due to the\n> >> generation-number cutoff in in_merge_bases_many(). However, that fix doesn't\n> >> help users without a commit-graph, and it can still be painful if that\n> >> cutoff is sufficiently low compared to the tags we are using for\n> >> reachability testing.\n> >>\n> >> Add a new method in commit-reach.c called get_reachable_subset() which does\n> >> a many-to-many reachability test. Starting at the 'from' commits, walk until\n> >> the generation is below the smallest generation in the 'to' commits, or all\n> >> 'to' commits have been discovered. This performs only one commit walk for\n> >> the entire add_missing_tags() method, giving linear performance in the worst\n> >> case.\n> >>\n> >> Tests are added in t6600-test-reach.sh to ensure get_reachable_subset()\n> >> works independently of its application in add_missing_tags().\n> >\n> > On the original repo where the topic was brought up, with commit-graph\n> > NOT turned on and using origin/master, I see:\n> >\n> > $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> > To /home/newren/repo-mirror\n> > * [new branch] test5 -> test5\n> >\n> > real 1m20.081s\n> > user 1m19.688s\n> > sys 0m0.292s\n> >\n> > Merging this series in, I now get:\n> >\n> > $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> > To /home/newren/repo-mirror\n> > * [new branch] test5 -> test5\n> >\n> > real 0m2.857s\n> > user 0m2.580s\n> > sys 0m0.328s\n> >\n> > which provides a very nice speedup.\n> >\n> > Oddly enough, if I _also_ do the following:\n> > $ git config core.commitgraph true\n> > $ git config gc.writecommitgraph true\n> > $ git gc\n> >\n> > then my timing actually slows down just slightly:\n> > $ time git push --follow-tags --dry-run /home/newren/repo-mirror\n> > To /home/newren/repo-mirror\n> > * [new branch] test5 -> test5\n> >\n> > real 0m3.027s\n> > user 0m2.696s\n> > sys 0m0.400s\n>\n> So you say that the commit-graph is off in the 2.8s case, but not here\n> in the 3.1s case? I would expect _at minimum_ that the cost of parsing\n> commits would have a speedup in the commit-graph case. There may be\n> something else going on here, since you are timing a `push` event that\n> is doing more than the current walk.\n>\n> > (run-to-run variation seems pretty consistent, < .1s variation, so\n> > this difference is just enough to notice.) I wouldn't be that\n> > surprised if that means there's some really old tags with very small\n> > generation numbers, meaning it's not gaining anything in this special\n> > case from the commit-graph, but it does pay the cost of loading the\n> > commit-graph.\n>\n> While you have this test environment, do you mind applying the diff\n> below and re-running the tests? It will output a count for how many\n> commits are walked by the algorithm. This should help us determine if\n> this is another case where generation numbers are worse than commit-date,\n> or if there is something else going on. Thanks!\n\nI can do that, but wouldn't you want a similar patch for the old\nget_merge_bases_many() in order to compare? Does an absolute number\nhelp by itself?\nIt's going to have to be tomorrow, though; not enough time tonight.\n"},{"id":"362171","messageId":"ad4ab388-6244-1811-ec1b-6f8143df620e@gmail.com","threadId":"49715","inReplyTo":"CABPp-BHHG9K0869=4CYkqjN6rwLCzRBiF_Z94KFevSo3_FvYAw@mail.gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-11-01T12:32:14Z","receivedAt":"2018-11-01T12:32:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 11/1/2018 2:52 AM, Elijah Newren wrote:\n> On Wed, Oct 31, 2018 at 5:05 AM Derrick Stolee wrote:\n>> On 10/31/2018 2:04 AM, Elijah Newren wrote:\n>>>\n>>> On the original repo where the topic was brought up, with commit-graph\n>>> NOT turned on and using origin/master, I see:\n>>>\n>>> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n>>> To /home/newren/repo-mirror\n>>> * [new branch] test5 -> test5\n>>>\n>>> real 1m20.081s\n>>> user 1m19.688s\n>>> sys 0m0.292s\n>>>\n>>> Merging this series in, I now get:\n>>>\n>>> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n>>> To /home/newren/repo-mirror\n>>> * [new branch] test5 -> test5\n>>>\n>>> real 0m2.857s\n>>> user 0m2.580s\n>>> sys 0m0.328s\n>>>\n>>> which provides a very nice speedup.\n>>>\n>>> Oddly enough, if I _also_ do the following:\n>>> $ git config core.commitgraph true\n>>> $ git config gc.writecommitgraph true\n>>> $ git gc\n>>>\n>>> then my timing actually slows down just slightly:\n>>> $ time git push --follow-tags --dry-run /home/newren/repo-mirror\n>>> To /home/newren/repo-mirror\n>>> * [new branch] test5 -> test5\n>>>\n>>> real 0m3.027s\n>>> user 0m2.696s\n>>> sys 0m0.400s\n>> So you say that the commit-graph is off in the 2.8s case, but not here\n>> in the 3.1s case? I would expect _at minimum_ that the cost of parsing\n>> commits would have a speedup in the commit-graph case. There may be\n>> something else going on here, since you are timing a `push` event that\n>> is doing more than the current walk.\n>>\n>>> (run-to-run variation seems pretty consistent, < .1s variation, so\n>>> this difference is just enough to notice.) I wouldn't be that\n>>> surprised if that means there's some really old tags with very small\n>>> generation numbers, meaning it's not gaining anything in this special\n>>> case from the commit-graph, but it does pay the cost of loading the\n>>> commit-graph.\n>> While you have this test environment, do you mind applying the diff\n>> below and re-running the tests? It will output a count for how many\n>> commits are walked by the algorithm. This should help us determine if\n>> this is another case where generation numbers are worse than commit-date,\n>> or if there is something else going on. Thanks!\n> I can do that, but wouldn't you want a similar patch for the old\n> get_merge_bases_many() in order to compare? Does an absolute number\n> help by itself?\n> It's going to have to be tomorrow, though; not enough time tonight.\n\nNo rush. I'd just like to understand how removing the commit-graph file\ncan make the new algorithm faster. Putting a similar count in the old\nalgorithm would involve giving a count for every call to\nin_merge_bases_many(), which would be very noisy.\n\nThanks!\n-Stolee\n"},{"id":"362205","messageId":"CABPp-BG6+3F+FY0JP2mj0OCLjp17xQXTe54mBCN+RifQd4Aj2A@mail.gmail.com","threadId":"49715","inReplyTo":"ad4ab388-6244-1811-ec1b-6f8143df620e@gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-11-01T18:57:29Z","receivedAt":"2018-11-01T18:57:45Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Nov 1, 2018 at 5:32 AM Derrick Stolee wrote:\n> On 11/1/2018 2:52 AM, Elijah Newren wrote:\n> > On Wed, Oct 31, 2018 at 5:05 AM Derrick Stolee wrote:\n> >> On 10/31/2018 2:04 AM, Elijah Newren wrote:\n> >>>\n> >>> On the original repo where the topic was brought up, with commit-graph\n> >>> NOT turned on and using origin/master, I see:\n> >>>\n> >>> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> >>> To /home/newren/repo-mirror\n> >>> * [new branch] test5 -> test5\n> >>>\n> >>> real 1m20.081s\n> >>> user 1m19.688s\n> >>> sys 0m0.292s\n> >>>\n> >>> Merging this series in, I now get:\n> >>>\n> >>> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> >>> To /home/newren/repo-mirror\n> >>> * [new branch] test5 -> test5\n> >>>\n> >>> real 0m2.857s\n> >>> user 0m2.580s\n> >>> sys 0m0.328s\n> >>>\n> >>> which provides a very nice speedup.\n> >>>\n> >>> Oddly enough, if I _also_ do the following:\n> >>> $ git config core.commitgraph true\n> >>> $ git config gc.writecommitgraph true\n> >>> $ git gc\n> >>>\n> >>> then my timing actually slows down just slightly:\n> >>> $ time git push --follow-tags --dry-run /home/newren/repo-mirror\n> >>> To /home/newren/repo-mirror\n> >>> * [new branch] test5 -> test5\n> >>>\n> >>> real 0m3.027s\n> >>> user 0m2.696s\n> >>> sys 0m0.400s\n> >> So you say that the commit-graph is off in the 2.8s case, but not here\n> >> in the 3.1s case? I would expect _at minimum_ that the cost of parsing\n> >> commits would have a speedup in the commit-graph case. There may be\n> >> something else going on here, since you are timing a `push` event that\n> >> is doing more than the current walk.\n> >>\n> >>> (run-to-run variation seems pretty consistent, < .1s variation, so\n> >>> this difference is just enough to notice.) I wouldn't be that\n> >>> surprised if that means there's some really old tags with very small\n> >>> generation numbers, meaning it's not gaining anything in this special\n> >>> case from the commit-graph, but it does pay the cost of loading the\n> >>> commit-graph.\n> >> While you have this test environment, do you mind applying the diff\n> >> below and re-running the tests? It will output a count for how many\n> >> commits are walked by the algorithm. This should help us determine if\n> >> this is another case where generation numbers are worse than commit-date,\n> >> or if there is something else going on. Thanks!\n> > I can do that, but wouldn't you want a similar patch for the old\n> > get_merge_bases_many() in order to compare? Does an absolute number\n> > help by itself?\n> > It's going to have to be tomorrow, though; not enough time tonight.\n>\n> No rush. I'd just like to understand how removing the commit-graph file\n> can make the new algorithm faster. Putting a similar count in the old\n> algorithm would involve giving a count for every call to\n> in_merge_bases_many(), which would be very noisy.\n\n$ time git push --dry-run --follow-tags /home/newren/repo-mirror\ncount: 92912\nTo /home/newren/repo-mirror\n * [new branch] test5 -> test5\n\nreal 0m3.024s\nuser 0m2.752s\nsys 0m0.320s\n\n\nAlso:\n$ git rev-list --count HEAD\n55764\n$ git rev-list --count --all\n91820\n\nSeems a little odd to me that count is greater than `git rev-list\n--count --all`. However, the fact that they are close in magnitude\nisn't surprising since I went digging for the commit with smallest\ngeneration number not found in the upstream repo, and found:\n$ git ls-remote /home/newren/repo-mirror/ | grep refs/tags/v0.2.0; echo $?\n1\n$ git rev-list --count refs/tags/v0.2.0\n4\n$ git rev-list --count refs/tags/v0.2.0 ^HEAD\n4\n\n\nSo, the commit-graph can only help us avoid parsing 3 or so commits,\nbut we have to parse the 5M .git/objects/info/commit-graph file, and\nthen for every parse_commit() call we need to bsearch_graph() for the\ncommit. My theory is that parsing the commit-graph file and binary\nsearching it for commits is relatively fast, but that the time is just\nbig enough to measure and notice, while avoiding parsing 3 more\ncommits is a negligible time savings.\n\nTo me, I'm thinking this is one of those bizarre corner cases where\nthe commit-graph is almost imperceptibly slower than without the\ncommit-graph. (And it is a very weird repo; someone repeatedly\nfilter-branched lots of small independent repos into a monorepo, but\ndidn't always push everything and didn't clean out all old stuff.)\nBut if you still see weird stuff you want to dig into further (maybe\nthe 92912 > 91820 bit?), I'm happy to try out other stuff.\n"},{"id":"362206","messageId":"3aadf261-9ed7-6ded-4482-ab01d74802aa@gmail.com","threadId":"49715","inReplyTo":"CABPp-BG6+3F+FY0JP2mj0OCLjp17xQXTe54mBCN+RifQd4Aj2A@mail.gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-11-01T19:02:08Z","receivedAt":"2018-11-01T19:02:14Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 11/1/2018 2:57 PM, Elijah Newren wrote:\n> On Thu, Nov 1, 2018 at 5:32 AM Derrick Stolee wrote:\n>> No rush. I'd just like to understand how removing the commit-graph file\n>> can make the new algorithm faster. Putting a similar count in the old\n>> algorithm would involve giving a count for every call to\n>> in_merge_bases_many(), which would be very noisy.\n> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> count: 92912\n> To /home/newren/repo-mirror\n> * [new branch] test5 -> test5\n>\n> real 0m3.024s\n> user 0m2.752s\n> sys 0m0.320s\n\nIs the above test with or without the commit-graph file? Can you run it \nin the other mode, too? I'd like to see if the \"count\" value changes \nwhen the only difference is the presence of a commit-graph file.\n\nThanks,\n-Stolee\n"},{"id":"362224","messageId":"xmqqk1lws0vh.fsf@gitster-ct.c.googlers.com","threadId":"49715","inReplyTo":"15ef2018-4bb1-430f-32fd-5676a1b5ac1a@gmail.com","subject":"Re: [PATCH 1/3] commit-reach: implement get_reachable_subset","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-11-02T01:51:14Z","receivedAt":"2018-11-02T01:51:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> We could do this, but it does come with a performance hit when the following\n> are all true:\n>\n> 1. 'to' is not reachable from any 'from' commits.\n>\n> 2. The 'to' and 'from' commits are close in commit-date.\n>\n> 3. Generation numbers are not available, or the topology is skewed to have\n> commits with high commit date and low generation number.\n>\n> Since in_merge_bases_many() calls paint_down_to_common(), it has the same\n> issues with the current generation numbers. This can be fixed when we have\n> the next version of generation numbers available.\n>\n> I'll make a note to have in_merge_bases_many() call get_reachable_subset()\n> conditionally (like the generation_numbers_available() trick in the\n> --topo-order\n> series) after the generation numbers are settled and implemented.\n\nSounds good.\n\nI wondered how this compares with in_merge_bases_many() primarily\nbecause how performance characteristics between two approaches trade\noff. After all, what it needs to compute is a specialized case of\nget_reachable_subset() where \"to\" happens to be a set with only\nsingle element. If the latter with a single element \"to\" has the\nabove performance \"issues\" compared to paint-down-to-common based\napproach, it could be possible that, for small enough N>1, running N\nin_merge_bases_many() traversals is more performant than a single\nget_reachable_subset() call that works on N-element \"to\".\n\nI am hoping that an update to better generation numbers to help\nget_reachable_subset() would help paint-down-to-common the same way,\nand would eventually allow us to use a single traversal that is best\nfor N==1 and N>1.\n\nThanks.\n\n"},{"id":"362265","messageId":"pull.60.v2.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.git.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] Make add_missing_tags() linear","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-11-02T13:14:44Z","receivedAt":"2018-11-02T13:14:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As reported earlier [1], the add_missing_tags() method in remote.c has\nquadratic performance. Some of that performance is curbed due to the\ngeneration-number cutoff in in_merge_bases_many(). However, that fix doesn't\nhelp users without a commit-graph, and it can still be painful if that\ncutoff is sufficiently low compared to the tags we are using for\nreachability testing.\n\nAdd a new method in commit-reach.c called get_reachable_subset() which does\na many-to-many reachability test. Starting at the 'from' commits, walk until\nthe generation is below the smallest generation in the 'to' commits, or all\n'to' commits have been discovered. This performs only one commit walk for\nthe entire add_missing_tags() method, giving linear performance in the worst\ncase.\n\nTests are added in t6600-test-reach.sh to ensure get_reachable_subset()\nworks independently of its application in add_missing_tags().\n\nThanks, -Stolee\n\n[1] \nhttps://public-inbox.org/git/CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com/\n\nDerrick Stolee (3):\n commit-reach: implement get_reachable_subset\n test-reach: test get_reachable_subset\n remote: make add_missing_tags() linear\n\n commit-reach.c | 70 +++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 13 ++++++++\n remote.c | 34 ++++++++++++++++++++-\n t/helper/test-reach.c | 34 ++++++++++++++++++---\n t/t6600-test-reach.sh | 52 ++++++++++++++++++++++++++++++++\n 5 files changed, 198 insertions(+), 5 deletions(-)\n\n\nbase-commit: c670b1f876521c9f7cd40184bf7ed05aad843433\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-60%2Fderrickstolee%2Fadd-missing-tags-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-60/derrickstolee/add-missing-tags-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/60\n\nRange-diff vs v1:\n\n 1: 4c0c5c9143 ! 1: 9e570603bd commit-reach: implement get_reachable_subset\n @@ -49,7 +49,7 @@\n +\n +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n +\t\t\t\t\t struct commit **to, int nr_to,\n -+\t\t\t\t\t int reachable_flag)\n ++\t\t\t\t\t unsigned int reachable_flag)\n +{\n +\tstruct commit **item;\n +\tstruct commit *current;\n @@ -129,9 +129,12 @@\n + * Return a list of commits containing the commits in the 'to' array\n + * that are reachable from at least one commit in the 'from' array.\n + * Also add the given 'flag' to each of the commits in the returned list.\n ++ *\n ++ * This method uses the PARENT1 and PARENT2 flags during its operation,\n ++ * so be sure these flags are not set before calling the method.\n + */\n +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n +\t\t\t\t\t struct commit **to, int nr_to,\n -+\t\t\t\t\t int reachable_flag);\n ++\t\t\t\t\t unsigned int reachable_flag);\n +\n #endif\n 2: 382f4f4a5b = 2: 52e847b928 test-reach: test get_reachable_subset\n 3: ecbed3de5c = 3: dfaceb162f remote: make add_missing_tags() linear\n\n-- \ngitgitgadget\n"},{"id":"362266","messageId":"9e570603bda528986f425cae8a9c32ba700bc29b.1541164482.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] commit-reach: implement get_reachable_subset","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-11-02T13:14:45Z","receivedAt":"2018-11-02T13:14:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe existing reachability algorithms in commit-reach.c focus on\nfinding merge-bases or determining if all commits in a set X can\nreach at least one commit in a set Y. However, for two commits sets\nX and Y, we may also care about which commits in Y are reachable\nfrom at least one commit in X.\n\nImplement get_reachable_subset() which answers this question. Given\ntwo arrays of commits, 'from' and 'to', return a commit_list with\nevery commit from the 'to' array that is reachable from at least\none commit in the 'from' array.\n\nThe algorithm is a simple walk starting at the 'from' commits, using\nthe PARENT2 flag to indicate \"this commit has already been added to\nthe walk queue\". By marking the 'to' commits with the PARENT1 flag,\nwe can determine when we see a commit from the 'to' array. We remove\nthe PARENT1 flag as we add that commit to the result list to avoid\nduplicates.\n\nThe order of the resulting list is a reverse of the order that the\ncommits are discovered in the walk.\n\nThere are a couple shortcuts to avoid walking more than we need:\n\n1. We determine the minimum generation number of commits in the\n 'to' array. We do not walk commits with generation number\n below this minimum.\n\n2. We count how many distinct commits are in the 'to' array, and\n decrement this count when we discover a 'to' commit during the\n walk. If this number reaches zero, then we can terminate the\n walk.\n\nTests will be added using the 'test-tool reach' helper in a\nsubsequent commit.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 13 ++++++++++\n 2 files changed, 83 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9f79ce0a22..8ad5352752 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \tobject_array_clear(&from_objs);\n \treturn result;\n }\n+\n+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n+\t\t\t\t\t struct commit **to, int nr_to,\n+\t\t\t\t\t unsigned int reachable_flag)\n+{\n+\tstruct commit **item;\n+\tstruct commit *current;\n+\tstruct commit_list *found_commits = NULL;\n+\tstruct commit **to_last = to + nr_to;\n+\tstruct commit **from_last = from + nr_from;\n+\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tint num_to_find = 0;\n+\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\n+\tfor (item = to; item < to_last; item++) {\n+\t\tstruct commit *c = *item;\n+\t\t\n+\t\tparse_commit(c);\n+\t\tif (c->generation < min_generation)\n+\t\t\tmin_generation = c->generation;\n+\n+\t\tif (!(c->object.flags & PARENT1)) {\n+\t\t\tc->object.flags |= PARENT1;\n+\t\t\tnum_to_find++;\n+\t\t}\n+\t}\n+\n+\tfor (item = from; item < from_last; item++) {\n+\t\tstruct commit *c = *item;\n+\t\tif (!(c->object.flags & PARENT2)) {\n+\t\t\tc->object.flags |= PARENT2;\n+\t\t\tparse_commit(c);\n+\n+\t\t\tprio_queue_put(&queue, *item);\n+\t\t}\n+\t}\n+\n+\twhile (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n+\t\tstruct commit_list *parents;\n+\n+\t\tif (current->object.flags & PARENT1) {\n+\t\t\tcurrent->object.flags &= ~PARENT1;\n+\t\t\tcurrent->object.flags |= reachable_flag;\n+\t\t\tcommit_list_insert(current, &found_commits);\n+\t\t\tnum_to_find--;\n+\t\t}\n+\n+\t\tfor (parents = current->parents; parents; parents = parents->next) {\n+\t\t\tstruct commit *p = parents->item;\n+\n+\t\t\tparse_commit(p);\n+\n+\t\t\tif (p->generation < min_generation)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (p->object.flags & PARENT2)\n+\t\t\t\tcontinue;\n+\n+\t\t\tp->object.flags |= PARENT2;\n+\t\t\tprio_queue_put(&queue, p);\n+\t\t}\n+\t}\n+\n+\tclear_commit_marks_many(nr_to, to, PARENT1);\n+\tclear_commit_marks_many(nr_from, from, PARENT2);\n+\n+\treturn found_commits;\n+}\n+\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 7d313e2975..bb34af0269 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -74,4 +74,17 @@ int can_all_from_reach_with_flag(struct object_array *from,\n int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t int commit_date_cutoff);\n \n+\n+/*\n+ * Return a list of commits containing the commits in the 'to' array\n+ * that are reachable from at least one commit in the 'from' array.\n+ * Also add the given 'flag' to each of the commits in the returned list.\n+ *\n+ * This method uses the PARENT1 and PARENT2 flags during its operation,\n+ * so be sure these flags are not set before calling the method.\n+ */\n+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n+\t\t\t\t\t struct commit **to, int nr_to,\n+\t\t\t\t\t unsigned int reachable_flag);\n+\n #endif\n-- \ngitgitgadget\n\n"},{"id":"362267","messageId":"52e847b9288439f25a7e06abfe0c68bc1e6dc915.1541164482.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] test-reach: test get_reachable_subset","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-11-02T13:14:47Z","receivedAt":"2018-11-02T13:14:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe get_reachable_subset() method returns the list of commits in\nthe 'to' array that are reachable from at least one commit in the\n'from' array. Add tests that check this method works in a few\ncases:\n\n1. All commits in the 'to' list are reachable. This exercises the\n early-termination condition.\n\n2. Some commits in the 'to' list are reachable. This exercises the\n loop-termination condition.\n\n3. No commits in the 'to' list are reachable. This exercises the\n NULL return condition.\n\nSigned-off-by: Derrick Stolee \n---\n t/helper/test-reach.c | 34 ++++++++++++++++++++++++----\n t/t6600-test-reach.sh | 52 +++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 82 insertions(+), 4 deletions(-)\n\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 08d2ea68e8..a0272178b7 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -32,8 +32,8 @@ int cmd__reach(int ac, const char **av)\n \tstruct commit *A, *B;\n \tstruct commit_list *X, *Y;\n \tstruct object_array X_obj = OBJECT_ARRAY_INIT;\n-\tstruct commit **X_array;\n-\tint X_nr, X_alloc;\n+\tstruct commit **X_array, **Y_array;\n+\tint X_nr, X_alloc, Y_nr, Y_alloc;\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct repository *r = the_repository;\n \n@@ -44,9 +44,10 @@ int cmd__reach(int ac, const char **av)\n \n \tA = B = NULL;\n \tX = Y = NULL;\n-\tX_nr = 0;\n-\tX_alloc = 16;\n+\tX_nr = Y_nr = 0;\n+\tX_alloc = Y_alloc = 16;\n \tALLOC_ARRAY(X_array, X_alloc);\n+\tALLOC_ARRAY(Y_array, Y_alloc);\n \n \twhile (strbuf_getline(&buf, stdin) != EOF) {\n \t\tstruct object_id oid;\n@@ -92,6 +93,8 @@ int cmd__reach(int ac, const char **av)\n \n \t\t\tcase 'Y':\n \t\t\t\tcommit_list_insert(c, &Y);\n+\t\t\t\tALLOC_GROW(Y_array, Y_nr + 1, Y_alloc);\n+\t\t\t\tY_array[Y_nr++] = c;\n \t\t\t\tbreak;\n \n \t\t\tdefault:\n@@ -136,6 +139,29 @@ int cmd__reach(int ac, const char **av)\n \t\t\tfilter.with_commit_tag_algo = 0;\n \n \t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n+\t} else if (!strcmp(av[1], \"get_reachable_subset\")) {\n+\t\tconst int reachable_flag = 1;\n+\t\tint i, count = 0;\n+\t\tstruct commit_list *current;\n+\t\tstruct commit_list *list = get_reachable_subset(X_array, X_nr,\n+\t\t\t\t\t\t\t\tY_array, Y_nr,\n+\t\t\t\t\t\t\t\treachable_flag);\n+\t\tprintf(\"get_reachable_subset(X,Y)\\n\");\n+\t\tfor (current = list; current; current = current->next) {\n+\t\t\tif (!(list->item->object.flags & reachable_flag))\n+\t\t\t\tdie(_(\"commit %s is not marked reachable\"),\n+\t\t\t\t oid_to_hex(&list->item->object.oid));\n+\t\t\tcount++;\n+\t\t}\n+\t\tfor (i = 0; i < Y_nr; i++) {\n+\t\t\tif (Y_array[i]->object.flags & reachable_flag)\n+\t\t\t\tcount--;\n+\t\t}\n+\n+\t\tif (count < 0)\n+\t\t\tdie(_(\"too many commits marked reachable\"));\n+\n+\t\tprint_sorted_commit_ids(list);\n \t}\n \n \texit(0);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex ae94b27f70..a0c64e617a 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -265,4 +265,56 @@ test_expect_success 'commit_contains:miss' '\n \ttest_three_modes commit_contains --tag\n '\n \n+test_expect_success 'get_reachable_subset:all' '\n+\tcat >input <<-\\EOF &&\n+\tX:commit-9-1\n+\tX:commit-8-3\n+\tX:commit-7-5\n+\tX:commit-6-6\n+\tX:commit-1-7\n+\tY:commit-3-3\n+\tY:commit-1-7\n+\tY:commit-5-6\n+\tEOF\n+\t(\n+\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\tgit rev-parse commit-3-3 \\\n+\t\t\t commit-1-7 \\\n+\t\t\t commit-5-6 | sort\n+\t) >expect &&\n+\ttest_three_modes get_reachable_subset\n+'\n+\n+test_expect_success 'get_reachable_subset:some' '\n+\tcat >input <<-\\EOF &&\n+\tX:commit-9-1\n+\tX:commit-8-3\n+\tX:commit-7-5\n+\tX:commit-1-7\n+\tY:commit-3-3\n+\tY:commit-1-7\n+\tY:commit-5-6\n+\tEOF\n+\t(\n+\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\tgit rev-parse commit-3-3 \\\n+\t\t\t commit-1-7 | sort\n+\t) >expect &&\n+\ttest_three_modes get_reachable_subset\n+'\n+\n+test_expect_success 'get_reachable_subset:none' '\n+\tcat >input <<-\\EOF &&\n+\tX:commit-9-1\n+\tX:commit-8-3\n+\tX:commit-7-5\n+\tX:commit-1-7\n+\tY:commit-9-3\n+\tY:commit-7-6\n+\tY:commit-2-8\n+\tEOF\n+\techo \"get_reachable_subset(X,Y)\" >expect &&\n+\ttest_three_modes get_reachable_subset\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"362268","messageId":"dfaceb162f2f1f40ff8f28f9e62a646e56bbd15a.1541164482.git.gitgitgadget@gmail.com","threadId":"49715","inReplyTo":"pull.60.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] remote: make add_missing_tags() linear","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-11-02T13:14:49Z","receivedAt":"2018-11-02T13:14:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe add_missing_tags() method currently has quadratic behavior.\nThis is due to a linear number (based on number of tags T) of\ncalls to in_merge_bases_many, which has linear performance (based\non number of commits C in the repository).\n\nReplace this O(T * C) algorithm with an O(T + C) algorithm by\nusing get_reachable_subset(). We ignore the return list and focus\ninstead on the reachable_flag assigned to the commits we care\nabout, because we need to interact with the tag ref and not just\nthe commit object.\n\nSigned-off-by: Derrick Stolee \n---\n remote.c | 34 +++++++++++++++++++++++++++++++++-\n 1 file changed, 33 insertions(+), 1 deletion(-)\n\ndiff --git a/remote.c b/remote.c\nindex 81f4f01b00..b850f2feb3 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1205,9 +1205,36 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t * sent to the other side.\n \t */\n \tif (sent_tips.nr) {\n+\t\tconst int reachable_flag = 1;\n+\t\tstruct commit_list *found_commits;\n+\t\tstruct commit **src_commits;\n+\t\tint nr_src_commits = 0, alloc_src_commits = 16;\n+\t\tALLOC_ARRAY(src_commits, alloc_src_commits);\n+\n \t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *ref = item->util;\n+\t\t\tstruct commit *commit;\n+\n+\t\t\tif (is_null_oid(&ref->new_oid))\n+\t\t\t\tcontinue;\n+\t\t\tcommit = lookup_commit_reference_gently(the_repository,\n+\t\t\t\t\t\t\t\t&ref->new_oid,\n+\t\t\t\t\t\t\t\t1);\n+\t\t\tif (!commit)\n+\t\t\t\t/* not pushing a commit, which is not an error */\n+\t\t\t\tcontinue;\n+\n+\t\t\tALLOC_GROW(src_commits, nr_src_commits + 1, alloc_src_commits);\n+\t\t\tsrc_commits[nr_src_commits++] = commit;\n+\t\t}\n+\n+\t\tfound_commits = get_reachable_subset(sent_tips.tip, sent_tips.nr,\n+\t\t\t\t\t\t src_commits, nr_src_commits,\n+\t\t\t\t\t\t reachable_flag);\n+\n+\t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *dst_ref;\n+\t\t\tstruct ref *ref = item->util;\n \t\t\tstruct commit *commit;\n \n \t\t\tif (is_null_oid(&ref->new_oid))\n@@ -1223,7 +1250,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\t * Is this tag, which they do not have, reachable from\n \t\t\t * any of the commits we are sending?\n \t\t\t */\n-\t\t\tif (!in_merge_bases_many(commit, sent_tips.nr, sent_tips.tip))\n+\t\t\tif (!(commit->object.flags & reachable_flag))\n \t\t\t\tcontinue;\n \n \t\t\t/* Add it in */\n@@ -1231,7 +1258,12 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\toidcpy(&dst_ref->new_oid, &ref->new_oid);\n \t\t\tdst_ref->peer_ref = copy_ref(ref);\n \t\t}\n+\n+\t\tclear_commit_marks_many(nr_src_commits, src_commits, reachable_flag);\n+\t\tfree(src_commits);\n+\t\tfree_commit_list(found_commits);\n \t}\n+\n \tstring_list_clear(&src_tag, 0);\n \tfree(sent_tips.tip);\n }\n-- \ngitgitgadget\n"},{"id":"362272","messageId":"CABPp-BEa3U6m8jWrHJXjFo77T32LqEKkdDs7H89m0y_gjHgOWw@mail.gmail.com","threadId":"49715","inReplyTo":"3aadf261-9ed7-6ded-4482-ab01d74802aa@gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-11-02T14:58:21Z","receivedAt":"2018-11-02T14:58:36Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Nov 1, 2018 at 12:02 PM Derrick Stolee wrote:\n>\n> On 11/1/2018 2:57 PM, Elijah Newren wrote:\n> > On Thu, Nov 1, 2018 at 5:32 AM Derrick Stolee wrote:\n> >> No rush. I'd just like to understand how removing the commit-graph file\n> >> can make the new algorithm faster. Putting a similar count in the old\n> >> algorithm would involve giving a count for every call to\n> >> in_merge_bases_many(), which would be very noisy.\n> > $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n> > count: 92912\n> > To /home/newren/repo-mirror\n> > * [new branch] test5 -> test5\n> >\n> > real 0m3.024s\n> > user 0m2.752s\n> > sys 0m0.320s\n>\n> Is the above test with or without the commit-graph file? Can you run it\n> in the other mode, too? I'd like to see if the \"count\" value changes\n> when the only difference is the presence of a commit-graph file.\n\nI apologize for providing misleading information earlier; this was an\napples to oranges comparison. Here's what I did:\n\n\ngit clone coworker.bundle coworker-repo\ncd coworker-repo\ntime git push --dry-run --follow-tags /home/newren/repo-mirror\ngit config core.commitgraph true\ngit config gc.writecommitgraph true\ngit gc\ntime git push --dry-run --follow-tags /home/newren/nucleus-mirror\n\n\nI figured I had just done a fresh clone, so surely the gc wouldn't do\nanything other than write the .git/objects/info/commit-graph file.\nHowever, the original bundle contained many references outside of\nrefs/heads/ and refs/tags/:\n\n$ git bundle list-heads ../coworker.bundle | grep -v -e refs/heads/ -e\nrefs/tags/ -e HEAD | wc -l\n2396\n\nThese other refs apparently referred to objects not otherwise\nreferenced in refs/heads/ and refs/tags/, and caused the gc to explode\nlots of loose objects:\n$ git count-objects -v\ncount: 147604\nsize: 856416\nin-pack: 1180692\npacks: 1\nsize-pack: 796143\nprune-packable: 0\ngarbage: 0\nsize-garbage: 0\n\n\nThe slowdown with commit-graph was entirely due to there being lots of\nloose objects (147K of them). If I add a git-prune before doing the\ntiming with commit-graph, then the timing with commit-graph is faster\nthan the run without a commit-graph.\n\nSorry for the wild goose chase.\n\nAnd thanks for the fixes; get_reachable_subset() makes things much\nfaster even without a commit-graph, and the commit-graph just improves\nit more. :-)\n"},{"id":"362275","messageId":"ba7ee399-029d-8cff-c582-c3e54ab61796@gmail.com","threadId":"49715","inReplyTo":"CABPp-BEa3U6m8jWrHJXjFo77T32LqEKkdDs7H89m0y_gjHgOWw@mail.gmail.com","subject":"Re: [PATCH 0/3] Make add_missing_tags() linear","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-11-02T15:38:55Z","receivedAt":"2018-11-02T15:39:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 11/2/2018 10:58 AM, Elijah Newren wrote:\n> On Thu, Nov 1, 2018 at 12:02 PM Derrick Stolee wrote:\n>> On 11/1/2018 2:57 PM, Elijah Newren wrote:\n>>> On Thu, Nov 1, 2018 at 5:32 AM Derrick Stolee wrote:\n>>>> No rush. I'd just like to understand how removing the commit-graph file\n>>>> can make the new algorithm faster. Putting a similar count in the old\n>>>> algorithm would involve giving a count for every call to\n>>>> in_merge_bases_many(), which would be very noisy.\n>>> $ time git push --dry-run --follow-tags /home/newren/repo-mirror\n>>> count: 92912\n>>> To /home/newren/repo-mirror\n>>> * [new branch] test5 -> test5\n>>>\n>>> real 0m3.024s\n>>> user 0m2.752s\n>>> sys 0m0.320s\n>> Is the above test with or without the commit-graph file? Can you run it\n>> in the other mode, too? I'd like to see if the \"count\" value changes\n>> when the only difference is the presence of a commit-graph file.\n> I apologize for providing misleading information earlier; this was an\n> apples to oranges comparison. Here's what I did:\n>\n> \n> git clone coworker.bundle coworker-repo\n> cd coworker-repo\n> time git push --dry-run --follow-tags /home/newren/repo-mirror\n> git config core.commitgraph true\n> git config gc.writecommitgraph true\n> git gc\n> time git push --dry-run --follow-tags /home/newren/nucleus-mirror\n>\n>\n> I figured I had just done a fresh clone, so surely the gc wouldn't do\n> anything other than write the .git/objects/info/commit-graph file.\n> However, the original bundle contained many references outside of\n> refs/heads/ and refs/tags/:\n>\n> $ git bundle list-heads ../coworker.bundle | grep -v -e refs/heads/ -e\n> refs/tags/ -e HEAD | wc -l\n> 2396\n>\n> These other refs apparently referred to objects not otherwise\n> referenced in refs/heads/ and refs/tags/, and caused the gc to explode\n> lots of loose objects:\n> $ git count-objects -v\n> count: 147604\n> size: 856416\n> in-pack: 1180692\n> packs: 1\n> size-pack: 796143\n> prune-packable: 0\n> garbage: 0\n> size-garbage: 0\n>\n>\n> The slowdown with commit-graph was entirely due to there being lots of\n> loose objects (147K of them). If I add a git-prune before doing the\n> timing with commit-graph, then the timing with commit-graph is faster\n> than the run without a commit-graph.\n>\n> Sorry for the wild goose chase.\n>\n> And thanks for the fixes; get_reachable_subset() makes things much\n> faster even without a commit-graph, and the commit-graph just improves\n> it more. :-)\n\n\nThanks for double-checking! It's good to have confidence that this is a good\n\nalgorithm to use.\n\n\nThanks,\n\n-Stolee\n\n"}]}