[PATCH 3/8] paint_down_to_common: use prio_queue

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.

The downside is that our priority queue is not stable, which means that commits with the same timestamp may not come out in the order we put them in. You can see this in the test update in t6024. That test does a recursive merge across a set of commits that all have the same timestamp. For the virtual ancestor, the test currently ends up with blob like this:

    <<<<<<< Temporary merge branch 1
    <<<<<<< Temporary merge branch 1
    C
    =======
    B
    >>>>>>> Temporary merge branch 2
    =======
    A
    >>>>>>> Temporary merge branch 2

but with this patch, the positions of B and A are swapped. This is probably fine, as the order is an internal implementation detail anyway (it would _not_ be fine if we were using a priority queue for "git log" traversal, which should show commits in parent order).

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>
---
This one is not strictly required for the series; it's just that I'm
adding what is essentially a clone of paint_down_to_common later in the
series. I wanted to use the priority queue there, too, so I looked into
using it here.

I'm slightly hesitant because of the stability thing mentioned above. I _think_ it's probably fine. But we could also implement a stable_prio_queue on top of the existing prio_queue if we're concerned (and that may be something we want to do anyway, because "git log" would want that if it switched to a priority queue).

I had no recollection while writing this patch, but after searching the list for "stable priority queue", I realized that Junio and I discussed it quite extensively a few years ago:

  http://thread.gmane.org/gmane.comp.version-control.git/204386/focus=204534

I think the conclusion there is that what this patch does is acceptable.

 commit.c                   | 42 +++++++++++++++++++-----------------------
 t/t6024-recursive-merge.sh |  2 +-
 2 files changed, 20 insertions(+), 24 deletions(-)