git grep performance regression on macOS

What did you do before the bug happened? (Steps to reproduce your issue)

git grep seems to have gotten much slower as of git 2.39 on macOS for complex extended regexes. We noticed this because git secrets --scan was running much more slowly for some people on our team, and eventually realized that it was due to them using a newer version of git. git secrets runs a git grep command with an extended regex (this is a somewhat simplified version of the command, but still shows the performance issue):

git grep -E "(A3T[A-Z0-9]|AKIA|AGPA|AIDA|AROA|AIPA|ANPA|ANVA|ASIA)[A-Z0-9]{16}|(\"|')?(AWS|aws|Aws)?_?(SECRET|secret|Secret)?_?(ACCESS|access|Access)?_?(KEY|key|Key)(\"|')?\s*(:|=>|=)\s*(\"|')?[A-Za-z0-9/\+=]{40}(\"|')?|(\"|')?(AWS|aws|Aws)?_?(ACCOUNT|account|Account)_?(ID|id|Id)?(\"|')?\s*(:|=>|=)\s*(\"|')?[0-9]{4}\-?[0-9]{4}\-?[0-9]{4}(\"|')?"

What did you expect to happen? (Expected behavior) With git 2.38, that command took under half a second to run on a large repo. Using the git (https://github.com/git/git) repo as an example, it took 0.2s on my laptop.

What happened instead? (Actual behavior) After 2.39, it now takes over 40 seconds on my laptop with the git repo!

What's different between what you expected and what actually happened? The command runs much more slowly, though it still does return the correct result.

Anything else you want to add: I confirmed that the performance regression was first introduced in 2.39. Additionally, I saw that reverting the change to Makefile from https://github.com/git/git/commit/1819ad327b7a1f19540a819813b70a0e8a7f798f fixed the performance regression and the git grep command went back to taking <1 second. That seems to indicate that switching from Git's regex library to the native macOS regex library caused this performance regression, but I haven't investigated beyond that to see why the native macOS regex library is so much slower.

Please review the rest of the bug report below. You can delete any lines you don't wish to share.

[System Info] git version: git version 2.42.0 cpu: arm64 no commit associated with this build sizeof-long: 8 sizeof-size_t: 8 shell-path: /bin/sh feature: fsmonitor--daemon uname: Darwin 22.4.0 Darwin Kernel Version 22.4.0: Mon Mar 6 21:00:41 PST 2023; root:xnu-8796.101.5~3/RELEASE_ARM64_T8103 arm64 compiler info: clang: 14.0.3 (clang-1403.0.22.14.1) libc info: no libc information available $SHELL (typically, interactive shell): /bin/zsh

[Enabled Hooks] post-checkout post-merge pre-commit pre-push

Benjamin Hiller <benhiller@gmail.com> writes:

Yeah, that does sound a plausible explanation.

The regexp code in compat/ is meant as a fallback implementation for platforms whose regexp library lack certain features we take advantage of, but it has a limitation that it is not unicode aware. In the olden days, regexp library on macOS lacked REG_STARTEND feature, which forced us to use NO_REGEX (hence the fallback implementation we ship that is not unicode aware). The commit you cite makes us use the macOS native regexp library, as somebody on the platform got annoyed enough by the lack of unicode awareness of the fallback implementation, and also noticed that REG_STARTEND is supported by the macOS native regexp library these days.

The change in 2.39 was unfortunately about correctness. It would have been nicer if macOS native implementation were faster, but use of fallback implementation would be favoring "performance" (which produces incorrect results "faster" when run with multi-byte strings) over correctness, so it is not likely that a straight reverting of the commit is a good idea.

On Fri, Sep 29, 2023 at 04:56:19PM -0700, Benjamin Hiller wrote:

changing this code to use `git grep -P` instead will make it at least 7x faster even if you have a pcre2 library without JIT.

Carlo