{"thread":{"id":"51501","subject":"[GSoC][RFC WIP PATCH 0/3] grep: allow parallelism in zlib inflation","startedAt":"2019-07-19T23:09:09Z","lastAt":"2019-07-19T23:09:28Z","messageCount":4,"participants":["Matheus Tavares"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"379129","messageId":"cover.1563570204.git.matheus.bernardino@usp.br","threadId":"51501","inReplyTo":null,"subject":"[GSoC][RFC WIP PATCH 0/3] grep: allow parallelism in zlib inflation","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-07-19T23:08:51Z","receivedAt":"2019-07-19T23:09:09Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Threads were disabled in git-grep for non-worktree case at 53b8d93\n(\"grep: disable threading in non-worktree case\", 12-12-2011), due to\nperfomance drops. \n\nTo regain performance, this series work on the object reading code so\nthat zlib inflation may be performed in parallel. This is a good hotspot\nfor parallelism as, in some test cases[1], it accounts for up to 48% of\nexecution time. And besides that, inflation tasks are already\nindependent from one another.\n\nGrep'ing 'abcd[02]' (\"Regex 1\") and '(static|extern) (int|double) \\*'\n(\"Regex 2\") at chromium's repository[2], I got:\n\n     Threads |   Regex 1  |  Regex 2\n    ---------|------------|-----------\n        1    |  17.5815s  | 21.7217s\n        2    |   9.7983s  | 11.3965s\n        8    |   6.3097s  |  6.9667s\n    \nThese are all means of 30 executions after 2 warmup runs. All tests were\nexecuted on a i7-7700HQ with 16GB of RAM and SSD. The output was also\nvalidated against current git-grep.\n\nI still want to repeat the test in an HDD machine and in a repo with\nmainly loose objects.\n\nThere're still some open issues thought:\n\n1) To allow parallel inflation, the `obj_read_mutex` is released at\n`unpack_compressed_entry()` and `get_size_from_delta()` right before\ncalling `git_inflate()` (and re-acquired right after). For git-grep it\nseems to be OK. But, besides git-grep, if it's wanted to read objects\nand perform other operations in parallel, we probably cannot guarantee\nthat the lock will be held by the current thread when it gets to those\ntwo functions. Also, as the lock does only protect this call tree, if\nthose other operations access the same global states through other\npaths, we may also have race conditions.\n\n2) git-grep operations on textconv and submodules are still\nunprotected and should result in race conditions. I'm not sure if\nhaving two separate mutexes for them would fix it as the latter also has\nto access the object store.\n\nAny comments on the series and open issues will be highly appreciated.\n\n[1]: https://matheustavares.gitlab.io/posts/week-6-working-at-zlib-inflation#multithreading-zlib-inflation \n[2]: chromium’s repo at commit 03ae96f (“Add filters testing at DSF=2”,\n     04-06-2019), after a 'git gc' execution.\n\ntravis build: https://travis-ci.org/matheustavares/git/builds/561200398\n\n\nMatheus Tavares (3):\n  object-store: make read_object_file_extended() thread-safe\n  grep: remove locks on object reading operations\n  grep: re-enable threads in non-worktree case\n\n builtin/grep.c | 20 ++++--------------\n grep.c         |  3 ---\n object-store.h |  4 ++++\n packfile.c     |  7 +++++++\n sha1-file.c    | 56 +++++++++++++++++++++++++++++++++++++++++++++-----\n 5 files changed, 66 insertions(+), 24 deletions(-)\n\n-- \n2.22.0\n\n"},{"id":"379130","messageId":"1525a0b55c4dddef09c9ea8ed26def21a3e790aa.1563570204.git.matheus.bernardino@usp.br","threadId":"51501","inReplyTo":"cover.1563570204.git.matheus.bernardino@usp.br","subject":"[GSoC][RFC WIP PATCH 1/3] object-store: make read_object_file_extended() thread-safe","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-07-19T23:08:52Z","receivedAt":"2019-07-19T23:09:21Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Allow read_object_file_extended() to be called by multiple threads\nprotecting it with a lock. The lock usage can be toggled with\nenable_obj_read_lock() and disable_obj_read_lock().\n\nProbably there are many spots in read_object_file_extended()'s call\nchain that could be executed unlocked (and thus, in parallel). But, just\nto make sure, let's protect everthing for now, and go refining the lock\nstep-by-step in the future.\n\nThe only (and perhaps most important) exception is git_inflate. Since it\nis already thread-safe and takes a significant amount of time, the lock\nis released when entering this function, so that it can be performed in\nparallel. This should already bring good performance, because of\ninflation's time cost.\n\nNote that add_delta_base_cache() was also modified to skip adding\nalready present cache entries. This wouldn't happen in the past, but now\nit's possible as phase I and phase III of unpack_entry() may execute\nconcurrently.\n\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n object-store.h |  4 ++++\n packfile.c     |  7 +++++++\n sha1-file.c    | 56 +++++++++++++++++++++++++++++++++++++++++++++-----\n 3 files changed, 62 insertions(+), 5 deletions(-)\n\ndiff --git a/object-store.h b/object-store.h\nindex 49f56ab8d9..8330ff3988 100644\n--- a/object-store.h\n+++ b/object-store.h\n@@ -157,6 +157,10 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,\n void *map_loose_object(struct repository *r, const struct object_id *oid,\n \t\t       unsigned long *size);\n \n+void enable_obj_read_lock(void);\n+void disable_obj_read_lock(void);\n+void obj_read_lock(void);\n+void obj_read_unlock(void);\n void *read_object_file_extended(struct repository *r,\n \t\t\t\tconst struct object_id *oid,\n \t\t\t\tenum object_type *type,\ndiff --git a/packfile.c b/packfile.c\nindex c0d83fdfed..a50be4e5e5 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1087,7 +1087,9 @@ unsigned long get_size_from_delta(struct packed_git *p,\n \tdo {\n \t\tin = use_pack(p, w_curs, curpos, &stream.avail_in);\n \t\tstream.next_in = in;\n+\t\tobj_read_unlock();\n \t\tst = git_inflate(&stream, Z_FINISH);\n+\t\tobj_read_lock();\n \t\tcurpos += stream.next_in - in;\n \t} while ((st == Z_OK || st == Z_BUF_ERROR) &&\n \t\t stream.total_out < sizeof(delta_head));\n@@ -1440,6 +1442,9 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tstruct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));\n \tstruct list_head *lru, *tmp;\n \n+\tif (get_delta_base_cache_entry(p, base_offset))\n+\t\treturn;\n+\n \tdelta_base_cached += base_size;\n \n \tlist_for_each_safe(lru, tmp, &delta_base_cache_lru) {\n@@ -1569,7 +1574,9 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \tdo {\n \t\tin = use_pack(p, w_curs, curpos, &stream.avail_in);\n \t\tstream.next_in = in;\n+\t\tobj_read_unlock();\n \t\tst = git_inflate(&stream, Z_FINISH);\n+\t\tobj_read_lock();\n \t\tif (!stream.avail_out)\n \t\t\tbreak; /* the payload is larger than it should be */\n \t\tcurpos += stream.next_in - in;\ndiff --git a/sha1-file.c b/sha1-file.c\nindex 888b6024d5..37cde4a494 100644\n--- a/sha1-file.c\n+++ b/sha1-file.c\n@@ -1463,16 +1463,49 @@ int pretend_object_file(void *buf, unsigned long len, enum object_type type,\n \treturn 0;\n }\n \n+static pthread_mutex_t obj_read_mutex;\n+static int obj_read_use_lock = 0;\n+\n+void enable_obj_read_lock(void)\n+{\n+\tif (obj_read_use_lock)\n+\t\treturn;\n+\n+\tobj_read_use_lock = 1;\n+\tpthread_mutex_init(&obj_read_mutex, NULL);\n+}\n+\n+void disable_obj_read_lock(void)\n+{\n+\tif (!obj_read_use_lock)\n+\t\treturn;\n+\n+\tobj_read_use_lock = 0;\n+\tpthread_mutex_destroy(&obj_read_mutex);\n+}\n+\n+void obj_read_lock(void)\n+{\n+\tif(obj_read_use_lock)\n+\t\tpthread_mutex_lock(&obj_read_mutex);\n+}\n+\n+void obj_read_unlock(void)\n+{\n+\tif(obj_read_use_lock)\n+\t\tpthread_mutex_unlock(&obj_read_mutex);\n+}\n+\n /*\n  * This function dies on corrupt objects; the callers who want to\n  * deal with them should arrange to call read_object() and give error\n  * messages themselves.\n  */\n-void *read_object_file_extended(struct repository *r,\n-\t\t\t\tconst struct object_id *oid,\n-\t\t\t\tenum object_type *type,\n-\t\t\t\tunsigned long *size,\n-\t\t\t\tint lookup_replace)\n+static void *do_read_object_file_extended(struct repository *r,\n+\t\t\t\t\t  const struct object_id *oid,\n+\t\t\t\t\t  enum object_type *type,\n+\t\t\t\t\t  unsigned long *size,\n+\t\t\t\t\t  int lookup_replace)\n {\n \tvoid *data;\n \tconst struct packed_git *p;\n@@ -1505,6 +1538,19 @@ void *read_object_file_extended(struct repository *r,\n \treturn NULL;\n }\n \n+void *read_object_file_extended(struct repository *r,\n+\t\t\t\tconst struct object_id *oid,\n+\t\t\t\tenum object_type *type,\n+\t\t\t\tunsigned long *size,\n+\t\t\t\tint lookup_replace)\n+{\t\n+\tvoid *data;\n+\tobj_read_lock();\n+\tdata = do_read_object_file_extended(r, oid, type, size, lookup_replace);\n+\tobj_read_unlock();\n+\treturn data;\n+}\n+\n void *read_object_with_reference(const struct object_id *oid,\n \t\t\t\t const char *required_type_name,\n \t\t\t\t unsigned long *size,\n-- \n2.22.0\n\n"},{"id":"379131","messageId":"10005e2838ef3bc219b4a775de522339046db318.1563570204.git.matheus.bernardino@usp.br","threadId":"51501","inReplyTo":"cover.1563570204.git.matheus.bernardino@usp.br","subject":"[GSoC][RFC WIP PATCH 2/3] grep: remove locks on object reading operations","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-07-19T23:08:53Z","receivedAt":"2019-07-19T23:09:25Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"git-grep has locks around the object reading operations it performs. But\nthese have an internal lock now, which can be enabled through\nenable_obj_read_lock(). So let's use it and drop git-grep's ones.\n\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n builtin/grep.c | 18 +++---------------\n grep.c         |  3 ---\n 2 files changed, 3 insertions(+), 18 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 580fd38f41..682e2461d0 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -206,6 +206,7 @@ static void start_threads(struct grep_opt *opt)\n \tpthread_cond_init(&cond_write, NULL);\n \tpthread_cond_init(&cond_result, NULL);\n \tgrep_use_locks = 1;\n+\tenable_obj_read_lock();\n \n \tfor (i = 0; i < ARRAY_SIZE(todo); i++) {\n \t\tstrbuf_init(&todo[i].out, 0);\n@@ -263,6 +264,7 @@ static int wait_all(void)\n \tpthread_cond_destroy(&cond_write);\n \tpthread_cond_destroy(&cond_result);\n \tgrep_use_locks = 0;\n+\tdisable_obj_read_lock();\n \n \treturn hit;\n }\n@@ -295,16 +297,6 @@ static int grep_cmd_config(const char *var, const char *value, void *cb)\n \treturn st;\n }\n \n-static void *lock_and_read_oid_file(const struct object_id *oid, enum object_type *type, unsigned long *size)\n-{\n-\tvoid *data;\n-\n-\tgrep_read_lock();\n-\tdata = read_object_file(oid, type, size);\n-\tgrep_read_unlock();\n-\treturn data;\n-}\n-\n static int grep_oid(struct grep_opt *opt, const struct object_id *oid,\n \t\t     const char *filename, int tree_name_len,\n \t\t     const char *path)\n@@ -457,10 +449,8 @@ static int grep_submodule(struct grep_opt *opt,\n \n \t\tobject = parse_object_or_die(oid, oid_to_hex(oid));\n \n-\t\tgrep_read_lock();\n \t\tdata = read_object_with_reference(&object->oid, tree_type,\n \t\t\t\t\t\t  &size, NULL);\n-\t\tgrep_read_unlock();\n \n \t\tif (!data)\n \t\t\tdie(_(\"unable to read tree (%s)\"), oid_to_hex(&object->oid));\n@@ -585,7 +575,7 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,\n \t\t\tvoid *data;\n \t\t\tunsigned long size;\n \n-\t\t\tdata = lock_and_read_oid_file(&entry.oid, &type, &size);\n+\t\t\tdata = read_object_file(&entry.oid, &type, &size);\n \t\t\tif (!data)\n \t\t\t\tdie(_(\"unable to read tree (%s)\"),\n \t\t\t\t    oid_to_hex(&entry.oid));\n@@ -622,10 +612,8 @@ static int grep_object(struct grep_opt *opt, const struct pathspec *pathspec,\n \t\tstruct strbuf base;\n \t\tint hit, len;\n \n-\t\tgrep_read_lock();\n \t\tdata = read_object_with_reference(&obj->oid, tree_type,\n \t\t\t\t\t\t  &size, NULL);\n-\t\tgrep_read_unlock();\n \n \t\tif (!data)\n \t\t\tdie(_(\"unable to read tree (%s)\"), oid_to_hex(&obj->oid));\ndiff --git a/grep.c b/grep.c\nindex f7c3a5803e..984a9e99cf 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -2109,10 +2109,7 @@ static int grep_source_load_oid(struct grep_source *gs)\n {\n \tenum object_type type;\n \n-\tgrep_read_lock();\n \tgs->buf = read_object_file(gs->identifier, &type, &gs->size);\n-\tgrep_read_unlock();\n-\n \tif (!gs->buf)\n \t\treturn error(_(\"'%s': unable to read %s\"),\n \t\t\t     gs->name,\n-- \n2.22.0\n\n"},{"id":"379132","messageId":"e72330c6747218545cce1b6b1edfd1e448141a8f.1563570204.git.matheus.bernardino@usp.br","threadId":"51501","inReplyTo":"cover.1563570204.git.matheus.bernardino@usp.br","subject":"[GSoC][RFC WIP PATCH 3/3] grep: re-enable threads in non-worktree case","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-07-19T23:08:54Z","receivedAt":"2019-07-19T23:09:28Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"They were disabled at 53b8d93 (\"grep: disable threading in non-worktree\ncase\", 12-12-2011), due to observable perfomance drops. But now that\nzlib inflation can be performed in parallel, we can regain the speedup.\n\nGrep'ing 'abcd[02]' (\"Regex 1\") and '(static|extern) (int|double) \\*'\n(\"Regex 2\") at chromium's repository[1] I got:\n\n Threads |   Regex 1  |  Regex 2\n---------|------------|-----------\n    1    |  17.5815s  | 21.7217s\n    2    |   9.7983s  | 11.3965s\n    8    |   6.3097s  |  6.9667s\n\nThese are all means of 30 executions after 2 warmup runs. All tests were\nexecuted on a i7-7700HQ with 16GB of RAM and SSD.\n\n[1]: chromium’s repo at commit 03ae96f (“Add filters testing at DSF=2”,\n     04-06-2019), after a 'git gc' execution.\n\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n builtin/grep.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 682e2461d0..9309dea833 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -1046,7 +1046,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \tpathspec.recursive = 1;\n \tpathspec.recurse_submodules = !!recurse_submodules;\n \n-\tif (list.nr || cached || show_in_pager) {\n+\tif (show_in_pager) {\n \t\tif (num_threads > 1)\n \t\t\twarning(_(\"invalid option combination, ignoring --threads\"));\n \t\tnum_threads = 1;\n-- \n2.22.0\n\n"}]}