Re: [PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue

[Junio C Hamano <gitster@pobox.com>]

René Scharfe <l.s.r@web.de> writes:

> We add and retrieve each commit in the (relevant part of) history.  That
> takes O(N) and O(1) for the sorted list, and O(log N) and O(log N) for
> the prio_queue, where N is the length of the list.
>
> So the best-case history is a string of single-parent commits, keeping
> only a single item on the list/queue throughout.  That requires no
> sorting or heaping, making the additions and retrievals O(1).  The
> overall complexity is then O(N) for both variants, N being the number
> of commits in the history.
>
> Worst-case history might be a single merge of all commits -- a
> centipede or myriapod?  With all commits on the sorted list we get a
> complexity of O(N²) for the traversal, and O(N log N) with a prio_queue.

In other words, for a typical two-parent merge, we peek the current
one, "replace" it with its first parent and then do the usual "put
and sift it down into place" for the second one.  

I am wondering if there is a more optimization opportunity if we
allowed "put more than one, and then sift all of them down into
place".  In other words, if I told the machinery:

    I am doing this put.  I promise I won't do get until I say "now
    I'll start doing get's, so you are free to delay your internal
    state maintenance and do so immediately before my next 'get'".

and did such put's a few times before I do a 'get', would there be a
way to teach the machinery to take advantage of the promise?

In any case, it is very much welcome to speed up "describe" with a
better data structure and algorithm.  Will queue.

Thanks.