Re: [PATCH 3/8] paint_down_to_common: use prio_queue

[Junio C Hamano <gitster@pobox.com>]

Jeff King <peff@peff.net> writes:

> 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).

Interesting that the queue is not "stable", but the test can still
rely on a fixed output.  While I tend to agree that for the purpose
of this code path, the order is an internal implementation detail,
but I wonder if it would benefit us a lot if we taught prio-queue to
be optionally more "stable", which would allow us to use it in other
code paths that care.  If we really wanted to, I would imagine that
we could keep the "insertion counter" in the elements of the queue
to make the result stable (i.e. the "void **array" would become
something like "struct { int insertion_ctr; void *thing; } *array").

> 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).

Heh, I should have read the below-three-dashs commentary before
commenting (I often start working from the commit messages in "git
log" and then go back to the original thread).