carlosmn/libgit2 — comment on commit 9656377b5481680be279765c30b8c3fba35f4643
File: src/revwalk.c line 97
By peff:

How hard would it be to replace this commit_list with a priority queue? There are parts of git that experience O(n^2) behavior inserting into the commit list. The worst offender was hacked around by fce87ae (Fix quadratic performance in rewrite_one., 2008-07-12), but I've had to fix a few others. E.g., ea5f220 (fetch: avoid repeated commits in mark_complete, 2011-05-19), which was triggered by large numbers of refs (like we have in our network repos). But even with the hack in fce87ae, I think each insertion is O(width of graph), where the width is the number of simultaneous lines of development.

I wrote a priority queue implementation and did a test patch to fix the same problem as ea5f220. It works, but we didn't end up applying it because the commit_list data structure is so embedded in the git code, and ripping it out would involve a lot of rewriting. Since libgit2 is starting from scratch, it might be a good time to see if we can use a more sensible data structure.