{"thread":{"id":"27412","subject":"[PATCH] fetch: avoid repeated commits in mark_complete","startedAt":"2011-05-19T20:48:51Z","lastAt":"2011-05-20T22:03:08Z","messageCount":12,"participants":["Jeff King","Thiago Farina","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"168259","messageId":"20110519204851.GA28574@sigill.intra.peff.net","threadId":"27412","inReplyTo":null,"subject":"[PATCH] fetch: avoid repeated commits in mark_complete","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T20:48:51Z","receivedAt":"2011-05-19T20:48:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We add every local ref to a list so that we can mark them\nand all of their ancestors back to a certain cutoff point.\nHowever, if some refs point to the same commit, we will end\nup adding them to the list many times.\n\nFurthermore, since commit_lists are stored as linked lists,\nwe must do an O(n) traversal of the list in order to find\nthe right place to insert each commit. This makes building\nthe list O(n^2) in the number of refs.\n\nFor normal repositories, this isn't a big deal. We have a\nfew hundreds refs at most, and most of them are unique. But\nconsider an \"alternates\" repo that serves as an object\ndatabase for many other similar repos. For reachability, it\nneeds to keep a copy of the refs in each child repo. This\nmeans it may have a large number of refs, many of which\npoint to the same commits.\n\nBy noting commits we have already added to the list, we can\nshrink the size of \"n\" in such a repo to the number of\nunique commits, which is on the order of what a normal repo\nwould contain (it's actually more than a normal repo, since child repos\nmay have branches at different states, but in practice it tends\nto be much smaller than the list with duplicates).\n\nHere are the results on one particular giant repo\n(containing objects for all Rails forks on GitHub):\n\n  $ git for-each-ref | wc -l\n  112514\n\n  [before]\n  $ git fetch --no-tags ../remote.git\n  63.52user 0.12system 1:03.68elapsed 99%CPU (0avgtext+0avgdata 137648maxresident)k\n  1856inputs+48outputs (11major+19603minor)pagefaults 0swaps\n\n  $ git fetch --no-tags ../remote.git\n  6.15user 0.08system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123856maxresident)k\n  0inputs+40outputs (0major+18872minor)pagefaults 0swaps\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/fetch-pack.c |    6 ++++--\n 1 files changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 85aff02..56c0b4a 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -472,8 +472,10 @@ static int mark_complete(const char *path, const unsigned char *sha1, int flag,\n \t}\n \tif (o && o->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *)o;\n-\t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\tif (!(commit->object.flags & COMPLETE)) {\n+\t\t\tcommit->object.flags |= COMPLETE;\n+\t\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\t}\n \t}\n \treturn 0;\n }\n-- \n1.7.5.8.ga95ab\n"},{"id":"168261","messageId":"20110519212349.GA28589@sigill.intra.peff.net","threadId":"27412","inReplyTo":"20110519204851.GA28574@sigill.intra.peff.net","subject":"[RFC/PATCH 0/4] commit lists as priority queues","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:23:49Z","receivedAt":"2011-05-19T21:23:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 19, 2011 at 04:48:51PM -0400, Jeff King wrote:\n\n> By noting commits we have already added to the list, we can\n> shrink the size of \"n\" in such a repo to the number of\n> unique commits, which is on the order of what a normal repo\n> would contain (it's actually more than a normal repo, since child repos\n> may have branches at different states, but in practice it tends\n> to be much smaller than the list with duplicates).\n> \n> Here are the results on one particular giant repo\n> (containing objects for all Rails forks on GitHub):\n> \n>   $ git for-each-ref | wc -l\n>   112514\n\nSo this seems to work pretty well for us in practice, because our\ngiant-refs use case is a big alternates repo, and of those ~112K refs,\nthere are only ~5K or so unique ones. Which is small enough that in this\ntiming:\n\n>   [before]\n>   $ git fetch --no-tags ../remote.git\n>   63.52user 0.12system 1:03.68elapsed 99%CPU (0avgtext+0avgdata 137648maxresident)k\n>   1856inputs+48outputs (11major+19603minor)pagefaults 0swaps\n> \n>   $ git fetch --no-tags ../remote.git\n>   6.15user 0.08system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123856maxresident)k\n>   0inputs+40outputs (0major+18872minor)pagefaults 0swaps\n\nThe 6 seconds are not spent doing anything related to mark_complete, so\nit's effectively fast enough (i.e., we made \"n\" small enough that the\nO(n^2) behavior doesn't matter). But obviously there's still a\nworst-case where you get bad behavior if you have a lot of unique refs.\nI don't know if anybody has that situation in practice (it might be\nsomething like creating a ref for every commit).\n\nSo I also considered a different approach, which is to use a better data\nstructure to hold the sorted commit list (a priority queue). That gives\na similar speedup:\n\n  $ git fetch --no-tags ../remote.git\n  6.20user 0.03system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123712maxresident)k\n  0inputs+40outputs (0major+18885minor)pagefaults 0swaps\n\nand actually has good asymptotic complexity. I also had a feeling we\ncould use a faster commit_list in other places, since get_revision is\nall based around the same pop-and-push-the-parents workflow. But after\nspending a few hours on it, it seems that _lots_ of places in the code\nwork on the assumption of a linked list (or at least doing very simple\nin-order traversal), and the changes got very ugly very quickly. And\nperformance-wise, it doesn't seem to be a huge problem, mainly because:\n\n  1. We don't tend to put more items in a commit_list than the width of\n     the history graph. So our \"n\" tends to be in the dozens at most.\n\n  2. We have the hack in fce87ae (Fix quadratic performance in\n     rewrite_one., 2008-07-12) which works OK in practice.\n\nSo it's a lot of extra code, and I haven't found a case where it\nactually improves performance. But here's that series, just for\nreference. We may want to take 1/4, which is an unrelated cleanup.\n\n  [1/4]: Makefile: sort TEST_PROGRAMS list\n  [2/4]: basic priority queue implementation\n  [3/4]: commit: add infrastructure for priority queues of commits\n  [4/4]: fetch-pack: use priority queue for mark_complete\n\n-Peff\n"},{"id":"168262","messageId":"20110519212424.GA29584@sigill.intra.peff.net","threadId":"27412","inReplyTo":"20110519212349.GA28589@sigill.intra.peff.net","subject":"[PATCH 1/4] Makefile: sort TEST_PROGRAMS list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:24:24Z","receivedAt":"2011-05-19T21:24:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We usually keep these lists in sorted order, but the last\nfew entries were just tacked on the end.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Makefile |    4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 5379aaa..d09ee70 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -415,8 +415,10 @@ TEST_PROGRAMS_NEED_X += test-date\n TEST_PROGRAMS_NEED_X += test-delta\n TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n 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-mktemp\n TEST_PROGRAMS_NEED_X += test-obj-pool\n TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n@@ -427,8 +429,6 @@ TEST_PROGRAMS_NEED_X += test-string-pool\n TEST_PROGRAMS_NEED_X += test-subprocess\n TEST_PROGRAMS_NEED_X += test-svn-fe\n TEST_PROGRAMS_NEED_X += test-treap\n-TEST_PROGRAMS_NEED_X += test-index-version\n-TEST_PROGRAMS_NEED_X += test-mktemp\n \n TEST_PROGRAMS = $(patsubst %,%$X,$(TEST_PROGRAMS_NEED_X))\n \n-- \n1.7.5.8.ga95ab\n"},{"id":"168263","messageId":"20110519212448.GB29584@sigill.intra.peff.net","threadId":"27412","inReplyTo":"20110519212349.GA28589@sigill.intra.peff.net","subject":"[PATCH 2/4] basic priority queue implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:24:48Z","receivedAt":"2011-05-19T21:24:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This can provide better algorithmic complexity for some of\nthe date-sorted commit list uses, among other things.\n\nThe queue is stored as a heap, allowing O(log) insertion and\ntop-element removal, and O(1) peeking at the top element.\nCurrent commit lists are sorted linked lists, giving O(1)\npeeking and top-element removal, but O(n^2) insertion.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n .gitignore       |    1 +\n Makefile         |    3 ++\n queue.c          |   70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n queue.h          |   17 +++++++++++++\n t/t0007-queue.sh |   50 ++++++++++++++++++++++++++++++++++++++\n test-queue.c     |   39 ++++++++++++++++++++++++++++++\n 6 files changed, 180 insertions(+), 0 deletions(-)\n create mode 100644 queue.c\n create mode 100644 queue.h\n create mode 100755 t/t0007-queue.sh\n create mode 100644 test-queue.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 711fce7..179483a 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -174,6 +174,7 @@\n /test-obj-pool\n /test-parse-options\n /test-path-utils\n+/test-queue\n /test-run-command\n /test-sha1\n /test-sigchain\ndiff --git a/Makefile b/Makefile\nindex d09ee70..737b2d5 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -422,6 +422,7 @@ TEST_PROGRAMS_NEED_X += test-mktemp\n TEST_PROGRAMS_NEED_X += test-obj-pool\n TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n+TEST_PROGRAMS_NEED_X += test-queue\n TEST_PROGRAMS_NEED_X += test-run-command\n TEST_PROGRAMS_NEED_X += test-sha1\n TEST_PROGRAMS_NEED_X += test-sigchain\n@@ -532,6 +533,7 @@ LIB_H += parse-options.h\n LIB_H += patch-ids.h\n LIB_H += pkt-line.h\n LIB_H += progress.h\n+LIB_H += queue.h\n LIB_H += quote.h\n LIB_H += reflog-walk.h\n LIB_H += refs.h\n@@ -629,6 +631,7 @@ LIB_OBJS += pkt-line.o\n LIB_OBJS += preload-index.o\n LIB_OBJS += pretty.o\n LIB_OBJS += progress.o\n+LIB_OBJS += queue.o\n LIB_OBJS += quote.o\n LIB_OBJS += reachable.o\n LIB_OBJS += read-cache.o\ndiff --git a/queue.c b/queue.c\nnew file mode 100644\nindex 0000000..068b559\n--- /dev/null\n+++ b/queue.c\n@@ -0,0 +1,70 @@\n+#include \"queue.h\"\n+#include \"cache.h\"\n+\n+static inline void queue_swap(struct queue *pq, unsigned i, unsigned j)\n+{\n+\tvoid *tmp = pq->items[i];\n+\tpq->items[i] = pq->items[j];\n+\tpq->items[j] = tmp;\n+}\n+\n+static void queue_heapify_up(struct queue *pq)\n+{\n+\tunsigned i = pq->nr - 1;\n+\twhile (i > 0) {\n+\t\tint parent = (i-1)/2;\n+\n+\t\tif (pq->cmp(pq->items[i], pq->items[parent]) <= 0)\n+\t\t\treturn;\n+\n+\t\tqueue_swap(pq, i, parent);\n+\t\ti = parent;\n+\t}\n+}\n+\n+void queue_insert(struct queue *pq, void *item)\n+{\n+\tALLOC_GROW(pq->items, pq->nr + 1, pq->alloc);\n+\tpq->items[pq->nr++] = item;\n+\tqueue_heapify_up(pq);\n+}\n+\n+static void queue_heapify_down(struct queue *pq)\n+{\n+\tunsigned i = 0;\n+\twhile (1) {\n+\t\tint largest = i, left = 2*i + 1, right = 2*i + 2;\n+\n+\t\tif (left < pq->nr &&\n+\t\t    pq->cmp(pq->items[left], pq->items[largest]) > 0)\n+\t\t\tlargest = left;\n+\t\tif (right < pq->nr &&\n+\t\t    pq->cmp(pq->items[right], pq->items[largest]) > 0)\n+\t\t\tlargest = right;\n+\n+\t\tif (largest == i)\n+\t\t\treturn;\n+\n+\t\tqueue_swap(pq, i, largest);\n+\t\ti = largest;\n+\t}\n+}\n+\n+void *queue_peek(struct queue *pq)\n+{\n+\treturn pq->nr ? pq->items[0] : NULL;\n+}\n+\n+void *queue_pop(struct queue *pq)\n+{\n+\tvoid *ret;\n+\n+\tif (!pq->nr)\n+\t\treturn NULL;\n+\tret = pq->items[0];\n+\n+\tpq->items[0] = pq->items[--pq->nr];\n+\tqueue_heapify_down(pq);\n+\n+\treturn ret;\n+}\ndiff --git a/queue.h b/queue.h\nnew file mode 100644\nindex 0000000..fee5a51\n--- /dev/null\n+++ b/queue.h\n@@ -0,0 +1,17 @@\n+#ifndef QUEUE_H\n+#define QUEUE_H\n+\n+typedef int (*queue_comparison_func_t)(const void *, const void *);\n+\n+struct queue {\n+\tqueue_comparison_func_t cmp;\n+\tvoid **items;\n+\tunsigned nr;\n+\tunsigned alloc;\n+};\n+\n+void queue_insert(struct queue *pq, void *item);\n+void *queue_peek(struct queue *pq);\n+void *queue_pop(struct queue *pq);\n+\n+#endif /* QUEUE_H */\ndiff --git a/t/t0007-queue.sh b/t/t0007-queue.sh\nnew file mode 100755\nindex 0000000..ee357bb\n--- /dev/null\n+++ b/t/t0007-queue.sh\n@@ -0,0 +1,50 @@\n+#!/bin/sh\n+\n+test_description='basic tests for priority queue implementation'\n+. ./test-lib.sh\n+\n+cat >expect <<'EOF'\n+10\n+9\n+8\n+7\n+6\n+5\n+5\n+4\n+3\n+2\n+1\n+EOF\n+test_expect_success 'basic ordering' '\n+\ttest-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+3\n+5\n+4\n+6\n+2\n+1\n+EOF\n+test_expect_success 'mixed insert and pop' '\n+\ttest-queue 1 2 3 pop 4 5 pop pop 6 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+2\n+1\n+NULL\n+2\n+1\n+NULL\n+EOF\n+test_expect_success 'notice empty queue' '\n+\ttest-queue 1 2 pop pop pop 1 2 pop pop pop >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/test-queue.c b/test-queue.c\nnew file mode 100644\nindex 0000000..a1e92e2\n--- /dev/null\n+++ b/test-queue.c\n@@ -0,0 +1,39 @@\n+#include \"cache.h\"\n+#include \"queue.h\"\n+\n+static int intcmp(const void *va, const void *vb)\n+{\n+\tconst int *a = va, *b = vb;\n+\treturn *a - *b;\n+}\n+\n+static void show(int *v)\n+{\n+\tif (!v)\n+\t\tprintf(\"NULL\\n\");\n+\telse\n+\t\tprintf(\"%d\\n\", *v);\n+\tfree(v);\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct queue pq = { intcmp };\n+\n+\twhile (*++argv) {\n+\t\tif (!strcmp(*argv, \"pop\"))\n+\t\t\tshow(queue_pop(&pq));\n+\t\telse if (!strcmp(*argv, \"dump\")) {\n+\t\t\tint *v;\n+\t\t\twhile ((v = queue_pop(&pq)))\n+\t\t\t       show(v);\n+\t\t}\n+\t\telse {\n+\t\t\tint *v = malloc(sizeof(*v));\n+\t\t\t*v = atoi(*argv);\n+\t\t\tqueue_insert(&pq, v);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n-- \n1.7.5.8.ga95ab\n"},{"id":"168264","messageId":"20110519212517.GC29584@sigill.intra.peff.net","threadId":"27412","inReplyTo":"20110519212349.GA28589@sigill.intra.peff.net","subject":"[PATCH 3/4] commit: add infrastructure for priority queues of commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:25:17Z","receivedAt":"2011-05-19T21:25:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Using a priority queue to store date-ordered commits can be\nalgorithmically faster than the current implementation\n(which uses sorted linked lists).\n\nThe previous commit introduced a generic priority queue.\nThis commit adds some infrastructure for using it with\ncommits. Specifically:\n\n  1. A date-comparison function and queue-initializer, so\n     you can create a queue like:\n\n       struct queue pq = COMMIT_QUEUE_INIT;\n\n  2. A function to pop the most recent commit from the\n     queue, adding its parents to the queue unless a\n     particular mark is seen on them. This is equivalent to\n     the current pop_most_recent_commit, which operates on\n     commit_list structs.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit.c |   27 +++++++++++++++++++++++++++\n commit.h |    5 +++++\n 2 files changed, 32 insertions(+), 0 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex ac337c7..9d0a182 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -419,6 +419,33 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \treturn ret;\n }\n \n+int commit_datecmp(const void *va, const void *vb)\n+{\n+\tconst struct commit *a = va, *b = vb;\n+\tif (a->date < b->date)\n+\t\treturn -1;\n+\telse if (a->date > b->date)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+struct commit *pop_commit_from_queue(struct queue *pq, unsigned int mark)\n+{\n+\tstruct commit *ret = queue_pop(pq);\n+\tstruct commit_list *parents = ret ? ret->parents : NULL;\n+\n+\twhile (parents) {\n+\t\tstruct commit *commit = parents->item;\n+\t\tif (!parse_commit(commit) && !(commit->object.flags & mark)) {\n+\t\t\tcommit->object.flags |= mark;\n+\t\t\tqueue_insert(pq, commit);\n+\t\t}\n+\t\tparents = parents->next;\n+\t}\n+\n+\treturn ret;\n+}\n+\n void clear_commit_marks(struct commit *commit, unsigned int mark)\n {\n \twhile (commit) {\ndiff --git a/commit.h b/commit.h\nindex 43940e2..87c9b4a 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -5,6 +5,7 @@\n #include \"tree.h\"\n #include \"strbuf.h\"\n #include \"decorate.h\"\n+#include \"queue.h\"\n \n struct commit_list {\n \tstruct commit *item;\n@@ -121,6 +122,10 @@ void pp_remainder(enum cmit_fmt fmt,\n struct commit *pop_most_recent_commit(struct commit_list **list,\n \t\t\t\t      unsigned int mark);\n \n+#define COMMIT_QUEUE_INIT { commit_datecmp }\n+int commit_datecmp(const void *a, const void *b);\n+struct commit *pop_commit_from_queue(struct queue *pq, unsigned int mark);\n+\n struct commit *pop_commit(struct commit_list **stack);\n \n void clear_commit_marks(struct commit *commit, unsigned int mark);\n-- \n1.7.5.8.ga95ab\n"},{"id":"168265","messageId":"20110519212657.GD29584@sigill.intra.peff.net","threadId":"27412","inReplyTo":"20110519212349.GA28589@sigill.intra.peff.net","subject":"[PATCH 4/4] fetch-pack: use priority queue for mark_complete","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-19T21:26:57Z","receivedAt":"2011-05-19T21:26:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The regular commit_list has quadratic insertion complexity.\nFetch-pack will insert an item for each ref we have.  For a\n\"normal\" number of refs, this is not a big deal, but it is\nquite inefficient when you have tens or hundreds of\nthousands of refs.\n\nInstead, let's use a priority queue with better insertion\nperformance. For example, timings from one repo (which\nstores alternates for all of the Rails forks at GitHub, with\nmirrored refs from each individual repo to manage object\npruning):\n\n  $ git for-each-ref | wc -l\n  112514\n\n  [before]\n  $ time git fetch --no-tags ../remote.git\n  63.52user 0.12system 1:03.68elapsed 99%CPU (0avgtext+0avgdata 137648maxresident)k\n  1856inputs+48outputs (11major+19603minor)pagefaults 0swaps\n\n  [after]\n  $ time git fetch --no-tags ../remote.git\n  6.20user 0.03system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123712maxresident)k\n  0inputs+40outputs (0major+18885minor)pagefaults 0swaps\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nSo this is the big performance-win patch. But if you didn't read my\nother \"fetch: avoid repeated commits in mark_complete\", go do that. It's\na much simpler solution that yields the same speedup in practice.\n\n builtin/fetch-pack.c |   11 ++++++-----\n 1 files changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 85aff02..9a951f3 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -457,7 +457,7 @@ done:\n \treturn count ? retval : 0;\n }\n \n-static struct commit_list *complete;\n+static struct queue complete = COMMIT_QUEUE_INIT;\n \n static int mark_complete(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n@@ -473,18 +473,19 @@ static int mark_complete(const char *path, const unsigned char *sha1, int flag,\n \tif (o && o->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *)o;\n \t\tcommit->object.flags |= COMPLETE;\n-\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\tqueue_insert(&complete, commit);\n \t}\n \treturn 0;\n }\n \n static void mark_recent_complete_commits(unsigned long cutoff)\n {\n-\twhile (complete && cutoff <= complete->item->date) {\n+\tstruct commit *c;\n+\twhile ((c = queue_peek(&complete)) && cutoff <= c->date) {\n \t\tif (args.verbose)\n \t\t\tfprintf(stderr, \"Marking %s as complete\\n\",\n-\t\t\t\tsha1_to_hex(complete->item->object.sha1));\n-\t\tpop_most_recent_commit(&complete, COMPLETE);\n+\t\t\t\tsha1_to_hex(c->object.sha1));\n+\t\tpop_commit_from_queue(&complete, COMPLETE);\n \t}\n }\n \n-- \n1.7.5.8.ga95ab\n"},{"id":"168285","messageId":"BANLkTikLSwWanxUksf3Ezx7uhaTR4mMiWw@mail.gmail.com","threadId":"27412","inReplyTo":"20110519212448.GB29584@sigill.intra.peff.net","subject":"Re: [PATCH 2/4] basic priority queue implementation","fromName":"Thiago Farina","fromEmail":"tfransosi@gmail.com","sentAt":"2011-05-20T00:47:38Z","receivedAt":"2011-05-20T00:47:38Z","isPatch":true,"sender":{"key":"tfransosi@gmail.com","avatar":"https://avatars.githubusercontent.com/u/970071?v=4"},"body":"On Thu, May 19, 2011 at 6:24 PM, Jeff King <peff@peff.net> wrote:\n> This can provide better algorithmic complexity for some of\n> the date-sorted commit list uses, among other things.\n>\n> The queue is stored as a heap, allowing O(log) insertion and\n> top-element removal, and O(1) peeking at the top element.\n> Current commit lists are sorted linked lists, giving O(1)\n> peeking and top-element removal, but O(n^2) insertion.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  .gitignore       |    1 +\n>  Makefile         |    3 ++\n>  queue.c          |   70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  queue.h          |   17 +++++++++++++\n>  t/t0007-queue.sh |   50 ++++++++++++++++++++++++++++++++++++++\n>  test-queue.c     |   39 ++++++++++++++++++++++++++++++\n>  6 files changed, 180 insertions(+), 0 deletions(-)\n>  create mode 100644 queue.c\n>  create mode 100644 queue.h\n>  create mode 100755 t/t0007-queue.sh\n>  create mode 100644 test-queue.c\n>\n> diff --git a/.gitignore b/.gitignore\n> index 711fce7..179483a 100644\n> --- a/.gitignore\n> +++ b/.gitignore\n> @@ -174,6 +174,7 @@\n>  /test-obj-pool\n>  /test-parse-options\n>  /test-path-utils\n> +/test-queue\n>  /test-run-command\n>  /test-sha1\n>  /test-sigchain\n> diff --git a/Makefile b/Makefile\n> index d09ee70..737b2d5 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -422,6 +422,7 @@ TEST_PROGRAMS_NEED_X += test-mktemp\n>  TEST_PROGRAMS_NEED_X += test-obj-pool\n>  TEST_PROGRAMS_NEED_X += test-parse-options\n>  TEST_PROGRAMS_NEED_X += test-path-utils\n> +TEST_PROGRAMS_NEED_X += test-queue\n>  TEST_PROGRAMS_NEED_X += test-run-command\n>  TEST_PROGRAMS_NEED_X += test-sha1\n>  TEST_PROGRAMS_NEED_X += test-sigchain\n> @@ -532,6 +533,7 @@ LIB_H += parse-options.h\n>  LIB_H += patch-ids.h\n>  LIB_H += pkt-line.h\n>  LIB_H += progress.h\n> +LIB_H += queue.h\n>  LIB_H += quote.h\n>  LIB_H += reflog-walk.h\n>  LIB_H += refs.h\n> @@ -629,6 +631,7 @@ LIB_OBJS += pkt-line.o\n>  LIB_OBJS += preload-index.o\n>  LIB_OBJS += pretty.o\n>  LIB_OBJS += progress.o\n> +LIB_OBJS += queue.o\n>  LIB_OBJS += quote.o\n>  LIB_OBJS += reachable.o\n>  LIB_OBJS += read-cache.o\n> diff --git a/queue.c b/queue.c\n> new file mode 100644\n> index 0000000..068b559\n> --- /dev/null\n> +++ b/queue.c\n> @@ -0,0 +1,70 @@\n> +#include \"queue.h\"\n> +#include \"cache.h\"\n> +\n> +static inline void queue_swap(struct queue *pq, unsigned i, unsigned j)\n> +{\n> +       void *tmp = pq->items[i];\n> +       pq->items[i] = pq->items[j];\n> +       pq->items[j] = tmp;\n> +}\n> +\n> +static void queue_heapify_up(struct queue *pq)\n> +{\n> +       unsigned i = pq->nr - 1;\n> +       while (i > 0) {\n> +               int parent = (i-1)/2;\n> +\n> +               if (pq->cmp(pq->items[i], pq->items[parent]) <= 0)\n> +                       return;\n> +\n> +               queue_swap(pq, i, parent);\n> +               i = parent;\n> +       }\n> +}\n> +\n> +void queue_insert(struct queue *pq, void *item)\n> +{\n> +       ALLOC_GROW(pq->items, pq->nr + 1, pq->alloc);\n> +       pq->items[pq->nr++] = item;\n> +       queue_heapify_up(pq);\n> +}\n> +\n> +static void queue_heapify_down(struct queue *pq)\n> +{\n> +       unsigned i = 0;\n> +       while (1) {\n> +               int largest = i, left = 2*i + 1, right = 2*i + 2;\n> +\n> +               if (left < pq->nr &&\n> +                   pq->cmp(pq->items[left], pq->items[largest]) > 0)\n> +                       largest = left;\n> +               if (right < pq->nr &&\n> +                   pq->cmp(pq->items[right], pq->items[largest]) > 0)\n> +                       largest = right;\n> +\n> +               if (largest == i)\n> +                       return;\n> +\n> +               queue_swap(pq, i, largest);\n> +               i = largest;\n> +       }\n> +}\n> +\n> +void *queue_peek(struct queue *pq)\n> +{\n> +       return pq->nr ? pq->items[0] : NULL;\n> +}\n> +\n> +void *queue_pop(struct queue *pq)\n> +{\n> +       void *ret;\n> +\n> +       if (!pq->nr)\n> +               return NULL;\n> +       ret = pq->items[0];\n> +\n> +       pq->items[0] = pq->items[--pq->nr];\n> +       queue_heapify_down(pq);\n> +\n> +       return ret;\n> +}\n> diff --git a/queue.h b/queue.h\n> new file mode 100644\n> index 0000000..fee5a51\n> --- /dev/null\n> +++ b/queue.h\n> @@ -0,0 +1,17 @@\n> +#ifndef QUEUE_H\n> +#define QUEUE_H\n> +\n> +typedef int (*queue_comparison_func_t)(const void *, const void *);\n> +\n> +struct queue {\n> +       queue_comparison_func_t cmp;\n> +       void **items;\n> +       unsigned nr;\n> +       unsigned alloc;\n> +};\n> +\n> +void queue_insert(struct queue *pq, void *item);\nI'd rename this to queue_append as we add |item| to the end of the\narray (like you did for sha1_array_append), opposed of inserting it at\nsome position/index.\n\n> +void *queue_peek(struct queue *pq);\n> +void *queue_pop(struct queue *pq);\n> +\n> +#endif /* QUEUE_H */\n> diff --git a/t/t0007-queue.sh b/t/t0007-queue.sh\n> new file mode 100755\n> index 0000000..ee357bb\n> --- /dev/null\n> +++ b/t/t0007-queue.sh\n> @@ -0,0 +1,50 @@\n> +#!/bin/sh\n> +\n> +test_description='basic tests for priority queue implementation'\n> +. ./test-lib.sh\n> +\n> +cat >expect <<'EOF'\n> +10\n> +9\n> +8\n> +7\n> +6\n> +5\n> +5\n> +4\n> +3\n> +2\n> +1\n> +EOF\n> +test_expect_success 'basic ordering' '\n> +       test-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&\n> +       test_cmp expect actual\n> +'\n> +\n> +cat >expect <<'EOF'\n> +3\n> +5\n> +4\n> +6\n> +2\n> +1\n> +EOF\n> +test_expect_success 'mixed insert and pop' '\n> +       test-queue 1 2 3 pop 4 5 pop pop 6 dump >actual &&\n> +       test_cmp expect actual\n> +'\n> +\n> +cat >expect <<'EOF'\n> +2\n> +1\n> +NULL\n> +2\n> +1\n> +NULL\n> +EOF\n> +test_expect_success 'notice empty queue' '\n> +       test-queue 1 2 pop pop pop 1 2 pop pop pop >actual &&\n> +       test_cmp expect actual\n> +'\n> +\n> +test_done\n> diff --git a/test-queue.c b/test-queue.c\n> new file mode 100644\n> index 0000000..a1e92e2\n> --- /dev/null\n> +++ b/test-queue.c\n> @@ -0,0 +1,39 @@\n> +#include \"cache.h\"\n> +#include \"queue.h\"\n> +\n> +static int intcmp(const void *va, const void *vb)\n> +{\n> +       const int *a = va, *b = vb;\n> +       return *a - *b;\n> +}\n> +\n> +static void show(int *v)\n> +{\n> +       if (!v)\n> +               printf(\"NULL\\n\");\n> +       else\n> +               printf(\"%d\\n\", *v);\n> +       free(v);\n> +}\n> +\n> +int main(int argc, char **argv)\n> +{\n> +       struct queue pq = { intcmp };\n> +\n> +       while (*++argv) {\n> +               if (!strcmp(*argv, \"pop\"))\n> +                       show(queue_pop(&pq));\n> +               else if (!strcmp(*argv, \"dump\")) {\n> +                       int *v;\n> +                       while ((v = queue_pop(&pq)))\n> +                              show(v);\n> +               }\n> +               else {\n> +                       int *v = malloc(sizeof(*v));\n> +                       *v = atoi(*argv);\n> +                       queue_insert(&pq, v);\n> +               }\n> +       }\n> +\n> +       return 0;\n> +}\n> --\n> 1.7.5.8.ga95ab\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n>\n"},{"id":"168288","messageId":"7vliy25erq.fsf@alter.siamese.dyndns.org","threadId":"27412","inReplyTo":"20110519204851.GA28574@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid repeated commits in mark_complete","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-05-20T01:42:17Z","receivedAt":"2011-05-20T01:42:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Trivially correct and the right thing to do.  I love this kind of patches\n;-)\n\nThanks.\n"},{"id":"168301","messageId":"20110520073821.GA3663@sigill.intra.peff.net","threadId":"27412","inReplyTo":"BANLkTikLSwWanxUksf3Ezx7uhaTR4mMiWw@mail.gmail.com","subject":"Re: [PATCH 2/4] basic priority queue implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-20T07:38:21Z","receivedAt":"2011-05-20T07:38:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 19, 2011 at 09:47:38PM -0300, Thiago Farina wrote:\n\n> > +void queue_insert(struct queue *pq, void *item);\n> I'd rename this to queue_append as we add |item| to the end of the\n> array (like you did for sha1_array_append), opposed of inserting it at\n> some position/index.\n\nIt's definitely not an append. The data structure is a priority queue,\nso the element is inserted within the heap at the proper position\naccording to the comparison function (notice that we stick at the end,\nbut then heapify_up).\n\nSpeaking of naming, though, the real problem is that this data structure\nshould be called \"pqueue\" or something similar to indicate that it is\nnot a simple FIFO. Unfortunately, the short-and-sweet \"pqueue\" is taken\nby openssl, which pollutes all over the global namespace.\n\n-Peff\n\nPS If you don't mind, please try to trim your quoted text a bit. Finding\nyour 3-line paragraph amid 200 lines of quoted text was a little\nchallenging. :)\n"},{"id":"168315","messageId":"BANLkTinojbxq=y3f-GPJsL7OH2OAJfW6zw@mail.gmail.com","threadId":"27412","inReplyTo":"20110520073821.GA3663@sigill.intra.peff.net","subject":"Re: [PATCH 2/4] basic priority queue implementation","fromName":"Thiago Farina","fromEmail":"tfransosi@gmail.com","sentAt":"2011-05-20T13:13:10Z","receivedAt":"2011-05-20T13:13:10Z","isPatch":true,"sender":{"key":"tfransosi@gmail.com","avatar":"https://avatars.githubusercontent.com/u/970071?v=4"},"body":"On Fri, May 20, 2011 at 4:38 AM, Jeff King <peff@peff.net> wrote:\n> On Thu, May 19, 2011 at 09:47:38PM -0300, Thiago Farina wrote:\n>\n>> > +void queue_insert(struct queue *pq, void *item);\n>> I'd rename this to queue_append as we add |item| to the end of the\n>> array (like you did for sha1_array_append), opposed of inserting it at\n>> some position/index.\n>\n> It's definitely not an append. The data structure is a priority queue,\n> so the element is inserted within the heap at the proper position\n> according to the comparison function (notice that we stick at the end,\n> but then heapify_up).\n>\nOK, sorry. I didn't read the heapify_up part :(\n\n> Speaking of naming, though, the real problem is that this data structure\n> should be called \"pqueue\" or something similar to indicate that it is\n> not a simple FIFO. Unfortunately, the short-and-sweet \"pqueue\" is taken\n> by openssl, which pollutes all over the global namespace.\n>\nHum, yeah when I read the commit message I though about the name of\nthe structure, but I didn't want to bother you with that. Probably you\nhave considered the option of naming it 'priority_queue' too. Haven't\nyou chose priority_queue, because you consider the name longer than\nnecessary?\n\n> -Peff\n>\n> PS If you don't mind, please try to trim your quoted text a bit. Finding\n> your 3-line paragraph amid 200 lines of quoted text was a little\n> challenging. :)\n>\nOK. ;)\n"},{"id":"168316","messageId":"20110520132344.GA30616@sigill.intra.peff.net","threadId":"27412","inReplyTo":"BANLkTinojbxq=y3f-GPJsL7OH2OAJfW6zw@mail.gmail.com","subject":"Re: [PATCH 2/4] basic priority queue implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-05-20T13:23:44Z","receivedAt":"2011-05-20T13:23:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 20, 2011 at 10:13:10AM -0300, Thiago Farina wrote:\n\n> > Speaking of naming, though, the real problem is that this data structure\n> > should be called \"pqueue\" or something similar to indicate that it is\n> > not a simple FIFO. Unfortunately, the short-and-sweet \"pqueue\" is taken\n> > by openssl, which pollutes all over the global namespace.\n> >\n> Hum, yeah when I read the commit message I though about the name of\n> the structure, but I didn't want to bother you with that. Probably you\n> have considered the option of naming it 'priority_queue' too. Haven't\n> you chose priority_queue, because you consider the name longer than\n> necessary?\n\nExactly. Though unless somebody can come up with a practical case where\nusing the priority queue speeds up some operation, I don't think it is\nworth applying anyway. So the naming question is somewhat academic. :)\n\n-Peff\n"},{"id":"168337","messageId":"7v4o4p2foj.fsf@alter.siamese.dyndns.org","threadId":"27412","inReplyTo":"20110519212349.GA28589@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 0/4] commit lists as priority queues","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-05-20T22:03:08Z","receivedAt":"2011-05-20T22:03:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ... I also had a feeling we\n> could use a faster commit_list in other places, since get_revision is\n> all based around the same pop-and-push-the-parents workflow. But after\n> spending a few hours on it, it seems that _lots_ of places in the code\n> work on the assumption of a linked list (or at least doing very simple\n> in-order traversal), and the changes got very ugly very quickly.\n\nI recall looking at the same codepaths a few years ago for different\nreasons. get_revision() callchain does a _lot_ of alloc/free, so I\nnaturally wanted to catch all the allocations and frees to replace them\nwith a custom allocator that slices from a larger slab. It involved too\nmany places so I decided it wasn't really worth doing only that change\nwithout other benefit (e.g. lifting the \"listness\" assumption), and\nstopped.\n\nIf somebody is interested to tackle it, we would probably need a two step\nconversion process. First introduce an abstracted interface that passes\naround the \"list-as-a-whole\" object with a few selected methods (e.g. drop\nan element into it at the sorted location and get a \"cursor\" that points\nat it, given a \"cursor\", grab an element from the list, increment the\n\"cursor\" to point at the next object, etc.), choosing a set just\nsufficient to express the patterns of accesses the current codebase makes,\nand implement the API over the existing linked-list implementation to\nconvert all the callers. After making sure this works, update the API\nimplementation with the queue in this patch.\n\nOr something like that.\n\n> ... And\n> performance-wise, it doesn't seem to be a huge problem, mainly because:\n>\n>   1. We don't tend to put more items in a commit_list than the width of\n>      the history graph. So our \"n\" tends to be in the dozens at most.\n\nI was worried that you may end up with many concurrent traversal going in\na very bushy history (think: traversing from the tip of \"next\"), but I\nagree that it would be in the order of dozens, not thousands.\n"}]}