Jeff King [off-list ref] 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).
On Tue, Jul 01, 2014 at 09:23:21AM -0700, Junio C Hamano wrote:
quoted
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.
I think it is deterministic for a particular sequence of inserts/pops,
but not stable with respect to insertion order.
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").
Yeah, I think the reasons to be stable are:
1. To be on the safe side for operations like this where it
_shouldn't_ matter, but perhaps there are hidden dependencies we
don't know of.
2. To make it easier for later callers to use prio-queue for cases
where it does matter (and I think "git log" is one of these).
If we can do it without a big performance loss (and I don't see any
reason it should be any worse than a slight bump to the constant-factor
of the logarithmic operations), it probably makes sense to.
I'll take a look at it (in fact, I already implemented something like it
once long ago in the thread I linked to earlier). My sense of taste says
it should be a stable_prio_queue implemented on top of prio_queue (i.e.,
storing pointers to the struct you mention above). That means you can
still use the unstable one if you want the (presumably minor)
performance benefit, and it keeps the logic nice and tidy.
But given that we have implemented prio_queue using void pointers, I
think it would introduce an extra pointer per item and an extra layer of
indirection on each access. So maybe it is better to just build it in.
The low-cost alternative is to implement prio_queue to hold items of
arbitrary size. I'm not sure if that is the worth the complexity and
maintenance cost.
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).
I always wonder how people read those. I tend to write them as if people
have (just) read the commit message, but not yet read the patch.
-Peff
PS Thanks for your earlier comments on the actual commit-slab painting
algorithm. Responding to those is taking more thinking, and I haven't
gotten to it yet, but it's on my agenda.