From: Jeff King <peff@peff•net>
To: Kristofer Karlsson <krka@spotify•com>
Cc: Derrick Stolee <stolee@gmail•com>,
Junio C Hamano <gitster@pobox•com>,
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail•com>,
git@vger•kernel.org
Subject: Re: [PATCH] revision: use priority queue in limit_list()
Date: Mon, 18 May 2026 20:54:29 -0400 [thread overview]
Message-ID: <20260519005429.GD1612961@coredump.intra.peff.net> (raw)
In-Reply-To: <CAL71e4MxhcZqxPVEe38Shuqt7h5dxLDGi66hN2cFXnmg-POKWA@mail.gmail.com>
On Sun, May 17, 2026 at 05:26:06PM +0200, Kristofer Karlsson wrote:
> Another note - I think I managed to apply the same change to
> get_revision_1 too - speeding up a monorepo "git rev-list HEAD" by
> 3.3x so it seems like a reasonable thing to do.
> This simplifies process_parents and also makes
> commit_list_insert_by_date dead code.
>
> The only caveat is that get_revision_1 starts to get messier and the
> rev_info struct needs both a prio_queue and a linked list of commits -
> and then flushing everything
> from the list into the prio_queue when executing get_revision_1.
IMHO it is worth replacing rev_info's list with a prio_queue and letting
that be the source of authority. You do have to be careful to cover
cases where the list _isn't_ date-sorted, but prio_queue supports that
with a NULL comparator.
You do still have to convert between list and queue at a few spots, but
I think in the long run many of those could be converted to use a queue.
You can see my patches to do so at:
https://github.com/peff/git jk/revs-commits-prio-queue
I've been running with them locally for a few years. Mostly I hadn't
gotten around to polishing them, and I think I had wanted to do some
more perf testing. It sounds like you have a good candidate repo for
showing off the improvement. ;)
If you'd like to go in that direction, please feel free to pick out
whatever is useful from what you find on that branch.
> I don't want to pollute this patch with that change - should I start a
> separate thread for it or just revisit this later?
> (Perhaps I have too many optimization patches in flux already)
Yes, it definitely makes sense to do that as a separate change. If you
look at the patches I linked above, note that they'll get a bit simpler
by rebasing on top of your limit_list() changes, since it does some of
the same things.
-Peff
next prev parent reply other threads:[~2026-05-19 0:54 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-14 16:51 [PATCH] revision: use priority queue in limit_list() Kristofer Karlsson via GitGitGadget
2026-05-14 19:40 ` Junio C Hamano
2026-05-14 19:57 ` Derrick Stolee
2026-05-17 16:50 ` René Scharfe
2026-05-15 4:16 ` Jeff King
2026-05-15 7:47 ` Kristofer Karlsson
2026-05-15 13:10 ` Derrick Stolee
2026-05-17 15:26 ` Kristofer Karlsson
2026-05-17 23:31 ` Junio C Hamano
2026-05-19 0:54 ` Jeff King [this message]
2026-05-19 9:33 ` Kristofer Karlsson
2026-05-19 21:56 ` Jeff King
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=20260519005429.GD1612961@coredump.intra.peff.net \
--to=peff@peff$(echo .)net \
--cc=git@vger$(echo .)kernel.org \
--cc=gitgitgadget@gmail$(echo .)com \
--cc=gitster@pobox$(echo .)com \
--cc=krka@spotify$(echo .)com \
--cc=stolee@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