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

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

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to