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

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 1, 2014, 16:23 UTC
Message-ID: <xmqqionhxd3a.fsf@gitster.dls.corp.google.com>
In-Reply-To: <20140625233952.GC23146@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 23 quoted lines

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

Show 5 quoted lines

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