{"thread":{"id":"30104","subject":"Git push performance problems with ~100K refs","startedAt":"2012-03-30T00:18:49Z","lastAt":"2012-04-11T16:44:52Z","messageCount":37,"participants":["Martin Fick","Junio C Hamano","Jeff King","René Scharfe","Shawn Pearce","Nguyen Thai Ngoc Duy","Nguyễn Thái Ngọc Duy","Stephen Boyd"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"188109","messageId":"201203291818.49933.mfick@codeaurora.org","threadId":"30104","inReplyTo":null,"subject":"Git push performance problems with ~100K refs","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-03-30T00:18:49Z","receivedAt":"2012-03-30T00:18:49Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"Hello,\n\nI am back to talk about git performance with lots of refs: \n~100K. This time I am investigating pushes to a repo with \nabout ~100K ref, a gerrit mirror which includes the gerrit \nchanges. When I push just a simple one line change to a \nfile, the push takes about ~43s. If I delete the changes\nfrom the destination repo, this push takes about 6s. This \nseems rather excessive to me, in fact given that the repo \nwith 100K refs has more data in it and is more likely to \nhave the objects I am pushing in it, if things are done \nright, it should be a faster push (in theory).\n\nSo, upon early investigation, I noticed that the time to \npush seems mostly determined by the receiving end which is \nprocessing all out for 100% on a CPU. During this time \nperiod, the receiving end git commands look like this:\n\n git-receive-pack path/to/repo.git\n\nand:\n\n git rev-list --objects --stdin --not --all\n\nThe latter of these two commands is the one burning CPU.\n\nDoes anyone have any hints as to what might be wrong with \nthe receiving end algorithm that would cause a small change \nto use so much CPU? Is there anything that can be done \nabout it? I noticed that the --all option will effectively \nfeed all the 100K refs to rev-list, is this really \nnecessary? Are there any tests that I can perform to help \ndebug this?\n\nI am using git 1.7.8.3 and I also tried 1.7.10.rc3, same \nresults.\n\nThanks,\n\n-Martin\n\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"188115","messageId":"7v7gy2q1kq.fsf@alter.siamese.dyndns.org","threadId":"30104","inReplyTo":"201203291818.49933.mfick@codeaurora.org","subject":"Re: Git push performance problems with ~100K refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-30T02:12:21Z","receivedAt":"2012-03-30T02:12:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick writes:\n\n> Does anyone have any hints as to what might be wrong with \n> the receiving end algorithm that would cause a small change \n> to use so much CPU? Is there anything that can be done \n> about it? I noticed that the --all option will effectively \n> feed all the 100K refs to rev-list, is this really \n> necessary?\n\nIt is trying to minimize the transfer cost. By showing a ref to the\nsending side, you prove you have chains of commits leading to that commit\nand the sender knows that it does not have to send objects that are\nreachable from that ref. One thing you could immediately do is de-dup the\n100k refs but we may already do that in the current code.\n\n> Are there any tests that I can perform to help \n> debug this?\n\nYou do not need to \"help debug\" it. It's cause is already known: the\nreceiver exposes too many refs to the sending side.\n\nWe've talked about possible solutions but no concrete design nor code is\nthere yet.\n"},{"id":"188118","messageId":"60bff12d-544c-4fbd-b48a-0fdf44efaded@email.android.com","threadId":"30104","inReplyTo":"7v7gy2q1kq.fsf@alter.siamese.dyndns.org","subject":"Re: Git push performance problems with ~100K refs","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-03-30T02:43:06Z","receivedAt":"2012-03-30T02:43:06Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"\n\nJunio C Hamano wrote:\n\n>Martin Fick writes:\n>\n>> Does anyone have any hints as to what might be wrong with \n>> the receiving end algorithm that would cause a small change \n>> to use so much CPU? Is there anything that can be done \n>> about it? I noticed that the --all option will effectively \n>> feed all the 100K refs to rev-list, is this really \n>> necessary?\n>\n>It is trying to minimize the transfer cost. By showing a ref to the\n>sending side, you prove you have chains of commits leading to that\n>commit\n>and the sender knows that it does not have to send objects that are\n>reachable from that ref. One thing you could immediately do is de-dup\n>the\n>100k refs but we may already do that in the current code.\n\nI am sorry I don't quite understand what you are suggesting is taking up the CPU time? It doesn't take that much CPU just to gather 100refs and send them to the other side, that would be i/o bound. Could you explain what is happening on the receiving side that is so time consuming?\n\n>> Are there any tests that I can perform to help \n>> debug this?\n>\n>You do not need to \"help debug\" it. It's cause is already known: the\n>receiver exposes too many refs to the sending side.\n\nBut wouldn't that cause excessive CPU for the sending side? It did with jgit, but that can be remedied with a simple jgit fix.\n\nThanks for your insights,\n\n-Martin\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"188141","messageId":"20120330093207.GA12298@sigill.intra.peff.net","threadId":"30104","inReplyTo":"60bff12d-544c-4fbd-b48a-0fdf44efaded@email.android.com","subject":"Re: Git push performance problems with ~100K refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-03-30T09:32:08Z","receivedAt":"2012-03-30T09:32:08Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 29, 2012 at 08:43:06PM -0600, Martin Fick wrote:\n\n> >It is trying to minimize the transfer cost. By showing a ref to the\n> >sending side, you prove you have chains of commits leading to that\n> >commit\n> >and the sender knows that it does not have to send objects that are\n> >reachable from that ref. One thing you could immediately do is de-dup\n> >the\n> >100k refs but we may already do that in the current code.\n> \n> I am sorry I don't quite understand what you are suggesting is taking\n> up the CPU time? It doesn't take that much CPU just to gather 100refs\n> and send them to the other side, that would be i/o bound. Could you\n> explain what is happening on the receiving side that is so time\n> consuming?\n\nYou said earlier that it is \"git rev-list --objects --stdin --not --all\"\ntaking up all the CPU. That is probably called by\ncheck_everything_connected. And that is why it is slow when you push\neven a small change, but fast when you push only a deletion (in the\nlatter case, we skip the check because there are no new objects).\n\nAs for why that rev-list is slow, my suspicion is that it may be\nquadratic behavior in commit_list_insert_by_date as we process the set\nof negative refs. Basically, we keep a priority queue of commits to be\nprocessed in our graph walk, but the queue is stored as a linked list.\nSo insertion is O(n), and building a list of n items (especially if they\nare not in sorted order) is O(n^2).\n\nI've run into this before dealing with repos with many refs (at GitHub,\nsome of our alternates repositories hit 100K refs, although typically we\nhave a lot of duplicated refs, as we are storing identical tags from\nmany repositories).\n\nBut that's just a suspicion. I don't have time tonight to work out a\ntest case. Is it possible for you to run something like:\n\n # make a new commit on top of HEAD, but not yet referenced\n sha1=`git commit-tree HEAD^{tree} -p HEAD But that's just a suspicion. I don't have time tonight to work out a\n> test case. Is it possible for you to run something like:\n> \n> # make a new commit on top of HEAD, but not yet referenced\n> sha1=`git commit-tree HEAD^{tree} -p HEAD \n> # now do the same \"connected\" test that receive-pack would do\n> git rev-list --objects $sha1 --not --all\n> \n> That should replicate the slow behavior you are seeing. If that works,\n> try running the latter command under \"perf\"; my guess is that you will\n> see commit_list_insert_by_date as a hot-spot.\n> \n> Even doing this simple test on a moderate repository (my git.git has\n> ~1100 refs), commit_list_insert_by_date accounts for 10% of the CPU\n> according to perf.\n\nActually, I did have time for a simple test. Doing:\n\n git rev-list HEAD |\n while read sha1; do\n echo $sha1 refs/heads/$sha1\n done >>packed-refs\n git pack-refs\n\nin git.git slows down the test above considerably, and perf reports 90%\nof the time spent in commit_list_insert_by_date. So I think that is\nindeed the problem.\n\nAt one point, I looked at replacing the commit_list implementation with\na heap-based priority queue, but unfortunately many parts of the code\ndepend on the list-like nature and would need to be rewritten. We might\nbe able to hack around it by at least adding all of the initial items to\nan unordered list, then sorting it into its final form.\n\n-Peff\n"},{"id":"188162","messageId":"53c2a263-69f5-4de0-b2e2-17639d311405@email.android.com","threadId":"30104","inReplyTo":"20120330094052.GB12298@sigill.intra.peff.net","subject":"Re: Git push performance problems with ~100K refs","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-03-30T14:22:15Z","receivedAt":"2012-03-30T14:22:15Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"\n\nJeff King wrote:\n>\n>Actually, I did have time for a simple test. Doing:\n>\n> git rev-list HEAD |\n> while read sha1; do\n> echo $sha1 refs/heads/$sha1\n> done >>packed-refs\n> git pack-refs\n>\n>in git.git slows down the test above considerably, and perf reports 90%\n>of the time spent in commit_list_insert_by_date. So I think that is\n>indeed the problem.\n>\n>At one point, I looked at replacing the commit_list implementation with\n>a heap-based priority queue, but unfortunately many parts of the code\n>depend on the list-like nature and would need to be rewritten. We might\n>be able to hack around it by at least adding all of the initial items\n>to\n>an unordered list, then sorting it into its final form.\n\nThanks Peff for the explanation. Jgit actually has the exact same problem, it slows down the pushing side. Fortunately, in jgit it is well isolated and can easily be remedied by both the solutions you mention, and both work to speed it (jgit) up drastically! I wonder if libgit2 suffers from the same problem?\n\nThis might be one of the last pieces to git ref scalability left? Does this affect many other use cases, fetches?\n\n-Martin\n\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"188266","messageId":"4F7780C3.2050408@lsrfire.ath.cx","threadId":"30104","inReplyTo":"20120330094052.GB12298@sigill.intra.peff.net","subject":"[PATCH 1/3] add mergesort() for linked lists","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-03-31T22:10:11Z","receivedAt":"2012-03-31T22:10:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"This adds a generic bottom-up mergesort implementation for singly linked\nlists. It was inspired by Simon Tatham's webpage on the topic[1], but\nnot so much by his implementation -- for no good reason, really, just a\ncase of NIH.\n\n[1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html\n\nSigned-off-by: Rene Scharfe \n---\nAs you can guess from the patch, I just love function pointers. :) It\nmay be interesting to know how much overhead they add, but in the test\ncase you described (a ref for each revision of git.git) the call to\nmergesort (wired up in patch 3) only contributes less than 1% of the cost\naccording to callgrind, including its callees.\n\nWARNING! This is fresh code, and while the algorithm is simple, it's\npossible that I was still somehow able to sneak in a bug.\n\n .gitignore | 1 +\n Makefile | 3 +++\n mergesort.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n mergesort.h | 9 +++++++\n test-mergesort.c | 52 +++++++++++++++++++++++++++++++++++++\n 5 files changed, 140 insertions(+)\n create mode 100644 mergesort.c\n create mode 100644 mergesort.h\n create mode 100644 test-mergesort.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 87fcc5f..225656a 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -180,6 +180,7 @@\n /test-index-version\n /test-line-buffer\n /test-match-trees\n+/test-mergesort\n /test-mktemp\n /test-parse-options\n /test-path-utils\ndiff --git a/Makefile b/Makefile\nindex be1957a..b04d6ec 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -480,6 +480,7 @@ TEST_PROGRAMS_NEED_X += test-genrandom\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-line-buffer\n TEST_PROGRAMS_NEED_X += test-match-trees\n+TEST_PROGRAMS_NEED_X += test-mergesort\n TEST_PROGRAMS_NEED_X += test-mktemp\n TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n@@ -590,6 +591,7 @@ LIB_H += log-tree.h\n LIB_H += mailmap.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n+LIB_H += mergesort.h\n LIB_H += notes.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n@@ -694,6 +696,7 @@ LIB_OBJS += mailmap.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\n+LIB_OBJS += mergesort.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/mergesort.c b/mergesort.c\nnew file mode 100644\nindex 0000000..c0f1874\n--- /dev/null\n+++ b/mergesort.c\n@@ -0,0 +1,75 @@\n+#include \"cache.h\"\n+#include \"mergesort.h\"\n+\n+#include \"commit.h\"\n+\n+struct mergesort_sublist {\n+\tvoid *ptr;\n+\tunsigned long len;\n+};\n+\n+static void *get_nth_next(void *list, unsigned long n,\n+\t\t\t void *(*get_next_fn)(const void *))\n+{\n+\twhile (n-- && list)\n+\t\tlist = get_next_fn(list);\n+\treturn list;\n+}\n+\n+static void *pop_item(struct mergesort_sublist *l,\n+\t\t void *(*get_next_fn)(const void *))\n+{\n+\tvoid *p = l->ptr;\n+\tl->ptr = get_next_fn(l->ptr);\n+\tl->len = l->ptr ? (l->len - 1) : 0;\n+\treturn p;\n+}\n+\n+void *mergesort(void *list,\n+\t\tvoid *(*get_next_fn)(const void *),\n+\t\tvoid (*set_next_fn)(void *, void *),\n+\t\tint (*compare_fn)(const void *, const void *))\n+{\n+\tunsigned long l;\n+\n+\tif (!list)\n+\t\treturn NULL;\n+\tfor (l = 1; ; l *= 2) {\n+\t\tvoid *curr;\n+\t\tstruct mergesort_sublist p, q;\n+\n+\t\tp.ptr = list;\n+\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n+\t\tif (!q.ptr)\n+\t\t\tbreak;\n+\t\tp.len = q.len = l;\n+\n+\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n+\t\t\tlist = curr = pop_item(&q, get_next_fn);\n+\t\telse\n+\t\t\tlist = curr = pop_item(&p, get_next_fn);\n+\n+\t\twhile (p.ptr) {\n+\t\t\twhile (p.len || q.len) {\n+\t\t\t\tvoid *prev = curr;\n+\n+\t\t\t\tif (!p.len)\n+\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n+\t\t\t\telse if (!q.len)\n+\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n+\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n+\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n+\t\t\t\telse\n+\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n+\t\t\t\tset_next_fn(prev, curr);\n+\t\t\t}\n+\t\t\tp.ptr = q.ptr;\n+\t\t\tp.len = l;\n+\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n+\t\t\tq.len = q.ptr ? l : 0;\n+\n+\t\t}\n+\t\tset_next_fn(curr, NULL);\n+\t}\n+\treturn list;\n+}\ndiff --git a/mergesort.h b/mergesort.h\nnew file mode 100644\nindex 0000000..d6e5f4a\n--- /dev/null\n+++ b/mergesort.h\n@@ -0,0 +1,9 @@\n+#ifndef MERGESORT_H\n+#define MERGESORT_H\n+\n+void *mergesort(void *list,\n+\t\tvoid *(*get_next_fn)(const void *),\n+\t\tvoid (*set_next_fn)(void *, void *),\n+\t\tint (*compare_fn)(const void *, const void *));\n+\n+#endif\ndiff --git a/test-mergesort.c b/test-mergesort.c\nnew file mode 100644\nindex 0000000..02441ab\n--- /dev/null\n+++ b/test-mergesort.c\n@@ -0,0 +1,52 @@\n+#include \"cache.h\"\n+#include \"mergesort.h\"\n+\n+struct line {\n+\tchar *text;\n+\tstruct line *next;\n+};\n+\n+static void *get_next(const void *a)\n+{\n+\treturn ((const struct line *)a)->next;\n+}\n+\n+static void set_next(void *a, void *b)\n+{\n+\t((struct line *)a)->next = b;\n+}\n+\n+static int compare_strings(const void *a, const void *b)\n+{\n+\tconst struct line *x = a, *y = b;\n+\treturn strcmp(x->text, y->text);\n+}\n+\n+int main(int argc, const char **argv)\n+{\n+\tstruct line *line, *p = NULL, *lines = NULL;\n+\tstruct strbuf sb = STRBUF_INIT;\n+\n+\tfor (;;) {\n+\t\tif (strbuf_getwholeline_fd(&sb, 0, '\\n'))\n+\t\t\tbreak;\n+\t\tline = xmalloc(sizeof(struct line));\n+\t\tline->text = strbuf_detach(&sb, NULL);\n+\t\tif (p) {\n+\t\t\tline->next = p->next;\n+\t\t\tp->next = line;\n+\t\t} else {\n+\t\t\tline->next = NULL;\n+\t\t\tlines = line;\n+\t\t}\n+\t\tp = line;\n+\t}\n+\n+\tlines = mergesort(lines, get_next, set_next, compare_strings);\n+\n+\twhile (lines) {\n+\t\tprintf(\"%s\", lines->text);\n+\t\tlines = lines->next;\n+\t}\n+\treturn 0;\n+}\n-- \n1.7.9.2\n"},{"id":"188265","messageId":"4F7780DF.1000902@lsrfire.ath.cx","threadId":"30104","inReplyTo":"20120330094052.GB12298@sigill.intra.peff.net","subject":"[PATCH 2/3] commit: use mergesort() in commit_list_sort_by_date()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-03-31T22:10:39Z","receivedAt":"2012-03-31T22:10:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Replace the insertion sort in commit_list_sort_by_date() with a\ncall to the generic mergesort function. This sets the stage for\nusing commit_list_sort_by_date() for larger lists, as shown in\nthe next patch.\n\nSigned-off-by: Rene Scharfe \n---\n commit.c | 29 +++++++++++++++++++++++------\n 1 file changed, 23 insertions(+), 6 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 4b39c19..0d0c424 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 \"mergesort.h\"\n \n int save_commit_buffer = 1;\n \n@@ -390,15 +391,31 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm\n \treturn commit_list_insert(item, pp);\n }\n \n+static int commit_list_compare_by_date(const void *a, const void *b)\n+{\n+\tunsigned long a_date = ((const struct commit_list *)a)->item->date;\n+\tunsigned long b_date = ((const struct commit_list *)b)->item->date;\n+\tif (a_date < b_date)\n+\t\treturn 1;\n+\tif (a_date > b_date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n+static void *commit_list_get_next(const void *a)\n+{\n+\treturn ((const struct commit_list *)a)->next;\n+}\n+\n+static void commit_list_set_next(void *a, void *next)\n+{\n+\t((struct commit_list *)a)->next = next;\n+}\n \n void commit_list_sort_by_date(struct commit_list **list)\n {\n-\tstruct commit_list *ret = NULL;\n-\twhile (*list) {\n-\t\tcommit_list_insert_by_date((*list)->item, &ret);\n-\t\t*list = (*list)->next;\n-\t}\n-\t*list = ret;\n+\t*list = mergesort(*list, commit_list_get_next, commit_list_set_next,\n+\t\t\t commit_list_compare_by_date);\n }\n \n struct commit *pop_most_recent_commit(struct commit_list **list,\n-- \n1.7.9.2\n"},{"id":"188267","messageId":"4F7780F5.3060306@lsrfire.ath.cx","threadId":"30104","inReplyTo":"20120330094052.GB12298@sigill.intra.peff.net","subject":"[PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-03-31T22:11:01Z","receivedAt":"2012-03-31T22:11:01Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Speed up prepare_revision_walk() by adding commits without sorting\nto the commit_list and at the end sort the list in one go. Thanks\nto mergesort() working behind the scenes, this is a lot faster for\nlarge numbers of commits than the current insert sort.\n\nAlso introduce and use commit_list_reverse(), to keep the ordering\nof commits sharing the same commit date unchanged. That's because\ncommit_list_insert_by_date() sorts commits with descending date,\nbut adds later entries with the same date entries last, while\ncommit_list_insert() always inserts entries at the top. The\nfollowing commit_list_sort_by_date() keeps the order of entries\nsharing the same date.\n\nJeff's test case, in a repo with lots of refs, was to run:\n\n # make a new commit on top of HEAD, but not yet referenced\n sha1=`git commit-tree HEAD^{tree} -p HEAD \n---\n commit.c | 15 +++++++++++++++\n commit.h | 1 +\n revision.c | 4 +++-\n 3 files changed, 19 insertions(+), 1 deletion(-)\n\ndiff --git a/commit.c b/commit.c\nindex 0d0c424..5ebbda0 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -361,6 +361,21 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *\n \treturn new_list;\n }\n \n+void commit_list_reverse(struct commit_list **list_p)\n+{\n+\tstruct commit_list *prev = NULL, *curr = *list_p, *next;\n+\n+\tif (!list_p)\n+\t\treturn;\n+\twhile (curr) {\n+\t\tnext = curr->next;\n+\t\tcurr->next = prev;\n+\t\tprev = curr;\n+\t\tcurr = next;\n+\t}\n+\t*list_p = prev;\n+}\n+\n unsigned commit_list_count(const struct commit_list *l)\n {\n \tunsigned c = 0;\ndiff --git a/commit.h b/commit.h\nindex 154c0e3..f8d250d 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -57,6 +57,7 @@ unsigned commit_list_count(const struct commit_list *l);\n struct commit_list *commit_list_insert_by_date(struct commit *item,\n \t\t\t\t struct commit_list **list);\n void commit_list_sort_by_date(struct commit_list **list);\n+void commit_list_reverse(struct commit_list **list_p);\n \n void free_commit_list(struct commit_list *list);\n \ndiff --git a/revision.c b/revision.c\nindex b3554ed..92095f5 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2076,11 +2076,13 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (commit) {\n \t\t\tif (!(commit->object.flags & SEEN)) {\n \t\t\t\tcommit->object.flags |= SEEN;\n-\t\t\t\tcommit_list_insert_by_date(commit, &revs->commits);\n+\t\t\t\tcommit_list_insert(commit, &revs->commits);\n \t\t\t}\n \t\t}\n \t\te++;\n \t}\n+\tcommit_list_reverse(&revs->commits);\n+\tcommit_list_sort_by_date(&revs->commits);\n \tif (!revs->leak_pending)\n \t\tfree(list);\n \n-- \n1.7.9.2\n"},{"id":"188268","messageId":"2e914933-a57d-4d16-a1ba-37f6f4365606@email.android.com","threadId":"30104","inReplyTo":"4F7780F5.3060306@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-03-31T22:36:04Z","receivedAt":"2012-03-31T22:36:04Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"\n\n\"René Scharfe\" wrote:\n\n>Speed up prepare_revision_walk() by adding commits without sorting\n>to the commit_list and at the end sort the list in one go. Thanks\n>to mergesort() working behind the scenes, this is a lot faster for\n>large numbers of commits than the current insert sort.\n\nThanks for these René, I will see if I can try them out on Monday!\n\n-Martin\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"188270","messageId":"7vlimgibce.fsf@alter.siamese.dyndns.org","threadId":"30104","inReplyTo":"4F7780F5.3060306@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-31T23:45:21Z","receivedAt":"2012-03-31T23:45:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Speed up prepare_revision_walk() by adding commits without sorting\n> to the commit_list and at the end sort the list in one go. Thanks\n> to mergesort() working behind the scenes, this is a lot faster for\n> large numbers of commits than the current insert sort.\n\nThis is one of these moments I am reminded why I am grateful to have you\nin the community. The first message from you in a topic that needs to\ntouch a quite core part of the system often is not a participation in the\ndiscussion, but is a solution that is already well crafted.\n\nThanks, will queue.\n"},{"id":"188323","messageId":"201204021024.49706.mfick@codeaurora.org","threadId":"30104","inReplyTo":"4F7780F5.3060306@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-04-02T16:24:49Z","receivedAt":"2012-04-02T16:24:49Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Saturday, March 31, 2012 04:11:01 pm René Scharfe wrote:\n> Speed up prepare_revision_walk() by adding commits\n> without sorting to the commit_list and at the end sort\n> the list in one go. Thanks to mergesort() working\n> behind the scenes, this is a lot faster for large\n> numbers of commits than the current insert sort.\n\nThis speeds up my git push test on my repo with ~100K refs \ncase from out ~43s to about ~10s. Not bad, thanks!\n\nThe rest of the 10s do not seem to be spent with high CPU on \neither the pushing or the receiving side (only a very small \n100% burst on both sides near the end of the operation). I \nalso ran iotop on the receiving side and could not find any \nactivity (of course, the repo is likely cached). iftop does \nshow a decent amount of traffic during this time, so perhaps \nwe are finally approaching the protocol limit? \n\nBut, I have my doubts on that to be honest. The reason is \nbecause I am able to hack Gerrit to receive this push much \nfaster (around 3.5s) by reusing a cached RevWalk. Without \nthe cached RevWalk, Gerrit (using jgit) is about the same as \nyour new patch ~10s. I am not saying that git is spending \nits time in the same place (but it may be) as jgit, but with \njgit, the time I was able to save with the cached RevWalk \nwas the time spent loading and parsing the RevCommits. This \ncould be the same thing that git is doing? And while it may \nnot be I/O (disk) bound so to speak since the packs are \nlikely cached, it may still be memory bound on that I/O? If \nit is memory bound, and not I/O(disk) or CPU bound, I guess \nit makes sense that git and jgit would perform about the \nsame (10s)?\n\nThanks again for your patch,\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"188325","messageId":"CAJo=hJshOBg4pT8nuWZ=eZvj=E9x+4b9M_EANa=02x=NFW2OfQ@mail.gmail.com","threadId":"30104","inReplyTo":"201204021024.49706.mfick@codeaurora.org","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-02T16:39:59Z","receivedAt":"2012-04-02T16:39:59Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Apr 2, 2012 at 09:24, Martin Fick wrote:\n> On Saturday, March 31, 2012 04:11:01 pm René Scharfe wrote:\n>> Speed up prepare_revision_walk() by adding commits\n>> without sorting to the commit_list and at the end sort\n>> the list in one go.  Thanks to mergesort() working\n>> behind the scenes, this is a lot faster for large\n>> numbers of commits than the current insert sort.\n>\n> This speeds up my git push test on my repo with ~100K refs\n> case from out ~43s to about ~10s.  Not bad, thanks!\n>\n> The rest of the 10s do not seem to be spent with high CPU on\n> either the pushing or the receiving side (only a very small\n> 100% burst on both sides near the end of the operation).  I\n> also ran iotop on the receiving side and could not find any\n> activity (of course, the repo is likely cached).  iftop does\n> show a decent amount of traffic during this time, so perhaps\n> we are finally approaching the protocol limit?\n\nThe protocol is basically two round trips, receive side tells push\nside what it has, push side sends data, receive side sends\nsuccess/error response. It would be more traffic with SSH due to the\nencryption and custom ACK messages that SSH runs to wrap the stream.\n\n> But, I have my doubts on that to be honest.  The reason is\n> because I am able to hack Gerrit to receive this push much\n> faster (around 3.5s) by reusing a cached RevWalk.  Without\n> the cached RevWalk, Gerrit (using jgit) is about the same as\n> your new patch ~10s.  I am not saying that git is spending\n> its time in the same place (but it may be) as jgit, but with\n> jgit, the time I was able to save with the cached RevWalk\n> was the time spent loading and parsing the RevCommits.  This\n> could be the same thing that git is doing?  And while it may\n> not be I/O (disk) bound so to speak since the packs are\n> likely cached, it may still be memory bound on that I/O?  If\n> it is memory bound, and not I/O(disk) or CPU bound, I guess\n> it makes sense that git and jgit would perform about the\n> same (10s)?\n\nGit can't really do the same thing as \"cache the RevWalk\". Its\nspawning a new process that needs to decompress and parse each commit\nobject to determine its timestamp so the commits can be sorted into\nthe priority queue. This is still an O(N) operation given N\nreferences.\n"},{"id":"188327","messageId":"201204021049.04901.mfick@codeaurora.org","threadId":"30104","inReplyTo":"CAJo=hJshOBg4pT8nuWZ=eZvj=E9x+4b9M_EANa=02x=NFW2OfQ@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-04-02T16:49:04Z","receivedAt":"2012-04-02T16:49:04Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Monday, April 02, 2012 10:39:59 am Shawn Pearce wrote:\n> On Mon, Apr 2, 2012 at 09:24, Martin Fick \n wrote:\n> > On Saturday, March 31, 2012 04:11:01 pm René Scharfe \nwrote:\n> Git can't really do the same thing as \"cache the\n> RevWalk\". Its spawning a new process that needs to\n> decompress and parse each commit object to determine its\n> timestamp so the commits can be sorted into the priority\n> queue. This is still an O(N) operation given N\n> references.\n\nWhile I suspect this has been suggested before, an ondisk \ncache of commits to timestamps would probably help here with \nlarge repos. Such a cache could make even new processes \nable to create this list much quicker. Since this cache \nwould contain immutable data, even if it is out of date it \nwould likely provided significant improvements by providing \nmost of the timestamps leaving only a few to parse from \nnewer commits?\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"188329","messageId":"CAJo=hJsprQtjDChtrSMcne+OCeUx=NVxLHs3k_qnYLzO=aQWuw@mail.gmail.com","threadId":"30104","inReplyTo":"201204021049.04901.mfick@codeaurora.org","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-02T16:51:21Z","receivedAt":"2012-04-02T16:51:21Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Apr 2, 2012 at 09:49, Martin Fick wrote:\n> On Monday, April 02, 2012 10:39:59 am Shawn Pearce wrote:\n>> On Mon, Apr 2, 2012 at 09:24, Martin Fick\n> wrote:\n>> > On Saturday, March 31, 2012 04:11:01 pm René Scharfe\n> wrote:\n>> Git can't really do the same thing as \"cache the\n>> RevWalk\". Its spawning a new process that needs to\n>> decompress and parse each commit object to determine its\n>> timestamp so the commits can be sorted into the priority\n>> queue. This is still an O(N) operation given N\n>> references.\n>\n> While I suspect this has been suggested before, an ondisk\n> cache of commits to timestamps would probably help here with\n> large repos.  Such a cache could make even new processes\n> able to create this list much quicker.  Since this cache\n> would contain immutable data, even if it is out of date it\n> would likely provided significant improvements by providing\n> most of the timestamps leaving only a few to parse from\n> newer commits?\n\nProbably. But we tend to hate caches in Git because they can get stale\nand need to be rebuilt, and are redundant with the base data. The\nmythical \"pack v4\" work was going to approach this problem by storing\nthe commit timestamps uncompressed in a more machine friendly format.\nUnfortunately the work has been stalled for years.\n"},{"id":"188344","messageId":"20120402201432.GA26503@sigill.intra.peff.net","threadId":"30104","inReplyTo":"4F7780F5.3060306@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-02T20:14:33Z","receivedAt":"2012-04-02T20:14:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 01, 2012 at 12:11:01AM +0200, René Scharfe wrote:\n\n> Speed up prepare_revision_walk() by adding commits without sorting\n> to the commit_list and at the end sort the list in one go. Thanks\n> to mergesort() working behind the scenes, this is a lot faster for\n> large numbers of commits than the current insert sort.\n\nI think this is probably a sane thing to do, but I have two slight\nmisgivings:\n\n 1. Is it worth the complexity of the linked-list mergesort? I was\n planning to just build an array, qsort it, and then put the results\n into a linked list. The patch for that is below for reference.\n\n It's a lot less code and complexity for the same performance\n (actually, I measured it at 1% faster, but that is probably\n negligible). The downside is that it is not nicely encapsulated in\n commit_list_sort_by_date(). We call the latter from two other\n places; I don't know if they can be fed with enough commits to\n actually benefit from the performance gain or not.\n\n 2. I'm not super happy about fixing this one spot. This quadratic\n behavior comes up in a lot of places, and we're slowly hacking them\n one by one. E.g., this does nothing to help the same case in\n fetch-pack.c:mark_complete[1]. Nor does it help the fact that\n when we follow parents, we will do an O(n) insert_by_date for each\n commit we insert. The latter is largely saved by the locality of\n timestamps (i.e., timestamps of the parents of recently popped\n commits tend to be near the front of the list), as well as the hack\n in fce87ae (Fix quadratic performance in rewrite_one., 2008-07-12).\n\n So I wonder if in the long term we would benefit from a better data\n structure, which would make these problems just go away. That being\n said, there is a lot of code to be updated with such a change, so\n even if we do want to do that eventually, a quick fix like this is\n probably still a good thing.\n\n-Peff\n\n[1] I fixed the mark_complete thing in ea5f220 (fetch: avoid repeated\n commits in mark_complete, 2011-05-19), but only for exact-duplicate\n commits. The real-world case where it came up was an \"alternates\"\n repository that held refs for many clones (so we had hundreds or\n thousands of copies of each tag). But on a repository like the one\n we are testing on, I think it would be similarly slow.\n\n---\nHere's the qsort-in-array patch, for reference.\n\ndiff --git a/revision.c b/revision.c\nindex b3554ed..22c26d0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2062,10 +2062,24 @@ static void set_children(struct rev_info *revs)\n \t}\n }\n \n+static int commit_compare_by_date(const void *va, const void *vb)\n+{\n+\tconst struct commit *a = va;\n+\tconst struct commit *b = vb;\n+\tif (a->date < b->date)\n+\t\treturn -1;\n+\tif (b->date < a->date)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n int prepare_revision_walk(struct rev_info *revs)\n {\n \tint nr = revs->pending.nr;\n \tstruct object_array_entry *e, *list;\n+\tstruct commit **commits = NULL;\n+\tint commits_nr = 0, commits_alloc = 0;\n+\tint i;\n \n \te = list = revs->pending.objects;\n \trevs->pending.nr = 0;\n@@ -2076,11 +2090,17 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (commit) {\n \t\t\tif (!(commit->object.flags & SEEN)) {\n \t\t\t\tcommit->object.flags |= SEEN;\n-\t\t\t\tcommit_list_insert_by_date(commit, &revs->commits);\n+\t\t\t\tALLOC_GROW(commits, commits_nr + 1, commits_alloc);\n+\t\t\t\tcommits[commits_nr++] = commit;\n \t\t\t}\n \t\t}\n \t\te++;\n \t}\n+\tqsort(commits, commits_nr, sizeof(*commits), commit_compare_by_date);\n+\tfor (i = commits_nr - 1; i >= 0; i--)\n+\t\tcommit_list_insert(commits[i], &revs->commits);\n+\tfree(commits);\n+\n \tif (!revs->leak_pending)\n \t\tfree(list);\n \n"},{"id":"188346","messageId":"20120402203728.GB26503@sigill.intra.peff.net","threadId":"30104","inReplyTo":"CAJo=hJsprQtjDChtrSMcne+OCeUx=NVxLHs3k_qnYLzO=aQWuw@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-02T20:37:28Z","receivedAt":"2012-04-02T20:37:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 02, 2012 at 09:51:21AM -0700, Shawn O. Pearce wrote:\n\n> Probably. But we tend to hate caches in Git because they can get stale\n> and need to be rebuilt, and are redundant with the base data. The\n> mythical \"pack v4\" work was going to approach this problem by storing\n> the commit timestamps uncompressed in a more machine friendly format.\n> Unfortunately the work has been stalled for years.\n\nI'd love for packv4 to exist, but even once it does, it comes with its\nown complications for network transfer (since we will have to translate\nto/from packv2 on the wire).\n\nHas anyone looked seriously at a new index format that stores the\nredundant information in a more easily accessible way? It would increase\nour disk usage, but for something like linux-2.6, only by 10MB per\n32-bit word. On most of my systems I would gladly spare some extra RAM\nfor the disk cache if it meant I could avoid inflating a bunch of\nobjects. And this could easily be made optional for systems that don't\nwant to make the tradeoff (if it's not there, you fall back to the\ncurrent procedure; we could even store the data in a separate file to\nretain indexv2 compatibility).\n\nSo it's sort-of a cache, in that it's redundant with the actual data.\nBut staleness and writing issues are a lot simpler, since it only gets\nupdated when we index the pack (and the pack index in general is a\nsimilar concept; we are \"caching\" the location of the object in the\npackfile, rather than doing a linear search to look it up each time).\n\n-Peff\n"},{"id":"188350","messageId":"20120402205112.GA28824@sigill.intra.peff.net","threadId":"30104","inReplyTo":"20120402203728.GB26503@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-02T20:51:12Z","receivedAt":"2012-04-02T20:51:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 02, 2012 at 04:37:28PM -0400, Jeff King wrote:\n\n> Has anyone looked seriously at a new index format that stores the\n> redundant information in a more easily accessible way? It would increase\n> our disk usage, but for something like linux-2.6, only by 10MB per\n> 32-bit word. On most of my systems I would gladly spare some extra RAM\n> for the disk cache if it meant I could avoid inflating a bunch of\n> objects.\n\nActually, that is an over-statement of the size. That would be a\nper-object piece of metadata. A per-commit piece like timestamp would be\nonly 1M per 32-bit word in linux-2.6 (about 1/4 million commits). Or put\nanother way, we could store timestamps and 20-byte parent sha1s in about\n11M.\n\n-Peff\n"},{"id":"188364","messageId":"4F7A2E0D.9030402@lsrfire.ath.cx","threadId":"30104","inReplyTo":"20120402201432.GA26503@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-04-02T22:54:05Z","receivedAt":"2012-04-02T22:54:05Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 02.04.2012 22:14, schrieb Jeff King:\n> On Sun, Apr 01, 2012 at 12:11:01AM +0200, René Scharfe wrote:\n>\n>> Speed up prepare_revision_walk() by adding commits without sorting\n>> to the commit_list and at the end sort the list in one go. Thanks\n>> to mergesort() working behind the scenes, this is a lot faster for\n>> large numbers of commits than the current insert sort.\n>\n> I think this is probably a sane thing to do, but I have two slight\n> misgivings:\n>\n> 1. Is it worth the complexity of the linked-list mergesort? I was\n> planning to just build an array, qsort it, and then put the results\n> into a linked list. The patch for that is below for reference.\n>\n> It's a lot less code and complexity for the same performance\n> (actually, I measured it at 1% faster, but that is probably\n> negligible). The downside is that it is not nicely encapsulated in\n> commit_list_sort_by_date(). We call the latter from two other\n> places; I don't know if they can be fed with enough commits to\n> actually benefit from the performance gain or not.\n\nUsing a temporary array here is just sad, because linked lists are \nalready sortable, albeit not with qsort(). Your measurements seem to \nanswer my question regarding the overhead of the callback functions of \nmergesort(), in any case. :)\n\nAdding mergesort() only pays if we have other linked lists that we want \nto sort in-place. I didn't search thoroughly for such a use case, but I \nthink we tended to prefer arrays so far instead.\n\n> So I wonder if in the long term we would benefit from a better data\n> structure, which would make these problems just go away. That being\n> said, there is a lot of code to be updated with such a change, so\n> even if we do want to do that eventually, a quick fix like this is\n> probably still a good thing.\n\nUsing a more appropriate data structure sounds good in general. How \nabout using a skip list? (Or perhaps I need to lay the hammer of linked \nlists to rest for a while to stop seeing all data structures as the \nproverbial nails, or something. ;-)\n\n> Here's the qsort-in-array patch, for reference.\n\nIt looks nice and to the point, but breaks several tests for me (t3508, \nt4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401). Not sure why.\n\nRené\n"},{"id":"188368","messageId":"201204021716.22842.mfick@codeaurora.org","threadId":"30104","inReplyTo":"20120402203728.GB26503@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-04-02T23:16:22Z","receivedAt":"2012-04-02T23:16:22Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Monday, April 02, 2012 02:37:28 pm Jeff King wrote:\n> On Mon, Apr 02, 2012 at 09:51:21AM -0700, Shawn O. Pearce \nwrote:\n> > Probably. But we tend to hate caches in Git because\n> > they can get stale and need to be rebuilt, and are\n> > redundant with the base data. The mythical \"pack v4\"\n> > work was going to approach this problem by storing the\n> > commit timestamps uncompressed in a more machine\n> > friendly format. Unfortunately the work has been\n> > stalled for years.\n...\n\n> So it's sort-of a cache, in that it's redundant with the\n> actual data. But staleness and writing issues are a lot\n> simpler, since it only gets updated when we index the\n> pack (and the pack index in general is a similar\n> concept; \n...\nexcept that in the case of timestamps, it never even gets \nstale, it simply misses some entries or keeps entries around \nwhich should go away. So even if the pack files are rebuilt \nand someone forgets to update the timestamp index, it \nshouldn't cause any problems: the timestamps which are \nthere should still work and likely will still be useful,\n\n-Martin\n\n\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"188379","messageId":"CACsJy8CSohtWUV_BT-d+tGX9R4LUr1K=jgFh841nST01QLSGuA@mail.gmail.com","threadId":"30104","inReplyTo":"CAJo=hJsprQtjDChtrSMcne+OCeUx=NVxLHs3k_qnYLzO=aQWuw@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T03:44:30Z","receivedAt":"2012-04-03T03:44:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Apr 2, 2012 at 11:51 PM, Shawn Pearce wrote:\n> On Mon, Apr 2, 2012 at 09:49, Martin Fick wrote:\n>> On Monday, April 02, 2012 10:39:59 am Shawn Pearce wrote:\n>>> On Mon, Apr 2, 2012 at 09:24, Martin Fick\n>> wrote:\n>>> > On Saturday, March 31, 2012 04:11:01 pm René Scharfe\n>> wrote:\n>>> Git can't really do the same thing as \"cache the\n>>> RevWalk\". Its spawning a new process that needs to\n>>> decompress and parse each commit object to determine its\n>>> timestamp so the commits can be sorted into the priority\n>>> queue. This is still an O(N) operation given N\n>>> references.\n>>\n>> While I suspect this has been suggested before, an ondisk\n>> cache of commits to timestamps would probably help here with\n>> large repos.  Such a cache could make even new processes\n>> able to create this list much quicker.  Since this cache\n>> would contain immutable data, even if it is out of date it\n>> would likely provided significant improvements by providing\n>> most of the timestamps leaving only a few to parse from\n>> newer commits?\n>\n> Probably. But we tend to hate caches in Git because they can get stale\n> and need to be rebuilt, and are redundant with the base data. The\n> mythical \"pack v4\" work was going to approach this problem by storing\n> the commit timestamps uncompressed in a more machine friendly format.\n> Unfortunately the work has been stalled for years.\n\nwhich reminds me, hello Nico!\n\nOn Sat, Feb 18, 2012 at 10:34 PM, Nicolas Pitre wrote:\n>> By the way, is latest packv4 code available somewhere to fetch?\n>\n> Well, not yet. Incidentally, I'm going in the Caribbeans for a week in\n> a week, with no kids and only my wife who is going to be busy with scuba\n> diving activities. Like I did last year, I'm going to take some time to\n> pursue my work on Pack v4 during that time. And I intend to publish it\n> when I come back, whatever state it is in, so someone else can complete\n> the work eventually (I have too much to do to spend significant time on\n> Git these days).\n\nHow's the packv4 work going? Is it in a public place? I hope somebody\nelse may have spare time and be motivated enough to finish it.\n-- \nDuy\n"},{"id":"188380","messageId":"CACsJy8DGaFg=oEwLWWo33cJa=SDuuZshW4=cZpifCWLp5gGcTA@mail.gmail.com","threadId":"30104","inReplyTo":"20120402203728.GB26503@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T03:49:01Z","receivedAt":"2012-04-03T03:49:01Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 3, 2012 at 3:37 AM, Jeff King wrote:\n> On Mon, Apr 02, 2012 at 09:51:21AM -0700, Shawn O. Pearce wrote:\n>\n>> Probably. But we tend to hate caches in Git because they can get stale\n>> and need to be rebuilt, and are redundant with the base data. The\n>> mythical \"pack v4\" work was going to approach this problem by storing\n>> the commit timestamps uncompressed in a more machine friendly format.\n>> Unfortunately the work has been stalled for years.\n>\n> I'd love for packv4 to exist, but even once it does, it comes with its\n> own complications for network transfer (since we will have to translate\n> to/from packv2 on the wire).\n>\n> Has anyone looked seriously at a new index format that stores the\n> redundant information in a more easily accessible way? It would increase\n> our disk usage, but for something like linux-2.6, only by 10MB per\n> 32-bit word. On most of my systems I would gladly spare some extra RAM\n> for the disk cache if it meant I could avoid inflating a bunch of\n> objects. And this could easily be made optional for systems that don't\n> want to make the tradeoff (if it's not there, you fall back to the\n> current procedure; we could even store the data in a separate file to\n> retain indexv2 compatibility).\n>\n> So it's sort-of a cache, in that it's redundant with the actual data.\n> But staleness and writing issues are a lot simpler, since it only gets\n> updated when we index the pack (and the pack index in general is a\n> similar concept; we are \"caching\" the location of the object in the\n> packfile, rather than doing a linear search to look it up each time).\n\nI think I have something like that, (generate a machine-friendly\ncommit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's\nseparate cache staying in $GIT_DIR/objects/pack, just like pack-.idx\nfiles. It does improve rev-list time, but I'd rather wait for packv4,\nor at least be sure that packv4 will not come anytime soon, before\npushing the cache route.\n-- \nDuy\n"},{"id":"188384","messageId":"53707c0a-3782-47a4-8a35-da7136ff4822@email.android.com","threadId":"30104","inReplyTo":"CACsJy8DGaFg=oEwLWWo33cJa=SDuuZshW4=cZpifCWLp5gGcTA@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-04-03T05:55:02Z","receivedAt":"2012-04-03T05:55:02Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"\n\nNguyen Thai Ngoc Duy wrote:\n>> we could even store the data in a separate file to\n>> retain indexv2 compatibility).\n>>\n>> So it's sort-of a cache, in that it's redundant with the actual data.\n>> But staleness and writing issues are a lot simpler, since it only\n>gets\n>> updated when we index the pack (and the pack index in general is a\n>> similar concept; we are \"caching\" the location of the object in the\n>> packfile, rather than doing a linear search to look it up each time).\n>\n>I think I have something like that, (generate a machine-friendly\n>commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's\n>separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx\n>files. It does improve rev-list time, but I'd rather wait for packv4,\n>or at least be sure that packv4 will not come anytime soon, before\n>pushing the cache route.\n\nI would love to try those patches out if you have them?\n\n-Martin\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"188386","messageId":"1333436109-16526-1-git-send-email-pclouds@gmail.com","threadId":"30104","inReplyTo":"53707c0a-3782-47a4-8a35-da7136ff4822@email.android.com","subject":"[PATCH 0/3] Commit cache","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T06:55:06Z","receivedAt":"2012-04-03T06:55:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 3, 2012 at 12:55 PM, Martin Fick wrote:\n> Nguyen Thai Ngoc Duy wrote:\n>>> we could even store the data in a separate file to\n>>> retain indexv2 compatibility).\n>>>\n>>> So it's sort-of a cache, in that it's redundant with the actual data.\n>>> But staleness and writing issues are a lot simpler, since it only\n>>gets\n>>> updated when we index the pack (and the pack index in general is a\n>>> similar concept; we are \"caching\" the location of the object in the\n>>> packfile, rather than doing a linear search to look it up each time).\n>>\n>>I think I have something like that, (generate a machine-friendly\n>>commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's\n>>separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx\n>>files. It does improve rev-list time, but I'd rather wait for packv4,\n>>or at least be sure that packv4 will not come anytime soon, before\n>>pushing the cache route.\n>\n> I would love to try those patches out if you have them?\n\nThere you go. Note that these patches are not of high quality. I did not even\nrun \"make test\". To create commit cache, simply run index-pack, e.g.\n\n$ git repack -ad\n$ git index-pack --stdin < .git/objects/pack/pack-XXX.pack\n\nIt will create two more files, pack-XXX.sha1 and pack-XXX.sidx. On\nlinux-2.6.git, \"git rev-list --all --quiet HEAD\" takes 1.9s with the\npatches and 6.6s without. Disk usage:\n\ntotal 531M\n 56M pack-ab843186bdfb00956c1b1c0cdb4ed5e4aa3e549e.idx\n460M pack-ab843185bdfb00956c1b1c0cdb4ed5e4aa3e549e.pack\n9.7M pack-ab843185bdfb00956c1b1c0cdb4ed5e4aa3e549e.sha1\n5.3M pack-ab843185bdfb00956c1b1c0cdb4ed5e4aa3e549e.sidx\n\nNguyễn Thái Ngọc Duy (3):\n parse_commit_buffer: rename a confusing variable name\n Add commit cache to help speed up commit traversal\n Add parse_commit_for_rev() to take advantage of sha1-cache\n\n Makefile | 3 +\n builtin/index-pack.c | 113 ++++++++++++++++++++++++++++++++++-\n builtin/reflog.c | 2 +-\n cache.h | 9 +++\n commit.c | 46 +++++++++++---\n commit.h | 1 +\n log-tree.c | 2 +-\n pack-write.c | 11 +++-\n pack.h | 1 +\n revision.c | 10 ++--\n sha1_cache.c | 161 ++++++++++++++++++++++++++++++++++++++++++++++++++\n sha1_cache.h | 6 ++\n sha1_file.c | 12 ++++-\n test-sha1-cache.c | 19 ++++++\n upload-pack.c | 2 +-\n walker.c | 2 +-\n 16 files changed, 377 insertions(+), 23 deletions(-)\n create mode 100644 sha1_cache.c\n create mode 100644 sha1_cache.h\n create mode 100644 test-sha1-cache.c\n\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"188387","messageId":"1333436109-16526-2-git-send-email-pclouds@gmail.com","threadId":"30104","inReplyTo":"53707c0a-3782-47a4-8a35-da7136ff4822@email.android.com","subject":"[PATCH 1/3] parse_commit_buffer: rename a confusing variable name","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T06:55:07Z","receivedAt":"2012-04-03T06:55:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n commit.c | 10 +++++-----\n 1 files changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 4b39c19..946ea70 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -252,7 +252,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n {\n \tconst char *tail = buffer;\n \tconst char *bufptr = buffer;\n-\tunsigned char parent[20];\n+\tunsigned char sha1[20];\n \tstruct commit_list **pptr;\n \tstruct commit_graft *graft;\n \n@@ -262,10 +262,10 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \ttail += size;\n \tif (tail <= bufptr + 46 || memcmp(bufptr, \"tree \", 5) || bufptr[45] != '\\n')\n \t\treturn error(\"bogus commit object %s\", sha1_to_hex(item->object.sha1));\n-\tif (get_sha1_hex(bufptr + 5, parent) < 0)\n+\tif (get_sha1_hex(bufptr + 5, sha1) < 0)\n \t\treturn error(\"bad tree pointer in commit %s\",\n \t\t\t sha1_to_hex(item->object.sha1));\n-\titem->tree = lookup_tree(parent);\n+\titem->tree = lookup_tree(sha1);\n \tbufptr += 46; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n \tpptr = &item->parents;\n \n@@ -274,7 +274,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \t\tstruct commit *new_parent;\n \n \t\tif (tail <= bufptr + 48 ||\n-\t\t get_sha1_hex(bufptr + 7, parent) ||\n+\t\t get_sha1_hex(bufptr + 7, sha1) ||\n \t\t bufptr[47] != '\\n')\n \t\t\treturn error(\"bad parents in commit %s\", sha1_to_hex(item->object.sha1));\n \t\tbufptr += 48;\n@@ -284,7 +284,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \t\t */\n \t\tif (graft && (graft->nr_parent < 0 || grafts_replace_parents))\n \t\t\tcontinue;\n-\t\tnew_parent = lookup_commit(parent);\n+\t\tnew_parent = lookup_commit(sha1);\n \t\tif (new_parent)\n \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n \t}\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"188388","messageId":"1333436109-16526-3-git-send-email-pclouds@gmail.com","threadId":"30104","inReplyTo":"53707c0a-3782-47a4-8a35-da7136ff4822@email.android.com","subject":"[PATCH 2/3] Add commit cache to help speed up commit traversal","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T06:55:08Z","receivedAt":"2012-04-03T06:55:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This patch extracts tree, parent sha-1 and committer date of packed\ncommits that have exactly one parent out. So that revision traversal\ncode can avoid inflating commit for these sha-1. The assumption is\ncommits with one parent dominate.\n\nTwo new files are created per pack: one file contains sha-1 and dates.\nThe other file contains commit sha-1 mapping to the offset in the former\nfile.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Makefile | 3 +\n builtin/index-pack.c | 113 ++++++++++++++++++++++++++++++++++-\n cache.h | 9 +++\n pack-write.c | 11 +++-\n pack.h | 1 +\n sha1_cache.c | 161 ++++++++++++++++++++++++++++++++++++++++++++++++++\n sha1_cache.h | 6 ++\n sha1_file.c | 12 ++++-\n test-sha1-cache.c | 19 ++++++\n 9 files changed, 331 insertions(+), 4 deletions(-)\n create mode 100644 sha1_cache.c\n create mode 100644 sha1_cache.h\n create mode 100644 test-sha1-cache.c\n\ndiff --git a/Makefile b/Makefile\nindex 87fb30a..fced758 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -481,6 +481,7 @@ TEST_PROGRAMS_NEED_X += test-sha1\n TEST_PROGRAMS_NEED_X += test-sigchain\n TEST_PROGRAMS_NEED_X += test-subprocess\n TEST_PROGRAMS_NEED_X += test-svn-fe\n+TEST_PROGRAMS_NEED_X += test-sha1-cache\n \n TEST_PROGRAMS = $(patsubst %,%$X,$(TEST_PROGRAMS_NEED_X))\n \n@@ -606,6 +607,7 @@ LIB_H += run-command.h\n LIB_H += sequencer.h\n LIB_H += sha1-array.h\n LIB_H += sha1-lookup.h\n+LIB_H += sha1_cache.h\n LIB_H += sideband.h\n LIB_H += sigchain.h\n LIB_H += strbuf.h\n@@ -722,6 +724,7 @@ LIB_OBJS += setup.o\n LIB_OBJS += sequencer.o\n LIB_OBJS += sha1-array.o\n LIB_OBJS += sha1-lookup.o\n+LIB_OBJS += sha1_cache.o\n LIB_OBJS += sha1_file.o\n LIB_OBJS += sha1_name.o\n LIB_OBJS += shallow.o\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex dd1c5c9..67673ef 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -15,6 +15,7 @@ static const char index_pack_usage[] =\n \n struct object_entry {\n \tstruct pack_idx_entry idx;\n+\toff_t commit_offset;\n \tunsigned long size;\n \tunsigned int hdr_size;\n \tenum object_type type;\n@@ -63,6 +64,7 @@ static int nr_resolved_deltas;\n static int from_stdin;\n static int strict;\n static int verbose;\n+static int write_cache = 1;\n \n static struct progress *progress;\n \n@@ -75,6 +77,13 @@ static git_SHA_CTX input_ctx;\n static uint32_t input_crc32;\n static int input_fd, output_fd, pack_fd;\n \n+static int cache_fd;\n+static int cache_written;\n+static uint32_t cache_nr;\n+static char cache_filename[PATH_MAX];\n+static const char *cache_idxname;\n+static unsigned char cache_sha1[20];\n+\n static int mark_link(struct object *obj, int type, void *data)\n {\n \tif (!obj)\n@@ -682,6 +691,58 @@ static int compare_delta_entry(const void *a, const void *b)\n \t\t\t\t objects[delta_b->obj_no].type);\n }\n \n+static unsigned long parse_commit_date(const char *buf, const char *tail)\n+{\n+\tconst char *dateptr;\n+\n+\tif (buf + 6 >= tail)\n+\t\treturn 0;\n+\tif (memcmp(buf, \"author\", 6))\n+\t\treturn 0;\n+\twhile (buf < tail && *buf++ != '\\n')\n+\t\t/* nada */;\n+\tif (buf + 9 >= tail)\n+\t\treturn 0;\n+\tif (memcmp(buf, \"committer\", 9))\n+\t\treturn 0;\n+\twhile (buf < tail && *buf++ != '>')\n+\t\t/* nada */;\n+\tif (buf >= tail)\n+\t\treturn 0;\n+\tdateptr = buf;\n+\twhile (buf < tail && *buf++ != '\\n')\n+\t\t/* nada */;\n+\tif (buf >= tail)\n+\t\treturn 0;\n+\t/* dateptr < buf && buf[-1] == '\\n', so strtoul will stop at buf-1 */\n+\treturn strtoul(dateptr, NULL, 10);\n+}\n+\n+static void write_commit_sha1(struct object_entry *obj, const char *data)\n+{\n+\tunsigned char sha1[20];\n+\tif (!obj->commit_offset &&\n+\t !memcmp(data, \"tree \", 5) &&\n+\t !memcmp(data + 45, \"\\nparent \", 8) &&\n+\t memcmp(data + 45 + 48, \"\\nparent \", 8)) {\n+\t\tuint32_t date;\n+\t\tobj->commit_offset = cache_written;\n+\t\tcache_nr++;\n+\n+\t\tget_sha1_hex(data + 5, sha1);\n+\t\tcache_written += xwrite(cache_fd, sha1, 20);\n+\t\tget_sha1_hex(data + 5 + 48, sha1);\n+\t\tcache_written += xwrite(cache_fd, sha1, 20);\n+\t\tdate = parse_commit_date(data + 5 + 48 + 41, data + obj->size);\n+\t\tdate = htonl(date);\n+\t\tcache_written += xwrite(cache_fd, &date, 4);\n+\t}\n+#if 0\n+\thashclr(sha1);\n+\tcache_written += xwrite(cache_fd, sha1, 20);\n+#endif\n+}\n+\n /* Parse all objects and return the pack content SHA1 hash */\n static void parse_pack_objects(unsigned char *sha1)\n {\n@@ -707,8 +768,13 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\tnr_deltas++;\n \t\t\tdelta->obj_no = i;\n \t\t\tdelta++;\n-\t\t} else\n+\t\t} else {\n \t\t\tsha1_object(data, obj->size, obj->type, obj->idx.sha1);\n+\n+\t\t\t/* We assume that commits are never deltified */\n+\t\t\tif (write_cache && obj->real_type == OBJ_COMMIT)\n+\t\t\t\twrite_commit_sha1(obj, data);\n+\t\t}\n \t\tfree(data);\n \t\tdisplay_progress(progress, i+1);\n \t}\n@@ -919,6 +985,18 @@ static void final(const char *final_pack_name, const char *curr_pack_name,\n \t} else if (from_stdin)\n \t\tchmod(final_pack_name, 0444);\n \n+\tif (write_cache) {\n+\t\tsnprintf(name, sizeof(name), \"%s/pack/pack-%s.sha1\",\n+\t\t\t get_object_directory(), sha1_to_hex(sha1));\n+\t\tif (move_temp_to_file(cache_filename, name))\n+\t\t\tdie(\"cannot store commit cache file\");\n+\n+\t\tsnprintf(name, sizeof(name), \"%s/pack/pack-%s.sidx\",\n+\t\t\t get_object_directory(), sha1_to_hex(sha1));\n+\t\tif (move_temp_to_file(cache_idxname, name))\n+\t\t\tdie(\"cannot store commit cache file\");\n+\t}\n+\n \tif (final_index_name != curr_index_name) {\n \t\tif (!final_index_name) {\n \t\t\tsnprintf(name, sizeof(name), \"%s/pack/pack-%s.idx\",\n@@ -1120,6 +1198,8 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t\tkeep_msg = \"\";\n \t\t\t} else if (!prefixcmp(arg, \"--keep=\")) {\n \t\t\t\tkeep_msg = arg + 7;\n+\t\t\t} else if (!strcmp(arg, \"--no-cache\")) {\n+\t\t\t\twrite_cache = 0;\n \t\t\t} else if (!prefixcmp(arg, \"--pack_header=\")) {\n \t\t\t\tstruct pack_header *hdr;\n \t\t\t\tchar *c;\n@@ -1191,6 +1271,17 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tif (strict)\n \t\topts.flags |= WRITE_IDX_STRICT;\n \n+\tif (verify)\n+\t\twrite_cache = 0;\n+\tif (write_cache) {\n+\t\tunsigned char sha1[20];\n+\t\tcache_fd = odb_mkstemp(cache_filename,\n+\t\t\t\t sizeof(cache_filename),\n+\t\t\t\t \"pack/tmp_sha1_XXXXXX\");\n+\t\thashclr(sha1);\n+\t\tcache_written = xwrite(cache_fd, sha1, 20);\n+\t}\n+\n \tcurr_pack = open_pack_file(pack_name);\n \tparse_pack_header();\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n@@ -1243,6 +1334,26 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tcurr_index = write_idx_file(index_name, idx_objects, nr_objects, &opts, pack_sha1);\n \tfree(idx_objects);\n \n+\tif (write_cache) {\n+\t\tint nr;\n+\t\tstruct pack_idx_entry **idx;\n+\n+\t\tclose(cache_fd);\n+\n+\t\tidx = idx_objects = xmalloc((cache_nr) * sizeof(struct pack_idx_entry *));\n+\t\tfor (nr = i = 0; i < nr_objects; i++) {\n+\t\t\tif (objects[i].commit_offset) {\n+\t\t\t\tobjects[i].idx.offset = objects[i].commit_offset;\n+\t\t\t\t*idx++ = &objects[i].idx;\n+\t\t\t\tnr++;\n+\t\t\t}\n+\t\t}\n+\t\tassert(nr == cache_nr);\n+\t\topts.flags |= WRITE_IDX_SHA1_CACHE;\n+\t\tcache_idxname = write_idx_file(NULL, idx_objects, cache_nr, &opts, cache_sha1);\n+\t\tfree(idx_objects);\n+\t}\n+\n \tif (!verify)\n \t\tfinal(pack_name, curr_pack,\n \t\t index_name, curr_index,\ndiff --git a/cache.h b/cache.h\nindex 9bd8c2d..fd3953f 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -972,6 +972,14 @@ struct pack_window {\n \tunsigned int inuse_cnt;\n };\n \n+struct sha1_cache {\n+\tconst void *idx;\n+\tconst void *data;\n+\tsize_t idx_size;\n+\tsize_t data_size;\n+\tuint32_t nr;\n+};\n+\n extern struct packed_git {\n \tstruct packed_git *next;\n \tstruct pack_window *windows;\n@@ -984,6 +992,7 @@ extern struct packed_git {\n \tint index_version;\n \ttime_t mtime;\n \tint pack_fd;\n+\tstruct sha1_cache commit_cache;\n \tunsigned pack_local:1,\n \t\t pack_keep:1,\n \t\t do_not_close:1;\ndiff --git a/pack-write.c b/pack-write.c\nindex ca9e63b..6da977a 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -85,8 +85,11 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\tf = sha1fd(fd, index_name);\n \t}\n \n-\t/* if last object's offset is >= 2^31 we should use index V2 */\n-\tindex_version = need_large_offset(last_obj_offset, opts) ? 2 : opts->version;\n+\tif (opts->flags & WRITE_IDX_SHA1_CACHE)\n+\t\tindex_version = 2;\n+\telse\n+\t\t/* if last object's offset is >= 2^31 we should use index V2 */\n+\t\tindex_version = need_large_offset(last_obj_offset, opts) ? 2 : opts->version;\n \n \t/* index versions 2 and above need a header */\n \tif (index_version >= 2) {\n@@ -138,6 +141,9 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \tif (index_version >= 2) {\n \t\tunsigned int nr_large_offset = 0;\n \n+\t\tif (opts->flags & WRITE_IDX_SHA1_CACHE)\n+\t\t\tgoto skip_crc32;\n+\n \t\t/* write the crc32 table */\n \t\tlist = sorted_by_sha;\n \t\tfor (i = 0; i < nr_objects; i++) {\n@@ -146,6 +152,7 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\t\tsha1write(f, &crc32_val, 4);\n \t\t}\n \n+skip_crc32:\n \t\t/* write the 32-bit offset table */\n \t\tlist = sorted_by_sha;\n \t\tfor (i = 0; i < nr_objects; i++) {\ndiff --git a/pack.h b/pack.h\nindex aa6ee7d..f002b6a 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -40,6 +40,7 @@ struct pack_idx_option {\n \t/* flag bits */\n #define WRITE_IDX_VERIFY 01 /* verify only, do not write the idx file */\n #define WRITE_IDX_STRICT 02\n+#define WRITE_IDX_SHA1_CACHE 04\n \n \tuint32_t version;\n \tuint32_t off32_limit;\ndiff --git a/sha1_cache.c b/sha1_cache.c\nnew file mode 100644\nindex 0000000..3f244bb\n--- /dev/null\n+++ b/sha1_cache.c\n@@ -0,0 +1,161 @@\n+#include \"cache.h\"\n+#include \"pack.h\"\n+#include \"sha1_cache.h\"\n+\n+static int git_open_noatime(const char *name)\n+{\n+\tstatic int sha1_file_open_flag = O_NOATIME;\n+\n+\tfor (;;) {\n+\t\tint fd = open(name, O_RDONLY | sha1_file_open_flag);\n+\t\tif (fd >= 0)\n+\t\t\treturn fd;\n+\n+\t\t/* Might the failure be due to O_NOATIME? */\n+\t\tif (errno != ENOENT && sha1_file_open_flag) {\n+\t\t\tsha1_file_open_flag = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\treturn -1;\n+\t}\n+}\n+\n+/*\n+ * Commit cache format is basically pack index v2 except that:\n+ * - no crc32 table\n+ * - no large offset support\n+ * - offset table contains offset in _this_ file, in the commit\n+ * cache section\n+ * - the commit cache section follows offset table, each entry\n+ * consists of tree sha1, parent sha1 if any, and terminated\n+ * by null sha-1.\n+ */\n+\n+int open_sha1_cache(struct sha1_cache *cache,\n+\t\t const char *data_path, const char *idx_path)\n+{\n+\tvoid *idx_map, *data;\n+\tstruct pack_idx_header *hdr;\n+\tsize_t idx_size, data_size;\n+\tuint32_t nr, i, *index;\n+\tint fd = git_open_noatime(idx_path);\n+\tstruct stat st;\n+\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tif (fstat(fd, &st)) {\n+\t\tclose(fd);\n+\t\treturn -1;\n+\t}\n+\tidx_size = xsize_t(st.st_size);\n+\tif (idx_size < 4 * 256 + 20 + 20) {\n+\t\tclose(fd);\n+\t\treturn error(\"index file %s is too small\", idx_path);\n+\t}\n+\tidx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\n+\tfd = git_open_noatime(data_path);\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tif (fstat(fd, &st)) {\n+\t\tclose(fd);\n+\t\treturn -1;\n+\t}\n+\tdata_size = xsize_t(st.st_size);\n+\tdata = xmmap(NULL, data_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\n+\thdr = idx_map;\n+\tif (hdr->idx_signature != htonl(PACK_IDX_SIGNATURE))\n+\t\treturn error(\"not a commit cache file %s\", idx_path);\n+\tif (ntohl(hdr->idx_version) != 2)\n+\t\treturn error(\"wrong version %s %d\", idx_path, ntohl(hdr->idx_version));\n+\n+\tnr = 0;\n+\tindex = idx_map;\n+\tindex += 2; /* skip index header */\n+\tfor (i = 0; i < 256; i++) {\n+\t\tuint32_t n = ntohl(index[i]);\n+\t\tif (n < nr) {\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\treturn error(\"non-monotonic index %s\", idx_path);\n+\t\t}\n+\t\tnr = n;\n+\t}\n+\n+\tcache->idx = idx_map;\n+\tcache->idx_size = idx_size;\n+\tcache->nr = nr;\n+\tcache->data = data;\n+\tcache->data_size = data_size;\n+\treturn 0;\n+}\n+\n+static const void *object_offset(const struct sha1_cache *cache, uint32_t n)\n+{\n+\tconst unsigned char *index = cache->idx;\n+\tuint32_t off;\n+\tindex += 4 * 256;\n+\tindex += 8 + cache->nr * 20;\n+\toff = ntohl(*((uint32_t *)(index + 4 * n)));\n+\treturn (const char *)cache->data + off;\n+}\n+\n+const void *find_sha1_in_cache(const unsigned char *sha1)\n+{\n+\tconst uint32_t *level1_ofs;\n+\tconst unsigned char *index;\n+\tunsigned hi, lo, stride;\n+\n+\tstruct packed_git *p = find_sha1_pack(sha1, packed_git);\n+\tif (!p)\n+\t\treturn 0;\n+\n+\topen_pack_index(p);\n+\tif (!p->commit_cache.nr)\n+\t\treturn 0;\n+\n+\tlevel1_ofs = p->commit_cache.idx;\n+\tindex = p->commit_cache.idx;\n+\n+\t/* skip header */\n+\tlevel1_ofs += 2;\n+\tindex += 8;\n+\n+\t/* fanout table */\n+\tindex += 4 * 256;\n+\thi = ntohl(level1_ofs[*sha1]);\n+\tlo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\tstride = 20;\n+\n+\tdo {\n+\t\tunsigned mi = (lo + hi) / 2;\n+\t\tint cmp = hashcmp(index + mi * stride, sha1);\n+\n+\t\tif (!cmp)\n+\t\t\treturn object_offset(&p->commit_cache, mi);\n+\t\tif (cmp > 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi+1;\n+\t} while (lo < hi);\n+\treturn NULL;\n+}\n+\n+int has_commit_cache(const unsigned char *sha1,\n+\t\t unsigned char *tree,\n+\t\t unsigned char *parent,\n+\t\t unsigned long *date)\n+{\n+\tconst unsigned char *data;\n+\tdata = find_sha1_in_cache(sha1);\n+\tif (!data)\n+\t\treturn 0;\n+\n+\thashcpy(tree, data);\n+\thashcpy(parent, data + 20);\n+\t*date = ntohl(*((uint32_t*)(data + 40)));\n+\treturn 1;\n+}\ndiff --git a/sha1_cache.h b/sha1_cache.h\nnew file mode 100644\nindex 0000000..59823cf\n--- /dev/null\n+++ b/sha1_cache.h\n@@ -0,0 +1,6 @@\n+extern int open_sha1_cache(struct sha1_cache *cache,\n+\t\t\t const char *data_path, const char *idx_path);\n+extern const void *find_sha1_in_cache(const unsigned char *sha1);\n+extern int has_commit_cache(const unsigned char *sha1,\n+\t\t\t unsigned char *tree, unsigned char *parent,\n+\t\t\t unsigned long *date);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 88f2151..fc2f460 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -19,6 +19,7 @@\n #include \"pack-revindex.h\"\n #include \"sha1-lookup.h\"\n #include \"bulk-checkin.h\"\n+#include \"sha1_cache.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -578,14 +579,23 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n int open_pack_index(struct packed_git *p)\n {\n \tchar *idx_name;\n+\tint baselen = strlen(p->pack_name) - strlen(\".pack\");\n \tint ret;\n \n \tif (p->index_data)\n \t\treturn 0;\n \n \tidx_name = xstrdup(p->pack_name);\n-\tstrcpy(idx_name + strlen(idx_name) - strlen(\".pack\"), \".idx\");\n+\tstrcpy(idx_name + baselen, \".idx\");\n \tret = check_packed_git_idx(idx_name, p);\n+\tif (!ret) {\n+\t\tchar *cache_name;\n+\t\tcache_name = xstrdup(p->pack_name);\n+\t\tstrcpy(idx_name + baselen, \".sidx\");\n+\t\tstrcpy(cache_name + baselen, \".sha1\");\n+\t\topen_sha1_cache(&p->commit_cache, cache_name, idx_name);\n+\t\tfree(cache_name);\n+\t}\n \tfree(idx_name);\n \treturn ret;\n }\ndiff --git a/test-sha1-cache.c b/test-sha1-cache.c\nnew file mode 100644\nindex 0000000..7b7f32c\n--- /dev/null\n+++ b/test-sha1-cache.c\n@@ -0,0 +1,19 @@\n+#include \"cache.h\"\n+#include \"sha1_cache.h\"\n+\n+int main(int argc, char **argv)\n+{\n+\tunsigned char sha1[20];\n+\tunsigned char tree[20];\n+\tunsigned char parent[20];\n+\tunsigned long date;\n+\n+\tsetup_git_directory();\n+\tprepare_packed_git();\n+\tget_sha1_hex(argv[1], sha1);\n+\tif (!has_commit_cache(sha1, tree, parent, &date))\n+\t\treturn 1;\n+\tprintf(\"tree %s\\nparent %s\\ndate %ld\\n\",\n+\t sha1_to_hex(tree), sha1_to_hex(parent), date);\n+\treturn 0;\n+}\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"188389","messageId":"1333436109-16526-4-git-send-email-pclouds@gmail.com","threadId":"30104","inReplyTo":"53707c0a-3782-47a4-8a35-da7136ff4822@email.android.com","subject":"[PATCH 3/3] Add parse_commit_for_rev() to take advantage of sha1-cache","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-03T06:55:09Z","receivedAt":"2012-04-03T06:55:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This function tries to lookup sha1-cache. If it's found, struct commit\nis filled, no actual commit parsing is done. Otherwise parse_commit() is\ncalled.\n\nBecause sha1-cache only has information enough for rev machinery (tree,\nparent and date), this function is hardly suitable for general use.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n builtin/reflog.c | 2 +-\n commit.c | 36 +++++++++++++++++++++++++++++++-----\n commit.h | 1 +\n log-tree.c | 2 +-\n revision.c | 10 +++++-----\n upload-pack.c | 2 +-\n walker.c | 2 +-\n 7 files changed, 41 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/reflog.c b/builtin/reflog.c\nindex 062d7da..b15ff98 100644\n--- a/builtin/reflog.c\n+++ b/builtin/reflog.c\n@@ -240,7 +240,7 @@ static void mark_reachable(struct expire_reflog_cb *cb)\n \t\tfree(entry);\n \t\tif (commit->object.flags & REACHABLE)\n \t\t\tcontinue;\n-\t\tif (parse_commit(commit))\n+\t\tif (parse_commit_limited(commit))\n \t\t\tcontinue;\n \t\tcommit->object.flags |= REACHABLE;\n \t\tif (commit->date < expire_limit) {\ndiff --git a/commit.c b/commit.c\nindex 946ea70..aa32658 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 \"sha1_cache.h\"\n \n int save_commit_buffer = 1;\n \n@@ -28,7 +29,11 @@ static struct commit *check_commit(struct object *obj,\n struct commit *lookup_commit_reference_gently(const unsigned char *sha1,\n \t\t\t\t\t int quiet)\n {\n-\tstruct object *obj = deref_tag(parse_object(sha1), NULL, 0);\n+\tstruct object *obj;\n+\tstruct commit *c = lookup_commit(sha1);\n+\tif (c)\n+\t\treturn c;\n+\tobj = deref_tag(parse_object(sha1), NULL, 0);\n \n \tif (!obj)\n \t\treturn NULL;\n@@ -258,6 +263,12 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \n \tif (item->object.parsed)\n \t\treturn 0;\n+\n+\tif (item->parents) {\n+\t\tfree_commit_list(item->parents);\n+\t\titem->parents = NULL;\n+\t}\n+\n \titem->object.parsed = 1;\n \ttail += size;\n \tif (tail <= bufptr + 46 || memcmp(bufptr, \"tree \", 5) || bufptr[45] != '\\n')\n@@ -332,6 +343,21 @@ int parse_commit(struct commit *item)\n \treturn ret;\n }\n \n+int parse_commit_limited(struct commit *c)\n+{\n+\tunsigned char tree[20];\n+\tunsigned char parent[20];\n+\n+\tif (c->object.parsed || c->parents)\n+\t\treturn 0;\n+\tif (has_commit_cache(c->object.sha1, tree, parent, &c->date)) {\n+\t\tcommit_list_insert(lookup_commit(parent), &c->parents);\n+\t\tc->tree = lookup_tree(tree);\n+\t\treturn 0;\n+\t}\n+\treturn parse_commit(c);\n+}\n+\n int find_commit_subject(const char *commit_buffer, const char **subject)\n {\n \tconst char *eol;\n@@ -413,7 +439,7 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n-\t\tif (!parse_commit(commit) && !(commit->object.flags & mark)) {\n+\t\tif (!parse_commit_limited(commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n \t\t\tcommit_list_insert_by_date(commit, list);\n \t\t}\n@@ -605,10 +631,10 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \t\t\treturn commit_list_insert(one, &result);\n \t}\n \n-\tif (parse_commit(one))\n+\tif (parse_commit_limited(one))\n \t\treturn NULL;\n \tfor (i = 0; i < n; i++) {\n-\t\tif (parse_commit(twos[i]))\n+\t\tif (parse_commit_limited(twos[i]))\n \t\t\treturn NULL;\n \t}\n \n@@ -645,7 +671,7 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co\n \t\t\tparents = parents->next;\n \t\t\tif ((p->object.flags & flags) == flags)\n \t\t\t\tcontinue;\n-\t\t\tif (parse_commit(p))\n+\t\t\tif (parse_commit_limited(p))\n \t\t\t\treturn NULL;\n \t\t\tp->object.flags |= flags;\n \t\t\tcommit_list_insert_by_date(p, &list);\ndiff --git a/commit.h b/commit.h\nindex 154c0e3..113303b 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -47,6 +47,7 @@ struct commit *lookup_commit_or_die(const unsigned char *sha1, const char *ref_n\n \n int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size);\n int parse_commit(struct commit *item);\n+int parse_commit_limited(struct commit *item);\n \n /* Find beginning and length of commit subject. */\n int find_commit_subject(const char *commit_buffer, const char **subject);\ndiff --git a/log-tree.c b/log-tree.c\nindex cea8756..047ddec 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -643,7 +643,7 @@ void show_log(struct rev_info *opt)\n \t\tshow_mergetag(opt, commit);\n \t}\n \n-\tif (!commit->buffer)\n+\tif (!commit->buffer && parse_commit(commit) < 0)\n \t\treturn;\n \n \t/*\ndiff --git a/revision.c b/revision.c\nindex c97d834..4c229fd 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -273,7 +273,7 @@ static struct commit *handle_commit(struct rev_info *revs, struct object *object\n \t */\n \tif (object->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *)object;\n-\t\tif (parse_commit(commit) < 0)\n+\t\tif (parse_commit_limited(commit) < 0)\n \t\t\tdie(\"unable to parse commit %s\", name);\n \t\tif (flags & UNINTERESTING) {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n@@ -465,7 +465,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t */\n \t\tif (revs->first_parent_only && nth_parent++)\n \t\t\tbreak;\n-\t\tif (parse_commit(p) < 0)\n+\t\tif (parse_commit_limited(p) < 0)\n \t\t\tdie(\"cannot simplify commit %s (because of %s)\",\n \t\t\t sha1_to_hex(commit->object.sha1),\n \t\t\t sha1_to_hex(p->object.sha1));\n@@ -498,7 +498,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t\t\t * IOW, we pretend this parent is a\n \t\t\t\t * \"root\" commit.\n \t\t\t\t */\n-\t\t\t\tif (parse_commit(p) < 0)\n+\t\t\t\tif (parse_commit_limited(p) < 0)\n \t\t\t\t\tdie(\"cannot simplify commit %s (invalid %s)\",\n \t\t\t\t\t sha1_to_hex(commit->object.sha1),\n \t\t\t\t\t sha1_to_hex(p->object.sha1));\n@@ -561,7 +561,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,\n \t\t\tparent = parent->next;\n \t\t\tif (p)\n \t\t\t\tp->object.flags |= UNINTERESTING;\n-\t\t\tif (parse_commit(p) < 0)\n+\t\t\tif (parse_commit_limited(p) < 0)\n \t\t\t\tcontinue;\n \t\t\tif (p->parents)\n \t\t\t\tmark_parents_uninteresting(p);\n@@ -588,7 +588,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,\n \tfor (parent = commit->parents; parent; parent = parent->next) {\n \t\tstruct commit *p = parent->item;\n \n-\t\tif (parse_commit(p) < 0)\n+\t\tif (parse_commit_limited(p) < 0)\n \t\t\treturn -1;\n \t\tif (revs->show_source && !p->util)\n \t\t\tp->util = commit->util;\ndiff --git a/upload-pack.c b/upload-pack.c\nindex bb08e2e..d30e604 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -694,7 +694,7 @@ static void receive_needs(void)\n \t\t\t\t/* make sure the real parents are parsed */\n \t\t\t\tunregister_shallow(object->sha1);\n \t\t\t\tobject->parsed = 0;\n-\t\t\t\tif (parse_commit((struct commit *)object))\n+\t\t\t\tif (parse_commit_limited((struct commit *)object))\n \t\t\t\t\tdie(\"invalid commit\");\n \t\t\t\tparents = ((struct commit *)object)->parents;\n \t\t\t\twhile (parents) {\ndiff --git a/walker.c b/walker.c\nindex be389dc..7b818f5 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -71,7 +71,7 @@ static struct commit_list *complete = NULL;\n \n static int process_commit(struct walker *walker, struct commit *commit)\n {\n-\tif (parse_commit(commit))\n+\tif (parse_commit_limited(commit))\n \t\treturn -1;\n \n \twhile (complete && complete->item->date >= commit->date) {\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"188394","messageId":"20120403084035.GA14483@sigill.intra.peff.net","threadId":"30104","inReplyTo":"4F7A2E0D.9030402@lsrfire.ath.cx","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-03T08:40:36Z","receivedAt":"2012-04-03T08:40:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 03, 2012 at 12:54:05AM +0200, René Scharfe wrote:\n\n> > 1. Is it worth the complexity of the linked-list mergesort? I was\n> > planning to just build an array, qsort it, and then put the results\n> > into a linked list. The patch for that is below for reference.\n>\n> Using a temporary array here is just sad, because linked lists are\n> already sortable, albeit not with qsort(). Your measurements seem to\n> answer my question regarding the overhead of the callback functions\n> of mergesort(), in any case. :)\n\nI agree it is a little gross. The main impetus was shortened code, since\nwe get qsort for free. However, after reading Simon's page that you\nreferenced and reading your code carefully, I'm beginning to think that\nthe linked-list mergesort is pretty damn cool (I hadn't seen it before).\nAfter all, mergesort without the auxiliary space should be better than\nqsort.\n\nSo let's go with your patches.\n\n> [...]\n> It looks nice and to the point, but breaks several tests for me\n> (t3508, t4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401).\n> Not sure why.\n\nI probably screwed up the reversal or something. My patch was a quick \"I\nwas thinking of this direction\" and I didn't actually test it well.\n\n> > So I wonder if in the long term we would benefit from a better data\n> > structure, which would make these problems just go away. That being\n> > said, there is a lot of code to be updated with such a change, so\n> > even if we do want to do that eventually, a quick fix like this is\n> > probably still a good thing.\n> \n> Using a more appropriate data structure sounds good in general. How\n> about using a skip list? (Or perhaps I need to lay the hammer of\n> linked lists to rest for a while to stop seeing all data structures\n> as the proverbial nails, or something. ;-)\n\nActually, I think a skip list would make a lot of sense, as it mostly\nretains the linked-list properties. When I tried converting it to a\nheap-based priority queue, I seem to recall that there were some spots\nthat wanted to splice the commit list (among other things). Although I'm\nnot sure how splicing works in a skip list; I guess you'd have to do a\nlist merge.\n\n-Peff\n"},{"id":"188398","messageId":"20120403091937.GB14483@sigill.intra.peff.net","threadId":"30104","inReplyTo":"20120403084035.GA14483@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-03T09:19:37Z","receivedAt":"2012-04-03T09:19:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 03, 2012 at 04:40:36AM -0400, Jeff King wrote:\n\n> > It looks nice and to the point, but breaks several tests for me\n> > (t3508, t4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401).\n> > Not sure why.\n> \n> I probably screwed up the reversal or something. My patch was a quick \"I\n> was thinking of this direction\" and I didn't actually test it well.\n\nUgh. Not that it matters now, but the patch below fixes my version.\n\nNot only did I manage to screw up the reversal, but I also messed up the\ncalling convention for qsort. So the moral is that we should take 100\nlines of your tested code over 5 lines of my junk. ;)\n\nAs a fun fact, I tried fixing the reversal by sorting low to high, and\nthen just doing the commit_list_insert calls in that order (since it\nprepends). However, that loses the stability of the sort. It turns out\nthat t4207 fails in this case (though not reliably, since your commits\nmight or might not be made in the same second).\n\nI had already checked your mergesort() implementation to be sure that it\nis stable (and it is). But it's nice to know that t4207 also backs up\nthe analysis. :)\n\n-Peff\n\n---\ndiff --git a/revision.c b/revision.c\nindex 22c26d0..15bf30a 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2064,11 +2064,11 @@ static void set_children(struct rev_info *revs)\n \n static int commit_compare_by_date(const void *va, const void *vb)\n {\n-\tconst struct commit *a = va;\n-\tconst struct commit *b = vb;\n-\tif (a->date < b->date)\n+\tconst struct commit *a = *(const struct commit **)va;\n+\tconst struct commit *b = *(const struct commit **)vb;\n+\tif (a->date > b->date)\n \t\treturn -1;\n-\tif (b->date < a->date)\n+\tif (b->date > a->date)\n \t\treturn 1;\n \treturn 0;\n }\n"},{"id":"188560","messageId":"CACsJy8BbNEJBn5i0Rntv21d8qvhPwkrNBdaj+sGh2W-aN9jYGg@mail.gmail.com","threadId":"30104","inReplyTo":"CACsJy8DGaFg=oEwLWWo33cJa=SDuuZshW4=cZpifCWLp5gGcTA@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-05T13:02:15Z","receivedAt":"2012-04-05T13:02:15Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 3, 2012 at 10:49 AM, Nguyen Thai Ngoc Duy wrote:\n>> Has anyone looked seriously at a new index format that stores the\n>> redundant information in a more easily accessible way? It would increase\n>> our disk usage, but for something like linux-2.6, only by 10MB per\n>> 32-bit word. On most of my systems I would gladly spare some extra RAM\n>> for the disk cache if it meant I could avoid inflating a bunch of\n>> objects. And this could easily be made optional for systems that don't\n>> want to make the tradeoff (if it's not there, you fall back to the\n>> current procedure; we could even store the data in a separate file to\n>> retain indexv2 compatibility).\n>>\n>> So it's sort-of a cache, in that it's redundant with the actual data.\n>> But staleness and writing issues are a lot simpler, since it only gets\n>> updated when we index the pack (and the pack index in general is a\n>> similar concept; we are \"caching\" the location of the object in the\n>> packfile, rather than doing a linear search to look it up each time).\n>\n> I think I have something like that, (generate a machine-friendly\n> commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's\n> separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx\n> files. It does improve rev-list time, but I'd rather wait for packv4,\n> or at least be sure that packv4 will not come anytime soon, before\n> pushing the cache route.\n\nWhen I looked at commit cache for rev-list, I tried to cache trees too\nbut the result cache was too big. I managed to shrink the tree cache\ndown and measured the performance gain. Sorry no code here because\nit's ugly, just numbers, but you can look at the cache generation code\nat [1]\n\nOn linux-2.6.git, one 521MB pack, it generates a 356MB cache and a\n30MB index companion. Though if you are willing to pay extra 5 seconds\nfor decompressing, then the cache can go down to 94MB. We can cut\nnearly half \"rev-list --objects --all\" time with this cache\n(uncompressed cache):\n\n$ time ~/w/git/git rev-list --objects --all --quiet writes:\n\n> This adds a generic bottom-up mergesort implementation for singly linked\n> lists. It was inspired by Simon Tatham's webpage on the topic[1], but\n> not so much by his implementation -- for no good reason, really, just a\n> case of NIH.\n>\n> [1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html\n>\n> Signed-off-by: Rene Scharfe \n> +void *mergesort(void *list,\n> +\t\tvoid *(*get_next_fn)(const void *),\n> +\t\tvoid (*set_next_fn)(void *, void *),\n> +\t\tint (*compare_fn)(const void *, const void *))\n> +{\n> +\tunsigned long l;\n> +\n> +\tif (!list)\n> +\t\treturn NULL;\n> +\tfor (l = 1; ; l *= 2) {\n> +\t\tvoid *curr;\n> +\t\tstruct mergesort_sublist p, q;\n> +\n> +\t\tp.ptr = list;\n> +\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n> +\t\tif (!q.ptr)\n> +\t\t\tbreak;\n> +\t\tp.len = q.len = l;\n> +\n> +\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n> +\t\t\tlist = curr = pop_item(&q, get_next_fn);\n> +\t\telse\n> +\t\t\tlist = curr = pop_item(&p, get_next_fn);\n> +\n> +\t\twhile (p.ptr) {\n> +\t\t\twhile (p.len || q.len) {\n> +\t\t\t\tvoid *prev = curr;\n> +\n> +\t\t\t\tif (!p.len)\n> +\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n> +\t\t\t\telse if (!q.len)\n> +\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n> +\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n> +\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n> +\t\t\t\telse\n> +\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n> +\t\t\t\tset_next_fn(prev, curr);\n> +\t\t\t}\n> +\t\t\tp.ptr = q.ptr;\n> +\t\t\tp.len = l;\n> +\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n> +\t\t\tq.len = q.ptr ? l : 0;\n> +\n> +\t\t}\n> +\t\tset_next_fn(curr, NULL);\n> +\t}\n> +\treturn list;\n> +}\n\nAfter seeing \"I wrote it myself due to NIH\", it strikes me a bit odd that\nyou still used \"start from bunch of singleton sublist, elongating twice\nper round as we go\" structure from the original.\n\nI wonder if it would be an improvement if you structured the loop so that:\n\n (1) the first sublist 'p' grabs as many elements in the ascending order\n as you find;\n\n (2) the second sublist 'q' begins at the end of the first sublist and\n grabs as many elements in the ascending order;\n\n (3) 'p' and 'q' are merge-sorted into the result list;\n\n (4) if your two sublists did not cover \"list\" in its entirety, process\n the remainder (i.e. where the second sublist stopped because of an\n unordered element) by going back to step (1); and\n\n (5) if you did not need to jump back to step (1) from step (4), then you\n had only two sublists (or less), so the result is sorted. Otherwise,\n the result now has fewer ascending sublists than the original, so go\n back to (1) and iterate.\n\nIf the input is in a random order, this may end up doing the same number\nof iterations as the original, but if the input is mostly sorted, wouldn't\nit allow us to take advantage of the fact by starting with a longer\nsublist in the earlier rounds?\n"},{"id":"188679","messageId":"CAJo=hJusnnaMomQzb90ed9=HHpamVTktN0Qrw8MsaY+addF=rw@mail.gmail.com","threadId":"30104","inReplyTo":"CACsJy8BbNEJBn5i0Rntv21d8qvhPwkrNBdaj+sGh2W-aN9jYGg@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-06T19:21:09Z","receivedAt":"2012-04-06T19:21:09Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Apr 5, 2012 at 06:02, Nguyen Thai Ngoc Duy wrote:\n> On linux-2.6.git, one 521MB pack, it generates a 356MB cache and a\n> 30MB index companion. Though if you are willing to pay extra 5 seconds\n> for decompressing, then the cache can go down to 94MB. We can cut\n> nearly half \"rev-list --objects --all\" time with this cache\n> (uncompressed cache):\n>\n> $ time ~/w/git/git rev-list --objects --all --quiet real    2m31.310s\n> user    2m28.735s\n> sys     0m1.604s\n>\n> $ time TREE_CACHE=cache ~/w/git/git rev-list --objects --all --quiet real    1m6.810s\n> user    1m6.091s\n> sys     0m0.708s\n>\n>  $ time ~/w/git/git rev-list --all --quiet real    0m14.261s  # should be cut down to one third with commit cache\n> user    0m14.088s\n> sys     0m0.171s\n>\n> Not really good. \"rev-list --objects\"'s taking less than 30s would be\n> nicer. lookup_object() is on top from 'perf' report with cache on. Not\n> sure what to do with it.\n\n\nMy officemate Colby and I came up with a better solution a few weeks\nago, but haven't really had a chance to discuss it in on the list. I\nguess I should try to do that now. Like anything else, we went into\nthis work with some assumptions.\n\nThere are two operations we really wanted to improve the performance\nof, `git rev-list --objects` for the two commonly used cases from\npack-objects, notably `rev-list --objects $WANT` and `rev-list\n--objects $WANT --not $HAVE`. That is, clone and incrementally\nfetching something when you have a common ancestor. I'm currently\nignoring shallow clone in this work as it tends to be a bit less\nexpensive on the object enumeration part.\n\nWorking from the linux repository, with roughly 2.2M objects, we can\nassume the vast majority of these objects are stored in a pack file.\nIf we further assume these are mostly in a single pack file, we can\neasily assign every packed object a unique integer. We do this by\nassigning the N-th object in the pack integer N. You can already do\nthis by taking the pack index and computing the reverse index, sorted\nby offset in pack. Finding the integer value for any SHA-1 is then a\nmatter of locating its offset in the normal index, and locating the\nposition of it in the reverse index... a O(2 log N) operation.\n\nWith all of the packed objects named by an integer [0, N) we can build\na series of bitmaps representing reachability. Given a commit, its\nbitmap has every bit set for every object that `git rev-list --objects\n$COMMIT_SHA1` would output. If the pack is built from a single branch\n(e.g. a repository with no tags and only a master branch), that tip\ncommit would have every bit set in its bitmap, as all objects in the\npack are contained in the bitmap.\n\nA bitmap of 2.2M objects is 2.2M bits in size, and is roughly 275 KiB\nworth of data. But we can compress the bitmap using word aligned\nhybrid compression (WAH) [1] and have it drop to about 1 KiB in size.\n\nPacks have fairly good locality given that they are roughly ordered by\ntime. The further back in history you go, the bitmap for any given\ncommit will start to contain more zeros than ones, and the zeros will\nbe roughly consecutive as the regions of the pack are less full, so\nthe bitmap still compresses well.\n\nWe actually did an experiment computing the bitmaps for all of the\ncommits in the kernel repository, IIRC the largest ones were coming in\naround 40 KiB in the middle of history, and then shrinking smaller\nagain as you got further back in history.\n\nAssuming all bitmaps are around 20 KiB average size (most were in this\nrange), storing bitmaps for every commit costs around 4.2G. Not worth\nit. However.\n\nIf we take the kernel history in rev-list and pick two commits that\nare roughly ~10,000 commits apart from one another, JGit can compute\nthe rev-list --objects between these two commits in about 120\nmilliseconds (git-core should be faster, or at least comparable).\n\nGiven that, we don't have to store every bitmap. Instead you store the\nbitmaps about every 10,000 commits. Now your bitmap storage is closer\nto 1 MiB in size for the entire pack. This can be easily appended to\nthe end of the pack-*.idx file as a new section when the pack is\nbuilt. The packer can construct the necessary data during packing with\nwhat I suspect relatively little additional cost to what its already\ndoing, as most of the required data is in memory or being touched\nanyway.\n\nObviously that 10k distance between bitmaps is tuneable, and could be\na config variable. We could even make it a % of the pack size, with\nGit automatically selecting equidistant points between commits in the\nhistory such that the compressed bitmaps fit within the target\npercentage. Repository owners could set this to e.g. 10% and let the\nmachine do the rest of the work. (10% of a 560M pack might be ~56M\nworth of bitmaps or every ~2800 commits.)\n\n\nComputing `rev-list objects $WANT` is just a matter of OR-ing together\nthe bitmaps that correspond to what the client asked for. WAH\ncompressed bitmaps can apply OR without decompressing, in ~5ms time\nrange, rather than 14.2s... or 90s. :-)\n\nComputing `rev-list objects $WANT --not $HAVE` is likewise an OR of\nthe $WANT and $HAVE groups, then a negation, which again can be done\ndirectly on the compressed bitmaps.\n\nWhen the client uses a $WANT or $HAVE that we don't have a direct\nbitmap for, build the bitmap on the fly by running `rev-list $WANT`\n(or $HAVE) until the revision traversal produces a commit that does\nhave a bitmap. Extend the bitmap with the additional objects that\naren't in the pack by assigning them new temporary integers that are\nlarger than the number of objects in the pack. Finish the operation\nwith the bitmaps.\n\n\nTo output the pack we don't even need to build up a huge list of\nstruct packed_obj in memory. Instead we iterate the set bits in the\nbitmap, working off the compressed format. When an object has its bit\nset, it needs to be sent to the client. The object can be found in the\npack by looking at the N-th position of the reverse index to get its\noffset, or the N-th position in the reverse index to get its SHA-1.\nCopying slices of pack data should be a pretty simple task. The bits\nare already sorted by preferred pack order, since they came from a\npack, so the writer still produces a good stream. Obviously if you\nwant to change the ordering, or the deltas, aka repack -f, we need to\navoid using the bitmap ordering here.\n\nThere is some complication relating to swapping out delta compressed\nform for non-delta compressed form if you cannot prove the peer has\nthe delta base that is currently being used. But with the bitmaps we\nactually have a much more accurate representation of what the client\n*actually* has. Instead of being limited to the common ancestor\nnegotiation point's trees, the $HAVE bitmap covers *every single\nobject to the beginning of time*. This significantly increases the\nnumber of candidates available for delta reuse, because there are\nbetter chances that the base we use is already available to the\nclient.\n\nThe $HAVE bitmap covering a much bigger section of history also means\nwe transmit fewer objects, which makes for a faster transfer for the\nclient. This often happens with cherry-picks or reverts across the\ncommon ancestor cut point in the graph, where the peer already has the\nrelevant object(s) but we can't prove it from the limited section of\nhistory we look at today. The $HAVE bitmap is much more comprehensive\npicture of the client's state, making for a smaller transfer.\n\n\nHaving multiple packs is common, and does complicate this algorithm.\nThere are known ways to combine different bitmap indexes together to\ncreate a single larger bitmap, mostly by applying a unique \"base\nprefix\" to each bitmap's values. Its very common in the full text\nsearch community to do this when incrementally updating a full text\nindex.\n\nA process can assign each pack it observes a unique base prefix, and\nthen join together bitmaps across those packs to get a more complete\npicture. Its not entirely that simple though because a commit in a\nnewer pack probably still references a parent in an older pack, and so\nthat commit in the newer pack doesn't have a complete bitmap.\n\nOne way out of this is to only produce bitmaps on a full GC, where the\nentire repository is rewritten. If every 10k commits worth of history\ncosts about 100ms additional processing time to do object enumeration,\nwe only really have to do a major repack about every 100k commits when\nprocessing is starting to come close to 1.2 seconds of CPU time. The\nlinux history has done ~220k commits in ~5 years, or 44k commits/year.\nAsking a repository to do a full GC at least once per year so that\nthere only needs to be one set of bitmaps might be acceptable. :-)\n\n\nThe other operation that matters is `git rev-list --objects $NEW --not\n--all`, which is done for a reachability test during receive of data\ninto a repository from the network (in either fetch or receive-pack).\n\nIf we know a pack was created locally by the git gc or git repack\ncommand, we only need to run `git rev-list --objects $NEW` and stop\ntraversal for a section of the graph when we find a commit or object\nthat already exists in a locally created pack index. In other words we\ndon't use the \"--not --all\" bit and we instead we look at each object\ncoming out of the traversal to see if it is in a locally created pack,\nif it exists in a pack's index we mark it UNINTERESTING and continue\nthe traversal. This would eliminate the need to parse and load --all\ninto the priority queue, instead we parse and insert only the commits\nthat are directly connected to the part of the $NEW graph we were just\ngiven, and we only do that so we can stop traversal at the common\nancestor point(s) and avoid walking back to the root. It probably\nisn't even necessary to parse or insert these commits, we just have to\ntag them UNINTERESTING and avoid putting them into the priority queue.\n\nHowever not all locally stored packs were locally created. Some are\ncreated from the network (e.g. when the number of objects is > 100).\nSo for this optimization to work we need an additional chunk of\nmetadata written with the pack to say \"this pack was made by git gc /\ngit repack and is trustworthy\". This could be a new \".local\" file\nalongside .pack/.idx, or we could do a minor change to the .idx format\nto allow a \"source bit\" to be written to say where the pack came from\n(network or fast-import vs. local gc).\n\n\nI think a lot of the other users of the commit graph / object graph\nare just looking at small enough slices of history that walking\nthrough 10k commits in 120 ms is acceptable response time to the human\nrunning the command. So its not really pack v4. It only needs a few\nMiB additional space on top of existing pack data, and is easily\nstored onto the end of the local index file. But it gets us a lot of\nimprovement in some pretty tough areas.\n\n\nI don't have any code to share, because we haven't written it yet. But\nthis should shave off some of the big corners within Git, with\nrelatively little additional disk usage.\n\n\n[1] \"Sorting improves word-aligned bitmap indexes\", Daniel Lemire,\nOwen Kaser, Kamel Aouiche\n http://arxiv.org/abs/0901.3751\n"},{"id":"188715","messageId":"CACsJy8Bj6jHypqk5OEuCmRm4YVf4ttnv5LL=9jukWDyY6H__4Q@mail.gmail.com","threadId":"30104","inReplyTo":"CAJo=hJusnnaMomQzb90ed9=HHpamVTktN0Qrw8MsaY+addF=rw@mail.gmail.com","subject":"Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-07T04:20:59Z","receivedAt":"2012-04-07T04:20:59Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Hi,\n\nVery insightful write-up. I'll need more time to read through again,\njust some initial opinions.\n\nOn Sat, Apr 7, 2012 at 2:21 AM, Shawn Pearce wrote:\n> My officemate Colby and I came up with a better solution a few weeks\n> ago, but haven't really had a chance to discuss it in on the list. I\n> guess I should try to do that now. Like anything else, we went into\n> this work with some assumptions.\n>\n> There are two operations we really wanted to improve the performance\n> of, `git rev-list --objects` for the two commonly used cases from\n> pack-objects, notably `rev-list --objects $WANT` and `rev-list\n> --objects $WANT --not $HAVE`. That is, clone and incrementally\n> fetching something when you have a common ancestor. I'm currently\n> ignoring shallow clone in this work as it tends to be a bit less\n> expensive on the object enumeration part.\n>\n> Working from the linux repository, with roughly 2.2M objects, we can\n> assume the vast majority of these objects are stored in a pack file.\n> If we further assume these are mostly in a single pack file, we can\n> easily assign every packed object a unique integer. We do this by\n> assigning the N-th object in the pack integer N. You can already do\n> this by taking the pack index and computing the reverse index, sorted\n> by offset in pack. Finding the integer value for any SHA-1 is then a\n> matter of locating its offset in the normal index, and locating the\n> position of it in the reverse index... a O(2 log N) operation.\n>\n> With all of the packed objects named by an integer [0, N) we can build\n> a series of bitmaps representing reachability. Given a commit, its\n> bitmap has every bit set for every object that `git rev-list --objects\n> $COMMIT_SHA1` would output. If the pack is built from a single branch\n> (e.g. a repository with no tags and only a master branch), that tip\n> commit would have every bit set in its bitmap, as all objects in the\n> pack are contained in the bitmap.\n>\n> ...\n>\n> Having multiple packs is common, and does complicate this algorithm.\n> There are known ways to combine different bitmap indexes together to\n> create a single larger bitmap, mostly by applying a unique \"base\n> prefix\" to each bitmap's values. Its very common in the full text\n> search community to do this when incrementally updating a full text\n> index.\n\nCommon repos usually have a big pack as a result of clone and several\nsmaller packs. How about we create the bitmap for the largest pack\nonly and fall back to normal rev walking for the rest? We need to deal\nwith loose objects anyway. I wonder if we could also mark the boundary\nobjects for a given commits (i.e. another bitmap) so we can start\nwalking from there to get to other packs and loose objects.\n\nThe second bitmap hopefully compresses well. Not sure how it\ncomplicates the want-have bitmap operations you describe above though.\n\n> A process can assign each pack it observes a unique base prefix, and\n> then join together bitmaps across those packs to get a more complete\n> picture. Its not entirely that simple though because a commit in a\n> newer pack probably still references a parent in an older pack, and so\n> that commit in the newer pack doesn't have a complete bitmap.\n>\n> One way out of this is to only produce bitmaps on a full GC, where the\n> entire repository is rewritten. If every 10k commits worth of history\n> costs about 100ms additional processing time to do object enumeration,\n> we only really have to do a major repack about every 100k commits when\n> processing is starting to come close to 1.2 seconds of CPU time. The\n> linux history has done ~220k commits in ~5 years, or 44k commits/year.\n> Asking a repository to do a full GC at least once per year so that\n> there only needs to be one set of bitmaps might be acceptable. :-)\n\nI'd be happy for it to run, even once a month, as long as it is not\nrun automatically, unexpectedly and stops me from doing whatever I'm\ndoing, like \"gc --auto\".\n-- \nDuy\n"},{"id":"188785","messageId":"4F81F5E6.2070609@lsrfire.ath.cx","threadId":"30104","inReplyTo":"7vpqbm56pf.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/3] add mergesort() for linked lists","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-04-08T20:32:38Z","receivedAt":"2012-04-08T20:32:38Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.2012 21:17, schrieb Junio C Hamano:\n> After seeing \"I wrote it myself due to NIH\", it strikes me a bit odd that\n> you still used \"start from bunch of singleton sublist, elongating twice\n> per round as we go\" structure from the original.\n\nIt's just becasue the dumb bottom-up approach is the most simple way to\nimplement merge sort.\n\n> I wonder if it would be an improvement if you structured the loop so that:\n> \n> (1) the first sublist 'p' grabs as many elements in the ascending order\n> as you find;\n> \n> (2) the second sublist 'q' begins at the end of the first sublist and\n> grabs as many elements in the ascending order;\n> \n> (3) 'p' and 'q' are merge-sorted into the result list;\n> \n> (4) if your two sublists did not cover \"list\" in its entirety, process\n> the remainder (i.e. where the second sublist stopped because of an\n> unordered element) by going back to step (1); and\n> \n> (5) if you did not need to jump back to step (1) from step (4), then you\n> had only two sublists (or less), so the result is sorted. Otherwise,\n> the result now has fewer ascending sublists than the original, so go\n> back to (1) and iterate.\n> \n> If the input is in a random order, this may end up doing the same number\n> of iterations as the original, but if the input is mostly sorted, wouldn't\n> it allow us to take advantage of the fact by starting with a longer\n> sublist in the earlier rounds?\n\nThis optimization speeds up the pre-sorted case but slows down the case of\na reversed pre-sorted list because we have to determine the length of the\nsublists each time, while the dumb implementation already knows it. I\ndidn't measure a significant difference for Jeff's test case. Here's my\nattempt at an implementation, for reference.\n\n---\n mergesort.c | 61 +++++++++++++++++++++++++++++++++++++++--------------------\n 1 file changed, 41 insertions(+), 20 deletions(-)\n\ndiff --git a/mergesort.c b/mergesort.c\nindex c0f1874..3a61b9b 100644\n--- a/mergesort.c\n+++ b/mergesort.c\n@@ -8,12 +8,37 @@ struct mergesort_sublist {\n \tunsigned long len;\n };\n \n-static void *get_nth_next(void *list, unsigned long n,\n-\t\t\t void *(*get_next_fn)(const void *))\n+static unsigned long run_length(const void *list,\n+\t\t\t\tstruct mergesort_sublist *next_list,\n+\t\t\t\tvoid *(*get_next_fn)(const void *),\n+\t\t\t\tint (*compare_fn)(const void *, const void *))\n {\n-\twhile (n-- && list)\n-\t\tlist = get_next_fn(list);\n-\treturn list;\n+\tunsigned long len = 1;\n+\n+\tif (!list)\n+\t\treturn 0;\n+\tfor (;;) {\n+\t\tvoid *next = get_next_fn(list);\n+\n+\t\tif (!next || compare_fn(list, next) > 0) {\n+\t\t\tif (next_list)\n+\t\t\t\tnext_list->ptr = next;\n+\t\t\tbreak;\n+\t\t}\n+\t\tlist = next;\n+\t\tlen++;\n+\t}\n+\treturn len;\n+}\n+\n+static void set_next_pair(struct mergesort_sublist *p,\n+\t\t\t struct mergesort_sublist *q, void *list,\n+\t\t\t void *(*get_next_fn)(const void *),\n+\t\t\t int (*compare_fn)(const void *, const void *))\n+{\n+\tp->ptr = list;\n+\tp->len = run_length(p->ptr, q, get_next_fn, compare_fn);\n+\tq->len = q->ptr ? run_length(q->ptr, NULL, get_next_fn, compare_fn) : 0;\n }\n \n static void *pop_item(struct mergesort_sublist *l,\n@@ -30,24 +55,16 @@ void *mergesort(void *list,\n \t\tvoid (*set_next_fn)(void *, void *),\n \t\tint (*compare_fn)(const void *, const void *))\n {\n-\tunsigned long l;\n-\n \tif (!list)\n \t\treturn NULL;\n-\tfor (l = 1; ; l *= 2) {\n+\tfor (;;) {\n \t\tvoid *curr;\n \t\tstruct mergesort_sublist p, q;\n \n-\t\tp.ptr = list;\n-\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n+\t\tset_next_pair(&p, &q, list, get_next_fn, compare_fn);\n \t\tif (!q.ptr)\n \t\t\tbreak;\n-\t\tp.len = q.len = l;\n-\n-\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n-\t\t\tlist = curr = pop_item(&q, get_next_fn);\n-\t\telse\n-\t\t\tlist = curr = pop_item(&p, get_next_fn);\n+\t\tlist = curr = pop_item(&q, get_next_fn);\n \n \t\twhile (p.ptr) {\n \t\t\twhile (p.len || q.len) {\n@@ -63,10 +80,14 @@ void *mergesort(void *list,\n \t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n \t\t\t\tset_next_fn(prev, curr);\n \t\t\t}\n-\t\t\tp.ptr = q.ptr;\n-\t\t\tp.len = l;\n-\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n-\t\t\tq.len = q.ptr ? l : 0;\n+\n+\t\t\tset_next_pair(&p, &q, q.ptr, get_next_fn, compare_fn);\n+\t\t\tif (q.ptr) {\n+\t\t\t\tvoid *prev = curr;\n+\n+\t\t\t\tcurr = pop_item(&q, get_next_fn);\n+\t\t\t\tset_next_fn(prev, curr);\n+\t\t\t}\n \n \t\t}\n \t\tset_next_fn(curr, NULL);\n-- \n1.7.10\n"},{"id":"188802","messageId":"7vk41owylh.fsf@alter.siamese.dyndns.org","threadId":"30104","inReplyTo":"4F81F5E6.2070609@lsrfire.ath.cx","subject":"Re: [PATCH 1/3] add mergesort() for linked lists","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-09T18:26:34Z","receivedAt":"2012-04-09T18:26:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Am 05.04.2012 21:17, schrieb Junio C Hamano:\n>> After seeing \"I wrote it myself due to NIH\", it strikes me a bit odd that\n>> you still used \"start from bunch of singleton sublist, elongating twice\n>> per round as we go\" structure from the original.\n>\n> It's just becasue the dumb bottom-up approach is the most simple way to\n> implement merge sort.\n> ...\n> This optimization speeds up the pre-sorted case but slows down the case of\n> a reversed pre-sorted list because we have to determine the length of the\n> sublists each time,...\n\nAh, I somehow missed that point. Thanks.\n"},{"id":"188931","messageId":"4F85226A.7050709@gmail.com","threadId":"30104","inReplyTo":"4F7780C3.2050408@lsrfire.ath.cx","subject":"Re: [PATCH 1/3] add mergesort() for linked lists","fromName":"Stephen Boyd","fromEmail":"bebarino@gmail.com","sentAt":"2012-04-11T06:19:22Z","receivedAt":"2012-04-11T06:19:22Z","isPatch":true,"sender":{"key":"bebarino@gmail.com","avatar":"https://avatars.githubusercontent.com/u/38832?v=4"},"body":"On 03/31/2012 03:10 PM, René Scharfe wrote:\n> diff --git a/mergesort.c b/mergesort.c\n> new file mode 100644\n> index 0000000..c0f1874\n> --- /dev/null\n> +++ b/mergesort.c\n> @@ -0,0 +1,75 @@\n> +#include \"cache.h\"\n> +#include \"mergesort.h\"\n> +\n> +#include \"commit.h\"\n\nThis is an unnecessary include, right?\n\ndiff --git a/mergesort.c b/mergesort.c\nindex c0f1874..d084c60 100644\n--- a/mergesort.c\n+++ b/mergesort.c\n@@ -1,8 +1,6 @@\n #include \"cache.h\"\n #include \"mergesort.h\"\n\n-#include \"commit.h\"\n-\n struct mergesort_sublist {\n void *ptr;\n unsigned long len;\n"},{"id":"188989","messageId":"7vlim2md4r.fsf@alter.siamese.dyndns.org","threadId":"30104","inReplyTo":"4F85226A.7050709@gmail.com","subject":"Re: [PATCH 1/3] add mergesort() for linked lists","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-11T16:44:52Z","receivedAt":"2012-04-11T16:44:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stephen Boyd writes:\n\n> On 03/31/2012 03:10 PM, René Scharfe wrote:\n>> diff --git a/mergesort.c b/mergesort.c\n>> new file mode 100644\n>> index 0000000..c0f1874\n>> --- /dev/null\n>> +++ b/mergesort.c\n>> @@ -0,0 +1,75 @@\n>> +#include \"cache.h\"\n>> +#include \"mergesort.h\"\n>> +\n>> +#include \"commit.h\"\n>\n> This is an unnecessary include, right?\n>\n> diff --git a/mergesort.c b/mergesort.c\n> index c0f1874..d084c60 100644\n> --- a/mergesort.c\n> +++ b/mergesort.c\n> @@ -1,8 +1,6 @@\n> #include \"cache.h\"\n> #include \"mergesort.h\"\n>\n> -#include \"commit.h\"\n> -\n> struct mergesort_sublist {\n> void *ptr;\n> unsigned long len;\n\nYes. I'll squash in, as I tentatively kicked many topics out of 'next' and\nthis was among them.\n"}]}