grep: allow parallelism in zlib inflation
cover 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.9667sThese 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
RFC PATCH 1/3 object-store: make read_object_file_extended() thread-safe
Allow read_object_file_extended() to be called by multiple threads protecting it with a lock. The lock usage can be toggled with enable_obj_read_lock() and disable_obj_read_lock().
Probably there are many spots in read_object_file_extended()'s call chain that could be executed unlocked (and thus, in parallel). But, just to make sure, let's protect everthing for now, and go refining the lock step-by-step in the future.
The only (and perhaps most important) exception is git_inflate. Since it is already thread-safe and takes a significant amount of time, the lock is released when entering this function, so that it can be performed in parallel. This should already bring good performance, because of inflation's time cost.
Note that add_delta_base_cache() was also modified to skip adding already present cache entries. This wouldn't happen in the past, but now it's possible as phase I and phase III of unpack_entry() may execute concurrently.
--- object-store.h | 4 ++++ packfile.c | 7 +++++++ sha1-file.c | 56 +++++++++++++++++++++++++++++++++++++++++++++----- 3 files changed, 62 insertions(+), 5 deletions(-)
object-store.h +4 -0
@@ -157,6 +157,10 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,void *map_loose_object (struct repository *r,const struct object_id *oid,unsigned long *size); +void enable_obj_read_lock (void ); +void disable_obj_read_lock (void ); +void obj_read_lock (void ); +void obj_read_unlock (void ); void *read_object_file_extended(struct repository *r, const struct object_id *oid, enum object_type *type,
packfile.c +7 -0
@@ -1087,7 +1087,9 @@ unsigned long get_size_from_delta(struct packed_git *p,do { in =use_pack (p, w_curs, curpos, &stream.avail_in); stream.next_in = in; +obj_read_unlock (); st =git_inflate (&stream,Z_FINISH ); +obj_read_lock (); curpos += stream.next_in - in; }while ((st ==Z_OK || st ==Z_BUF_ERROR ) && stream.total_out <sizeof (delta_head));
@@ -1440,6 +1442,9 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,struct delta_base_cache_entry *ent =xmalloc (sizeof (*ent));struct list_head *lru, *tmp; +if (get_delta_base_cache_entry (p, base_offset)) +return ; + delta_base_cached += base_size;list_for_each_safe (lru, tmp, &delta_base_cache_lru) {
@@ -1569,7 +1574,9 @@ static void *unpack_compressed_entry(struct packed_git *p, do { in = use_pack(p, w_curs, curpos, &stream.avail_in); stream.next_in = in; + obj_read_unlock(); st = git_inflate(&stream, Z_FINISH); + obj_read_lock(); if (!stream.avail_out) break; /* the payload is larger than it should be */ curpos += stream.next_in - in;
sha1-file.c +51 -5
73 lines not on this page · raw message
Signature · 1 line
2.22.0
RFC PATCH 2/3 grep: remove locks on object reading operations
In reply to Matheus Tavaresgit-grep has locks around the object reading operations it performs. But these have an internal lock now, which can be enabled through enable_obj_read_lock(). So let's use it and drop git-grep's ones.
--- builtin/grep.c | 18 +++--------------- grep.c | 3 --- 2 files changed, 3 insertions(+), 18 deletions(-)
builtin/grep.c +3 -15
@@ -206,6 +206,7 @@ static void start_threads(struct grep_opt *opt)pthread_cond_init (&cond_write,NULL );pthread_cond_init (&cond_result,NULL ); grep_use_locks =1 ; +enable_obj_read_lock ();for (i =0 ; i <ARRAY_SIZE (todo); i++) {strbuf_init (&todo[i].out,0 );
@@ -263,6 +264,7 @@ static int wait_all(void)pthread_cond_destroy (&cond_write);pthread_cond_destroy (&cond_result); grep_use_locks =0 ; +disable_obj_read_lock ();return hit; }
@@ -295,16 +297,6 @@ static int grep_cmd_config(const char *var, const char *value, void *cb)return st; } -static void *lock_and_read_oid_file (const struct object_id *oid,enum object_type *type,unsigned long *size) -{ -void *data; - -grep_read_lock (); - data =read_object_file (oid, type, size); -grep_read_unlock (); -return data; -} -static int grep_oid (struct grep_opt *opt,const struct object_id *oid,const char *filename,int tree_name_len,const char *path)
@@ -457,10 +449,8 @@ static int grep_submodule(struct grep_opt *opt, object =parse_object_or_die (oid,oid_to_hex (oid)); -grep_read_lock (); data =read_object_with_reference (&object->oid, tree_type, &size,NULL ); -grep_read_unlock ();if (!data)die (_ ("unable to read tree (%s)" ),oid_to_hex (&object->oid));
@@ -585,7 +575,7 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,void *data;unsigned long size; - data =lock_and_read_oid_file (&entry.oid, &type, &size); + data =read_object_file (&entry.oid, &type, &size);if (!data)die (_ ("unable to read tree (%s)" ),oid_to_hex (&entry.oid));
@@ -622,10 +612,8 @@ static int grep_object(struct grep_opt *opt, const struct pathspec *pathspec,struct strbuf base;int hit, len; -grep_read_lock (); data =read_object_with_reference (&obj->oid, tree_type, &size,NULL ); -grep_read_unlock ();if (!data)die (_ ("unable to read tree (%s)" ),oid_to_hex (&obj->oid));
grep.c +0 -3
@@ -2109,10 +2109,7 @@ static int grep_source_load_oid(struct grep_source *gs) {enum object_type type; -grep_read_lock (); gs->buf =read_object_file (gs->identifier, &type, &gs->size); -grep_read_unlock (); -if (!gs->buf) return error(_("'%s': unable to read %s"), gs->name,
Signature · 1 line
2.22.0
RFC PATCH 3/3 grep: re-enable threads in non-worktree case
In reply to Matheus TavaresThey were disabled at 53b8d93 ("grep: disable threading in non-worktree case", 12-12-2011), due to observable perfomance drops. But now that zlib inflation can be performed in parallel, we can regain the speedup.
Grep'ing 'abcd[02]' ("Regex 1") and '(static|extern) (int|double) \*' ("Regex 2") at chromium's repository[1] I got:
Threads | Regex 1 | Regex 2
---------|------------|-----------
1 | 17.5815s | 21.7217s
2 | 9.7983s | 11.3965s
8 | 6.3097s | 6.9667sThese are all means of 30 executions after 2 warmup runs. All tests were executed on a i7-7700HQ with 16GB of RAM and SSD.
[1]: chromium’s repo at commit 03ae96f (“Add filters testing at DSF=2”,
04-06-2019), after a 'git gc' execution.
--- builtin/grep.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
builtin/grep.c +1 -1
@@ -1046,7 +1046,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix) pathspec.recursive =1 ; pathspec.recurse_submodules = !!recurse_submodules; -if (list.nr || cached || show_in_pager) { +if (show_in_pager) {if (num_threads >1 )warning (_ ("invalid option combination, ignoring --threads" )); num_threads =1 ;
Signature · 1 line
2.22.0