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

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 3, 2025, 16:48 UTC
Message-ID: <xmqqtt2oe4gi.fsf@gitster.g>
In-Reply-To: <c5d91cec-3fec-422e-86d4-78767d95f208@web.de>

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

Show 13 quoted lines

> 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.