Re: [PATCH 2/2] commit: use a priority queue in merge base functions

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 30, 2012, 16:23 UTC
Message-ID: <7v3934tkle.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20120830125421.GA5687@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 7 quoted lines

> Anyway, since this isn't yielding any performance benefit, I'm not going
> to go down that route. But stability of the queue is something that we
> need to consider if we ever do replace commit_list with a different data
> structure.
>
> Here's the patch to make the existing priority queue stable (by wasting
> space) in case we ever want to use it.

Thanks for being thorough and showing a good analysis.

If we want stability, the space to hold insertion counter is not "wasted", by the way.

I actually think the generic "queue" implementation may want to handle elements that are not just single pointers. Just like qsort() is not about sorting an array of pointers but it is about sorting an array of elements of caller specified size, perhaps "queue" can hold elements of size the caller specified (set in stone when the queue is initialized).

Then, a caller that wants a stable priority queue of commits can tell the queue to manage "struct { struct commit *c; int gen; }", use the "gen" field for stability in its comparison callback, etc., while a caller that does not need stability can tell the queue to manage "struct commit *". That way, the generic queue layer does not have to worry about wasting the insertion counter space, no?