{"thread":{"id":"29912","subject":"[PATCH v2 0/2] Multithread index-pack","startedAt":"2012-03-12T02:32:27Z","lastAt":"2012-03-14T10:29:32Z","messageCount":9,"participants":["Nguyễn Thái Ngọc Duy","Thomas Rast","Nguyen Thai Ngoc Duy","Ramsay Jones"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"186674","messageId":"1331519549-28090-1-git-send-email-pclouds@gmail.com","threadId":"29912","inReplyTo":null,"subject":"[PATCH v2 0/2] Multithread index-pack","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-12T02:32:27Z","receivedAt":"2012-03-12T02:32:27Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Compared to the first version [1], this fixes thin-pack appending\nproblem because nr_resolved_detas is misupdated. It also makes sure no\npthread calls are called before thread data is initialized, and after\nit is destroyed. This should fix the crash Ramsay observed on MinGW.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/191698\n\nNguyễn Thái Ngọc Duy (2):\n  index-pack: split second pass obj handling into own function\n  index-pack: support multithreaded delta resolving\n\n Documentation/git-index-pack.txt |   10 ++\n Makefile                         |    2 +-\n builtin/index-pack.c             |  225 +++++++++++++++++++++++++++++++++-----\n 3 files changed, 208 insertions(+), 29 deletions(-)\n\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"186675","messageId":"1331519549-28090-2-git-send-email-pclouds@gmail.com","threadId":"29912","inReplyTo":"1331519549-28090-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 1/2] index-pack: split second pass obj handling into own function","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-12T02:32:28Z","receivedAt":"2012-03-12T02:32:28Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c |   31 ++++++++++++++++++-------------\n 1 files changed, 18 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex dd1c5c9..918684f 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -682,6 +682,23 @@ static int compare_delta_entry(const void *a, const void *b)\n \t\t\t\t   objects[delta_b->obj_no].type);\n }\n \n+/*\n+ * Second pass:\n+ * - for all non-delta objects, look if it is used as a base for\n+ *   deltas;\n+ * - if used as a base, uncompress the object and apply all deltas,\n+ *   recursively checking if the resulting object is used as a base\n+ *   for some more deltas.\n+ */\n+static void second_pass(struct object_entry *obj)\n+{\n+\tstruct base_data *base_obj = alloc_base_data();\n+\tbase_obj->obj = obj;\n+\tbase_obj->data = NULL;\n+\tfind_unresolved_deltas(base_obj);\n+\tdisplay_progress(progress, nr_resolved_deltas);\n+}\n+\n /* Parse all objects and return the pack content SHA1 hash */\n static void parse_pack_objects(unsigned char *sha1)\n {\n@@ -736,26 +753,14 @@ static void parse_pack_objects(unsigned char *sha1)\n \tqsort(deltas, nr_deltas, sizeof(struct delta_entry),\n \t      compare_delta_entry);\n \n-\t/*\n-\t * Second pass:\n-\t * - for all non-delta objects, look if it is used as a base for\n-\t *   deltas;\n-\t * - if used as a base, uncompress the object and apply all deltas,\n-\t *   recursively checking if the resulting object is used as a base\n-\t *   for some more deltas.\n-\t */\n \tif (verbose)\n \t\tprogress = start_progress(\"Resolving deltas\", nr_deltas);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tstruct base_data *base_obj = alloc_base_data();\n \n \t\tif (is_delta_type(obj->type))\n \t\t\tcontinue;\n-\t\tbase_obj->obj = obj;\n-\t\tbase_obj->data = NULL;\n-\t\tfind_unresolved_deltas(base_obj);\n-\t\tdisplay_progress(progress, nr_resolved_deltas);\n+\t\tsecond_pass(obj);\n \t}\n }\n \n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"186676","messageId":"1331519549-28090-3-git-send-email-pclouds@gmail.com","threadId":"29912","inReplyTo":"1331519549-28090-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-12T02:32:29Z","receivedAt":"2012-03-12T02:32:29Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This puts delta resolving on each base on a separate thread, one base\ncache per thread. Per-thread data is grouped in struct thread_local.\nWhen running with nr_threads == 1, no pthreads calls are made. The\nsystem essentially runs in non-thread mode.\n\nAn experiment on a Xeon 24 core machine with linux-2.6.git shows that\nperformance does not increase proportional to the number of cores. So\nby default, we use maximum 3 cores. Some numbers with --threads from 1\nto 16:\n\n1..4\nreal    1m16.310s  0m48.183s  0m37.866s  0m32.834s\nuser    1m13.773s  1m15.537s  1m15.781s  1m16.233s\nsys     0m2.480s   0m3.936s   0m4.448s   0m4.852s\n\n5..8\nreal    0m33.170s  0m30.369s  0m28.406s  0m26.968s\nuser    1m31.474s  1m30.322s  1m29.562s  1m28.694s\nsys     0m6.096s   0m6.268s   0m6.684s   0m7.172s\n\n9..12\nreal    0m26.288s  0m26.207s  0m26.239s  0m24.945s\nuser    1m29.530s  1m36.146s  1m43.134s  1m34.182s\nsys     0m8.129s   0m8.437s   0m9.697s   0m10.201s\n\n13..16\nreal    0m25.110s  0m25.043s  0m23.955s  0m25.746s\nuser    1m39.262s  1m43.598s  1m38.350s  1m59.775s\nsys     0m10.997s  0m11.553s  0m11.949s  0m13.689s\n\nThanks to Ramsay Jones for troubleshooting on MinGW platform.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n I changed Ramsay's mutex patch a little bit and incorporate it here.\n Ramsay, it'd be great if you could try it again on MinGW\n\n Documentation/git-index-pack.txt |   10 ++\n Makefile                         |    2 +-\n builtin/index-pack.c             |  198 ++++++++++++++++++++++++++++++++++----\n 3 files changed, 192 insertions(+), 18 deletions(-)\n\ndiff --git a/Documentation/git-index-pack.txt b/Documentation/git-index-pack.txt\nindex 909687f..39e6d0d 100644\n--- a/Documentation/git-index-pack.txt\n+++ b/Documentation/git-index-pack.txt\n@@ -74,6 +74,16 @@ OPTIONS\n --strict::\n \tDie, if the pack contains broken objects or links.\n \n+--threads=<n>::\n+\tSpecifies the number of threads to spawn when resolving\n+\tdeltas. This requires that index-pack be compiled with\n+\tpthreads otherwise this option is ignored with a warning.\n+\tThis is meant to reduce packing time on multiprocessor\n+\tmachines. The required amount of memory for the delta search\n+\twindow is however multiplied by the number of threads.\n+\tSpecifying 0 will cause git to auto-detect the number of CPU's\n+\tand use maximum 3 threads.\n+\n \n Note\n ----\ndiff --git a/Makefile b/Makefile\nindex 1fb1705..5fae875 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -2159,7 +2159,7 @@ builtin/branch.o builtin/checkout.o builtin/clone.o builtin/reset.o branch.o tra\n builtin/bundle.o bundle.o transport.o: bundle.h\n builtin/bisect--helper.o builtin/rev-list.o bisect.o: bisect.h\n builtin/clone.o builtin/fetch-pack.o transport.o: fetch-pack.h\n-builtin/grep.o builtin/pack-objects.o transport-helper.o thread-utils.o: thread-utils.h\n+builtin/index-pack.o builtin/grep.o builtin/pack-objects.o transport-helper.o thread-utils.o: thread-utils.h\n builtin/send-pack.o transport.o: send-pack.h\n builtin/log.o builtin/shortlog.o: shortlog.h\n builtin/prune.o builtin/reflog.o reachable.o: reachable.h\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 918684f..c6712cb 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -9,6 +9,7 @@\n #include \"progress.h\"\n #include \"fsck.h\"\n #include \"exec_cmd.h\"\n+#include \"thread-utils.h\"\n \n static const char index_pack_usage[] =\n \"git index-pack [-v] [-o <index-file>] [--keep | --keep=<msg>] [--verify] [--strict] (<pack-file> | --stdin [--fix-thin] [<pack-file>])\";\n@@ -38,6 +39,14 @@ struct base_data {\n \tint ofs_first, ofs_last;\n };\n \n+struct thread_local {\n+#ifndef NO_PTHREADS\n+\tpthread_t thread;\n+#endif\n+\tstruct base_data *base_cache;\n+\tsize_t base_cache_used;\n+};\n+\n /*\n  * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n  * to memcmp() only the first 20 bytes.\n@@ -54,11 +63,12 @@ struct delta_entry {\n \n static struct object_entry *objects;\n static struct delta_entry *deltas;\n-static struct base_data *base_cache;\n-static size_t base_cache_used;\n+static struct thread_local nothread_data;\n static int nr_objects;\n+static int nr_processed;\n static int nr_deltas;\n static int nr_resolved_deltas;\n+static int nr_threads;\n \n static int from_stdin;\n static int strict;\n@@ -75,6 +85,72 @@ static git_SHA_CTX input_ctx;\n static uint32_t input_crc32;\n static int input_fd, output_fd, pack_fd;\n \n+#ifndef NO_PTHREADS\n+\n+static struct thread_local *thread_data;\n+\n+static pthread_mutex_t read_mutex;\n+#define read_lock()\t\tlock_mutex(&read_mutex)\n+#define read_unlock()\t\tunlock_mutex(&read_mutex)\n+\n+static pthread_mutex_t counter_mutex;\n+#define counter_lock()\t\tlock_mutex(&counter_mutex)\n+#define counter_unlock()\tunlock_mutex(&counter_mutex)\n+\n+static pthread_mutex_t work_mutex;\n+#define work_lock()\t\tlock_mutex(&work_mutex)\n+#define work_unlock()\t\tunlock_mutex(&work_mutex)\n+\n+static pthread_key_t key;\n+\n+static inline void lock_mutex(pthread_mutex_t *mutex)\n+{\n+\tif (nr_threads > 1)\n+\t\tpthread_mutex_lock(mutex);\n+}\n+\n+static inline void unlock_mutex(pthread_mutex_t *mutex)\n+{\n+\tif (nr_threads > 1)\n+\t\tpthread_mutex_unlock(mutex);\n+}\n+\n+/*\n+ * Mutex and conditional variable can't be statically-initialized on Windows.\n+ */\n+static void init_thread(void)\n+{\n+\tinit_recursive_mutex(&read_mutex);\n+\tpthread_mutex_init(&counter_mutex, NULL);\n+\tpthread_mutex_init(&work_mutex, NULL);\n+\tpthread_key_create(&key, NULL);\n+\tthread_data = xcalloc(nr_threads, sizeof(*thread_data));\n+}\n+\n+static void cleanup_thread(void)\n+{\n+\tpthread_mutex_destroy(&read_mutex);\n+\tpthread_mutex_destroy(&counter_mutex);\n+\tpthread_mutex_destroy(&work_mutex);\n+\tpthread_key_delete(key);\n+\tnr_threads = 1;\n+\tfree(thread_data);\n+}\n+\n+#else\n+\n+#define read_lock()\n+#define read_unlock()\n+\n+#define counter_lock()\n+#define counter_unlock()\n+\n+#define work_lock()\n+#define work_unlock()\n+\n+#endif\n+\n+\n static int mark_link(struct object *obj, int type, void *data)\n {\n \tif (!obj)\n@@ -223,6 +299,17 @@ static NORETURN void bad_object(unsigned long offset, const char *format, ...)\n \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n }\n \n+static struct thread_local *get_thread_data()\n+{\n+#ifndef NO_PTHREADS\n+\tif (nr_threads > 1)\n+\t\treturn pthread_getspecific(key);\n+#endif\n+\tassert(nr_threads == 1 &&\n+\t       \"This should only be reached when all threads are gone\");\n+\treturn &nothread_data;\n+}\n+\n static struct base_data *alloc_base_data(void)\n {\n \tstruct base_data *base = xmalloc(sizeof(struct base_data));\n@@ -237,15 +324,16 @@ static void free_base_data(struct base_data *c)\n \tif (c->data) {\n \t\tfree(c->data);\n \t\tc->data = NULL;\n-\t\tbase_cache_used -= c->size;\n+\t\tget_thread_data()->base_cache_used -= c->size;\n \t}\n }\n \n static void prune_base_data(struct base_data *retain)\n {\n \tstruct base_data *b;\n-\tfor (b = base_cache;\n-\t     base_cache_used > delta_base_cache_limit && b;\n+\tstruct thread_local *data = get_thread_data();\n+\tfor (b = data->base_cache;\n+\t     data->base_cache_used > delta_base_cache_limit && b;\n \t     b = b->child) {\n \t\tif (b->data && b != retain)\n \t\t\tfree_base_data(b);\n@@ -257,12 +345,12 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \tif (base)\n \t\tbase->child = c;\n \telse\n-\t\tbase_cache = c;\n+\t\tget_thread_data()->base_cache = c;\n \n \tc->base = base;\n \tc->child = NULL;\n \tif (c->data)\n-\t\tbase_cache_used += c->size;\n+\t\tget_thread_data()->base_cache_used += c->size;\n \tprune_base_data(c);\n }\n \n@@ -272,7 +360,7 @@ static void unlink_base_data(struct base_data *c)\n \tif (base)\n \t\tbase->child = NULL;\n \telse\n-\t\tbase_cache = NULL;\n+\t\tget_thread_data()->base_cache = NULL;\n \tfree_base_data(c);\n }\n \n@@ -461,19 +549,24 @@ static void sha1_object(const void *data, unsigned long size,\n \t\t\tenum object_type type, unsigned char *sha1)\n {\n \thash_sha1_file(data, size, typename(type), sha1);\n+\tread_lock();\n \tif (has_sha1_file(sha1)) {\n \t\tvoid *has_data;\n \t\tenum object_type has_type;\n \t\tunsigned long has_size;\n \t\thas_data = read_sha1_file(sha1, &has_type, &has_size);\n+\t\tread_unlock();\n \t\tif (!has_data)\n \t\t\tdie(\"cannot read existing object %s\", sha1_to_hex(sha1));\n \t\tif (size != has_size || type != has_type ||\n \t\t    memcmp(data, has_data, size) != 0)\n \t\t\tdie(\"SHA1 COLLISION FOUND WITH %s !\", sha1_to_hex(sha1));\n \t\tfree(has_data);\n-\t}\n+\t} else\n+\t\tread_unlock();\n+\n \tif (strict) {\n+\t\tread_lock();\n \t\tif (type == OBJ_BLOB) {\n \t\t\tstruct blob *blob = lookup_blob(sha1);\n \t\t\tif (blob)\n@@ -507,6 +600,7 @@ static void sha1_object(const void *data, unsigned long size,\n \t\t\t}\n \t\t\tobj->flags |= FLAG_CHECKED;\n \t\t}\n+\t\tread_unlock();\n \t}\n }\n \n@@ -552,7 +646,7 @@ static void *get_base_data(struct base_data *c)\n \t\tif (!delta_nr) {\n \t\t\tc->data = get_data_from_pack(obj);\n \t\t\tc->size = obj->size;\n-\t\t\tbase_cache_used += c->size;\n+\t\t\tget_thread_data()->base_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfor (; delta_nr > 0; delta_nr--) {\n@@ -568,7 +662,7 @@ static void *get_base_data(struct base_data *c)\n \t\t\tfree(raw);\n \t\t\tif (!c->data)\n \t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n-\t\t\tbase_cache_used += c->size;\n+\t\t\tget_thread_data()->base_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfree(delta);\n@@ -596,7 +690,9 @@ static void resolve_delta(struct object_entry *delta_obj,\n \t\tbad_object(delta_obj->idx.offset, \"failed to apply delta\");\n \tsha1_object(result->data, result->size, delta_obj->real_type,\n \t\t    delta_obj->idx.sha1);\n+\tcounter_lock();\n \tnr_resolved_deltas++;\n+\tcounter_unlock();\n }\n \n static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n@@ -696,7 +792,31 @@ static void second_pass(struct object_entry *obj)\n \tbase_obj->obj = obj;\n \tbase_obj->data = NULL;\n \tfind_unresolved_deltas(base_obj);\n-\tdisplay_progress(progress, nr_resolved_deltas);\n+}\n+\n+static void *threaded_second_pass(void *arg)\n+{\n+#ifndef NO_PTHREADS\n+\tif (nr_threads > 1)\n+\t\tpthread_setspecific(key, arg);\n+#endif\n+\tfor (;;) {\n+\t\tint i;\n+\t\twork_lock();\n+\t\tdisplay_progress(progress, nr_resolved_deltas);\n+\t\twhile (nr_processed < nr_objects &&\n+\t\t       is_delta_type(objects[nr_processed].type))\n+\t\t\tnr_processed++;\n+\t\tif (nr_processed >= nr_objects) {\n+\t\t\twork_unlock();\n+\t\t\tbreak;\n+\t\t}\n+\t\ti = nr_processed++;\n+\t\twork_unlock();\n+\n+\t\tsecond_pass(&objects[i]);\n+\t}\n+\treturn NULL;\n }\n \n /* Parse all objects and return the pack content SHA1 hash */\n@@ -755,13 +875,25 @@ static void parse_pack_objects(unsigned char *sha1)\n \n \tif (verbose)\n \t\tprogress = start_progress(\"Resolving deltas\", nr_deltas);\n-\tfor (i = 0; i < nr_objects; i++) {\n-\t\tstruct object_entry *obj = &objects[i];\n \n-\t\tif (is_delta_type(obj->type))\n-\t\t\tcontinue;\n-\t\tsecond_pass(obj);\n+\tnr_processed = 0;\n+#ifndef NO_PTHREADS\n+\tif (nr_threads > 1) {\n+\t\tinit_thread();\n+\t\tfor (i = 0; i < nr_threads; i++) {\n+\t\t\tint ret = pthread_create(&thread_data[i].thread, NULL,\n+\t\t\t\t\t\t threaded_second_pass, thread_data + i);\n+\t\t\tif (ret)\n+\t\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t\t}\n+\t\tfor (i = 0; i < nr_threads; i++)\n+\t\t\tpthread_join(thread_data[i].thread, NULL);\n+\n+\t\tcleanup_thread();\n+\t\treturn;\n \t}\n+#endif\n+\tthreaded_second_pass(NULL);\n }\n \n static int write_compressed(struct sha1file *f, void *in, unsigned int size)\n@@ -967,6 +1099,18 @@ static int git_index_pack_config(const char *k, const char *v, void *cb)\n \t\t\tdie(\"bad pack.indexversion=%\"PRIu32, opts->version);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.threads\")) {\n+\t\tnr_threads = git_config_int(k, v);\n+\t\tif (nr_threads < 0)\n+\t\t\tdie(\"invalid number of threads specified (%d)\",\n+\t\t\t    nr_threads);\n+#ifdef NO_PTHREADS\n+\t\tif (nr_threads != 1)\n+\t\t\twarning(\"no threads support, ignoring %s\", k);\n+\t\tnr_threads = 1;\n+#endif\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v, cb);\n }\n \n@@ -1125,6 +1269,17 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t\tkeep_msg = \"\";\n \t\t\t} else if (!prefixcmp(arg, \"--keep=\")) {\n \t\t\t\tkeep_msg = arg + 7;\n+\t\t\t} else if (!prefixcmp(arg, \"--threads=\")) {\n+\t\t\t\tchar *end;\n+\t\t\t\tnr_threads = strtoul(arg+10, &end, 0);\n+\t\t\t\tif (!arg[10] || *end || nr_threads < 0)\n+\t\t\t\t\tusage(index_pack_usage);\n+#ifdef NO_PTHREADS\n+\t\t\t\tif (nr_threads != 1)\n+\t\t\t\t\twarning(\"no threads support, \"\n+\t\t\t\t\t\t\"ignoring %s\", arg);\n+\t\t\t\tnr_threads = 1;\n+#endif\n \t\t\t} else if (!prefixcmp(arg, \"--pack_header=\")) {\n \t\t\t\tstruct pack_header *hdr;\n \t\t\t\tchar *c;\n@@ -1196,6 +1351,15 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tif (strict)\n \t\topts.flags |= WRITE_IDX_STRICT;\n \n+#ifndef NO_PTHREADS\n+\tif (!nr_threads) {\n+\t\tnr_threads = online_cpus();\n+\t\t/* An experiment showed that more threads does not mean faster */\n+\t\tif (nr_threads > 3)\n+\t\t\tnr_threads = 3;\n+\t}\n+#endif\n+\n \tcurr_pack = open_pack_file(pack_name);\n \tparse_pack_header();\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n-- \n1.7.3.1.256.g2539c.dirty\n"},{"id":"186690","messageId":"87y5r684t6.fsf@thomas.inf.ethz.ch","threadId":"29912","inReplyTo":"1331519549-28090-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-03-12T10:57:41Z","receivedAt":"2012-03-12T10:57:41Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n\n> This puts delta resolving on each base on a separate thread, one base\n> cache per thread. Per-thread data is grouped in struct thread_local.\n> When running with nr_threads == 1, no pthreads calls are made. The\n> system essentially runs in non-thread mode.\n\nAs discussed when we took the git-grep measurements, it may be\ninteresting to have a way to run 1 thread.  Can you put in such an\noption?\n\n> An experiment on a Xeon 24 core machine with linux-2.6.git shows that\n> performance does not increase proportional to the number of cores. So\n> by default, we use maximum 3 cores. Some numbers with --threads from 1\n> to 16:\n>\n> 1..4\n> real    1m16.310s  0m48.183s  0m37.866s  0m32.834s\n> user    1m13.773s  1m15.537s  1m15.781s  1m16.233s\n> sys     0m2.480s   0m3.936s   0m4.448s   0m4.852s\n>\n> 5..8\n> real    0m33.170s  0m30.369s  0m28.406s  0m26.968s\n> user    1m31.474s  1m30.322s  1m29.562s  1m28.694s\n> sys     0m6.096s   0m6.268s   0m6.684s   0m7.172s\n\nInteresting.  Is this a real 24-core machine or 12*2 hyperthreaded?\nDoes it use Turbo Boost and how far (how fast and on how many cores\nsimultaneously) does that go?\n\nI'm asking because if Turbo Boost starts to wear off around 4 cores,\nlike these measurements suggest, then it may not be beneficial to spawn\nthreads on 2*2HT CPUs (found in many laptops) where Turbo Boost only\nreally works if you only use a single core.\n\nOh, and could you write a perf test for this? :-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"186694","messageId":"CACsJy8CyLgKrEAriS-uLU9qG6ahBeQ6qLbvHiLvsbTjMZsMW+g@mail.gmail.com","threadId":"29912","inReplyTo":"87y5r684t6.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-12T11:42:14Z","receivedAt":"2012-03-12T11:42:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2012/3/12 Thomas Rast <trast@inf.ethz.ch>:\n> Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n>\n>> This puts delta resolving on each base on a separate thread, one base\n>> cache per thread. Per-thread data is grouped in struct thread_local.\n>> When running with nr_threads == 1, no pthreads calls are made. The\n>> system essentially runs in non-thread mode.\n>\n> As discussed when we took the git-grep measurements, it may be\n> interesting to have a way to run 1 thread.  Can you put in such an\n> option?\n\nSorry I wasn't clear, nr_threads == 1 is equivalent to --threads=1. So\nyes it supports running in non-thread mode.\n\n>> An experiment on a Xeon 24 core machine with linux-2.6.git shows that\n>> performance does not increase proportional to the number of cores. So\n>> by default, we use maximum 3 cores. Some numbers with --threads from 1\n>> to 16:\n>>\n>> 1..4\n>> real    1m16.310s  0m48.183s  0m37.866s  0m32.834s\n>> user    1m13.773s  1m15.537s  1m15.781s  1m16.233s\n>> sys     0m2.480s   0m3.936s   0m4.448s   0m4.852s\n>>\n>> 5..8\n>> real    0m33.170s  0m30.369s  0m28.406s  0m26.968s\n>> user    1m31.474s  1m30.322s  1m29.562s  1m28.694s\n>> sys     0m6.096s   0m6.268s   0m6.684s   0m7.172s\n>\n> Interesting.  Is this a real 24-core machine or 12*2 hyperthreaded?\n> Does it use Turbo Boost and how far (how fast and on how many cores\n> simultaneously) does that go?\n\nI'll check on that later.\n\n> I'm asking because if Turbo Boost starts to wear off around 4 cores,\n> like these measurements suggest, then it may not be beneficial to spawn\n> threads on 2*2HT CPUs (found in many laptops) where Turbo Boost only\n> really works if you only use a single core.\n\nThat might explain why it performs poorly on my two (probably HT)\ncores laptop after 4 threads. I was worried there was some contention\nin the code (and failed to find one) that made it perform worse as\nmore threads were spawn. Any pointers for identifying cpu features in\nlinux?\n\n> Oh, and could you write a perf test for this? :-)\n\nYeah, about that, index-pack is mostly used as part of git-fetch or\ngit-clone. Maybe we need to add --threads to those commands too, then\nwe can see how clone/fetch performs. I'll need such tests anyway if\nI'm going to push for cheaper connectivity check in git-fetch in\nanother thread.\n\nI guess one test with --threads=1, one with threads=2 and one without\n--threads. Any ideas? We can try testing it on half available cores,\nall cores, double available cores, but that would require exporting\nonline_cpus(), perhaps via test command. I didn't see grep --threads\nperf test either (wanted to use it as template..)\n-- \nDuy\n"},{"id":"186696","messageId":"87boo282hg.fsf@thomas.inf.ethz.ch","threadId":"29912","inReplyTo":"CACsJy8CyLgKrEAriS-uLU9qG6ahBeQ6qLbvHiLvsbTjMZsMW+g@mail.gmail.com","subject":"Re: [PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-03-12T11:47:55Z","receivedAt":"2012-03-12T11:47:55Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n\n> 2012/3/12 Thomas Rast <trast@inf.ethz.ch>:\n>> Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n>>\n>>> This puts delta resolving on each base on a separate thread, one base\n>>> cache per thread. Per-thread data is grouped in struct thread_local.\n>>> When running with nr_threads == 1, no pthreads calls are made. The\n>>> system essentially runs in non-thread mode.\n>>\n>> As discussed when we took the git-grep measurements, it may be\n>> interesting to have a way to run 1 thread.  Can you put in such an\n>> option?\n>\n> Sorry I wasn't clear, nr_threads == 1 is equivalent to --threads=1. So\n> yes it supports running in non-thread mode.\n\nWell, in that case I wasn't clear: I meant that there should be a way to\nrun with the whole threading machinery enabled, but still only have one\nthread (doing the work, possibly having another that fills the queue).\n\nThat allows us to see how big the overhead is.\n\n>> Oh, and could you write a perf test for this? :-)\n>\n> Yeah, about that, index-pack is mostly used as part of git-fetch or\n> git-clone. Maybe we need to add --threads to those commands too, then\n> we can see how clone/fetch performs. I'll need such tests anyway if\n> I'm going to push for cheaper connectivity check in git-fetch in\n> another thread.\n>\n> I guess one test with --threads=1, one with threads=2 and one without\n> --threads. Any ideas? We can try testing it on half available cores,\n> all cores, double available cores, but that would require exporting\n> online_cpus(), perhaps via test command. I didn't see grep --threads\n> perf test either (wanted to use it as template..)\n\nA simple one is in t/perf/p7810-grep.sh (in master already).  It doesn't\ntest threads though.  For index-pack you'll also have to find a good way\nto choose a pack, perhaps simply the biggest one in the repo.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"186701","messageId":"CACsJy8A5xY54Ls+yWbY3E_aef22Znu4Jygdoppx4_3+DL17zDA@mail.gmail.com","threadId":"29912","inReplyTo":"87boo282hg.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-12T12:18:44Z","receivedAt":"2012-03-12T12:18:44Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Mar 12, 2012 at 6:47 PM, Thomas Rast <trast@inf.ethz.ch> wrote:\n> Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n>\n>> 2012/3/12 Thomas Rast <trast@inf.ethz.ch>:\n>>> Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n>>>\n>>>> This puts delta resolving on each base on a separate thread, one base\n>>>> cache per thread. Per-thread data is grouped in struct thread_local.\n>>>> When running with nr_threads == 1, no pthreads calls are made. The\n>>>> system essentially runs in non-thread mode.\n>>>\n>>> As discussed when we took the git-grep measurements, it may be\n>>> interesting to have a way to run 1 thread.  Can you put in such an\n>>> option?\n>>\n>> Sorry I wasn't clear, nr_threads == 1 is equivalent to --threads=1. So\n>> yes it supports running in non-thread mode.\n>\n> Well, in that case I wasn't clear: I meant that there should be a way to\n> run with the whole threading machinery enabled, but still only have one\n> thread (doing the work, possibly having another that fills the queue).\n>\n> That allows us to see how big the overhead is.\n\nI really don't want to add overhead, no matter how small it is, to\n--threads=1. How's GIT_USE_THREADS variable for testing purposes?\nThreaded grep can share the same variable if you also like to avoid\nthreading machinery in git grep --threads=1.\n-- \nDuy\n"},{"id":"186886","messageId":"4F5E95A2.8050106@ramsay1.demon.co.uk","threadId":"29912","inReplyTo":"1331519549-28090-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsay1.demon.co.uk","sentAt":"2012-03-13T00:32:34Z","receivedAt":"2012-03-13T00:32:34Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"Nguyễn Thái Ngọc Duy wrote:\n[snipped]\n> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n> ---\n>  I changed Ramsay's mutex patch a little bit and incorporate it here.\n>  Ramsay, it'd be great if you could try it again on MinGW\n\nHmm, well do you want the good news, or the bad news ... :-D\n\nFirst, I should say that I feel like I'm doing a very bad job of\ncommunicating, so let me apologize for that and hope that this time\nI make a better job of it!\n\nThis patch breaks the build on MinGW, since the emulation code has not\n(thus far) included an implementation of pthread_key_delete(). I simply\ncommented out the call to that function, in cleanup_thread(), so that I\ncould test the remainder of the patch.\n\nAlthough this patch is an improvement on previous patches, it still fails\nin *exactly* the same way as earlier attempts.\n\nI probably didn't make clear before that 'nr_threads' has been given too\nmany duties, which is the main reason for me introducing a new variable\n'threads_active'. For example, ...\n\n>  builtin/index-pack.c             |  198 ++++++++++++++++++++++++++++++++++----\n>  3 files changed, 192 insertions(+), 18 deletions(-)\n> \n\n[snipped]\n\n> +static inline void lock_mutex(pthread_mutex_t *mutex)\n> +{\n> +\tif (nr_threads > 1)\n> +\t\tpthread_mutex_lock(mutex);\n> +}\n\nWhat is this condition testing (ie. what does it mean)? Does it mean:\n\n    1. there are some threads currently running ?\n    2. the mutex variables are in a usable state ?\n\nDoes this expression always express the same invariant?\n\nThe answer, of course, is *no*.\n\nLet us consider the call to parse_pack_objects() at line 1367. Let us\nsuppose that we have been asked to use threads (from the config file,\nthe command-line, or simply !NO_PTHREADS), so that when we call the\nparse_pack_objects() function nr_threads > 1.\n\nNote that, at this point, no threads are active and the mutex variables\nhave not been initialised.\n\nNow, at the beginning of parse_pack_objects(), we find some 'first pass'\nprocessing [for (i = 0; i < nr_objects; i++) ... lines 839-851], which\nincludes a call to sha1_object() at line 848. sha1_object() in turn has\nan invocation of the read_lock() macro (line 552), which in turn calls\nlock_mutex() with a pointer to the read_mutex.\n\nNote that, at this point, no threads are active and the mutex variables\nhave not been initialised.\n\nAlso note that \"nr_threads > 1\" is true. At this point, nr_threads is still\nplaying the \"this is how many threads I have been requested to create\" role.\nBut again, no threads have been created yet, the mutex variables haven't been\ninitialised, and ... well, *boom*.\n\nSo, in order to get it to work on MinGW (and this time I only tested on MinGW),\nI had to apply the patch below (look familiar?).\n\n[I ran the same four tests as before, five times in a row. On *one* occasion\nt5300.22 (verify-pack catches a corrupted type/size of the 1st packed object data)\nfailed because the 'dd' command crashed! So, maybe there is a problem lurking.]\n\nATB,\nRamsay Jones\n\n-- >8 --\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 7e3b287..6679734 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -69,6 +69,7 @@ static int nr_processed;\n static int nr_deltas;\n static int nr_resolved_deltas;\n static int nr_threads;\n+static int threads_active;\n \n static int from_stdin;\n static int strict;\n@@ -105,13 +106,13 @@ static pthread_key_t key;\n \n static inline void lock_mutex(pthread_mutex_t *mutex)\n {\n-\tif (nr_threads > 1)\n+\tif (threads_active)\n \t\tpthread_mutex_lock(mutex);\n }\n \n static inline void unlock_mutex(pthread_mutex_t *mutex)\n {\n-\tif (nr_threads > 1)\n+\tif (threads_active)\n \t\tpthread_mutex_unlock(mutex);\n }\n \n@@ -125,14 +126,16 @@ static void init_thread(void)\n \tpthread_mutex_init(&work_mutex, NULL);\n \tpthread_key_create(&key, NULL);\n \tthread_data = xcalloc(nr_threads, sizeof(*thread_data));\n+\tthreads_active = 1;\n }\n \n static void cleanup_thread(void)\n {\n+\tthreads_active = 0;\n \tpthread_mutex_destroy(&read_mutex);\n \tpthread_mutex_destroy(&counter_mutex);\n \tpthread_mutex_destroy(&work_mutex);\n-\tpthread_key_delete(key);\n+\t/*pthread_key_delete(key);*/\n \tnr_threads = 1;\n \tfree(thread_data);\n }\n-- 8< --\n"},{"id":"186928","messageId":"CACsJy8Ae=oy5UsN1zHDptOO4_kVv4NuHgHGp2aPokmO_wgOhwA@mail.gmail.com","threadId":"29912","inReplyTo":"4F5E95A2.8050106@ramsay1.demon.co.uk","subject":"Re: [PATCH v2 2/2] index-pack: support multithreaded delta resolving","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-14T10:29:32Z","receivedAt":"2012-03-14T10:29:32Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2012/3/13 Ramsay Jones <ramsay@ramsay1.demon.co.uk>:\n> Nguyễn Thái Ngọc Duy wrote:\n> [snipped]\n>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n>> ---\n>>  I changed Ramsay's mutex patch a little bit and incorporate it here.\n>>  Ramsay, it'd be great if you could try it again on MinGW\n>\n> Hmm, well do you want the good news, or the bad news ... :-D\n>\n> First, I should say that I feel like I'm doing a very bad job of\n> communicating, so let me apologize for that and hope that this time\n> I make a better job of it!\n>\n> This patch breaks the build on MinGW, since the emulation code has not\n> (thus far) included an implementation of pthread_key_delete(). I simply\n> commented out the call to that function, in cleanup_thread(), so that I\n> could test the remainder of the patch.\n>\n> Although this patch is an improvement on previous patches, it still fails\n> in *exactly* the same way as earlier attempts.\n>\n> I probably didn't make clear before that 'nr_threads' has been given too\n> many duties, which is the main reason for me introducing a new variable\n> 'threads_active'. For example, ...\n\nYou are right. I will incorporate your changes in the next reroll. Thank you.\n\n> [I ran the same four tests as before, five times in a row. On *one* occasion\n> t5300.22 (verify-pack catches a corrupted type/size of the 1st packed object data)\n> failed because the 'dd' command crashed! So, maybe there is a problem lurking.]\n\nI fail to see how verify-pack can make dd crash, especially when\nverify-pack is called after dd in t5300.22. Anyway it's good to keep\nan eye on this case.\n-- \nDuy\n"}]}