Comment 4 for bug 535118

Benjamin:
Thanks for the suggestions on improving the revision-walking code. One more improvement that could make a lot of difference in your implementation would be to avoid re-sorting the list on every iteration by using a priority queue (e.g. with the heapq module in Python's standard library).

I have a long patch series that implements revision-walking in a general way using a pqueue with lots of additional options. For some solid benchmark numbers: I can walk the >23k commits in git.git, starting from a loose repo and a hot disk cache, in about 8 seconds wall time. About 80% of that time is spent in commit parsing, so I think my commit-walking code is pretty fast. To put that in perspective, 'git log' on the same repo is about 10x faster.

My benchmark script is attached. I'll share my implementation when I can, but unfortunately it's at the end of a 40+ patch series at the moment.