Description
Currently there is branching code in git_odb::compound::Db::locate(…) to workaround a borrowcheck shortcoming using the upcoming Polonius borrow checker.
Without the workaround, the lookup costs are doubled.
Using Polonius solves the problem but comes at a cost.
- It requires the nightly compiler (forcing gitoxide to be compiled with nightly if that code-path is chosen).
- The borrow checker performance is reduced and can 'explode' for certain crates like
tinyvec. - It's unclear when Polonius will be stable.
Here is @joshtriplett thoughts on how to resolve this:
When first initializing the Db and looking up all the alternates, rather than recursing, collect all of the alternates as a top-level Vec of
(Packs, Loose), so that alternates themselves never have alternates. That way, you don't have to recurse, and there's only one level of alternates. Then, in the loop over alternates, rather than recursively calling locate, just inline the same code that looks in packs and loose, but without the check for alternates.
I think the simplest way to do that would be to have a version ofat(at_no_alternates) that ignores alternates entirely, and then have the top-levelatcollect a deduplicated list of alternates and callat_no_alternateson each one.
Additional Information
Also have a look at how this is currently done for looking up objects in packs. The gist is to get an index of where the object is found first, bypassing the need for borrowing an output buffer, and fill the buffer if an index was found.