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

[Junio C Hamano <gitster@pobox.com>]

Jeff King <peff@peff.net> writes:

> ... 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.

> ... 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.