🎉 Introducing gix index entries 🎉

[Byron]

Important

What follows is not an apples-to-apples comparison as in this version of gix, it will not validate the index's hash. Doing so costs significant amounts of time to the point where gix is only 20% faster than git when reading big index files. However, when index.skipHash is enabled and both don't validate the hash, gix is still 2.17x faster.

---

gix index entries is gitoxide's version of git ls-files, with some added features that I always wanted to have. As such, it mostly prints files that are in the index, i.e. under version control, but with a twist:

.cargo/config.toml ❌
.editorconfig
.gitattributes
[..]
gix-config/tests/fixtures/multi-core.txt (text, eol=lf)
gix-config/tests/fixtures/repo-config.crlf (text, eol=crlf)
[..]

By default, it also displays all attributes added via .gitattribute and .gitignore files, soometimes with surprising revelations when one realises that some ignored files have been checked in and are marked with a big red cross.

That alone makes it quite useful, but with the right pathspec it's also possible to drill in.

What are all the files that need git-lfs one might ask with an incantation like gix index entries ':(attr:filter=lfs)':

❯ gix index entries ':(attr:filter=lfs)'
gix-commitgraph/tests/fixtures/generated-archives/generation_number_overflow.tar.xz (diff=lfs, merge=lfs, -text, filter=lfs)
gix-commitgraph/tests/fixtures/generated-archives/octopus_merges.tar.xz (diff=lfs, merge=lfs, -text, filter=lfs)
[..]

The wonky expression :(attr:filter=lfs) is actually just one way of writing a pathspec.

About git-pathspecs

When interacting with git commands that take file path, that innocent looking path is actually a full-blown pathspec. Most of us won't ever realise this as expressions like * are typically expanded by the shell anyway, and whatever we do with paths just works.

Or does it?

On a case-insensitive filesystem as they occour naturally on Windows or MacOS, one could try the following:

❯ git init -q new && cd new
touch File && git add file && git commit -q -m init >/dev/null; echo $?
1

Indeed, the commit failed because the file File wasn't added even though git add didn't fail. What failed was git commit which didn't have anything to add to the commit.

With a trick, we can lure out the pathspecish nature of the innocent file-path we mistyped the first letter of.

❯ git add 'fil?'
fatal: pathspec 'fil?' did not match any files

But once the case is corrected, it does work:

❯ git add 'Fil?' && git commit -m init; echo $?
[main (root-commit) 8b5429d] init
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 File
0

Pathspecs are case-sensitive by default even if the underlying filesystem is not.

However, they can also do additional tricks, which are described quite concisely in the git-glossary, and I wasn't able to find a dedicated chapter akin to the one for git-attributes for example. To wrap up with something useful, here is how you can get everything under tests/ while ignoring shell scripts:

gix index entries /tests ':!*.sh'

Performance

Supporting pathspecs is great, but will it be fast enough? For those who want to reproduce it on their machine, there is the folded "Data" section at the bottom of the document. Note that for each run we made sure that the output git and gix match perfectly.

Before we start, note that r2k is the gitoxide repo with a mere 1994 files, while r370k is the WebKit repository with ~370,000 of them.

baseline - no pathspec

This is to see how fast it can be at best by merely dumping the index paths to standard out without doing any extra processing.

• hyperfine --warmup 3 'git ls-files' 'gix index entries --no-attributes' -N

time	git	gix	factor
r2k	8.2ms	4.3ms	1.91x
r370k	70.6ms	28.3ms	2.49x

It looks like gix gets better the more work there is by taking only half the time git takes to output 370k paths.

single attribute lookup

Attribute lookup is expensive as many paths have to be matched against many globs which are on top of that dependent on the input path.

• r2k = hyperfine --warmup 1 "git ls-files ':(attr:filter=lfs)'" "gix index entries --no-attributes ':(attr:filter=lfs)'" -N
• r370k = hyperfine --warmup 1 "git ls-files ':(attr:export-ignore)'" "gix index entries --no-attributes ':(attr:export-ignore)'" -N

time	git	gix	factor
r2k	10.1ms	6.3ms	1.60x
r370k	1068ms	397ms	2.69x

It's strange to see that git is that much slower in the r370k case, as it's unlikely that gix matching engine is this much faster. Apparently it manages to do way less work for the same result.

single attribute lookup - more fair


Since the algorithm used by gix in the case above, with --no-attributes is a bit different, maybe some special optimization sneaks in. Now we leave --no-attributes out which means that gix will use worktree attributes first, forcing it to touch disk each time the directory of a path to match is changing (this time turned out to be worth 70ms). Further, much like git, gix it will now query all attributes instead of just a single one.

• hyperfine --warmup 1 "git ls-files ':(attr:export-ignore)'" "gix index entries ':(attr:export-ignore)'" -N

time	git	gix	factor
r370k	1069ms	736ms	1.45x

As expected, less optimal attribute matching bears a cost, but gix is still significantly faster at that. It's worth noting that gix now also outputs more information, which represents another cost that git doesn't have, even though it's probably quite minor.

single glob

Much more common than attribute pathspecs certainly are those with shell-globs, which is also the default globbing mode in pathspecs.

• hyperfine --warmup 1 "git ls-files 'Web*'" "gix index entries --no-attributes 'Web*'" -N

time	git	gix	factor
r370k	33.0ms	18.5ms	1.78x

It's interesting that gix is still is faster - it must be more optimal implementation with less losses, as both most definitely do the same amount of work.

trivial prefix

Special optimisations are possible if the pathspecs have a common prefix. With it, one is able to work only on a subset of the entries in the index which can lead to significant speedups.

• hyperfine --warmup 1 "git ls-files WebDriverTests" "gix index entries --no-attributes WebDriverTests" -N

time	git	gix	factor
r370k	36.5ms	18.7ms	1.95x

In this case, the set of paths to work on is reduced to 828, and to my mind it's surprising is still takes that long. A lot of time is spent, of course, to read the entire 53MB index even though most of it remains unused.

Bonus: --recurse-submodules on Rust @ a39bdb1d6b9eaf23f2636baee0949d67890abcd8

With gix v0.28.0-233-gec1e5506e on the Rust repository we see what happens if --recurse-submodules is used, also in comparison with invocations that don't recurse into submodules.

time	git	gix	factor
no-recurse	14.9ms	7.2ms	2.07x
recurse	41.9ms	22.5ms	1.86x

It's interesting that there is overhead in dealing with recursion into submodules, which seems to weigh significantly enough to make gix loose some of its performance head-room. One may wonder if this trend continues to break-even, or if no-recurse version of git just has a disadvantage related to getting started.

Conclusion

pathspecs are a powerful and probably undervalued feature, which now is fully supported by gitoxide to enable a variety of features that build on it. gix index entries [PATHSPEC ...] is the first of many more gix commands to come, showing how much performance we can expect to gain when using it.

Q&A

Q: What's the deal with --no-attributes?

This is necessary to make gix index entries comparable to git ls-files. Without it, gix will do a lot of extra work which will be noticeable in the very large repositories we look at here.

Data

Programs

✦ ❯ git --version && gix --version
git version 2.39.2 (Apple Git-143)
gix v0.28.0-137-g10da05a76

Datasets

• https://github.com/Byron/gitoxide @ 9f4dfe0 with 1994 index entries (r2k)
• https://github.com/WebKit/WebKit @ 91f7b27a2c241b8753006ec66762aacbd2c66089 with 369084 index entries (r370k)

Runs

Baseline - no pathspec

r2k

❯ sha1sum <(git ls-files) <(gix index entries --no-attributes)
d1a185e743a7741aa42a7b1a2fe134dd189c7d0b  /dev/fd/11
d1a185e743a7741aa42a7b1a2fe134dd189c7d0b  /dev/fd/12

❯ hyperfine --warmup 3 'git ls-files' 'gix index entries --no-attributes' -N
Benchmark 1: git ls-files
  Time (mean ± σ):       8.2 ms ±   0.3 ms    [User: 4.1 ms, System: 2.5 ms]
  Range (min … max):     7.8 ms …  10.1 ms    296 runs

Benchmark 2: gix index entries --no-attributes
  Time (mean ± σ):       4.3 ms ±   0.1 ms    [User: 2.0 ms, System: 1.2 ms]
  Range (min … max):     4.1 ms …   5.5 ms    699 runs

  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.

Summary
  gix index entries --no-attributes ran
    1.89 ± 0.10 times faster than git ls-files

r370k

✦ ❯ sha1sum <(git ls-files) <(gix index entries --no-attributes)
64a75a6a91af9aafc64b3c671111706c852bc0e8  /dev/fd/11
64a75a6a91af9aafc64b3c671111706c852bc0e8  /dev/fd/12

✦ ❯ hyperfine --warmup 3 'git ls-files' 'gix index entries --no-attributes' -N
Benchmark 1: git ls-files
  Time (mean ± σ):      70.6 ms ±   0.4 ms    [User: 68.2 ms, System: 27.3 ms]
  Range (min … max):    69.9 ms …  71.4 ms    42 runs

Benchmark 2: gix index entries --no-attributes
  Time (mean ± σ):      28.3 ms ±   0.7 ms    [User: 22.8 ms, System: 31.4 ms]
  Range (min … max):    27.1 ms …  30.4 ms    105 runs

Summary
  gix index entries --no-attributes ran
    2.49 ± 0.06 times faster than git ls-files

Single attribute lookup

r2k

❯ sha1sum <(git ls-files  ':(attr:filter=lfs)') <(gix index entries --no-attributes  ':(attr:filter=lfs)')
b4c7c488fc15b98d47b2d58cb7526e11a0cd4345  /dev/fd/11
b4c7c488fc15b98d47b2d58cb7526e11a0cd4345  /dev/fd/12

❯ hyperfine --warmup 1 "git ls-files  ':(attr:filter=lfs)'" "gix index entries --no-attributes  ':(attr:filter=lfs)'" -N
Benchmark 1: git ls-files  ':(attr:filter=lfs)'
  Time (mean ± σ):      10.1 ms ±   0.4 ms    [User: 5.2 ms, System: 3.2 ms]
  Range (min … max):     9.5 ms …  12.6 ms    237 runs

Benchmark 2: gix index entries --no-attributes  ':(attr:filter=lfs)'
  Time (mean ± σ):       6.3 ms ±   0.1 ms    [User: 3.6 ms, System: 1.4 ms]
  Range (min … max):     6.0 ms …   7.1 ms    451 runs

Summary
  gix index entries --no-attributes  ':(attr:filter=lfs)' ran
    1.61 ± 0.07 times faster than git ls-files  ':(attr:filter=lfs)'

r370k

✦ ❯ sha1sum <(git ls-files  ':(attr:export-ignore)') <(gix index entries --no-attributes  ':(attr:export-ignore)')
0831e40d8a8312a0087d136750865db663ce5626  /dev/fd/11
0831e40d8a8312a0087d136750865db663ce5626  /dev/fd/12

✦ ❯ hyperfine --warmup 1 "git ls-files  ':(attr:export-ignore)'" "gix index entries --no-attributes  ':(attr:export-ignore)'" -N
Benchmark 1: git ls-files  ':(attr:export-ignore)'
  Time (mean ± σ):      1.068 s ±  0.003 s    [User: 1.031 s, System: 0.061 s]
  Range (min … max):    1.064 s …  1.072 s    10 runs

Benchmark 2: gix index entries --no-attributes  ':(attr:export-ignore)'
  Time (mean ± σ):     396.6 ms ±   1.0 ms    [User: 387.3 ms, System: 36.5 ms]
  Range (min … max):   395.7 ms … 398.6 ms    10 runs

Summary
  gix index entries --no-attributes  ':(attr:export-ignore)' ran
    2.69 ± 0.01 times faster than git ls-files  ':(attr:export-ignore)'

Single attribute lookup - more fair

r370k

Different output due to attribute display. This prints more, too.
Removal of --no-attributes matches all attributes for each path, and uses worktree attributes by default.

✦ ❯ sha1sum  <(git ls-files ':(attr:export-ignore)') <(gix index entries ':(attr:export-ignore)') <(gix index entries --attributes-from-index ':(attr:export-ignore)')
0831e40d8a8312a0087d136750865db663ce5626  /dev/fd/11
38ff74ce818063b53ce23c329e63725cd12c65e9  /dev/fd/12
38ff74ce818063b53ce23c329e63725cd12c65e9  /dev/fd/13

✦ ❯ hyperfine --warmup 1 "git ls-files ':(attr:export-ignore)'" "gix index entries ':(attr:export-ignore)'" "gix index entries --attributes-from-index ':(attr:export-ignore)'" -N
Benchmark 1: git ls-files ':(attr:export-ignore)'
  Time (mean ± σ):      1.069 s ±  0.003 s    [User: 1.031 s, System: 0.061 s]
  Range (min … max):    1.065 s …  1.073 s    10 runs

Benchmark 2: gix index entries ':(attr:export-ignore)'
  Time (mean ± σ):     735.6 ms ±   3.3 ms    [User: 648.3 ms, System: 113.9 ms]
  Range (min … max):   732.6 ms … 743.6 ms    10 runs

Benchmark 3: gix index entries --attributes-from-index ':(attr:export-ignore)'
  Time (mean ± σ):     646.6 ms ±   1.3 ms    [User: 635.3 ms, System: 38.3 ms]
  Range (min … max):   644.8 ms … 649.1 ms    10 runs

Summary
  gix index entries --attributes-from-index ':(attr:export-ignore)' ran
    1.14 ± 0.01 times faster than gix index entries ':(attr:export-ignore)'
    1.65 ± 0.01 times faster than git ls-files ':(attr:export-ignore)'

Simple single-glob

✦ ❯ sha1sum <(git ls-files  'Web*') <(gix index entries --no-attributes  'Web*')
9ba642c78fab013f6b2def4f411d80997ea66fc6  /dev/fd/11
9ba642c78fab013f6b2def4f411d80997ea66fc6  /dev/fd/12

✦ ❯ hyperfine --warmup 1 "git ls-files  'Web*'" "gix index entries --no-attributes  'Web*'" -N
Benchmark 1: git ls-files  'Web*'
  Time (mean ± σ):      33.0 ms ±   0.7 ms    [User: 31.3 ms, System: 26.3 ms]
  Range (min … max):    31.6 ms …  36.5 ms    85 runs

Benchmark 2: gix index entries --no-attributes  'Web*'
  Time (mean ± σ):      18.5 ms ±   0.5 ms    [User: 15.6 ms, System: 29.4 ms]
  Range (min … max):    17.3 ms …  20.0 ms    165 runs

Summary
  gix index entries --no-attributes  'Web*' ran
    1.79 ± 0.07 times faster than git ls-files  'Web*'

Trivial Prefix

r370k

✦ ❯ sha1sum <(git ls-files WebDriverTests) <(gix index entries --no-attributes WebDriverTests)
de7182803b0fe00b3b13564fada82d3a229b1404  /dev/fd/11
de7182803b0fe00b3b13564fada82d3a229b1404  /dev/fd/12

✦ ❯ hyperfine --warmup 1 "git ls-files WebDriverTests" "gix index entries --no-attributes WebDriverTests" -N
Benchmark 1: git ls-files WebDriverTests
  Time (mean ± σ):      36.5 ms ±   0.6 ms    [User: 34.8 ms, System: 26.7 ms]
  Range (min … max):    35.4 ms …  38.9 ms    78 runs

Benchmark 2: gix index entries --no-attributes WebDriverTests
  Time (mean ± σ):      18.7 ms ±   0.4 ms    [User: 15.5 ms, System: 29.9 ms]
  Range (min … max):    17.9 ms …  20.0 ms    159 runs

Summary
  gix index entries --no-attributes WebDriverTests ran
    1.95 ± 0.05 times faster than git ls-files WebDriverTests

Bonus: --recurse submodules on Rust repo

✦ ❯ git --version && gix --version
git version 2.39.2 (Apple Git-143)
gix v0.28.0-233-gec1e5506e

✦ ❯ hyperfine --warmup 2 "git ls-files"  "git ls-files --recurse-submodules" "gix index entries --no-attributes" "gix index entries -r --no-attributes " -N
Benchmark 1: git ls-files
  Time (mean ± σ):      14.9 ms ±   0.4 ms    [User: 10.0 ms, System: 3.7 ms]
  Range (min … max):    14.1 ms …  17.7 ms    169 runs

Benchmark 2: git ls-files --recurse-submodules
  Time (mean ± σ):      41.9 ms ±   0.6 ms    [User: 35.0 ms, System: 14.6 ms]
  Range (min … max):    40.9 ms …  44.4 ms    70 runs

Benchmark 3: gix index entries --no-attributes
  Time (mean ± σ):       7.2 ms ±   0.3 ms    [User: 4.2 ms, System: 3.0 ms]
  Range (min … max):     6.4 ms …   7.9 ms    431 runs

Benchmark 4: gix index entries -r --no-attributes
  Time (mean ± σ):      22.5 ms ±   0.4 ms    [User: 15.8 ms, System: 15.9 ms]
  Range (min … max):    21.5 ms …  23.5 ms    129 runs

Summary
  gix index entries --no-attributes ran
    2.07 ± 0.10 times faster than git ls-files
    3.14 ± 0.13 times faster than gix index entries -r --no-attributes
    5.83 ± 0.23 times faster than git ls-files --recurse-submodules

Apples vs Apples

When both aren't computing the index, gix is still a lot faster.

❯ gix --version && ../../git/git/git --version
gix v0.29.0-21-g5e3b7ac75
git version 2.42.0.45.g6807fcfeda

WebKit ( main) via △
❯ hyperfine --warmup 1 'gix index entries --no-attributes' '../../git/git/git -c index.skipHash ls-files' -N
Benchmark 1: gix index entries --no-attributes
  Time (mean ± σ):      29.3 ms ±   0.8 ms    [User: 23.6 ms, System: 32.2 ms]
  Range (min … max):    27.8 ms …  34.0 ms    88 runs

Benchmark 2: ../../git/git/git -c index.skipHash ls-files
  Time (mean ± σ):      63.6 ms ±   0.6 ms    [User: 65.8 ms, System: 26.0 ms]
  Range (min … max):    62.8 ms …  64.9 ms    47 runs

Summary
  gix index entries --no-attributes ran
    2.17 ± 0.06 times faster than ../../git/git/git -c index.skipHash ls-files