threads / discuss / 61426

Feature request: secondary index by path fragment

Subject: Feature request: secondary index by path fragment

## tl;dr

4 messages between May 6, 2024 and May 7, 2024.

replies: 3people: 3as markdown or json

Robin H. Johnson· May 6, 2024, 23:11 UTC · lore

Maybe this already happens in the code, but if not, please consider it as a feature request.

Gentoo has some tooling that boils down to repeated runs of 'git log -- somepath/' via cgit as well as other shell tooling.

If the path is relatively deep for the tree (e.g. to a specific file or sub-directory), the size of history [1] makes that a very slow operation to go all the way back to the initial repo commit: ~12 seconds per operation on fast hardware, ~45 seconds on slower harder - even with the packs cached.

I was wondering if Git could gain a secondary index of commits, based on path prefixes, that would speed up the 'git log' run.

It would need to be fast to append to the secondary index, because Gentoo gets a steady flow of commits 24/7.

[1] 825k+ commits based on GitHub stats.
-- 
Robin Hugh Johnson
Gentoo Linux: Dev, Infra Lead, Foundation President & Treasurer
E-Mail   : robbat2@gentoo.org
GnuPG FP : 11ACBA4F 4778E3F6 E4EDF38E B27B944E 34884E85
GnuPG FP : 7D0B3CEB E9B85B1F 825BCECF EE05E6F6 A48F6136
Junio C Hamano· May 6, 2024, 23:22 UTC · re: Robin H. Johnson · lore

Re: Feature request: secondary index by path fragment

"Robin H. Johnson" <robbat2@gentoo.org> writes:
Show 5 quoted lines
> Gentoo has some tooling that boils down to repeated runs of 'git log -- somepath/'
> via cgit as well as other shell tooling.
> ...
> I was wondering if Git could gain a secondary index of commits, based on
> path prefixes, that would speed up the 'git log' run.
Perhaps the bloom filters are good fit for the use case?
Patrick Steinhardt· May 7, 2024, 04:25 UTC · re: Junio C Hamano · lore

Re: Feature request: secondary index by path fragment

On Mon, May 06, 2024 at 04:22:11PM -0700, Junio C Hamano wrote:
Show 9 quoted lines
> "Robin H. Johnson" <robbat2@gentoo.org> writes:
> 
> > Gentoo has some tooling that boils down to repeated runs of 'git log -- somepath/'
> > via cgit as well as other shell tooling.
> > ...
> > I was wondering if Git could gain a secondary index of commits, based on
> > path prefixes, that would speed up the 'git log' run.
> 
> Perhaps the bloom filters are good fit for the use case?

Yes, Bloom filters are the first thing that pop into my mind here as they are exactly designed to solve this problem. So if you rewrite your commit graphs with `git commit-graph write --changed-paths --reachable` you should hopefully see a significant speedup.

It does surface some a usability issues though:
  - There is no easy way to enable the computation of bloom filters via
    configuration, to the best of my knowledge.
  - How would a non-Git-expert know?

It makes me wonder whether we can maybe enable generation of Bloom filters by default. The biggest downside is of course that writing commit graphs becomes slower. But that should happen in the background for normal users anyway, and most forges probably hand-roll maintenance and thus wouldn't care.

Is there any other thing I'm missing why those are not written by default?

Patrick
Robin H. Johnson· May 7, 2024, 05:38 UTC · re: Patrick Steinhardt · lore

Re: Feature request: secondary index by path fragment

On Tue, May 07, 2024 at 06:25:08AM +0200, Patrick Steinhardt wrote:
Show 15 quoted lines
> On Mon, May 06, 2024 at 04:22:11PM -0700, Junio C Hamano wrote:
> > "Robin H. Johnson" <robbat2@gentoo.org> writes:
> > 
> > > Gentoo has some tooling that boils down to repeated runs of 'git log -- somepath/'
> > > via cgit as well as other shell tooling.
> > > ...
> > > I was wondering if Git could gain a secondary index of commits, based on
> > > path prefixes, that would speed up the 'git log' run.
> > 
> > Perhaps the bloom filters are good fit for the use case?
> 
> Yes, Bloom filters are the first thing that pop into my mind here as
> they are exactly designed to solve this problem. So if you rewrite your
> commit graphs with `git commit-graph write --changed-paths --reachable`
> you should hopefully see a significant speedup.

Good news & bad news. "git log -- sys-apps/pv >/dev/null" as my testcase from before: The fast system (2.45.0) went from 11 seconds to ~1 second! The slow system (2.44.0) went from 45 seconds to 49 seconds :-(.

I'll try to trace down why one system slowed down.

commit-graph command: fast: 1m10s slow: 3m43s

Show 5 quoted lines
> It makes me wonder whether we can maybe enable generation of Bloom
> filters by default. The biggest downside is of course that writing
> commit graphs becomes slower. But that should happen in the background
> for normal users anyway, and most forges probably hand-roll maintenance
> and thus wouldn't care.

Most repos are also MUCH smaller than this, so it should be safe to enable.

-- 
Robin Hugh Johnson
Gentoo Linux: Dev, Infra Lead, Foundation President & Treasurer
E-Mail   : robbat2@gentoo.org
GnuPG FP : 11ACBA4F 4778E3F6 E4EDF38E B27B944E 34884E85
GnuPG FP : 7D0B3CEB E9B85B1F 825BCECF EE05E6F6 A48F6136

← back to recent threads