On Wed, Oct 16, 2024 at 10:48:28PM -0400, Jeff King wrote: > On Wed, Oct 16, 2024 at 06:11:47PM -0400, Taylor Blau wrote: > > > On Wed, Oct 16, 2024 at 08:00:30AM +0200, Patrick Steinhardt wrote: > > > But there is one exception here where we _can_ get away with sorting > > > refs while streaming: ref backends sort references returned by their > > > iterators in lexicographic order. So if the following conditions are all > > > true we can do iterative streaming: > > > > > > - The caller uses at most a single name pattern. Otherwise we'd have > > > to sort results from multiple invocations of the iterator. > > > > > > - There must be at most a single sorting specification, as otherwise > > > we're not using plain lexicographic ordering. > > > > > > - The sorting specification must use the "refname". > > > > > > - The sorting specification must not be using any flags, like > > > case-insensitive sorting. > > > > Perhaps a niche case, but what about ancient packed-refs files that were > > written before the 'sorted' capability was introduced? > > We should be OK there. In that case we actually read in and sort the > packed-refs entries ourselves. We have to, since we do an in-order merge > with the loose refs while iterating. > > I do think this optimization is worth doing, and not a problem with our > current backends. The biggest worries would be: > > 1. Some new ref backend that doesn't return sorted results. I find > this unlikely, and anyway it's easily caught by having coverage in > the test suite (which I assume we already have, but I didn't look). My assumption is that a ref iterator that _isn't_ sorted would lead to undesirable behaviour. I'd be surprised if git-show-ref(1) started to show refs in a random order. So we have essentially baked the requirement that ref iterators return refs in lexicographic order into our codebase already. > 2. Some new flag combination that requires disabling the optimization, > and which must be dealt with in the code. This seems unlikely to me > but not impossible. I think enabling the optimization is worth it, > though. And this part is an issue with or without my patch. The logic we have in the ref-filter API is quite fragile, and everybody who wants to add some new flags must remember to update `can_do_iterative_format()`. I'm not really a huge fan of that, but on the other hand the subsystem does not change all that frequently anyway. > > > to sort results from multiple invocations of the iterator. > > I think this part is erring on the cautious side, as we can often > collapse these into a single iteration due to the ref-prefix work. It > may be OK to keep using the slower code here if multiple patterns aren't > commonly used, but I'd suspect that: > > git for-each-ref --sort=refname refs/heads refs/tags > > could benefit. Mh. So we do end up using `refs_for_each_fullref_in_prefixes()`, which may or may not end up collapsing the prefixes. We do sort and dedup the prefixes via `find_longest_prefixes()`, so we don't have to worry about e.g. `git for-each-ref refs/tags refs/heads refs/tags`. So... it should be fine to also use this with multiple patterns? None of our tests fail, either, which reassures me a bit. I'll send a v2 that loosens this requirement. Thanks for your input! Patrick
