On Fri, Jun 10, 2011 at 12:41:39PM -0700, Shawn O. Pearce wrote: > Not really. > > The queue isn't sorting by SHA-1. Its sorting by commit timestamp, > descending. Those aren't pre-hashed. The O(N^2) insertion is because > the code is trying to find where this commit belongs in the list of > commits as sorted by commit timestamp. > > There are some priority queue datastructures designed for this sort of > work, e.g. a calendar queue might help. But its not as simple as a 1 > byte trie. All you really need is a heap-based priority queue, which gives O(lg n) insertion and popping (and O(1) peeking at the top). I even wrote one and posted it recently (I won't dig up the reference, but I posted it elsewhere in this thread, I think). The problem is that many parts of the code assume that commit_list is a linked list and do fast iterations, or even splicing. It's nothing you couldn't get around with some work, but it turns out to involve a lot of code changes. -Peff -- 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