Jeff King <peff@xxxxxxxx> 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. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html