Re: [PATCH] packfile: fix perf regression with many packsy

[Patrick Steinhardt <ps@pks.im>]

On Thu, Aug 13, 2026 at 12:42:10PM +0200, Johannes Schindelin wrote:
> Hi Patrick,
> 
> On Thu, 13 Aug 2026, Patrick Steinhardt wrote:
> 
> > On Thu, Aug 13, 2026 at 11:20:11AM +0200, Johannes Schindelin wrote:
> > > On Thu, 13 Aug 2026, Patrick Steinhardt wrote:
> > > > I wonder whether we should slightly reformulate this and rename `is_new`
> > > > to `accept_duplicates`. Because ultimately, that is what we're doing
> > > > now: instead of ensuring that the packfile is unique in the list, we
> > > > just don't care and just append the entry to the list.
> > > 
> > > Hmm. I don't quite agree, we're _not_ accepting duplicates. We know that
> > > those packfiles _cannot_ be duplicates.
> > 
> > I know that we're not, but this is only because the caller knows that
> > the packs are new. Seen outside that context though the new parameter
> > really just tells us whether or not we want to deduplicate packs or not.
> > 
> > Anyway, I'm splitting hairs and I won't insist on a change here.
> 
> You do have a point, though, `is_new` is too narrow. How about
> `skip_dup_check`?

Sounds reasonable.

> > > > An alternative would be to use a hashmap here that tracks the packs that
> > > > have already been added. It has the advantage that it also covers the
> > > > `prepend()` operation and that callers don't have to be aware of this
> > > > mechanism at all. Furthermore, moving preexisting entries to the back or
> > > > front could become O(logn) if the list was doubly-linked. We do this
> > > > operation quite often to re-sort entries in the list when looking up
> > > > objects.
> > > 
> > > Indeed, that was my initial reaction, too. I was well on my way to start
> > > writing a hashmap-based fix when the AI assistant pointed out that no
> > > duplicates could possibly exist yet.
> > > 
> > > > Overall though I'm not quite sure whether the added complexity would be
> > > > worth it, see below patch.
> > > 
> > > Wow, you got a lot further than I did! And yes, I agree that we do not
> > > (yet?) need to deal with the added complexity.
> > 
> > I may want to pursue this patch anyway, as I think that the reordering
> > would be sped up by that change quite signifcantly. And that would make
> > a difference indeed when you have 38k packfiles, at least when you
> > assume that objects are evenly distributed across all of those and that
> > we perform reads of random objects.
> > 
> > I could do that tomorrow, and in that case it'd supersede your patch.
> 
> I don't think that it would _quite_ supersede this patch. Sure, while
> searching through a hashset instead of a single-linked list is faster, it
> is not as fast as skipping the search altogether.

I guess that's fair. Let's move forward with your patch for now then.

Thanks!

Patrick