On Fri, Jul 25, 2025 at 07:02:43AM -0400, Jeff King wrote: > On Thu, Jul 24, 2025 at 03:03:27PM +0200, Patrick Steinhardt wrote: > > > I've quickly hacked something together now, see the work-in-progress > > patch below. The patch does not yet handle reflogs, but that isn't too > > hard to implement. > > > > And these changes indeed speed up things by quite a lot: instead of > > hours it now takes 7 seconds :) I'll polish this patch series and will > > likely send it in tomorrow. > > Cool. I agree with all of the pain points you outlined, and the general > direction. There was one other sub-optimal thing I noticed, which was... > > > - refs_for_each_ref(get_main_ref_store(the_repository), > > - read_remote_branches, &rename); > > [...] > > + result = refs_for_each_rawref(get_main_ref_store(the_repository), > > + queue_one_rename, &rename); > > Both before and after your patch, we're iterating over _all_ refs and > skipping ones that aren't in "refs/remotes/<remote>/". If we just ask to > iterate over that subset of refs, then we save the effort of iterating > over the others that we don't care about. > > But: > > 1. We have refs_for_each_ref_in() and refs_for_each_rawref(), but no > refs_for_each_rawref_in(). Feels like it should be easy to add it, > though. > > 2. It's an obvious small optimization, but it doesn't help us in a > big-O way. Iterating the refs is obviously O(n), and in the worst > case rewriting the packed-refs file is likewise O(n). So I wouldn't > expect to see the dramatic improvements you found by removing the > quadratic bits. But I'd bet it's still measurable in a repo with a > lot of refs (and maybe with reftables it actually would be bigger, > since the goal there is to amortize the rewrites). Yeah, I was wondering whether to re-do this part while at it. I initially decided to not do so, but I guess that was just me being lazy. Patrick
