{"thread":{"id":"37123","subject":"[PATCH/RFH 0/3] stable priority-queue","startedAt":"2014-07-14T05:40:22Z","lastAt":"2014-07-21T09:07:35Z","messageCount":7,"participants":["Jeff King","Duy Nguyen","David Kastrup"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"245968","messageId":"20140714054021.GA4422@sigill.intra.peff.net","threadId":"37123","inReplyTo":null,"subject":"[PATCH/RFH 0/3] stable priority-queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-14T05:40:22Z","receivedAt":"2014-07-14T05:40:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"As Junio and I discussed earlier in [1], this series makes the\nprio_queue struct stable with respect to object insertion (which in turn\nmeans we can use it to replace commit_list in more places).\n\nI think everything here is correct, but the second commit fails the\nfinal test in t5539. I think the test is just flaky (hence the RFH and\ncc to Duy).\n\nThat test creates some unrelated commits in two separate repositories,\nand then fetches from one to the other. Since the commit creation\nhappens in a subshell, the first commit in each ends up with the same\ntest_tick value. When fetch-pack looks at the two root commits\n\"unrelated1\" and \"new-too\", the exact sequence of ACKs is different\ndepending on which one it pulls out of the queue first.\n\nWith the current code, it happens to be \"unrelated1\" (though this is not\nat all guaranteed by the prio_queue data structure, it is deterministic\nfor this particular sequence of input). We see the ready-ACK, and the\ntest succeeds.\n\nWith the stable queue, we reliably get \"new-too\" out (since it is our\nlocal tip, it is added to the queue before we even talk to the remote).\nWe never see a ready-ACK, and the test fails due to the grep on the\nTRACE_PACKET output at the end (the fetch itself succeeds as expected).\n\nI'm really not quite clear on what's supposed to be going on in the\ntest. I can make it pass with:\n\ndiff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh\nindex 94553e1..b461188 100755\n--- a/t/t5539-fetch-http-shallow.sh\n+++ b/t/t5539-fetch-http-shallow.sh\n@@ -54,6 +54,7 @@ EOF\n test_expect_success 'no shallow lines after receiving ACK ready' '\n \t(\n \t\tcd shallow &&\n+\t\ttest_tick &&\n \t\tfor i in $(test_seq 15)\n \t\tdo\n \t\t\tgit checkout --orphan unrelated$i &&\n\nwhich just bumps the timestamp for the unrelated* commits (so that they\nare always more recent than \"new-too\" and get picked first). I'm not\nsure if that is too hacky, or if there's a more robust way to set up the\ntest.\n\nAnyway, here are the patches.\n\n  [1/3]: prio-queue: factor out compare and swap operations\n  [2/3]: prio-queue: make output stable with respect to insertion\n  [3/3]: paint_down_to_common: use prio_queue\n\n-Peff\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/252472/focus=252475\n"},{"id":"245969","messageId":"20140714054250.GA4838@sigill.intra.peff.net","threadId":"37123","inReplyTo":"20140714054021.GA4422@sigill.intra.peff.net","subject":"[PATCH 1/3] prio-queue: factor out compare and swap operations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-14T05:42:50Z","receivedAt":"2014-07-14T05:42:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When manipulating the priority queue's heap, we frequently\nhave to compare and swap heap entries. As we are storing\nonly void pointers right now, this is quite easy to do\ninline in a few lines. However, when we start using a more\ncomplicated heap entry in a future patch, that will get\nlonger. Factoring out these operations lets us make future\nchanges in one place. It also makes the code a little\nshorter and more readable.\n\nNote that we actually accept indices into the queue array\ninstead of pointers. This is slightly less flexible than\npassing pointers-to-pointers (we could not swap items from\nunrelated arrays, but we would not want to), but will make\nfurther refactoring simpler (and lets us avoid repeating\n\"queue->array\" at each callsite, which led to some long\nlines).\n\nAnd finally, note that we are cleaning up an accidental use\nof a \"struct commit\" pointer to hold a temporary entry\nduring swap. Even though we currently only use this code for\ncommits, it is supposed to be type-agnostic. In practice\nthis didn't matter anyway because we never dereferenced the\ncommit pointer (and on most systems, the pointer values\nthemselves are interchangeable between types).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n prio-queue.c | 49 +++++++++++++++++++++++++------------------------\n 1 file changed, 25 insertions(+), 24 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex c9f8c6d..0f4fcf2 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -1,18 +1,28 @@\n #include \"cache.h\"\n-#include \"commit.h\"\n #include \"prio-queue.h\"\n \n+static inline int compare(struct prio_queue *queue, int i, int j)\n+{\n+\tint cmp = queue->compare(queue->array[i], queue->array[j],\n+\t\t\t\t queue->cb_data);\n+\treturn cmp;\n+}\n+\n+static inline void swap(struct prio_queue *queue, int i, int j)\n+{\n+\tvoid *tmp = queue->array[i];\n+\tqueue->array[i] = queue->array[j];\n+\tqueue->array[j] = tmp;\n+}\n+\n void prio_queue_reverse(struct prio_queue *queue)\n {\n \tint i, j;\n \n \tif (queue->compare != NULL)\n \t\tdie(\"BUG: prio_queue_reverse() on non-LIFO queue\");\n-\tfor (i = 0; i <= (j = (queue->nr - 1) - i); i++) {\n-\t\tstruct commit *swap = queue->array[i];\n-\t\tqueue->array[i] = queue->array[j];\n-\t\tqueue->array[j] = swap;\n-\t}\n+\tfor (i = 0; i <= (j = (queue->nr - 1) - i); i++)\n+\t\tswap(queue, i, j);\n }\n \n void clear_prio_queue(struct prio_queue *queue)\n@@ -25,37 +35,32 @@ void clear_prio_queue(struct prio_queue *queue)\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n-\tprio_queue_compare_fn compare = queue->compare;\n \tint ix, parent;\n \n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n \tqueue->array[queue->nr++] = thing;\n-\tif (!compare)\n+\tif (!queue->compare)\n \t\treturn; /* LIFO */\n \n \t/* Bubble up the new one */\n \tfor (ix = queue->nr - 1; ix; ix = parent) {\n \t\tparent = (ix - 1) / 2;\n-\t\tif (compare(queue->array[parent], queue->array[ix],\n-\t\t\t    queue->cb_data) <= 0)\n+\t\tif (compare(queue, parent, ix) <= 0)\n \t\t\tbreak;\n \n-\t\tthing = queue->array[parent];\n-\t\tqueue->array[parent] = queue->array[ix];\n-\t\tqueue->array[ix] = thing;\n+\t\tswap(queue, parent, ix);\n \t}\n }\n \n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tvoid *result, *swap;\n+\tvoid *result;\n \tint ix, child;\n-\tprio_queue_compare_fn compare = queue->compare;\n \n \tif (!queue->nr)\n \t\treturn NULL;\n-\tif (!compare)\n+\tif (!queue->compare)\n \t\treturn queue->array[--queue->nr]; /* LIFO */\n \n \tresult = queue->array[0];\n@@ -67,18 +72,14 @@ void *prio_queue_get(struct prio_queue *queue)\n \t/* Push down the one at the root */\n \tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n \t\tchild = ix * 2 + 1; /* left */\n-\t\tif ((child + 1 < queue->nr) &&\n-\t\t    (compare(queue->array[child], queue->array[child + 1],\n-\t\t\t     queue->cb_data) >= 0))\n+\t\tif (child + 1 < queue->nr &&\n+\t\t    compare(queue, child, child + 1) >= 0)\n \t\t\tchild++; /* use right child */\n \n-\t\tif (compare(queue->array[ix], queue->array[child],\n-\t\t\t    queue->cb_data) <= 0)\n+\t\tif (compare(queue, ix, child) <= 0)\n \t\t\tbreak;\n \n-\t\tswap = queue->array[child];\n-\t\tqueue->array[child] = queue->array[ix];\n-\t\tqueue->array[ix] = swap;\n+\t\tswap(queue, child, ix);\n \t}\n \treturn result;\n }\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"245970","messageId":"20140714055159.GB4838@sigill.intra.peff.net","threadId":"37123","inReplyTo":"20140714054021.GA4422@sigill.intra.peff.net","subject":"[PATCH 2/3] prio-queue: make output stable with respect to insertion","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-14T05:51:59Z","receivedAt":"2014-07-14T05:51:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If two items are added to a prio_queue and compare equal,\nthey currently come out in an apparently random order (this\norder is deterministic for a particular sequence of\ninsertions and removals, but does not necessarily match the\ninsertion order). This makes it unlike using a date-ordered\ncommit_list, which is one of the main types we would like to\nreplace with it (because prio_queue does not suffer from\nO(n) insertions).\n\nWe can make the priority queue stable by keeping an\ninsertion counter for each element, and using it to break\nties. This does increase the memory usage of the structure\n(one int per element), but in practice it does not seem to\naffect runtime. A best-of-five \"git rev-list --topo-order\"\non linux.git showed less than 1% difference (well within the\nrun-to-run noise).\n\nIn an ideal world, we would offer both stable and unstable\npriority queues (the latter to try to maximize performance).\nHowever, given the lack of a measurable performance\ndifference, it is not worth the extra code.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI actually tried implementing a stable queue on top of the existing\nprio-queue. However, it was quite a mess. Because prio_queue only stores\none void pointer to a thing, the stable queue has to allocate its own its\n(counter,thing) pair. Doing it in a separate array doesn't work (you do\nnot pop them in insertion order, so you end up with \"holes\"). So you end\nup storing an extra pointer, _plus_ per-entry malloc overhead.\n\nIf we really want to offer a non-stable queue (and I do not think we\ndo), we should probably just do two totally separate queues, or\nimplement the whole thing with a run-time \"element size\" member (or even\ndo it in macros).\n\nI use struct assignment in the swap() function below. Do we want to\nreplace that with a memcpy? Presumably decent compilers can turn that\ninto the same code anyway, but I find the assignment more readable, and\nIIRC it has been around since C89.\n\n prio-queue.c | 15 ++++++++++-----\n prio-queue.h |  8 +++++++-\n 2 files changed, 17 insertions(+), 6 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 0f4fcf2..e4365b0 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -3,14 +3,16 @@\n \n static inline int compare(struct prio_queue *queue, int i, int j)\n {\n-\tint cmp = queue->compare(queue->array[i], queue->array[j],\n+\tint cmp = queue->compare(queue->array[i].data, queue->array[j].data,\n \t\t\t\t queue->cb_data);\n+\tif (!cmp)\n+\t\tcmp = queue->array[i].ctr - queue->array[j].ctr;\n \treturn cmp;\n }\n \n static inline void swap(struct prio_queue *queue, int i, int j)\n {\n-\tvoid *tmp = queue->array[i];\n+\tstruct prio_queue_entry tmp = queue->array[i];\n \tqueue->array[i] = queue->array[j];\n \tqueue->array[j] = tmp;\n }\n@@ -31,6 +33,7 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->nr = 0;\n \tqueue->alloc = 0;\n \tqueue->array = NULL;\n+\tqueue->insertion_ctr = 0;\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n@@ -39,7 +42,9 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n-\tqueue->array[queue->nr++] = thing;\n+\tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n+\tqueue->array[queue->nr].data = thing;\n+\tqueue->nr++;\n \tif (!queue->compare)\n \t\treturn; /* LIFO */\n \n@@ -61,9 +66,9 @@ void *prio_queue_get(struct prio_queue *queue)\n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr]; /* LIFO */\n+\t\treturn queue->array[--queue->nr].data; /* LIFO */\n \n-\tresult = queue->array[0];\n+\tresult = queue->array[0].data;\n \tif (!--queue->nr)\n \t\treturn result;\n \ndiff --git a/prio-queue.h b/prio-queue.h\nindex 9c3cd1f..d030ec9 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -21,11 +21,17 @@\n  */\n typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);\n \n+struct prio_queue_entry {\n+\tunsigned ctr;\n+\tvoid *data;\n+};\n+\n struct prio_queue {\n \tprio_queue_compare_fn compare;\n+\tunsigned insertion_ctr;\n \tvoid *cb_data;\n \tint alloc, nr;\n-\tvoid **array;\n+\tstruct prio_queue_entry *array;\n };\n \n /*\n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"245971","messageId":"20140714055354.GC4838@sigill.intra.peff.net","threadId":"37123","inReplyTo":"20140714054021.GA4422@sigill.intra.peff.net","subject":"[PATCH 3/3] paint_down_to_common: use prio_queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-14T05:53:54Z","receivedAt":"2014-07-14T05:53:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are traversing to find merge bases, we keep our\nusual commit_list of commits to process, sorted by their\ncommit timestamp. As we add each parent to the list, we have\nto spend \"O(width of history)\" to do the insertion, where\nthe width of history is the number of simultaneous lines of\ndevelopment.\n\nIf we instead use a heap-based priority queue, we can do\nthese insertions in \"O(log width)\" time. This provides minor\nspeedups to merge-base calculations (timings in linux.git,\nwarm cache, best-of-five):\n\n  [before]\n  $ git merge-base HEAD v2.6.12\n  real    0m3.251s\n  user    0m3.148s\n  sys     0m0.104s\n\n  [after]\n  $ git merge-base HEAD v2.6.12\n  real    0m3.234s\n  user    0m3.108s\n  sys     0m0.128s\n\nThat's only an 0.5% speedup, but it does help protect us\nagainst pathological cases.\n\nWhile we are munging the \"interesting\" function, we also\ntake the opportunity to give it a more descriptive name, and\nconvert the return value to an int (we returned the first\ninteresting commit, but nobody ever looked at it).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nSame as what I posted a few weeks ago, but now we do not have to tweak\nt6024 to account for the lack of stability.\n\n commit.c | 42 +++++++++++++++++++-----------------------\n 1 file changed, 19 insertions(+), 23 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex acb74b5..1fc60c0 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -786,45 +786,41 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \n static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n \n-static struct commit *interesting(struct commit_list *list)\n+static int queue_has_nonstale(struct prio_queue *queue)\n {\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tlist = list->next;\n-\t\tif (commit->object.flags & STALE)\n-\t\t\tcontinue;\n-\t\treturn commit;\n+\tint i;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\treturn 1;\n \t}\n-\treturn NULL;\n+\treturn 0;\n }\n \n /* all input commits in one and twos[] must have been parsed! */\n static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)\n {\n-\tstruct commit_list *list = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_list *result = NULL;\n \tint i;\n \n \tone->object.flags |= PARENT1;\n-\tcommit_list_insert_by_date(one, &list);\n-\tif (!n)\n-\t\treturn list;\n+\tif (!n) {\n+\t\tcommit_list_append(one, &result);\n+\t\treturn result;\n+\t}\n+\tprio_queue_put(&queue, one);\n+\n \tfor (i = 0; i < n; i++) {\n \t\ttwos[i]->object.flags |= PARENT2;\n-\t\tcommit_list_insert_by_date(twos[i], &list);\n+\t\tprio_queue_put(&queue, twos[i]);\n \t}\n \n-\twhile (interesting(list)) {\n-\t\tstruct commit *commit;\n+\twhile (queue_has_nonstale(&queue)) {\n+\t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n-\t\tstruct commit_list *next;\n \t\tint flags;\n \n-\t\tcommit = list->item;\n-\t\tnext = list->next;\n-\t\tfree(list);\n-\t\tlist = next;\n-\n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n \t\tif (flags == (PARENT1 | PARENT2)) {\n \t\t\tif (!(commit->object.flags & RESULT)) {\n@@ -843,11 +839,11 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc\n \t\t\tif (parse_commit(p))\n \t\t\t\treturn NULL;\n \t\t\tp->object.flags |= flags;\n-\t\t\tcommit_list_insert_by_date(p, &list);\n+\t\t\tprio_queue_put(&queue, p);\n \t\t}\n \t}\n \n-\tfree_commit_list(list);\n+\tclear_prio_queue(&queue);\n \treturn result;\n }\n \n-- \n2.0.0.566.gfe3e6b2\n"},{"id":"245980","messageId":"CACsJy8DCbY7hOknGVM7zd6uJBq70+MG9N+Mj-+VXvrSan5njcA@mail.gmail.com","threadId":"37123","inReplyTo":"20140714054021.GA4422@sigill.intra.peff.net","subject":"Re: [PATCH/RFH 0/3] stable priority-queue","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-07-14T10:12:07Z","receivedAt":"2014-07-14T10:12:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Jul 14, 2014 at 12:40 PM, Jeff King <peff@peff.net> wrote:\n> As Junio and I discussed earlier in [1], this series makes the\n> prio_queue struct stable with respect to object insertion (which in turn\n> means we can use it to replace commit_list in more places).\n>\n> I think everything here is correct, but the second commit fails the\n> final test in t5539. I think the test is just flaky (hence the RFH and\n> cc to Duy).\n>\n> That test creates some unrelated commits in two separate repositories,\n> and then fetches from one to the other. Since the commit creation\n> happens in a subshell, the first commit in each ends up with the same\n> test_tick value. When fetch-pack looks at the two root commits\n> \"unrelated1\" and \"new-too\", the exact sequence of ACKs is different\n> depending on which one it pulls out of the queue first.\n>\n> With the current code, it happens to be \"unrelated1\" (though this is not\n> at all guaranteed by the prio_queue data structure, it is deterministic\n> for this particular sequence of input). We see the ready-ACK, and the\n> test succeeds.\n>\n> With the stable queue, we reliably get \"new-too\" out (since it is our\n> local tip, it is added to the queue before we even talk to the remote).\n> We never see a ready-ACK, and the test fails due to the grep on the\n> TRACE_PACKET output at the end (the fetch itself succeeds as expected).\n>\n> I'm really not quite clear on what's supposed to be going on in the\n> test. I can make it pass with:\n>\n> diff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh\n> index 94553e1..b461188 100755\n> --- a/t/t5539-fetch-http-shallow.sh\n> +++ b/t/t5539-fetch-http-shallow.sh\n> @@ -54,6 +54,7 @@ EOF\n>  test_expect_success 'no shallow lines after receiving ACK ready' '\n>         (\n>                 cd shallow &&\n> +               test_tick &&\n>                 for i in $(test_seq 15)\n>                 do\n>                         git checkout --orphan unrelated$i &&\n>\n> which just bumps the timestamp for the unrelated* commits (so that they\n> are always more recent than \"new-too\" and get picked first). I'm not\n> sure if that is too hacky, or if there's a more robust way to set up the\n> test.\n\nThe test needs the right amount of \"have\"s with pkt-flush inserted at\nthe right place. If test_tick makes it happy, I think we could go with\nit for now. I'll try to study this code more and see if I can come up\nwith a better test. It'll be low priority in my backlog though.\n-- \nDuy\n"},{"id":"245982","messageId":"87tx6k5hjz.fsf@fencepost.gnu.org","threadId":"37123","inReplyTo":"20140714054021.GA4422@sigill.intra.peff.net","subject":"Re: [PATCH/RFH 0/3] stable priority-queue","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-07-14T11:02:56Z","receivedAt":"2014-07-14T11:02:56Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> As Junio and I discussed earlier in [1], this series makes the\n> prio_queue struct stable with respect to object insertion (which in turn\n> means we can use it to replace commit_list in more places).\n\nI don't think that this makes sense in general since it assumes the\nappropriate fallback behavior to be FIFO.  Depending on the use case, it\nmight be the other way round, or something else (like topology-based)\nentirely.\n\ncommit_list may be unsuitable as such for intermingled addition of\nunsorted and extraction of sorted elements (the general use case for\npriority queues).\n\nI see that struct commit already contains an integer field called\n\"index\", assigned sequentially, which might conceivably be used for\ntie-breaking independent from the actual prio_queue use at no extra\ncost.\n\nThe resulting order will of course be somewhat arbitrary in a different\nway, but at least will correspond to the order the commits have been\ndiscovered/generated, so they should still exhibit a more topological\nrelation than what prio_queue does without further help.\n\n-- \nDavid Kastrup\n"},{"id":"246433","messageId":"20140721090735.GA14548@peff.net","threadId":"37123","inReplyTo":"87tx6k5hjz.fsf@fencepost.gnu.org","subject":"Re: [PATCH/RFH 0/3] stable priority-queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-21T09:07:35Z","receivedAt":"2014-07-21T09:07:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 14, 2014 at 01:02:56PM +0200, David Kastrup wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > As Junio and I discussed earlier in [1], this series makes the\n> > prio_queue struct stable with respect to object insertion (which in turn\n> > means we can use it to replace commit_list in more places).\n> \n> I don't think that this makes sense in general since it assumes the\n> appropriate fallback behavior to be FIFO.  Depending on the use case, it\n> might be the other way round, or something else (like topology-based)\n> entirely.\n\nRemember that this is just a tie-breaker for the regular comparison\nfunction. If you want to represent some other ordering, you are free to\ndo the tie-breaking yourself in your comparison function. The one thing\nwe can easily provide but do not is LIFO ordering for the tie-breaker.\nThat would be trivial to add as a flag on the prio_queue, but I'd wait\nuntil there is actually a caller who wants it.\n\nYes, it's a bit hacky to provide it for cases which _don't_ care about\norder (or implement their own separate tie-breaker). But the worst case\nthere is that we are wasting some memory, and I wasn't able to measure a\nreal slow-down. I think it's a reasonable compromise given the lack of\ngenerics in C.\n\nBut if you have a case that is measurably affected, please let me know,\nand I can look into implementing it in a type-agnostic way (so that the\nembedded insertion counter becomes just another type).\n\n> I see that struct commit already contains an integer field called\n> \"index\", assigned sequentially, which might conceivably be used for\n> tie-breaking independent from the actual prio_queue use at no extra\n> cost.\n\nI don't think it's a good idea to rely on that index, as it is anything\nbut stable. It represents whatever order commits happened to be first\ntouched in the current program run. So:\n\n  1. Performing the same operation in-process versus in a sub-process\n     may produce different results.\n\n  2. Arguments to a command may have unexpected effects. E.g.,\n     specifying \"--tags\" to \"rev-list\" will look up the commit at\n     each tag ref, giving them much lower index numbers than they would\n     if we reached only through the normal traversal.\n\n-Peff\n"}]}