Re: [RFC/PATCH 0/4] commit lists as priority queues

From: Junio C Hamano <gitster@pobox.com>
Date: May 20, 2011, 22:03 UTC
Message-ID: <7v4o4p2foj.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20110519212349.GA28589@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 6 quoted lines

> ... I also had a feeling we
> could use a faster commit_list in other places, since get_revision is
> all based around the same pop-and-push-the-parents workflow. But after
> spending a few hours on it, it seems that _lots_ of places in the code
> work on the assumption of a linked list (or at least doing very simple
> in-order traversal), and the changes got very ugly very quickly.

I recall looking at the same codepaths a few years ago for different reasons. get_revision() callchain does a _lot_ of alloc/free, so I naturally wanted to catch all the allocations and frees to replace them with a custom allocator that slices from a larger slab. It involved too many places so I decided it wasn't really worth doing only that change without other benefit (e.g. lifting the "listness" assumption), and stopped.

If somebody is interested to tackle it, we would probably need a two step conversion process. First introduce an abstracted interface that passes around the "list-as-a-whole" object with a few selected methods (e.g. drop an element into it at the sorted location and get a "cursor" that points at it, given a "cursor", grab an element from the list, increment the "cursor" to point at the next object, etc.), choosing a set just sufficient to express the patterns of accesses the current codebase makes, and implement the API over the existing linked-list implementation to convert all the callers. After making sure this works, update the API implementation with the queue in this patch.

Or something like that.

Show 5 quoted lines

> ... And
> performance-wise, it doesn't seem to be a huge problem, mainly because:
>
>   1. We don't tend to put more items in a commit_list than the width of
>      the history graph. So our "n" tends to be in the dozens at most.

I was worried that you may end up with many concurrent traversal going in a very bushy history (think: traversing from the tip of "next"), but I agree that it would be in the order of dozens, not thousands.