Jeff King [off-list ref] writes:
As Junio and I discussed earlier in [1], this series makes the
prio_queue struct stable with respect to object insertion (which in turn
means we can use it to replace commit_list in more places).
I don't think that this makes sense in general since it assumes the
appropriate fallback behavior to be FIFO. Depending on the use case, it
might be the other way round, or something else (like topology-based)
entirely.
commit_list may be unsuitable as such for intermingled addition of
unsorted and extraction of sorted elements (the general use case for
priority queues).
I see that struct commit already contains an integer field called
"index", assigned sequentially, which might conceivably be used for
tie-breaking independent from the actual prio_queue use at no extra
cost.
The resulting order will of course be somewhat arbitrary in a different
way, but at least will correspond to the order the commits have been
discovered/generated, so they should still exhibit a more topological
relation than what prio_queue does without further help.
--
David Kastrup
On Mon, Jul 14, 2014 at 01:02:56PM +0200, David Kastrup wrote:
Jeff King [off-list ref] writes:
quoted
As Junio and I discussed earlier in [1], this series makes the
prio_queue struct stable with respect to object insertion (which in turn
means we can use it to replace commit_list in more places).
I don't think that this makes sense in general since it assumes the
appropriate fallback behavior to be FIFO. Depending on the use case, it
might be the other way round, or something else (like topology-based)
entirely.
Remember that this is just a tie-breaker for the regular comparison
function. If you want to represent some other ordering, you are free to
do the tie-breaking yourself in your comparison function. The one thing
we can easily provide but do not is LIFO ordering for the tie-breaker.
That would be trivial to add as a flag on the prio_queue, but I'd wait
until there is actually a caller who wants it.
Yes, it's a bit hacky to provide it for cases which _don't_ care about
order (or implement their own separate tie-breaker). But the worst case
there is that we are wasting some memory, and I wasn't able to measure a
real slow-down. I think it's a reasonable compromise given the lack of
generics in C.
But if you have a case that is measurably affected, please let me know,
and I can look into implementing it in a type-agnostic way (so that the
embedded insertion counter becomes just another type).
I see that struct commit already contains an integer field called
"index", assigned sequentially, which might conceivably be used for
tie-breaking independent from the actual prio_queue use at no extra
cost.
I don't think it's a good idea to rely on that index, as it is anything
but stable. It represents whatever order commits happened to be first
touched in the current program run. So:
1. Performing the same operation in-process versus in a sub-process
may produce different results.
2. Arguments to a command may have unexpected effects. E.g.,
specifying "--tags" to "rev-list" will look up the commit at
each tag ref, giving them much lower index numbers than they would
if we reached only through the normal traversal.
-Peff