{"thread":{"id":"31368","subject":"[PATCH 0/5] optimize fast-forward checks","startedAt":"2012-08-27T23:11:58Z","lastAt":"2012-08-30T22:16:38Z","messageCount":27,"participants":["Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"197948","messageId":"1346109123-12357-1-git-send-email-gitster@pobox.com","threadId":"31368","inReplyTo":null,"subject":"[PATCH 0/5] optimize fast-forward checks","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-27T23:11:58Z","receivedAt":"2012-08-27T23:11:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is a follow-up to $gmane/204149; somehow the discussion petered\nout, but I think this topic (and also \"tag --contains\" that was not\nreally discussed) needs to be looked into.  Here is a first baby\nstep.\n\n - The first one is an obvious simplification; we never supported\n   more than one \"reference\" commits and no caller had to invent a\n   loop around it to emulate multi-reference in_merge_base().\n\n - The two patches that follow are the uses of get_merge_bases()\n   where in_merge_bases() is sufficient.  These callers are not\n   interested in the merge bases between the two points; they only\n   want to know if one point is an ancestor of the other.\n\n - The next one [4/5] should be identical to Thomas's patch.\n\n - The last one attempts to reduce the cost of postprocessing from\n   N*(N-1) to N, but it somehow breaks 6010. I haven't looked into\n   why.  They say all bugs are shallow given enough eyeballs, so I\n   am sending it out to see if that is true ;-)\n\n\nJunio C Hamano (5):\n  in_merge_bases(): support only one \"other\" commit\n  receive-pack: use in_merge_bases() for fast-forward check\n  http-push: use in_merge_bases() for fast-forward check\n  in_merge_bases(): omit unnecessary redundant common ancestor\n    reduction\n  (BROKEN) get_merge_bases_many(): walk from many tips in parallel\n\n builtin/branch.c                       |  4 +--\n builtin/fetch.c                        |  2 +-\n builtin/receive-pack.c                 |  8 +----\n commit.c                               | 60 ++++++++++++++++++++--------------\n commit.h                               |  2 +-\n contrib/examples/builtin-fetch--tool.c |  2 +-\n fast-import.c                          |  2 +-\n http-push.c                            |  3 +-\n submodule.c                            | 12 +++----\n 9 files changed, 49 insertions(+), 46 deletions(-)\n\n-- \n1.7.12.116.g31e0100\n"},{"id":"197949","messageId":"1346109123-12357-2-git-send-email-gitster@pobox.com","threadId":"31368","inReplyTo":"1346109123-12357-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/5] in_merge_bases(): support only one \"other\" commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-27T23:11:59Z","receivedAt":"2012-08-27T23:11:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In early days of its life, I planned to make it possible to compute\n\"is a commit contained in all of these other commits?\" with this\nfunction, but it turned out that no caller needed it.\n\nJust make it take two commit objects and add a comment to say what\nthese two functions do.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/branch.c                       |  4 ++--\n builtin/fetch.c                        |  2 +-\n commit.c                               | 15 +++++++++------\n commit.h                               |  2 +-\n contrib/examples/builtin-fetch--tool.c |  2 +-\n fast-import.c                          |  2 +-\n submodule.c                            | 12 ++++++------\n 7 files changed, 21 insertions(+), 18 deletions(-)\n\ndiff --git a/builtin/branch.c b/builtin/branch.c\nindex 0e060f2..0360774 100644\n--- a/builtin/branch.c\n+++ b/builtin/branch.c\n@@ -129,7 +129,7 @@ static int branch_merged(int kind, const char *name,\n \tif (!reference_rev)\n \t\treference_rev = head_rev;\n \n-\tmerged = in_merge_bases(rev, &reference_rev, 1);\n+\tmerged = in_merge_bases(rev, reference_rev);\n \n \t/*\n \t * After the safety valve is fully redefined to \"check with\n@@ -139,7 +139,7 @@ static int branch_merged(int kind, const char *name,\n \t * a gentle reminder is in order.\n \t */\n \tif ((head_rev != reference_rev) &&\n-\t    in_merge_bases(rev, &head_rev, 1) != merged) {\n+\t    in_merge_bases(rev, head_rev) != merged) {\n \t\tif (merged)\n \t\t\twarning(_(\"deleting branch '%s' that has been merged to\\n\"\n \t\t\t\t\"         '%s', but not yet merged to HEAD.\"),\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex bb9a074..723072f 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -323,7 +323,7 @@ static int update_local_ref(struct ref *ref,\n \t\treturn r;\n \t}\n \n-\tif (in_merge_bases(current, &updated, 1)) {\n+\tif (in_merge_bases(current, updated)) {\n \t\tchar quickref[83];\n \t\tint r;\n \t\tstrcpy(quickref, find_unique_abbrev(current->object.sha1, DEFAULT_ABBREV));\ndiff --git a/commit.c b/commit.c\nindex 42af4c1..74ec5f1 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -780,6 +780,9 @@ struct commit_list *get_merge_bases(struct commit *one, struct commit *two,\n \treturn get_merge_bases_many(one, 1, &two, cleanup);\n }\n \n+/*\n+ * Is \"commit\" a decendant of one of the elements on the \"with_commit\" list?\n+ */\n int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n {\n \tif (!with_commit)\n@@ -789,21 +792,21 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n \n \t\tother = with_commit->item;\n \t\twith_commit = with_commit->next;\n-\t\tif (in_merge_bases(other, &commit, 1))\n+\t\tif (in_merge_bases(other, commit))\n \t\t\treturn 1;\n \t}\n \treturn 0;\n }\n \n-int in_merge_bases(struct commit *commit, struct commit **reference, int num)\n+/*\n+ * Is \"commit\" an ancestor of (i.e. reachable from) the \"reference\"?\n+ */\n+int in_merge_bases(struct commit *commit, struct commit *reference)\n {\n \tstruct commit_list *bases, *b;\n \tint ret = 0;\n \n-\tif (num == 1)\n-\t\tbases = get_merge_bases(commit, *reference, 1);\n-\telse\n-\t\tdie(\"not yet\");\n+\tbases = get_merge_bases(commit, reference, 1);\n \tfor (b = bases; b; b = b->next) {\n \t\tif (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n \t\t\tret = 1;\ndiff --git a/commit.h b/commit.h\nindex d617fa3..6edce87 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -171,7 +171,7 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,\n \t\tint depth, int shallow_flag, int not_shallow_flag);\n \n int is_descendant_of(struct commit *, struct commit_list *);\n-int in_merge_bases(struct commit *, struct commit **, int);\n+int in_merge_bases(struct commit *, struct commit *);\n \n extern int interactive_add(int argc, const char **argv, const char *prefix, int patch);\n extern int run_add_interactive(const char *revision, const char *patch_mode,\ndiff --git a/contrib/examples/builtin-fetch--tool.c b/contrib/examples/builtin-fetch--tool.c\nindex 0d54aa7..8bc8c75 100644\n--- a/contrib/examples/builtin-fetch--tool.c\n+++ b/contrib/examples/builtin-fetch--tool.c\n@@ -96,7 +96,7 @@ static int update_local_ref(const char *name,\n \tstrcpy(oldh, find_unique_abbrev(current->object.sha1, DEFAULT_ABBREV));\n \tstrcpy(newh, find_unique_abbrev(sha1_new, DEFAULT_ABBREV));\n \n-\tif (in_merge_bases(current, &updated, 1)) {\n+\tif (in_merge_bases(current, updated)) {\n \t\tfprintf(stderr, \"* %s: fast-forward to %s\\n\",\n \t\t\tname, note);\n \t\tfprintf(stderr, \"  old..new: %s..%s\\n\", oldh, newh);\ndiff --git a/fast-import.c b/fast-import.c\nindex eed97c8..c2a814e 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1691,7 +1691,7 @@ static int update_branch(struct branch *b)\n \t\t\treturn error(\"Branch %s is missing commits.\", b->name);\n \t\t}\n \n-\t\tif (!in_merge_bases(old_cmit, &new_cmit, 1)) {\n+\t\tif (!in_merge_bases(old_cmit, new_cmit)) {\n \t\t\tunlock_ref(lock);\n \t\t\twarning(\"Not updating %s\"\n \t\t\t\t\" (new tip %s does not contain %s)\",\ndiff --git a/submodule.c b/submodule.c\nindex 19dc6a6..d133796 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -788,7 +788,7 @@ static int find_first_merges(struct object_array *result, const char *path,\n \t\tdie(\"revision walk setup failed\");\n \twhile ((commit = get_revision(&revs)) != NULL) {\n \t\tstruct object *o = &(commit->object);\n-\t\tif (in_merge_bases(b, &commit, 1))\n+\t\tif (in_merge_bases(b, commit))\n \t\t\tadd_object_array(o, NULL, &merges);\n \t}\n \treset_revision_walk();\n@@ -803,7 +803,7 @@ static int find_first_merges(struct object_array *result, const char *path,\n \t\tcontains_another = 0;\n \t\tfor (j = 0; j < merges.nr; j++) {\n \t\t\tstruct commit *m2 = (struct commit *) merges.objects[j].item;\n-\t\t\tif (i != j && in_merge_bases(m2, &m1, 1)) {\n+\t\t\tif (i != j && in_merge_bases(m2, m1)) {\n \t\t\t\tcontains_another = 1;\n \t\t\t\tbreak;\n \t\t\t}\n@@ -865,18 +865,18 @@ int merge_submodule(unsigned char result[20], const char *path,\n \t}\n \n \t/* check whether both changes are forward */\n-\tif (!in_merge_bases(commit_base, &commit_a, 1) ||\n-\t    !in_merge_bases(commit_base, &commit_b, 1)) {\n+\tif (!in_merge_bases(commit_base, commit_a) ||\n+\t    !in_merge_bases(commit_base, commit_b)) {\n \t\tMERGE_WARNING(path, \"commits don't follow merge-base\");\n \t\treturn 0;\n \t}\n \n \t/* Case #1: a is contained in b or vice versa */\n-\tif (in_merge_bases(commit_a, &commit_b, 1)) {\n+\tif (in_merge_bases(commit_a, commit_b)) {\n \t\thashcpy(result, b);\n \t\treturn 1;\n \t}\n-\tif (in_merge_bases(commit_b, &commit_a, 1)) {\n+\tif (in_merge_bases(commit_b, commit_a)) {\n \t\thashcpy(result, a);\n \t\treturn 1;\n \t}\n-- \n1.7.12.116.g31e0100\n"},{"id":"197951","messageId":"1346109123-12357-3-git-send-email-gitster@pobox.com","threadId":"31368","inReplyTo":"1346109123-12357-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/5] receive-pack: use in_merge_bases() for fast-forward check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-27T23:12:00Z","receivedAt":"2012-08-27T23:12:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The original computed merge-base between the old commit and the new\ncommit and checked if the old commit was a merge base between them,\nin order to make sure we are fast-forwarding.\n\nInstead, call in_merge_bases(old, new) which does the same.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/receive-pack.c | 8 +-------\n 1 file changed, 1 insertion(+), 7 deletions(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 3f05d97..b1abe7b 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -478,7 +478,6 @@ static const char *update(struct command *cmd)\n \t    !prefixcmp(name, \"refs/heads/\")) {\n \t\tstruct object *old_object, *new_object;\n \t\tstruct commit *old_commit, *new_commit;\n-\t\tstruct commit_list *bases, *ent;\n \n \t\told_object = parse_object(old_sha1);\n \t\tnew_object = parse_object(new_sha1);\n@@ -491,12 +490,7 @@ static const char *update(struct command *cmd)\n \t\t}\n \t\told_commit = (struct commit *)old_object;\n \t\tnew_commit = (struct commit *)new_object;\n-\t\tbases = get_merge_bases(old_commit, new_commit, 1);\n-\t\tfor (ent = bases; ent; ent = ent->next)\n-\t\t\tif (!hashcmp(old_sha1, ent->item->object.sha1))\n-\t\t\t\tbreak;\n-\t\tfree_commit_list(bases);\n-\t\tif (!ent) {\n+\t\tif (!in_merge_bases(old_commit, new_commit)) {\n \t\t\trp_error(\"denying non-fast-forward %s\"\n \t\t\t\t \" (you should pull first)\", name);\n \t\t\treturn \"non-fast-forward\";\n-- \n1.7.12.116.g31e0100\n"},{"id":"197952","messageId":"1346109123-12357-4-git-send-email-gitster@pobox.com","threadId":"31368","inReplyTo":"1346109123-12357-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/5] http-push: use in_merge_bases() for fast-forward check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-27T23:12:01Z","receivedAt":"2012-08-27T23:12:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The original computed merge-base between HEAD and the remote ref and\nchecked if the remote ref is a merge base between them, in order to\nmake sure that we are fast-forwarding.\n\nInstead, call in_merge_bases(remote, HEAD) which does the same.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n http-push.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/http-push.c b/http-push.c\nindex a832ca7..8701c12 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1610,9 +1610,8 @@ static int verify_merge_base(unsigned char *head_sha1, struct ref *remote)\n {\n \tstruct commit *head = lookup_commit_or_die(head_sha1, \"HEAD\");\n \tstruct commit *branch = lookup_commit_or_die(remote->old_sha1, remote->name);\n-\tstruct commit_list *merge_bases = get_merge_bases(head, branch, 1);\n \n-\treturn (merge_bases && !merge_bases->next && merge_bases->item == branch);\n+\treturn in_merge_bases(branch, head);\n }\n \n static int delete_remote_branch(const char *pattern, int force)\n-- \n1.7.12.116.g31e0100\n"},{"id":"197953","messageId":"1346109123-12357-5-git-send-email-gitster@pobox.com","threadId":"31368","inReplyTo":"1346109123-12357-1-git-send-email-gitster@pobox.com","subject":"[PATCH 4/5] in_merge_bases(): omit unnecessary redundant common ancestor reduction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-27T23:12:02Z","receivedAt":"2012-08-27T23:12:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The function get_merge_bases() needs to postprocess the result from\nmerge_bases_many() in order to make sure none of the commit is a\ntrue ancestor of another commit, which is expensive.  However, when\nchecking if a commit is an ancestor of another commit, we only need\nto see if the commit is a common ancestor between the two, and do\nnot have to care if other common ancestors merge_bases_many() finds\nare true merge bases or an ancestor of another merge base.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n commit.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/commit.c b/commit.c\nindex 74ec5f1..f5211bd 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -806,7 +806,10 @@ int in_merge_bases(struct commit *commit, struct commit *reference)\n \tstruct commit_list *bases, *b;\n \tint ret = 0;\n \n-\tbases = get_merge_bases(commit, reference, 1);\n+\tbases = merge_bases_many(commit, 1, &reference);\n+\tclear_commit_marks(commit, all_flags);\n+\tclear_commit_marks(reference, all_flags);\n+\n \tfor (b = bases; b; b = b->next) {\n \t\tif (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n \t\t\tret = 1;\n-- \n1.7.12.116.g31e0100\n"},{"id":"197950","messageId":"1346109123-12357-6-git-send-email-gitster@pobox.com","threadId":"31368","inReplyTo":"1346109123-12357-1-git-send-email-gitster@pobox.com","subject":"[PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-27T23:12:03Z","receivedAt":"2012-08-27T23:12:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"After merge_bases_many() paints the graph in two colors to find\ncommon ancestors, get_merge_bases_many() reduces the result by\nexcluding commits that can be reached from other commits in the\nresult.  We used to do N * (N-1) traversals for this, but we can\ncheck if one commit is reachable from any of the other (N-1) commits\nby a single traversal, and repeat it N times to find the answer.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n commit.c | 42 +++++++++++++++++++++++-------------------\n 1 file changed, 23 insertions(+), 19 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex f5211bd..ccf2c5a 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -715,7 +715,7 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n \t\t\t\t\t int cleanup)\n {\n \tstruct commit_list *list;\n-\tstruct commit **rslt;\n+\tstruct commit **rslt, **others;\n \tstruct commit_list *result;\n \tint cnt, i, j;\n \n@@ -744,33 +744,37 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n \tfor (list = result, i = 0; list; list = list->next)\n \t\trslt[i++] = list->item;\n \tfree_commit_list(result);\n+\tresult = NULL;\n \n \tclear_commit_marks(one, all_flags);\n \tfor (i = 0; i < n; i++)\n \t\tclear_commit_marks(twos[i], all_flags);\n-\tfor (i = 0; i < cnt - 1; i++) {\n-\t\tfor (j = i+1; j < cnt; j++) {\n-\t\t\tif (!rslt[i] || !rslt[j])\n-\t\t\t\tcontinue;\n-\t\t\tresult = merge_bases_many(rslt[i], 1, &rslt[j]);\n-\t\t\tclear_commit_marks(rslt[i], all_flags);\n-\t\t\tclear_commit_marks(rslt[j], all_flags);\n-\t\t\tfor (list = result; list; list = list->next) {\n-\t\t\t\tif (rslt[i] == list->item)\n-\t\t\t\t\trslt[i] = NULL;\n-\t\t\t\tif (rslt[j] == list->item)\n-\t\t\t\t\trslt[j] = NULL;\n-\t\t\t}\n-\t\t}\n-\t}\n \n-\t/* Surviving ones in rslt[] are the independent results */\n-\tresult = NULL;\n+\tothers = xcalloc(cnt - 1, sizeof(*others));\n \tfor (i = 0; i < cnt; i++) {\n-\t\tif (rslt[i])\n+\t\t/*\n+\t\t * Is rslt[i] an ancestor of any of the others?\n+\t\t * then it is not interesting to us.\n+\t\t */\n+\t\tfor (j = 0; j < i; j++)\n+\t\t\tothers[j] = rslt[j];\n+\t\tfor (j = 1 + 1; j < cnt; j++)\n+\t\t\tothers[j - 1] = rslt[j];\n+\t\tlist = merge_bases_many(rslt[i], cnt - 1, others);\n+\t\tclear_commit_marks(rslt[i], all_flags);\n+\t\tfor (j = 0; j < cnt - 1; j++)\n+\t\t\tclear_commit_marks(others[j], all_flags);\n+\t\twhile (list) {\n+\t\t\tif (rslt[i] == list->item)\n+\t\t\t\tbreak;\n+\t\t\tlist = list->next;\n+\t\t}\n+\t\tif (!list)\n \t\t\tcommit_list_insert_by_date(rslt[i], &result);\n+\t\tfree_commit_list(list);\n \t}\n \tfree(rslt);\n+\tfree(others);\n \treturn result;\n }\n \n-- \n1.7.12.116.g31e0100\n"},{"id":"197956","messageId":"7vipc3q041.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"1346109123-12357-6-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-28T01:25:02Z","receivedAt":"2012-08-28T01:25:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n>  \tfor (i = 0; i < cnt; i++) {\n> -\t\tif (rslt[i])\n> +\t\t/*\n> +\t\t * Is rslt[i] an ancestor of any of the others?\n> +\t\t * then it is not interesting to us.\n> +\t\t */\n> +\t\tfor (j = 0; j < i; j++)\n> +\t\t\tothers[j] = rslt[j];\n> +\t\tfor (j = 1 + 1; j < cnt; j++)\n\ns/1 + 1/i + 1/;\n\nWith that, all tests seem to pass ;-)\n\n> +\t\t\tothers[j - 1] = rslt[j];\n> +\t\tlist = merge_bases_many(rslt[i], cnt - 1, others);\n> +\t\tclear_commit_marks(rslt[i], all_flags);\n> +\t\tfor (j = 0; j < cnt - 1; j++)\n> +\t\t\tclear_commit_marks(others[j], all_flags);\n> +\t\twhile (list) {\n> +\t\t\tif (rslt[i] == list->item)\n> +\t\t\t\tbreak;\n> +\t\t\tlist = list->next;\n> +\t\t}\n> +\t\tif (!list)\n>  \t\t\tcommit_list_insert_by_date(rslt[i], &result);\n> +\t\tfree_commit_list(list);\n>  \t}\n>  \tfree(rslt);\n> +\tfree(others);\n>  \treturn result;\n>  }\n"},{"id":"198016","messageId":"7v8vcyzomw.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"7vipc3q041.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-28T21:35:03Z","receivedAt":"2012-08-28T21:35:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n>\n>>  \tfor (i = 0; i < cnt; i++) {\n>> -\t\tif (rslt[i])\n>> +\t\t/*\n>> +\t\t * Is rslt[i] an ancestor of any of the others?\n>> +\t\t * then it is not interesting to us.\n>> +\t\t */\n>> +\t\tfor (j = 0; j < i; j++)\n>> +\t\t\tothers[j] = rslt[j];\n>> +\t\tfor (j = 1 + 1; j < cnt; j++)\n>\n> s/1 + 1/i + 1/;\n>\n> With that, all tests seem to pass ;-)\n\n\"git merge-base\" itself seems to have more room for improvement.\nTrying to recompute bases for recent 200 merges in the kernel\nhistory with the attached script does not show any improvement with\nor without the series on top of recent \"master\".  Correctnesswise it\nseems to be OK, though---I get byte-for-byte identical output.\n\n-- >8 --\n#!/bin/sh\n\ngit rev-list --committer=torvalds@linux-foundation.org \\\n    --max-parents=2 --min-parents=2 --parents v3.5..v3.6-rc2 >RL\n\ncmd='\n\twhile read result parent1 parent2\n\tdo\n\t\t$GIT merge-base $parent1 $parent2\n\tdone <RL\n'\n\nGIT=\"rungit master\" time sh -c \"$cmd\" >:stock\nGIT=../git.git/git time sh -c \"$cmd\" >:optim\ncmp :stock :optim\n-- 8< --\n"},{"id":"198021","messageId":"7vvcg2y4bk.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"7v8vcyzomw.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-28T23:39:11Z","receivedAt":"2012-08-28T23:39:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n>\n>> Junio C Hamano <gitster@pobox.com> writes:\n>>\n>>>  \tfor (i = 0; i < cnt; i++) {\n>>> -\t\tif (rslt[i])\n>>> +\t\t/*\n>>> +\t\t * Is rslt[i] an ancestor of any of the others?\n>>> +\t\t * then it is not interesting to us.\n>>> +\t\t */\n>>> +\t\tfor (j = 0; j < i; j++)\n>>> +\t\t\tothers[j] = rslt[j];\n>>> +\t\tfor (j = 1 + 1; j < cnt; j++)\n>>\n>> s/1 + 1/i + 1/;\n>>\n>> With that, all tests seem to pass ;-)\n>\n> \"git merge-base\" itself seems to have more room for improvement.\n> Trying to recompute bases for recent 200 merges in the kernel\n> history with the attached script does not show any improvement with\n> or without the series on top of recent \"master\".  Correctnesswise it\n> seems to be OK, though---I get byte-for-byte identical output.\n>\n> -- >8 --\n> #!/bin/sh\n>\n> git rev-list --committer=torvalds@linux-foundation.org \\\n>     --max-parents=2 --min-parents=2 --parents v3.5..v3.6-rc2 >RL\n>\n> cmd='\n> \twhile read result parent1 parent2\n> \tdo\n> \t\t$GIT merge-base $parent1 $parent2\n> \tdone <RL\n> '\n>\n> GIT=\"rungit master\" time sh -c \"$cmd\" >:stock\n> GIT=../git.git/git time sh -c \"$cmd\" >:optim\n> cmp :stock :optim\n> -- 8< --\n\nI have this suspicion that it is spending most of its time in\ninsert-by-date.  Luckily, merge_bases_many() is totally outside of\nthe usual revision traversal and its use of the commit list is\npretty well isolated.\n\nPeff, can I interest you into resurrecting your $gmane/174007 and\n$gmane/174008 (we do not need pop_commit_from_queue() in the latter;\neverything can stay as static to commit.c for now) to see how well\npriority queue based approach would perform?\n"},{"id":"198036","messageId":"20120829110812.GA14069@sigill.intra.peff.net","threadId":"31368","inReplyTo":"7vvcg2y4bk.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T11:08:12Z","receivedAt":"2012-08-29T11:08:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 28, 2012 at 04:39:11PM -0700, Junio C Hamano wrote:\n\n> > git rev-list --committer=torvalds@linux-foundation.org \\\n> >     --max-parents=2 --min-parents=2 --parents v3.5..v3.6-rc2 >RL\n> >\n> > cmd='\n> > \twhile read result parent1 parent2\n> > \tdo\n> > \t\t$GIT merge-base $parent1 $parent2\n> > \tdone <RL\n> > '\n> \n> I have this suspicion that it is spending most of its time in\n> insert-by-date.  Luckily, merge_bases_many() is totally outside of\n> the usual revision traversal and its use of the commit list is\n> pretty well isolated.\n> \n> Peff, can I interest you into resurrecting your $gmane/174007 and\n> $gmane/174008 (we do not need pop_commit_from_queue() in the latter;\n> everything can stay as static to commit.c for now) to see how well\n> priority queue based approach would perform?\n\nI did a quick port of merge_bases_many and get_merge_bases_many to use\npriority queues, but I didn't see any speedup at all on the above test\ncase.  According to perf, we spend most of our time in zlib, inflating\ncommits. Only 1% is spent on commit_list_insert_by_date, which is about\nthe same amount spent on queue insertion after my patches.\n\nPatches follow, just for reference.\n\n  [1/2]: basic priority queue implementation\n  [2/2]: commit: use a priority queue in merge base functions\n\n-Peff\n"},{"id":"198037","messageId":"20120829111056.GA14734@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120829110812.GA14069@sigill.intra.peff.net","subject":"[PATCH 1/2] basic priority queue implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T11:10:56Z","receivedAt":"2012-08-29T11:10:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This can provide better algorithmic complexity for some of\nthe date-sorted commit list uses, among other things.\n\nThe queue is stored as a heap, allowing O(log) insertion and\ntop-element removal, and O(1) peeking at the top element.\nCurrent commit lists are sorted linked lists, giving O(1)\npeeking and top-element removal, but O(n^2) insertion.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nMostly the same as $gmane/174007, but rebased on top of jc/merge-bases,\nand adding queue_clear() to avoid leaking memory.\n\n .gitignore       |  1 +\n Makefile         |  3 +++\n queue.c          | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n queue.h          | 18 ++++++++++++++\n t/t0007-queue.sh | 50 +++++++++++++++++++++++++++++++++++++\n test-queue.c     | 39 +++++++++++++++++++++++++++++\n 6 files changed, 186 insertions(+)\n create mode 100644 queue.c\n create mode 100644 queue.h\n create mode 100755 t/t0007-queue.sh\n create mode 100644 test-queue.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 3b7680e..f4539e8 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -184,6 +184,7 @@\n /test-obj-pool\n /test-parse-options\n /test-path-utils\n+/test-queue\n /test-run-command\n /test-sha1\n /test-sigchain\ndiff --git a/Makefile b/Makefile\nindex e4f8e0e..a37d962 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -476,6 +476,7 @@ TEST_PROGRAMS_NEED_X += test-path-utils\n TEST_PROGRAMS_NEED_X += test-obj-pool\n TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n+TEST_PROGRAMS_NEED_X += test-queue\n TEST_PROGRAMS_NEED_X += test-run-command\n TEST_PROGRAMS_NEED_X += test-sha1\n TEST_PROGRAMS_NEED_X += test-sigchain\n@@ -597,6 +598,7 @@ LIB_H += prompt.h\n LIB_H += pkt-line.h\n LIB_H += progress.h\n LIB_H += prompt.h\n+LIB_H += queue.h\n LIB_H += quote.h\n LIB_H += reflog-walk.h\n LIB_H += refs.h\n@@ -709,6 +711,7 @@ LIB_OBJS += prompt.o\n LIB_OBJS += pretty.o\n LIB_OBJS += progress.o\n LIB_OBJS += prompt.o\n+LIB_OBJS += queue.o\n LIB_OBJS += quote.o\n LIB_OBJS += reachable.o\n LIB_OBJS += read-cache.o\ndiff --git a/queue.c b/queue.c\nnew file mode 100644\nindex 0000000..7be6b86\n--- /dev/null\n+++ b/queue.c\n@@ -0,0 +1,75 @@\n+#include \"queue.h\"\n+#include \"cache.h\"\n+\n+static inline void queue_swap(struct queue *pq, unsigned i, unsigned j)\n+{\n+\tvoid *tmp = pq->items[i];\n+\tpq->items[i] = pq->items[j];\n+\tpq->items[j] = tmp;\n+}\n+\n+static void queue_heapify_up(struct queue *pq)\n+{\n+\tunsigned i = pq->nr - 1;\n+\twhile (i > 0) {\n+\t\tint parent = (i-1)/2;\n+\n+\t\tif (pq->cmp(pq->items[i], pq->items[parent]) <= 0)\n+\t\t\treturn;\n+\n+\t\tqueue_swap(pq, i, parent);\n+\t\ti = parent;\n+\t}\n+}\n+\n+void queue_insert(struct queue *pq, void *item)\n+{\n+\tALLOC_GROW(pq->items, pq->nr + 1, pq->alloc);\n+\tpq->items[pq->nr++] = item;\n+\tqueue_heapify_up(pq);\n+}\n+\n+static void queue_heapify_down(struct queue *pq)\n+{\n+\tunsigned i = 0;\n+\twhile (1) {\n+\t\tint largest = i, left = 2*i + 1, right = 2*i + 2;\n+\n+\t\tif (left < pq->nr &&\n+\t\t    pq->cmp(pq->items[left], pq->items[largest]) > 0)\n+\t\t\tlargest = left;\n+\t\tif (right < pq->nr &&\n+\t\t    pq->cmp(pq->items[right], pq->items[largest]) > 0)\n+\t\t\tlargest = right;\n+\n+\t\tif (largest == i)\n+\t\t\treturn;\n+\n+\t\tqueue_swap(pq, i, largest);\n+\t\ti = largest;\n+\t}\n+}\n+\n+void *queue_peek(struct queue *pq)\n+{\n+\treturn pq->nr ? pq->items[0] : NULL;\n+}\n+\n+void *queue_pop(struct queue *pq)\n+{\n+\tvoid *ret;\n+\n+\tif (!pq->nr)\n+\t\treturn NULL;\n+\tret = pq->items[0];\n+\n+\tpq->items[0] = pq->items[--pq->nr];\n+\tqueue_heapify_down(pq);\n+\n+\treturn ret;\n+}\n+\n+void queue_clear(struct queue *pq)\n+{\n+\tfree(pq->items);\n+}\ndiff --git a/queue.h b/queue.h\nnew file mode 100644\nindex 0000000..cc471b5\n--- /dev/null\n+++ b/queue.h\n@@ -0,0 +1,18 @@\n+#ifndef QUEUE_H\n+#define QUEUE_H\n+\n+typedef int (*queue_comparison_func_t)(const void *, const void *);\n+\n+struct queue {\n+\tqueue_comparison_func_t cmp;\n+\tvoid **items;\n+\tunsigned nr;\n+\tunsigned alloc;\n+};\n+\n+void queue_insert(struct queue *pq, void *item);\n+void *queue_peek(struct queue *pq);\n+void *queue_pop(struct queue *pq);\n+void queue_clear(struct queue *pq);\n+\n+#endif /* QUEUE_H */\ndiff --git a/t/t0007-queue.sh b/t/t0007-queue.sh\nnew file mode 100755\nindex 0000000..ee357bb\n--- /dev/null\n+++ b/t/t0007-queue.sh\n@@ -0,0 +1,50 @@\n+#!/bin/sh\n+\n+test_description='basic tests for priority queue implementation'\n+. ./test-lib.sh\n+\n+cat >expect <<'EOF'\n+10\n+9\n+8\n+7\n+6\n+5\n+5\n+4\n+3\n+2\n+1\n+EOF\n+test_expect_success 'basic ordering' '\n+\ttest-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+3\n+5\n+4\n+6\n+2\n+1\n+EOF\n+test_expect_success 'mixed insert and pop' '\n+\ttest-queue 1 2 3 pop 4 5 pop pop 6 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+2\n+1\n+NULL\n+2\n+1\n+NULL\n+EOF\n+test_expect_success 'notice empty queue' '\n+\ttest-queue 1 2 pop pop pop 1 2 pop pop pop >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/test-queue.c b/test-queue.c\nnew file mode 100644\nindex 0000000..a1e92e2\n--- /dev/null\n+++ b/test-queue.c\n@@ -0,0 +1,39 @@\n+#include \"cache.h\"\n+#include \"queue.h\"\n+\n+static int intcmp(const void *va, const void *vb)\n+{\n+\tconst int *a = va, *b = vb;\n+\treturn *a - *b;\n+}\n+\n+static void show(int *v)\n+{\n+\tif (!v)\n+\t\tprintf(\"NULL\\n\");\n+\telse\n+\t\tprintf(\"%d\\n\", *v);\n+\tfree(v);\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct queue pq = { intcmp };\n+\n+\twhile (*++argv) {\n+\t\tif (!strcmp(*argv, \"pop\"))\n+\t\t\tshow(queue_pop(&pq));\n+\t\telse if (!strcmp(*argv, \"dump\")) {\n+\t\t\tint *v;\n+\t\t\twhile ((v = queue_pop(&pq)))\n+\t\t\t       show(v);\n+\t\t}\n+\t\telse {\n+\t\t\tint *v = malloc(sizeof(*v));\n+\t\t\t*v = atoi(*argv);\n+\t\t\tqueue_insert(&pq, v);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n-- \n1.7.12.35.g38689e3\n"},{"id":"198038","messageId":"20120829111147.GB14734@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120829110812.GA14069@sigill.intra.peff.net","subject":"[PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T11:11:47Z","receivedAt":"2012-08-29T11:11:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The merge-base functions internally keep a commit lists and\ninsert by date, which causes a linear search of the commit\nlist for each insertion. Let's use a priority queue instead.\n\nUnfortunately, from my experiments, this didn't actually\ncause any speedup.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI'd probably split this into a few commits if we were really going to\napply it, but since it doesn't actually make anything faster, I doubt\nthe code churn is worth it.\n\n commit.c | 78 ++++++++++++++++++++++++++++++++++++++--------------------------\n 1 file changed, 47 insertions(+), 31 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 380f4ec..c64ef94 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -7,6 +7,7 @@\n #include \"revision.h\"\n #include \"notes.h\"\n #include \"gpg-interface.h\"\n+#include \"queue.h\"\n \n int save_commit_buffer = 1;\n \n@@ -360,6 +361,15 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *\n \treturn new_list;\n }\n \n+static void commit_list_append(struct commit *item, struct commit_list ***tail)\n+{\n+\tstruct commit_list *new_list = xmalloc(sizeof(*new_list));\n+\tnew_list->item = item;\n+\tnew_list->next = NULL;\n+\t**tail = new_list;\n+\t*tail = &new_list->next;\n+}\n+\n unsigned commit_list_count(const struct commit_list *l)\n {\n \tunsigned c = 0;\n@@ -422,6 +432,16 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \treturn ret;\n }\n \n+static int commit_datecmp(const void *va, const void *vb)\n+{\n+\tconst struct commit *a = va, *b = vb;\n+\tif (a->date < b->date)\n+\t\treturn -1;\n+\telse if (a->date > b->date)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n void clear_commit_marks(struct commit *commit, unsigned int mark)\n {\n \twhile (commit) {\n@@ -569,22 +589,23 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \n static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n \n-static struct commit *interesting(struct commit_list *list)\n+static int interesting(struct queue *q)\n {\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tlist = list->next;\n+\tint i;\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct commit *commit = q->items[i];\n \t\tif (commit->object.flags & STALE)\n \t\t\tcontinue;\n-\t\treturn commit;\n+\t\treturn 1;\n \t}\n-\treturn NULL;\n+\treturn 0;\n }\n \n static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)\n {\n-\tstruct commit_list *list = NULL;\n-\tstruct commit_list *result = NULL;\n+\tstruct queue result = { commit_datecmp };\n+\tstruct queue list = { commit_datecmp };\n+\tstruct commit_list *ret = NULL, **tail = &ret;\n \tint i;\n \n \tfor (i = 0; i < n; i++) {\n@@ -593,7 +614,7 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \t\t\t * We do not mark this even with RESULT so we do not\n \t\t\t * have to clean it up.\n \t\t\t */\n-\t\t\treturn commit_list_insert(one, &result);\n+\t\t\treturn commit_list_insert(one, &ret);\n \t}\n \n \tif (parse_commit(one))\n@@ -604,28 +625,24 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \t}\n \n \tone->object.flags |= PARENT1;\n-\tcommit_list_insert_by_date(one, &list);\n+\tqueue_insert(&list, one);\n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tcommit_list_insert_by_date(twos[i], &list);\n+\t\tqueue_insert(&list, twos[i]);\n \t}\n \n-\twhile (interesting(list)) {\n+\twhile (interesting(&list)) {\n \t\tstruct commit *commit;\n \t\tstruct commit_list *parents;\n-\t\tstruct commit_list *next;\n \t\tint flags;\n \n-\t\tcommit = list->item;\n-\t\tnext = list->next;\n-\t\tfree(list);\n-\t\tlist = next;\n+\t\tcommit = queue_pop(&list);\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n \t\tif (flags == (PARENT1 | PARENT2)) {\n \t\t\tif (!(commit->object.flags & RESULT)) {\n \t\t\t\tcommit->object.flags |= RESULT;\n-\t\t\t\tcommit_list_insert_by_date(commit, &result);\n+\t\t\t\tqueue_insert(&result, commit);\n \t\t\t}\n \t\t\t/* Mark parents of a found merge stale */\n \t\t\tflags |= STALE;\n@@ -639,21 +656,16 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \t\t\tif (parse_commit(p))\n \t\t\t\treturn NULL;\n \t\t\tp->object.flags |= flags;\n-\t\t\tcommit_list_insert_by_date(p, &list);\n+\t\t\tqueue_insert(&list, p);\n \t\t}\n \t}\n \n \t/* Clean up the result to remove stale ones */\n-\tfree_commit_list(list);\n-\tlist = result; result = NULL;\n-\twhile (list) {\n-\t\tstruct commit_list *next = list->next;\n-\t\tif (!(list->item->object.flags & STALE))\n-\t\t\tcommit_list_insert_by_date(list->item, &result);\n-\t\tfree(list);\n-\t\tlist = next;\n-\t}\n-\treturn result;\n+\twhile (result.nr)\n+\t\tcommit_list_append(queue_pop(&result), &tail);\n+\tqueue_clear(&result);\n+\tqueue_clear(&list);\n+\treturn ret;\n }\n \n struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n@@ -690,7 +702,8 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n {\n \tstruct commit_list *list;\n \tstruct commit **rslt, **others;\n-\tstruct commit_list *result;\n+\tstruct commit_list *result, **tail = &result;\n+\tstruct queue commit_queue = { commit_datecmp };\n \tint cnt, i, j;\n \n \tresult = merge_bases_many(one, n, twos);\n@@ -744,11 +757,14 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n \t\t\tlist = list->next;\n \t\t}\n \t\tif (!list)\n-\t\t\tcommit_list_insert_by_date(rslt[i], &result);\n+\t\t\tqueue_insert(&commit_queue, rslt[i]);\n \t\tfree_commit_list(list);\n \t}\n \tfree(rslt);\n \tfree(others);\n+\twhile (commit_queue.nr)\n+\t\tcommit_list_append(queue_pop(&commit_queue), &tail);\n+\tqueue_clear(&commit_queue);\n \treturn result;\n }\n \n-- \n1.7.12.35.g38689e3\n"},{"id":"198047","messageId":"7vtxvlwt7o.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"20120829111147.GB14734@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T16:36:43Z","receivedAt":"2012-08-29T16:36:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The merge-base functions internally keep a commit lists and\n> insert by date, which causes a linear search of the commit\n> list for each insertion. Let's use a priority queue instead.\n>\n> Unfortunately, from my experiments, this didn't actually\n> cause any speedup.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> I'd probably split this into a few commits if we were really going to\n> apply it, but since it doesn't actually make anything faster, I doubt\n> the code churn is worth it.\n\nThanks.  This seems to break t6010-merge-base.sh for me, though...\n\n\n\n>\n>  commit.c | 78 ++++++++++++++++++++++++++++++++++++++--------------------------\n>  1 file changed, 47 insertions(+), 31 deletions(-)\n>\n> diff --git a/commit.c b/commit.c\n> index 380f4ec..c64ef94 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -7,6 +7,7 @@\n>  #include \"revision.h\"\n>  #include \"notes.h\"\n>  #include \"gpg-interface.h\"\n> +#include \"queue.h\"\n>  \n>  int save_commit_buffer = 1;\n>  \n> @@ -360,6 +361,15 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *\n>  \treturn new_list;\n>  }\n>  \n> +static void commit_list_append(struct commit *item, struct commit_list ***tail)\n> +{\n> +\tstruct commit_list *new_list = xmalloc(sizeof(*new_list));\n> +\tnew_list->item = item;\n> +\tnew_list->next = NULL;\n> +\t**tail = new_list;\n> +\t*tail = &new_list->next;\n> +}\n> +\n>  unsigned commit_list_count(const struct commit_list *l)\n>  {\n>  \tunsigned c = 0;\n> @@ -422,6 +432,16 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n>  \treturn ret;\n>  }\n>  \n> +static int commit_datecmp(const void *va, const void *vb)\n> +{\n> +\tconst struct commit *a = va, *b = vb;\n> +\tif (a->date < b->date)\n> +\t\treturn -1;\n> +\telse if (a->date > b->date)\n> +\t\treturn 1;\n> +\treturn 0;\n> +}\n> +\n>  void clear_commit_marks(struct commit *commit, unsigned int mark)\n>  {\n>  \twhile (commit) {\n> @@ -569,22 +589,23 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n>  \n>  static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n>  \n> -static struct commit *interesting(struct commit_list *list)\n> +static int interesting(struct queue *q)\n>  {\n> -\twhile (list) {\n> -\t\tstruct commit *commit = list->item;\n> -\t\tlist = list->next;\n> +\tint i;\n> +\tfor (i = 0; i < q->nr; i++) {\n> +\t\tstruct commit *commit = q->items[i];\n>  \t\tif (commit->object.flags & STALE)\n>  \t\t\tcontinue;\n> -\t\treturn commit;\n> +\t\treturn 1;\n>  \t}\n> -\treturn NULL;\n> +\treturn 0;\n>  }\n>  \n>  static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)\n>  {\n> -\tstruct commit_list *list = NULL;\n> -\tstruct commit_list *result = NULL;\n> +\tstruct queue result = { commit_datecmp };\n> +\tstruct queue list = { commit_datecmp };\n> +\tstruct commit_list *ret = NULL, **tail = &ret;\n>  \tint i;\n>  \n>  \tfor (i = 0; i < n; i++) {\n> @@ -593,7 +614,7 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n>  \t\t\t * We do not mark this even with RESULT so we do not\n>  \t\t\t * have to clean it up.\n>  \t\t\t */\n> -\t\t\treturn commit_list_insert(one, &result);\n> +\t\t\treturn commit_list_insert(one, &ret);\n>  \t}\n>  \n>  \tif (parse_commit(one))\n> @@ -604,28 +625,24 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n>  \t}\n>  \n>  \tone->object.flags |= PARENT1;\n> -\tcommit_list_insert_by_date(one, &list);\n> +\tqueue_insert(&list, one);\n>  \tfor (i = 0; i < n; i++) {\n>  \t\ttwos[i]->object.flags |= PARENT2;\n> -\t\tcommit_list_insert_by_date(twos[i], &list);\n> +\t\tqueue_insert(&list, twos[i]);\n>  \t}\n>  \n> -\twhile (interesting(list)) {\n> +\twhile (interesting(&list)) {\n>  \t\tstruct commit *commit;\n>  \t\tstruct commit_list *parents;\n> -\t\tstruct commit_list *next;\n>  \t\tint flags;\n>  \n> -\t\tcommit = list->item;\n> -\t\tnext = list->next;\n> -\t\tfree(list);\n> -\t\tlist = next;\n> +\t\tcommit = queue_pop(&list);\n>  \n>  \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n>  \t\tif (flags == (PARENT1 | PARENT2)) {\n>  \t\t\tif (!(commit->object.flags & RESULT)) {\n>  \t\t\t\tcommit->object.flags |= RESULT;\n> -\t\t\t\tcommit_list_insert_by_date(commit, &result);\n> +\t\t\t\tqueue_insert(&result, commit);\n>  \t\t\t}\n>  \t\t\t/* Mark parents of a found merge stale */\n>  \t\t\tflags |= STALE;\n> @@ -639,21 +656,16 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n>  \t\t\tif (parse_commit(p))\n>  \t\t\t\treturn NULL;\n>  \t\t\tp->object.flags |= flags;\n> -\t\t\tcommit_list_insert_by_date(p, &list);\n> +\t\t\tqueue_insert(&list, p);\n>  \t\t}\n>  \t}\n>  \n>  \t/* Clean up the result to remove stale ones */\n> -\tfree_commit_list(list);\n> -\tlist = result; result = NULL;\n> -\twhile (list) {\n> -\t\tstruct commit_list *next = list->next;\n> -\t\tif (!(list->item->object.flags & STALE))\n> -\t\t\tcommit_list_insert_by_date(list->item, &result);\n> -\t\tfree(list);\n> -\t\tlist = next;\n> -\t}\n> -\treturn result;\n> +\twhile (result.nr)\n> +\t\tcommit_list_append(queue_pop(&result), &tail);\n> +\tqueue_clear(&result);\n> +\tqueue_clear(&list);\n> +\treturn ret;\n>  }\n>  \n>  struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n> @@ -690,7 +702,8 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n>  {\n>  \tstruct commit_list *list;\n>  \tstruct commit **rslt, **others;\n> -\tstruct commit_list *result;\n> +\tstruct commit_list *result, **tail = &result;\n> +\tstruct queue commit_queue = { commit_datecmp };\n>  \tint cnt, i, j;\n>  \n>  \tresult = merge_bases_many(one, n, twos);\n> @@ -744,11 +757,14 @@ struct commit_list *get_merge_bases_many(struct commit *one,\n>  \t\t\tlist = list->next;\n>  \t\t}\n>  \t\tif (!list)\n> -\t\t\tcommit_list_insert_by_date(rslt[i], &result);\n> +\t\t\tqueue_insert(&commit_queue, rslt[i]);\n>  \t\tfree_commit_list(list);\n>  \t}\n>  \tfree(rslt);\n>  \tfree(others);\n> +\twhile (commit_queue.nr)\n> +\t\tcommit_list_append(queue_pop(&commit_queue), &tail);\n> +\tqueue_clear(&commit_queue);\n>  \treturn result;\n>  }\n"},{"id":"198058","messageId":"20120829205332.GA16064@sigill.intra.peff.net","threadId":"31368","inReplyTo":"7vtxvlwt7o.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T20:53:32Z","receivedAt":"2012-08-29T20:53:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 09:36:43AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > The merge-base functions internally keep a commit lists and\n> > insert by date, which causes a linear search of the commit\n> > list for each insertion. Let's use a priority queue instead.\n> >\n> > Unfortunately, from my experiments, this didn't actually\n> > cause any speedup.\n> >\n> > Signed-off-by: Jeff King <peff@peff.net>\n> > ---\n> > I'd probably split this into a few commits if we were really going to\n> > apply it, but since it doesn't actually make anything faster, I doubt\n> > the code churn is worth it.\n> \n> Thanks.  This seems to break t6010-merge-base.sh for me, though...\n\nInteresting. It works fine here, even under --valgrind. Did you apply\nthe patches directly on top of 1251cc7?\n\nNot that it matters _too_ much if we are just going to scrap it anyway,\nbut maybe it is an indication that I screwed up something that could\nimpact the timing (I did check that the timed merge-base calculations on\nlinux-2.6 yielded the same results though).\n\n-Peff\n"},{"id":"198059","messageId":"20120829205525.GA28696@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120829205332.GA16064@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T20:55:25Z","receivedAt":"2012-08-29T20:55:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 04:53:32PM -0400, Jeff King wrote:\n\n> > Thanks.  This seems to break t6010-merge-base.sh for me, though...\n> \n> Interesting. It works fine here, even under --valgrind. Did you apply\n> the patches directly on top of 1251cc7?\n\nHmm, this does seem to break t6024 for me, though.\n\n-Peff\n"},{"id":"198060","messageId":"20120829210032.GA29179@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120829205525.GA28696@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T21:00:32Z","receivedAt":"2012-08-29T21:00:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 04:55:25PM -0400, Jeff King wrote:\n\n> On Wed, Aug 29, 2012 at 04:53:32PM -0400, Jeff King wrote:\n> \n> > > Thanks.  This seems to break t6010-merge-base.sh for me, though...\n> > \n> > Interesting. It works fine here, even under --valgrind. Did you apply\n> > the patches directly on top of 1251cc7?\n> \n> Hmm, this does seem to break t6024 for me, though.\n\nProbably because:\n\n>  \t/* Clean up the result to remove stale ones */\n> -\tfree_commit_list(list);\n> -\tlist = result; result = NULL;\n> -\twhile (list) {\n> -\t\tstruct commit_list *next = list->next;\n> -\t\tif (!(list->item->object.flags & STALE))\n> -\t\t\tcommit_list_insert_by_date(list->item, &result);\n> -\t\tfree(list);\n> -\t\tlist = next;\n> -\t}\n> -\treturn result;\n> +\twhile (result.nr)\n> +\t\tcommit_list_append(queue_pop(&result), &tail);\n> +\tqueue_clear(&result);\n> +\tqueue_clear(&list);\n> +\treturn ret;\n\nI forgot to to port the STALE flag handling here.\n\n-Peff\n"},{"id":"198061","messageId":"20120829210540.GA31756@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120829210032.GA29179@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-29T21:05:40Z","receivedAt":"2012-08-29T21:05:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 05:00:32PM -0400, Jeff King wrote:\n\n> > Hmm, this does seem to break t6024 for me, though.\n> \n> Probably because:\n> \n> >  \t/* Clean up the result to remove stale ones */\n> > -\tfree_commit_list(list);\n> > -\tlist = result; result = NULL;\n> > -\twhile (list) {\n> > -\t\tstruct commit_list *next = list->next;\n> > -\t\tif (!(list->item->object.flags & STALE))\n> > -\t\t\tcommit_list_insert_by_date(list->item, &result);\n> > -\t\tfree(list);\n> > -\t\tlist = next;\n> > -\t}\n> > -\treturn result;\n> > +\twhile (result.nr)\n> > +\t\tcommit_list_append(queue_pop(&result), &tail);\n> > +\tqueue_clear(&result);\n> > +\tqueue_clear(&list);\n> > +\treturn ret;\n> \n> I forgot to to port the STALE flag handling here.\n\nYou would want this on top:\n\ndiff --git a/commit.c b/commit.c\nindex c64ef94..8259871 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -661,8 +661,11 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \t}\n \n \t/* Clean up the result to remove stale ones */\n-\twhile (result.nr)\n-\t\tcommit_list_append(queue_pop(&result), &tail);\n+\twhile (result.nr) {\n+\t\tstruct commit *commit = queue_pop(&result);\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\tcommit_list_append(commit, &tail);\n+\t}\n \tqueue_clear(&result);\n \tqueue_clear(&list);\n \treturn ret;\n\nbut t6024 still fails (it clearly is finding a different merge base than\nthe test expects).  I'll trace through it, but it will have to be later\ntonight.\n\n-Peff\n"},{"id":"198066","messageId":"7vy5kxv1md.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"20120829210032.GA29179@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T21:18:02Z","receivedAt":"2012-08-29T21:18:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>> +\twhile (result.nr)\n>> +\t\tcommit_list_append(queue_pop(&result), &tail);\n>> +\tqueue_clear(&result);\n>> +\tqueue_clear(&list);\n>> +\treturn ret;\n>\n> I forgot to to port the STALE flag handling here.\n\nFigures..  Thanks.\n"},{"id":"198094","messageId":"20120830125421.GA5687@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120829210540.GA31756@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T12:54:21Z","receivedAt":"2012-08-30T12:54:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 05:05:40PM -0400, Jeff King wrote:\n\n> You would want this on top:\n> [...]\n> but t6024 still fails (it clearly is finding a different merge base than\n> the test expects).  I'll trace through it, but it will have to be later\n> tonight.\n\nThe problem in t6024 is caused by the fact that the commit timestamps\nfor every commit are identical. The linear commit_list has the property\nthat we always insert a new commit at the end of a chain of commits with\nthe same timestamp. So it works as a stable priority queue in the sense\nthat items with the same priority are returned in insertion order.\n\nBut the heap-based priority queue does not. Nor can it do so without\nextra storage requirements, as heaps are inherently unstable. The\nsimplest way to make it stable is to add an insertion counter to the\ncomparison function. The patch below does this, and it resolves the\nissue. It does waste one int per queue element.\n\nI think you could also make a priority queue based on a binary search\ntree that would be stable. It's slightly less efficient to create an\ninitial queue (you can heapify in O(n), but building the tree takes O(n\nlg n)).  But we do not care about that, as we always build the queue by\ninserting elements, anyway.  The other downside of using a tree is that\nyou would want a self-balancing tree for good performance (especially\nsince we tend to insert commits in sorted order), which increases the\ncode complexity.\n\nAnyway, since this isn't yielding any performance benefit, I'm not going\nto go down that route. But stability of the queue is something that we\nneed to consider if we ever do replace commit_list with a different data\nstructure.\n\nHere's the patch to make the existing priority queue stable (by wasting\nspace) in case we ever want to use it.\n\n-Peff\n\ndiff --git a/commit.c b/commit.c\nindex 8259871..a99d909 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -593,7 +593,7 @@ static int interesting(struct queue *q)\n {\n \tint i;\n \tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct commit *commit = q->items[i];\n+\t\tstruct commit *commit = q->items[i].item;\n \t\tif (commit->object.flags & STALE)\n \t\t\tcontinue;\n \t\treturn 1;\ndiff --git a/queue.c b/queue.c\nindex 7be6b86..1bdd948 100644\n--- a/queue.c\n+++ b/queue.c\n@@ -3,18 +3,28 @@ static void queue_heapify_up(struct queue *pq)\n \n static inline void queue_swap(struct queue *pq, unsigned i, unsigned j)\n {\n-\tvoid *tmp = pq->items[i];\n+\tstruct queue_item tmp = pq->items[i];\n \tpq->items[i] = pq->items[j];\n \tpq->items[j] = tmp;\n }\n \n+static inline int queue_cmp(struct queue *pq, unsigned i, unsigned j)\n+{\n+\tint cmp = pq->cmp(pq->items[i].item, pq->items[j].item);\n+\tif (cmp)\n+\t\treturn cmp;\n+\tif (pq->items[i].counter < pq->items[j].counter)\n+\t\treturn 1;\n+\treturn -1;\n+}\n+\n static void queue_heapify_up(struct queue *pq)\n {\n \tunsigned i = pq->nr - 1;\n \twhile (i > 0) {\n \t\tint parent = (i-1)/2;\n \n-\t\tif (pq->cmp(pq->items[i], pq->items[parent]) <= 0)\n+\t\tif (queue_cmp(pq, i, parent) <= 0)\n \t\t\treturn;\n \n \t\tqueue_swap(pq, i, parent);\n@@ -25,7 +35,9 @@ void queue_insert(struct queue *pq, void *item)\n void queue_insert(struct queue *pq, void *item)\n {\n \tALLOC_GROW(pq->items, pq->nr + 1, pq->alloc);\n-\tpq->items[pq->nr++] = item;\n+\tpq->items[pq->nr].item = item;\n+\tpq->items[pq->nr].counter = pq->counter++;\n+\tpq->nr++;\n \tqueue_heapify_up(pq);\n }\n \n@@ -35,11 +47,9 @@ static void queue_heapify_down(struct queue *pq)\n \twhile (1) {\n \t\tint largest = i, left = 2*i + 1, right = 2*i + 2;\n \n-\t\tif (left < pq->nr &&\n-\t\t    pq->cmp(pq->items[left], pq->items[largest]) > 0)\n+\t\tif (left < pq->nr && queue_cmp(pq, left, largest) > 0)\n \t\t\tlargest = left;\n-\t\tif (right < pq->nr &&\n-\t\t    pq->cmp(pq->items[right], pq->items[largest]) > 0)\n+\t\tif (right < pq->nr && queue_cmp(pq, right, largest) > 0)\n \t\t\tlargest = right;\n \n \t\tif (largest == i)\n@@ -52,7 +62,7 @@ void *queue_peek(struct queue *pq)\n \n void *queue_peek(struct queue *pq)\n {\n-\treturn pq->nr ? pq->items[0] : NULL;\n+\treturn pq->nr ? pq->items[0].item : NULL;\n }\n \n void *queue_pop(struct queue *pq)\n@@ -61,7 +71,7 @@ void *queue_pop(struct queue *pq)\n \n \tif (!pq->nr)\n \t\treturn NULL;\n-\tret = pq->items[0];\n+\tret = pq->items[0].item;\n \n \tpq->items[0] = pq->items[--pq->nr];\n \tqueue_heapify_down(pq);\ndiff --git a/queue.h b/queue.h\nindex cc471b5..a70f7d7 100644\n--- a/queue.h\n+++ b/queue.h\n@@ -3,11 +3,17 @@ struct queue {\n \n typedef int (*queue_comparison_func_t)(const void *, const void *);\n \n+struct queue_item {\n+\tvoid *item;\n+\tunsigned counter;\n+};\n+\n struct queue {\n \tqueue_comparison_func_t cmp;\n-\tvoid **items;\n+\tstruct queue_item *items;\n \tunsigned nr;\n \tunsigned alloc;\n+\tunsigned counter;\n };\n \n void queue_insert(struct queue *pq, void *item);\n"},{"id":"198095","messageId":"20120830130327.GB5687@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120830125421.GA5687@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T13:03:27Z","receivedAt":"2012-08-30T13:03:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 30, 2012 at 08:54:21AM -0400, Jeff King wrote:\n\n> On Wed, Aug 29, 2012 at 05:05:40PM -0400, Jeff King wrote:\n> \n> > You would want this on top:\n> > [...]\n> > but t6024 still fails (it clearly is finding a different merge base than\n> > the test expects).  I'll trace through it, but it will have to be later\n> > tonight.\n> \n> The problem in t6024 is caused by the fact that the commit timestamps\n> for every commit are identical.\n\nSo I was able to have my queue behave just like commit_list by fixing\nthe stability issue. But I still have no clue what is going on in t6024.\nIt does this for each commit it makes:\n\n  [...]\n  GIT_AUTHOR_DATE=\"2006-12-12 23:00:00\" git commit -m 1 a1 &&\n  [...]\n  GIT_AUTHOR_DATE=\"2006-12-12 23:00:01\" git commit -m A a1 &&\n  [...]\n\nwhich is just bizarre. At first I thought it was buggy, and that it\nreally wanted to be setting COMMITTER_DATE (in which case it should\nreally just be using test_tick, anyway). But if you do that, the test\nfails (even using a regular commit_list)!\n\nSo is the test buggy? Or are the identical commit timestamps part of the\nintended effect? I can't see how that would be, since:\n\n  1. You would need to set COMMITTER_DATE for that anyway, as you are\n     otherwise creating a race condition.\n\n  2. Why would you set AUTHOR_DATE? It's not used by the merge code at\n     all.\n\nThe script originally comes from here:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/33566/focus=33852\n\nand the discussion implies that the AUTHOR_DATEs were added to avoid a\nrace condition with the timestamps. But why would that ever have worked?\n\nConfused...\n\n-Peff\n"},{"id":"198098","messageId":"20120830132432.GC5687@sigill.intra.peff.net","threadId":"31368","inReplyTo":"20120830130327.GB5687@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T13:24:32Z","receivedAt":"2012-08-30T13:24:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 30, 2012 at 09:03:27AM -0400, Jeff King wrote:\n\n> So I was able to have my queue behave just like commit_list by fixing\n> the stability issue. But I still have no clue what is going on in t6024.\n> It does this for each commit it makes:\n> \n>   [...]\n>   GIT_AUTHOR_DATE=\"2006-12-12 23:00:00\" git commit -m 1 a1 &&\n>   [...]\n>   GIT_AUTHOR_DATE=\"2006-12-12 23:00:01\" git commit -m A a1 &&\n>   [...]\n> \n> which is just bizarre. At first I thought it was buggy, and that it\n> really wanted to be setting COMMITTER_DATE (in which case it should\n> really just be using test_tick, anyway). But if you do that, the test\n> fails (even using a regular commit_list)!\n> \n> So is the test buggy? Or are the identical commit timestamps part of the\n> intended effect? I can't see how that would be, since:\n> \n>   1. You would need to set COMMITTER_DATE for that anyway, as you are\n>      otherwise creating a race condition.\n> \n>   2. Why would you set AUTHOR_DATE? It's not used by the merge code at\n>      all.\n> \n> The script originally comes from here:\n> \n>   http://thread.gmane.org/gmane.comp.version-control.git/33566/focus=33852\n> \n> and the discussion implies that the AUTHOR_DATEs were added to avoid a\n> race condition with the timestamps. But why would that ever have worked?\n\nThat thread mentions that this is to fix \"Shawn's bug\", which I think is\nthis:\n\n  http://article.gmane.org/gmane.comp.version-control.git/33559\n\nIOW, the real thing that t6024 is trying to test is that we handle the\nfake empty tree properly. And the AUTHOR_DATEs probably were just there\nto try to fix the race condition, and they should really just be\ntest_ticks (and I can't see how they ever would have helped anything; I\nsuspect they were a placebo inserted at the same time as another change,\nand got credited with fixing the race).\n\nThat still leaves the question of why the test fails when the commits\nget distinct timestamps.\n\n-Peff\n"},{"id":"198106","messageId":"7v3934tkle.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"20120830125421.GA5687@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T16:23:25Z","receivedAt":"2012-08-30T16:23:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Anyway, since this isn't yielding any performance benefit, I'm not going\n> to go down that route. But stability of the queue is something that we\n> need to consider if we ever do replace commit_list with a different data\n> structure.\n>\n> Here's the patch to make the existing priority queue stable (by wasting\n> space) in case we ever want to use it.\n\nThanks for being thorough and showing a good analysis.\n\nIf we want stability, the space to hold insertion counter is not\n\"wasted\", by the way.\n\nI actually think the generic \"queue\" implementation may want to\nhandle elements that are not just single pointers.  Just like\nqsort() is not about sorting an array of pointers but it is about\nsorting an array of elements of caller specified size, perhaps\n\"queue\" can hold elements of size the caller specified (set in stone\nwhen the queue is initialized).\n\nThen, a caller that wants a stable priority queue of commits can\ntell the queue to manage \"struct { struct commit *c; int gen; }\",\nuse the \"gen\" field for stability in its comparison callback, etc.,\nwhile a caller that does not need stability can tell the queue to\nmanage \"struct commit *\".  That way, the generic queue layer does\nnot have to worry about wasting the insertion counter space, no?\n"},{"id":"198107","messageId":"7vy5kws5jn.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"20120830130327.GB5687@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T16:33:48Z","receivedAt":"2012-08-30T16:33:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The script originally comes from here:\n>\n>   http://thread.gmane.org/gmane.comp.version-control.git/33566/focus=33852\n>\n> and the discussion implies that the AUTHOR_DATEs were added to avoid a\n> race condition with the timestamps. But why would that ever have worked?\n\nI do not see how AUTHOR_DATE would affect anything there, either,\nother than to give reprodusible object names.  The test only sets\ncommitter-date upfront, so without setting author-date, you would\nstill get different object names on commits.  Which suggests me that\nthere may be something that tiebreaks based on object names?\n"},{"id":"198126","messageId":"20120830213105.GA18636@sigill.intra.peff.net","threadId":"31368","inReplyTo":"7v3934tkle.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T21:31:05Z","receivedAt":"2012-08-30T21:31:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 30, 2012 at 09:23:25AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Anyway, since this isn't yielding any performance benefit, I'm not going\n> > to go down that route. But stability of the queue is something that we\n> > need to consider if we ever do replace commit_list with a different data\n> > structure.\n> >\n> > Here's the patch to make the existing priority queue stable (by wasting\n> > space) in case we ever want to use it.\n> \n> Thanks for being thorough and showing a good analysis.\n> \n> If we want stability, the space to hold insertion counter is not\n> \"wasted\", by the way.\n\nIt is if there is another data structure that will do the same job with\nthe same performance characteristics and without using that space.\n\nBut I'm not even sure it is an issue in practice. There are ~320K\nobjects in linux-2.6. Even if we inserted _all_ of them at once into a\nqueue (which we don't; it's usually more like a couple dozen, with a few\npathological cases being equal to the number of refs we have, which is\nusually in the hundreds), then we are talking about an extra 2.5M on a\n64-bit system. Compared to dropping an O(n^2) operation to O(lg n),\nthat's probably not even going to be noticeable.\n\n> I actually think the generic \"queue\" implementation may want to\n> handle elements that are not just single pointers.  Just like\n> qsort() is not about sorting an array of pointers but it is about\n> sorting an array of elements of caller specified size, perhaps\n> \"queue\" can hold elements of size the caller specified (set in stone\n> when the queue is initialized).\n> \n> Then, a caller that wants a stable priority queue of commits can\n> tell the queue to manage \"struct { struct commit *c; int gen; }\",\n> use the \"gen\" field for stability in its comparison callback, etc.,\n> while a caller that does not need stability can tell the queue to\n> manage \"struct commit *\".  That way, the generic queue layer does\n> not have to worry about wasting the insertion counter space, no?\n\nYeah, that would be more generic. One wonky thing I didn't point out in\nmy implementation is this:\n\n> +static inline int queue_cmp(struct queue *pq, unsigned i, unsigned j)\n> +{\n> +       int cmp = pq->cmp(pq->items[i].item, pq->items[j].item);\n> +       if (cmp)\n> +               return cmp;\n> +       if (pq->items[i].counter < pq->items[j].counter)\n> +               return 1;\n> +       return -1;\n> +}\n\nNotice how the counter comparison is \"backwards\" to the regular\ncomparison. That's because the queue is actually a max-queue (I did it\nthat way since we are indexing on timestamp, and want to go in reverse\nchronological order). But the counter part wants to prioritize minimums,\nso you have to reverse it. You could also implement a min-queue and ask\nthe caller to reverse their comparison function.\n\nBut really, a caller could theoretically want to prioritize in either\ndirection (e.g., giving a LIFO behavior to elements with the same\npriority). Pulling the counter out of the queue would allow that.\n\nThe reason I didn't, though, is that it would make the interface a huge\npain if the caller had to do this:\n\n  struct stable_commit_queue_element qe;\n  qe.commit = commit;\n  qe.counter = counter++; /* who is holding the global counter? */\n  queue_push(&q, &qe);\n\ninstead of:\n\n  queue_push(&q, commit);\n\nI suspect you could build a \"queue\" object, and then implement a\n\"stable queue\" on top of it with some clever use of function pointers\nfor the comparison function.\n\n-Peff\n"},{"id":"198128","messageId":"20120830214802.GB18636@sigill.intra.peff.net","threadId":"31368","inReplyTo":"7vy5kws5jn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T21:48:03Z","receivedAt":"2012-08-30T21:48:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 30, 2012 at 09:33:48AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > The script originally comes from here:\n> >\n> >   http://thread.gmane.org/gmane.comp.version-control.git/33566/focus=33852\n> >\n> > and the discussion implies that the AUTHOR_DATEs were added to avoid a\n> > race condition with the timestamps. But why would that ever have worked?\n> \n> I do not see how AUTHOR_DATE would affect anything there, either,\n> other than to give reprodusible object names.  The test only sets\n> committer-date upfront, so without setting author-date, you would\n> still get different object names on commits.  Which suggests me that\n> there may be something that tiebreaks based on object names?\n\nHmm. I wouldn't think so. The order should come from timestamps, with\nties broken by order of insertion, which in turn comes from traversal,\nwhich depends only on parent order. We do check some raw sha1s in the\nexpected output, but it is only for blobs, not commits.  I guess it\ncould be some weirdness inside merge-recursive, though, and\nnot part of the merge-base computation.\n\nSo I really don't know how AUTHOR_DATE would change anything. And\nindeed, after removing them it still passes on my machine.\n\nHowever, I think I may understand why it fails if you tweak the\ncommitter dates.\n\nWhen my unstable-queue was used, I noticed that the merge bases returned\nwere the same (as you would expect), but that they came in a different\norder. Which makes sense, as the order of multiple bases would not\nnecessarily be deterministic (they do not have an ancestry relationship,\nor they would not be merge bases).\n\nSo the issue is that when you do a recursive merge with multiple bases,\nthe order in which you visit the recursive bases is going to impact the\nexact conflicts you see. In theory, after the merge is done, you're\ngoing to be at the same state, but the conflicts you see along the way\nwill be different. And it is this conflicted state that the test is\nlooking at.\n\nThe current test expects a particular order of merge bases based on the\nsame-second commit timestamps. There is no race condition because of the\nsetting of GIT_COMMITTER_DATE at the beginning (and _that_ is the real\nthing that fixed the race conditions Dscho saw in the thread above; the\nAUTHOR_DATE was just a red herring).\n\nSo the test is not broken or racy, which is good. It is just testing\nsomething that is somewhat of an implementation detail. We could switch\nit to use test_tick, and then adjust the expected output to look for the\nexpected conflict that git happens to generate in that case. But that is\nno better than the current behavior.\n\nBut I'm not sure there is a way to test what it wants to test (that we\nhit a conflict that involves one of the recursive merge bases) without\nrelying on the implementation detail. So I'm inclined to just leave it\nin place.\n\n-Peff\n"},{"id":"198129","messageId":"7v3934qbwe.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"20120830213105.GA18636@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T21:59:29Z","receivedAt":"2012-08-30T21:59:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Compared to dropping an O(n^2) operation to O(lg n), that's\n> probably not even going to be noticeable.\n\nYeah, that is something we would want to use when we eventually\nupdate the main revision traverser, not this codepath localized to\nthe merge-base.\n\nThanks.  I like (and agree with) everything you wrote in this\nmessage.\n"},{"id":"198130","messageId":"7vy5kwowjd.fsf@alter.siamese.dyndns.org","threadId":"31368","inReplyTo":"20120830214802.GB18636@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] commit: use a priority queue in merge base functions","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T22:16:38Z","receivedAt":"2012-08-30T22:16:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> So the issue is that when you do a recursive merge with multiple bases,\n> the order in which you visit the recursive bases is going to impact the\n> exact conflicts you see.\n\nYeah, that explains it.\n\n> So the test is not broken or racy, which is good. It is just testing\n> something that is somewhat of an implementation detail. We could switch\n> it to use test_tick, and then adjust the expected output to look for the\n> expected conflict that git happens to generate in that case. But that is\n> no better than the current behavior.\n\nTrue.\n\n> But I'm not sure there is a way to test what it wants to test (that we\n> hit a conflict that involves one of the recursive merge bases) without\n> relying on the implementation detail. So I'm inclined to just leave it\n> in place.\n\nOK.\n"}]}