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

From: Jeff King <peff@peff.net>
Date: Jul 21, 2014, 09:07 UTC
Message-ID: <20140721090735.GA14548@peff.net>
In-Reply-To: <87tx6k5hjz.fsf@fencepost.gnu.org>

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

Show 10 quoted lines

> 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