Jeff King <peff@xxxxxxxx> 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).
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html