René Scharfe <l.s.r@xxxxxx> writes: > > +# > +# Creates lots of merges to make history traversal costly. In > +# particular it creates 2^($max_level-1)-1 2-way merges on top of > +# 2^($max_level-1) root commits. E.g., the commit history looks like > +# this for a $max_level of 3: > +# > +# _1_ > +# / \ > +# 2 3 > +# / \ / \ > +# 4 5 6 7 > +# > +# The numbers are the fast-import marks, which also are the commit > +# messages. 1 is the HEAD commit and a merge, 2 and 3 are also merges, > +# 4-7 are the root commits. > +# I feel that the reason there's no significant performance improvement is probably because mostly we are using the priority queue to sort O(siblings) nodes. For example, in this case, the most time-consuming operation is when the priority queue or commit list contains 4 and 5, and we then need to insert 6 and 7. Assuming the maximum number of siblings is W and the number of nodes is N, the time complexity with a commit list is O(W² × N), while using a priority queue gives O(W log W × N). Perhaps in many projects, W isn't particularly large, which results in the performance improvement not being very significant. - Lidong
