From: "René Scharfe" <l.s.r@web•de>
To: Junio C Hamano <gitster@pobox•com>
Cc: Lidong Yan <yldhome2d2@gmail•com>, Git List <git@vger•kernel.org>,
Jeff King <peff@peff•net>, Justin Tobler <jltobler@gmail•com>
Subject: Re: [PATCH v2 1/3] commit: convert pop_most_recent_commit() to prio_queue
Date: Mon, 4 Aug 2025 21:56:27 +0200 [thread overview]
Message-ID: <a35aae22-da05-4098-88d0-f8dcb50a9a0f@web.de> (raw)
In-Reply-To: <xmqqtt2oe4gi.fsf@gitster.g>
On 8/3/25 6:48 PM, Junio C Hamano wrote:
> 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?
Well, we could reestablish the heap at a cost of O(N), which only pays
off if it's less than the O(P log N) needed for regular puts of P
parents, with N being the number of queue elements. This starts to
lose once queues become too long -- just when an optimization would be
most welcome. So it seems impractical.
We could replace our binary heap with an algorithm that has O(1)
inserts, like a pairing heap, though.
René
next prev parent reply other threads:[~2025-08-04 19:56 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-07-15 14:35 [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue René Scharfe
2025-07-15 14:51 ` [PATCH 1/3] " René Scharfe
2025-07-15 19:23 ` Junio C Hamano
2025-07-15 20:47 ` Justin Tobler
2025-07-16 9:39 ` René Scharfe
2025-07-16 5:05 ` Jeff King
2025-07-16 9:39 ` René Scharfe
2025-07-17 8:22 ` René Scharfe
2025-07-19 6:55 ` Jeff King
2025-07-19 6:57 ` Jeff King
2025-07-19 11:15 ` René Scharfe
2025-07-20 0:03 ` Jeff King
2025-07-20 1:22 ` Junio C Hamano
2025-07-16 22:23 ` Junio C Hamano
2025-07-17 8:22 ` René Scharfe
2025-07-15 14:51 ` [PATCH 2/3] prio-queue: add prio_queue_replace() René Scharfe
2025-07-16 5:09 ` Jeff King
2025-07-16 9:38 ` René Scharfe
2025-07-17 9:20 ` René Scharfe
2025-07-19 7:02 ` Jeff King
2025-07-15 14:51 ` [PATCH 3/3] commit: use prio_queue_replace() in pop_most_recent_commit() René Scharfe
2025-07-15 20:43 ` Junio C Hamano
2025-07-16 9:38 ` René Scharfe
2025-07-16 0:07 ` [PATCH 0/3] commit: convert pop_most_recent_commit() to prio_queue Junio C Hamano
2025-07-16 5:15 ` Jeff King
2025-07-16 9:38 ` René Scharfe
2025-07-19 6:45 ` Jeff King
2025-07-16 14:49 ` Junio C Hamano
2025-07-18 9:09 ` [PATCH v2 " René Scharfe
2025-07-18 9:39 ` [PATCH v2 1/3] " René Scharfe
2025-07-21 14:02 ` Lidong Yan
2025-08-03 9:54 ` René Scharfe
2025-08-03 16:48 ` Junio C Hamano
2025-08-04 19:56 ` René Scharfe [this message]
2025-07-18 9:39 ` [PATCH v2 3/3] commit: use prio_queue_replace() in pop_most_recent_commit(),MIME-Version: 1.0 René Scharfe
2025-08-03 11:12 ` Johannes Schindelin
2025-08-03 11:33 ` René Scharfe
2025-07-18 9:39 ` [PATCH v2 2/3] prio-queue: add prio_queue_replace() René Scharfe
2025-07-19 7:04 ` [PATCH v2 0/3] commit: convert pop_most_recent_commit() to prio_queue Jeff King
2025-07-22 6:26 ` SZEDER Gábor
2025-07-22 14:27 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=a35aae22-da05-4098-88d0-f8dcb50a9a0f@web.de \
--to=l.s.r@web$(echo .)de \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=jltobler@gmail$(echo .)com \
--cc=peff@peff$(echo .)net \
--cc=yldhome2d2@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox