Skip to content

RFC grep: allow parallelism in zlib inflation

Matheus Tavares git 1 version New

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest3 patches 0 repliesNew

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/3object-store: make read_object_file_extended() thread-safeobject-store.h packfile.c sha1-file.c+62 -50 replies
2/3grep: remove locks on object reading operationsbuiltin/grep.c grep.c+3 -180 replies
3/3grep: re-enable threads in non-worktree casebuiltin/grep.c+1 -10 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [GSoC][RFC WIP PATCH 0/3] grep: allow parallelism in zlib inflation

Threads were disabled in git-grep for non-worktree case at 53b8d93 ("grep: disable threading in non-worktree case", 12-12-2011), due to perfomance drops.

To regain performance, this series work on the object reading code so that zlib inflation may be performed in parallel. This is a good hotspot for parallelism as, in some test cases[1], it accounts for up to 48% of execution time. And besides that, inflation tasks are already independent from one another.

Grep'ing 'abcd[02]' ("Regex 1") and '(static|extern) (int|double) \*' ("Regex 2") at chromium's repository[2], I got:

     Threads |   Regex 1  |  Regex 2
    ---------|------------|-----------
        1    |  17.5815s  | 21.7217s
        2    |   9.7983s  | 11.3965s
        8    |   6.3097s  |  6.9667s

These are all means of 30 executions after 2 warmup runs. All tests were executed on a i7-7700HQ with 16GB of RAM and SSD. The output was also validated against current git-grep.

I still want to repeat the test in an HDD machine and in a repo with mainly loose objects.

There're still some open issues thought:

1) To allow parallel inflation, the obj_read_mutex is released at unpack_compressed_entry() and get_size_from_delta() right before calling git_inflate() (and re-acquired right after). For git-grep it seems to be OK. But, besides git-grep, if it's wanted to read objects and perform other operations in parallel, we probably cannot guarantee that the lock will be held by the current thread when it gets to those two functions. Also, as the lock does only protect this call tree, if those other operations access the same global states through other paths, we may also have race conditions.

2) git-grep operations on textconv and submodules are still unprotected and should result in race conditions. I'm not sure if having two separate mutexes for them would fix it as the latter also has to access the object store.

Any comments on the series and open issues will be highly appreciated.

[1]: https://matheustavares.gitlab.io/posts/week-6-working-at-zlib-inflation#multithreading-zlib-inflation
[2]: chromium’s repo at commit 03ae96f (“Add filters testing at DSF=2”,

     04-06-2019), after a 'git gc' execution.

travis build: https://travis-ci.org/matheustavares/git/builds/561200398

Matheus Tavares (3):
object-store: make read_object_file_extended() thread-safe
grep: remove locks on object reading operations
grep: re-enable threads in non-worktree case

 builtin/grep.c | 20 ++++--------------
 grep.c         |  3 ---
 object-store.h |  4 ++++
 packfile.c     |  7 +++++++
 sha1-file.c    | 56 +++++++++++++++++++++++++++++++++++++++++++++-----
 5 files changed, 66 insertions(+), 24 deletions(-)
Signature · 1 line
2.22.0