On Mon, Jul 14, 2014 at 01:02:56PM +0200, David Kastrup wrote:
> Jeff King <peff@xxxxxxxx> 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.
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
--
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