patch, 3 partsstable priority-queue

As Junio and I discussed earlier in [1], this series makes the prio_queue struct stable with respect to object insertion (which in turn means we can use it to replace commit_list in more places).

I think everything here is correct, but the second commit fails the final test in t5539. I think the test is just flaky (hence the RFH and cc to Duy).

That test creates some unrelated commits in two separate repositories, and then fetches from one to the other. Since the commit creation happens in a subshell, the first commit in each ends up with the same test_tick value. When fetch-pack looks at the two root commits "unrelated1" and "new-too", the exact sequence of ACKs is different depending on which one it pulls out of the queue first.

With the current code, it happens to be "unrelated1" (though this is not at all guaranteed by the prio_queue data structure, it is deterministic for this particular sequence of input). We see the ready-ACK, and the test succeeds.

With the stable queue, we reliably get "new-too" out (since it is our local tip, it is added to the queue before we even talk to the remote). We never see a ready-ACK, and the test fails due to the grep on the TRACE_PACKET output at the end (the fetch itself succeeds as expected).

I'm really not quite clear on what's supposed to be going on in the test. I can make it pass with:

When manipulating the priority queue's heap, we frequently have to compare and swap heap entries. As we are storing only void pointers right now, this is quite easy to do inline in a few lines. However, when we start using a more complicated heap entry in a future patch, that will get longer. Factoring out these operations lets us make future changes in one place. It also makes the code a little shorter and more readable.

Note that we actually accept indices into the queue array instead of pointers. This is slightly less flexible than passing pointers-to-pointers (we could not swap items from unrelated arrays, but we would not want to), but will make further refactoring simpler (and lets us avoid repeating "queue->array" at each callsite, which led to some long lines).

And finally, note that we are cleaning up an accidental use of a "struct commit" pointer to hold a temporary entry during swap. Even though we currently only use this code for commits, it is supposed to be type-agnostic. In practice this didn't matter anyway because we never dereferenced the commit pointer (and on most systems, the pointer values themselves are interchangeable between types).

Signed-off-by: Jeff King <peff@peff.net>
---
 prio-queue.c | 49 +++++++++++++++++++++++++------------------------
 1 file changed, 25 insertions(+), 24 deletions(-)

If two items are added to a prio_queue and compare equal, they currently come out in an apparently random order (this order is deterministic for a particular sequence of insertions and removals, but does not necessarily match the insertion order). This makes it unlike using a date-ordered commit_list, which is one of the main types we would like to replace with it (because prio_queue does not suffer from O(n) insertions).

We can make the priority queue stable by keeping an insertion counter for each element, and using it to break ties. This does increase the memory usage of the structure (one int per element), but in practice it does not seem to affect runtime. A best-of-five "git rev-list --topo-order" on linux.git showed less than 1% difference (well within the run-to-run noise).

In an ideal world, we would offer both stable and unstable priority queues (the latter to try to maximize performance). However, given the lack of a measurable performance difference, it is not worth the extra code.

Signed-off-by: Jeff King <peff@peff.net>
---
I actually tried implementing a stable queue on top of the existing
prio-queue. However, it was quite a mess. Because prio_queue only stores
one void pointer to a thing, the stable queue has to allocate its own its
(counter,thing) pair. Doing it in a separate array doesn't work (you do
not pop them in insertion order, so you end up with "holes"). So you end
up storing an extra pointer, _plus_ per-entry malloc overhead.

If we really want to offer a non-stable queue (and I do not think we do), we should probably just do two totally separate queues, or implement the whole thing with a run-time "element size" member (or even do it in macros).

I use struct assignment in the swap() function below. Do we want to replace that with a memcpy? Presumably decent compilers can turn that into the same code anyway, but I find the assignment more readable, and IIRC it has been around since C89.

 prio-queue.c | 15 ++++++++++-----
 prio-queue.h |  8 +++++++-
 2 files changed, 17 insertions(+), 6 deletions(-)

When we are traversing to find merge bases, we keep our usual commit_list of commits to process, sorted by their commit timestamp. As we add each parent to the list, we have to spend "O(width of history)" to do the insertion, where the width of history is the number of simultaneous lines of development.

If we instead use a heap-based priority queue, we can do these insertions in "O(log width)" time. This provides minor speedups to merge-base calculations (timings in linux.git, warm cache, best-of-five):

  [before]
  $ git merge-base HEAD v2.6.12
  real    0m3.251s
  user    0m3.148s
  sys     0m0.104s

  [after]
  $ git merge-base HEAD v2.6.12
  real    0m3.234s
  user    0m3.108s
  sys     0m0.128s

That's only an 0.5% speedup, but it does help protect us against pathological cases.

While we are munging the "interesting" function, we also take the opportunity to give it a more descriptive name, and convert the return value to an int (we returned the first interesting commit, but nobody ever looked at it).

Signed-off-by: Jeff King <peff@peff.net>
---
Same as what I posted a few weeks ago, but now we do not have to tweak
t6024 to account for the lack of stability.

 commit.c | 42 +++++++++++++++++++-----------------------
 1 file changed, 19 insertions(+), 23 deletions(-)

On Mon, Jul 14, 2014 at 12:40 PM, Jeff King <peff@peff.net> wrote:

The test needs the right amount of "have"s with pkt-flush inserted at the right place. If test_tick makes it happy, I think we could go with it for now. I'll try to study this code more and see if I can come up with a better test. It'll be low priority in my backlog though.

Jeff King <peff@peff.net> writes:

I don't think that this makes sense in general since it assumes the appropriate fallback behavior to be FIFO. Depending on the use case, it might be the other way round, or something else (like topology-based) entirely.

commit_list may be unsuitable as such for intermingled addition of unsorted and extraction of sorted elements (the general use case for priority queues).

I see that struct commit already contains an integer field called "index", assigned sequentially, which might conceivably be used for tie-breaking independent from the actual prio_queue use at no extra cost.

The resulting order will of course be somewhat arbitrary in a different way, but at least will correspond to the order the commits have been discovered/generated, so they should still exhibit a more topological relation than what prio_queue does without further help.

On Mon, Jul 14, 2014 at 01:02:56PM +0200, David Kastrup wrote:

Remember that this is just a tie-breaker for the regular comparison function. If you want to represent some other ordering, you are free to do the tie-breaking yourself in your comparison function. The one thing we can easily provide but do not is LIFO ordering for the tie-breaker. That would be trivial to add as a flag on the prio_queue, but I'd wait until there is actually a caller who wants it.

Yes, it's a bit hacky to provide it for cases which _don't_ care about order (or implement their own separate tie-breaker). But the worst case there is that we are wasting some memory, and I wasn't able to measure a real slow-down. I think it's a reasonable compromise given the lack of generics in C.

But if you have a case that is measurably affected, please let me know, and I can look into implementing it in a type-agnostic way (so that the embedded insertion counter becomes just another type).

I don't think it's a good idea to rely on that index, as it is anything but stable. It represents whatever order commits happened to be first touched in the current program run. So:

  1. Performing the same operation in-process versus in a sub-process
     may produce different results.

  2. Arguments to a command may have unexpected effects. E.g.,
     specifying "--tags" to "rev-list" will look up the commit at
     each tag ref, giving them much lower index numbers than they would
     if we reached only through the normal traversal.

-Peff