Re: [PATCH/RFH 0/3] stable priority-queue

[Jeff King <peff@peff.net>]

On Mon, Jul 14, 2014 at 01:02:56PM +0200, David Kastrup wrote:

> Jeff King <peff@peff.net> 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