{"thread":{"id":"9800","subject":"[PATCH] localize window memory usage accounting","startedAt":"2007-09-06T06:13:08Z","lastAt":"2007-09-07T16:19:26Z","messageCount":10,"participants":["Nicolas Pitre","David Kastrup","Junio C Hamano","Martin Koegler"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"52697","messageId":"11890591912193-git-send-email-nico@cam.org","threadId":"9800","inReplyTo":null,"subject":"[PATCH] straighten the list of objects to deltify","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-06T06:13:08Z","receivedAt":"2007-09-06T06:13:08Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Not all objects are subject to deltification, so avoid carrying those\nalong, and provide the real count to progress display.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |   77 ++++++++++++++++++++++++++----------------------\n 1 files changed, 42 insertions(+), 35 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex e64e3a0..b1c64be 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1313,12 +1313,6 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (trg_entry->type != src_entry->type)\n \t\treturn -1;\n \n-\t/* We do not compute delta to *create* objects we are not\n-\t * going to pack.\n-\t */\n-\tif (trg_entry->preferred_base)\n-\t\treturn -1;\n-\n \t/*\n \t * We do not bother to try a delta that we discarded\n \t * on an earlier try, but only when reusing delta data.\n@@ -1443,43 +1437,24 @@ static void free_unpacked(struct unpacked *n)\n \tn->depth = 0;\n }\n \n-static void find_deltas(struct object_entry **list, int window, int depth)\n+static void find_deltas(struct object_entry **list, unsigned list_size,\n+\t\t\tunsigned nr_deltas, int window, int depth)\n {\n-\tuint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n+\tuint32_t i = list_size, idx = 0, count = 0, processed = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n \tint max_depth;\n \n-\tif (!nr_objects)\n-\t\treturn;\n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n \tif (progress)\n-\t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_result);\n+\t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_deltas);\n \n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n \t\tstruct unpacked *n = array + idx;\n \t\tint j, best_base = -1;\n \n-\t\tif (!entry->preferred_base)\n-\t\t\tprocessed++;\n-\n-\t\tif (progress)\n-\t\t\tdisplay_progress(&progress_state, processed);\n-\n-\t\tif (entry->delta)\n-\t\t\t/* This happens if we decided to reuse existing\n-\t\t\t * delta from a pack.  \"!no_reuse_delta &&\" is implied.\n-\t\t\t */\n-\t\t\tcontinue;\n-\n-\t\tif (entry->size < 50)\n-\t\t\tcontinue;\n-\n-\t\tif (entry->no_try_delta)\n-\t\t\tcontinue;\n-\n \t\tfree_unpacked(n);\n \t\tn->entry = entry;\n \n@@ -1491,6 +1466,15 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\t\tcount--;\n \t\t}\n \n+\t\t/* We do not compute delta to *create* objects we are not\n+\t\t * going to pack.\n+\t\t */\n+\t\tif (entry->preferred_base)\n+\t\t\tgoto next;\n+\n+\t\tif (progress)\n+\t\t\tdisplay_progress(&progress_state, ++processed);\n+\n \t\t/*\n \t\t * If the current object is at pack edge, take the depth the\n \t\t * objects that depend on the current object into account\n@@ -1565,18 +1549,41 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n static void prepare_pack(int window, int depth)\n {\n \tstruct object_entry **delta_list;\n-\tuint32_t i;\n+\tuint32_t i, n, nr_deltas;\n \n \tget_object_details();\n \n-\tif (!window || !depth)\n+\tif (!nr_objects || !window || !depth)\n \t\treturn;\n \n \tdelta_list = xmalloc(nr_objects * sizeof(*delta_list));\n-\tfor (i = 0; i < nr_objects; i++)\n-\t\tdelta_list[i] = objects + i;\n-\tqsort(delta_list, nr_objects, sizeof(*delta_list), type_size_sort);\n-\tfind_deltas(delta_list, window+1, depth);\n+\tnr_deltas = n = 0;\n+\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tstruct object_entry *entry = objects + i;\n+\n+\t\tif (entry->delta)\n+\t\t\t/* This happens if we decided to reuse existing\n+\t\t\t * delta from a pack.  \"!no_reuse_delta &&\" is implied.\n+\t\t\t */\n+\t\t\tcontinue;\n+\n+\t\tif (entry->size < 50)\n+\t\t\tcontinue;\n+\n+\t\tif (entry->no_try_delta)\n+\t\t\tcontinue;\n+\n+\t\tif (!entry->preferred_base)\n+\t\t\tnr_deltas++;\n+\n+\t\tdelta_list[n++] = entry;\n+\t}\n+\n+\tif (nr_deltas) {\n+\t\tqsort(delta_list, n, sizeof(*delta_list), type_size_sort);\n+\t\tfind_deltas(delta_list, n, nr_deltas, window+1, depth);\n+\t}\n \tfree(delta_list);\n }\n \n-- \n1.5.3.1.844.g0a05-dirty\n"},{"id":"52696","messageId":"11890591923123-git-send-email-nico@cam.org","threadId":"9800","inReplyTo":"11890591912193-git-send-email-nico@cam.org","subject":"[PATCH] localize window memory usage accounting","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-06T06:13:09Z","receivedAt":"2007-09-06T06:13:09Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This is to help threadification of delta searching.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |   28 ++++++++++++++--------------\n 1 files changed, 14 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex b1c64be..b8495bf 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -78,7 +78,6 @@ static unsigned long delta_cache_size = 0;\n static unsigned long max_delta_cache_size = 0;\n static unsigned long cache_max_small_delta_size = 1000;\n \n-static unsigned long window_memory_usage = 0;\n static unsigned long window_memory_limit = 0;\n \n /*\n@@ -1300,7 +1299,7 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,\n  * one.\n  */\n static int try_delta(struct unpacked *trg, struct unpacked *src,\n-\t\t     unsigned max_depth)\n+\t\t     unsigned max_depth, unsigned long *mem_usage)\n {\n \tstruct object_entry *trg_entry = trg->entry;\n \tstruct object_entry *src_entry = src->entry;\n@@ -1356,7 +1355,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tif (sz != trg_size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n \t\t\t    sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);\n-\t\twindow_memory_usage += sz;\n+\t\t*mem_usage += sz;\n \t}\n \tif (!src->data) {\n \t\tsrc->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n@@ -1366,7 +1365,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tif (sz != src_size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\",\n \t\t\t    sha1_to_hex(src_entry->idx.sha1), sz, src_size);\n-\t\twindow_memory_usage += sz;\n+\t\t*mem_usage += sz;\n \t}\n \tif (!src->index) {\n \t\tsrc->index = create_delta_index(src->data, src_size);\n@@ -1376,7 +1375,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t\t\twarning(\"suboptimal pack - out of memory\");\n \t\t\treturn 0;\n \t\t}\n-\t\twindow_memory_usage += sizeof_delta_index(src->index);\n+\t\t*mem_usage += sizeof_delta_index(src->index);\n \t}\n \n \tdelta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);\n@@ -1423,18 +1422,19 @@ static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n \treturn m;\n }\n \n-static void free_unpacked(struct unpacked *n)\n+static unsigned long free_unpacked(struct unpacked *n)\n {\n-\twindow_memory_usage -= sizeof_delta_index(n->index);\n+\tunsigned long freed_mem = sizeof_delta_index(n->index);\n \tfree_delta_index(n->index);\n \tn->index = NULL;\n \tif (n->data) {\n+\t\tfreed_mem += n->entry->size;\n \t\tfree(n->data);\n \t\tn->data = NULL;\n-\t\twindow_memory_usage -= n->entry->size;\n \t}\n \tn->entry = NULL;\n \tn->depth = 0;\n+\treturn freed_mem;\n }\n \n static void find_deltas(struct object_entry **list, unsigned list_size,\n@@ -1443,7 +1443,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \tuint32_t i = list_size, idx = 0, count = 0, processed = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n-\tint max_depth;\n+\tunsigned long mem_usage = 0;\n \n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n@@ -1453,16 +1453,16 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n \t\tstruct unpacked *n = array + idx;\n-\t\tint j, best_base = -1;\n+\t\tint j, max_depth, best_base = -1;\n \n-\t\tfree_unpacked(n);\n+\t\tmem_usage -= free_unpacked(n);\n \t\tn->entry = entry;\n \n \t\twhile (window_memory_limit &&\n-\t\t       window_memory_usage > window_memory_limit &&\n+\t\t       mem_usage > window_memory_limit &&\n \t\t       count > 1) {\n \t\t\tuint32_t tail = (idx + window - count) % window;\n-\t\t\tfree_unpacked(array + tail);\n+\t\t\tmem_usage -= free_unpacked(array + tail);\n \t\t\tcount--;\n \t\t}\n \n@@ -1497,7 +1497,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\t\tm = array + other_idx;\n \t\t\tif (!m->entry)\n \t\t\t\tbreak;\n-\t\t\tret = try_delta(n, m, max_depth);\n+\t\t\tret = try_delta(n, m, max_depth, &mem_usage);\n \t\t\tif (ret < 0)\n \t\t\t\tbreak;\n \t\t\telse if (ret > 0)\n-- \n1.5.3.1.844.g0a05-dirty\n"},{"id":"52698","messageId":"11890591923270-git-send-email-nico@cam.org","threadId":"9800","inReplyTo":"11890591923123-git-send-email-nico@cam.org","subject":"[PATCH] rearrange delta search progress reporting","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-06T06:13:10Z","receivedAt":"2007-09-06T06:13:10Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This is to help threadification of the delta search code, with a bonus\nconsistency check.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |   23 ++++++++++++++---------\n 1 files changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex b8495bf..9d56592 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1438,17 +1438,15 @@ static unsigned long free_unpacked(struct unpacked *n)\n }\n \n static void find_deltas(struct object_entry **list, unsigned list_size,\n-\t\t\tunsigned nr_deltas, int window, int depth)\n+\t\t\tint window, int depth, unsigned *processed)\n {\n-\tuint32_t i = list_size, idx = 0, count = 0, processed = 0;\n+\tuint32_t i = list_size, idx = 0, count = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n \tunsigned long mem_usage = 0;\n \n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n-\tif (progress)\n-\t\tstart_progress(&progress_state, \"Deltifying %u objects...\", \"\", nr_deltas);\n \n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n@@ -1472,8 +1470,9 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\tif (entry->preferred_base)\n \t\t\tgoto next;\n \n+\t\t(*processed)++;\n \t\tif (progress)\n-\t\t\tdisplay_progress(&progress_state, ++processed);\n+\t\t\tdisplay_progress(&progress_state, *processed);\n \n \t\t/*\n \t\t * If the current object is at pack edge, take the depth the\n@@ -1536,9 +1535,6 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\t\tidx = 0;\n \t} while (i > 0);\n \n-\tif (progress)\n-\t\tstop_progress(&progress_state);\n-\n \tfor (i = 0; i < window; ++i) {\n \t\tfree_delta_index(array[i].index);\n \t\tfree(array[i].data);\n@@ -1581,8 +1577,17 @@ static void prepare_pack(int window, int depth)\n \t}\n \n \tif (nr_deltas) {\n+\t\tunsigned nr_done = 0;\n+\t\tif (progress)\n+\t\t\tstart_progress(&progress_state,\n+\t\t\t\t       \"Deltifying %u objects...\", \"\",\n+\t\t\t\t       nr_deltas);\n \t\tqsort(delta_list, n, sizeof(*delta_list), type_size_sort);\n-\t\tfind_deltas(delta_list, n, nr_deltas, window+1, depth);\n+\t\tfind_deltas(delta_list, n, window+1, depth, &nr_done);\n+\t\tif (progress)\n+\t\t\tstop_progress(&progress_state);\n+\t\tif (nr_done != nr_deltas)\n+\t\t\tdie(\"inconsistency with delta count\");\n \t}\n \tfree(delta_list);\n }\n-- \n1.5.3.1.844.g0a05-dirty\n"},{"id":"52699","messageId":"1189059193250-git-send-email-nico@cam.org","threadId":"9800","inReplyTo":"11890591923270-git-send-email-nico@cam.org","subject":"[PATCH] basic threaded delta search","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-06T06:13:11Z","receivedAt":"2007-09-06T06:13:11Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"this is still rough, hence it is disabled by default.  You need to compile\nwith \"make THREADED_DELTA_SEARCH=1 ...\" at the moment.\n\nThreading is done on different portions of the object list to be\ndeltified. This is currently done by spliting the list into n parts and\nthen a thread is spawned for each of them.  A better method would consist\nof spliting the list into more smaller parts and have the n threads\npick the next part available.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n Makefile               |    8 +++++\n builtin-pack-objects.c |   83 +++++++++++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 90 insertions(+), 1 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 51af531..a92fb31 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,6 +122,9 @@ all::\n # If not set it defaults to the bare 'wish'. If it is set to the empty\n # string then NO_TCLTK will be forced (this is used by configure script).\n #\n+# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n+# parallel delta searching when packing objects.\n+#\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -662,6 +665,11 @@ ifdef NO_HSTRERROR\n \tCOMPAT_OBJS += compat/hstrerror.o\n endif\n \n+ifdef THREADED_DELTA_SEARCH\n+\tBASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\n+\tEXTLIBS += -lpthread\n+endif\n+\n ifeq ($(TCLTK_PATH),)\n NO_TCLTK=NoThanks\n endif\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 9d56592..1bcee23 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -15,6 +15,10 @@\n #include \"list-objects.h\"\n #include \"progress.h\"\n \n+#ifdef THREADED_DELTA_SEARCH\n+#include <pthread.h>\n+#endif\n+\n static const char pack_usage[] = \"\\\n git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n \t[--max-pack-size=N] [--local] [--incremental] \\n\\\n@@ -1290,6 +1294,25 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,\n \treturn 0;\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+static pthread_mutex_t read_mutex = PTHREAD_MUTEX_INITIALIZER;\n+#define read_lock()\t\tpthread_mutex_lock(&read_mutex)\n+#define read_unlock()\t\tpthread_mutex_unlock(&read_mutex)\n+\n+static pthread_mutex_t progress_mutex = PTHREAD_MUTEX_INITIALIZER;\n+#define progress_lock()\t\tpthread_mutex_lock(&progress_mutex)\n+#define progress_unlock()\tpthread_mutex_unlock(&progress_mutex)\n+\n+#else\n+\n+#define read_lock()\t\t0\n+#define read_unlock()\t\t0\n+#define progress_lock()\t\t0\n+#define progress_unlock()\t0\n+\n+#endif\n+\n /*\n  * We search for deltas _backwards_ in a list sorted by type and\n  * by size, so that we see progressively smaller and smaller files.\n@@ -1348,7 +1371,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \n \t/* Load data if not already done */\n \tif (!trg->data) {\n+\t\tread_lock();\n \t\ttrg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);\n+\t\tread_unlock();\n \t\tif (!trg->data)\n \t\t\tdie(\"object %s cannot be read\",\n \t\t\t    sha1_to_hex(trg_entry->idx.sha1));\n@@ -1358,7 +1383,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t*mem_usage += sz;\n \t}\n \tif (!src->data) {\n+\t\tread_lock();\n \t\tsrc->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);\n+\t\tread_unlock();\n \t\tif (!src->data)\n \t\t\tdie(\"object %s cannot be read\",\n \t\t\t    sha1_to_hex(src_entry->idx.sha1));\n@@ -1470,9 +1497,11 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\tif (entry->preferred_base)\n \t\t\tgoto next;\n \n+\t\tprogress_lock();\n \t\t(*processed)++;\n \t\tif (progress)\n \t\t\tdisplay_progress(&progress_state, *processed);\n+\t\tprogress_unlock();\n \n \t\t/*\n \t\t * If the current object is at pack edge, take the depth the\n@@ -1542,6 +1571,58 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \tfree(array);\n }\n \n+#ifdef THREADED_DELTA_SEARCH\n+\n+struct thread_params {\n+\tpthread_t thread;\n+\tstruct object_entry **list;\n+\tunsigned list_size;\n+\tint window;\n+\tint depth;\n+\tunsigned *processed;\n+};\n+\n+static void *threaded_find_deltas(void *arg)\n+{\n+\tstruct thread_params *p = arg;\n+\tif (p->list_size)\n+\t\tfind_deltas(p->list, p->list_size,\n+\t\t\t    p->window, p->depth, p->processed);\n+\treturn NULL;\n+}\n+\n+#define NR_THREADS\t8\n+\n+static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n+\t\t\t   int window, int depth, unsigned *processed)\n+{\n+\tstruct thread_params p[NR_THREADS];\n+\tint i, ret;\n+\n+\tfor (i = 0; i < NR_THREADS; i++) {\n+\t\tunsigned sublist_size = list_size / (NR_THREADS - i);\n+\t\tp[i].list = list;\n+\t\tp[i].list_size = sublist_size;\n+\t\tp[i].window = window;\n+\t\tp[i].depth = depth;\n+\t\tp[i].processed = processed;\n+\t\tret = pthread_create(&p[i].thread, NULL,\n+\t\t\t\t     threaded_find_deltas, &p[i]);\n+\t\tif (ret)\n+\t\t\tdie(\"unable to create thread: %s\", strerror(ret));\n+\t\tlist += sublist_size;\n+\t\tlist_size -= sublist_size;\n+\t}\n+\n+\tfor (i = 0; i < NR_THREADS; i++) {\n+\t\tpthread_join(p[i].thread, NULL);\n+\t}\n+}\n+\n+#else\n+#define ll_find_deltas find_deltas\n+#endif\n+\n static void prepare_pack(int window, int depth)\n {\n \tstruct object_entry **delta_list;\n@@ -1583,7 +1664,7 @@ static void prepare_pack(int window, int depth)\n \t\t\t\t       \"Deltifying %u objects...\", \"\",\n \t\t\t\t       nr_deltas);\n \t\tqsort(delta_list, n, sizeof(*delta_list), type_size_sort);\n-\t\tfind_deltas(delta_list, n, window+1, depth, &nr_done);\n+\t\tll_find_deltas(delta_list, n, window+1, depth, &nr_done);\n \t\tif (progress)\n \t\t\tstop_progress(&progress_state);\n \t\tif (nr_done != nr_deltas)\n-- \n1.5.3.1.844.g0a05-dirty\n"},{"id":"52701","messageId":"85ps0wfh8h.fsf@lola.goethe.zz","threadId":"9800","inReplyTo":"1189059193250-git-send-email-nico@cam.org","subject":"Re: [PATCH] basic threaded delta search","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-06T06:19:42Z","receivedAt":"2007-09-06T06:19:42Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> this is still rough, hence it is disabled by default.  You need to compile\n> with \"make THREADED_DELTA_SEARCH=1 ...\" at the moment.\n>\n> Threading is done on different portions of the object list to be\n> deltified. This is currently done by spliting the list into n parts and\n> then a thread is spawned for each of them.  A better method would consist\n> of spliting the list into more smaller parts and have the n threads\n> pick the next part available.\n\nIn my experience, the worst performance hit happens when the real\nmemory is exhausted and things start paging.  Threading on different\nportions of the object list is going to exacerbate the problem in the\nareas where it hits worst.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"52703","messageId":"alpine.LFD.0.9999.0709060220520.21186@xanadu.home","threadId":"9800","inReplyTo":"85ps0wfh8h.fsf@lola.goethe.zz","subject":"Re: [PATCH] basic threaded delta search","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-06T06:23:38Z","receivedAt":"2007-09-06T06:23:38Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 6 Sep 2007, David Kastrup wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > this is still rough, hence it is disabled by default.  You need to compile\n> > with \"make THREADED_DELTA_SEARCH=1 ...\" at the moment.\n> >\n> > Threading is done on different portions of the object list to be\n> > deltified. This is currently done by spliting the list into n parts and\n> > then a thread is spawned for each of them.  A better method would consist\n> > of spliting the list into more smaller parts and have the n threads\n> > pick the next part available.\n> \n> In my experience, the worst performance hit happens when the real\n> memory is exhausted and things start paging.  Threading on different\n> portions of the object list is going to exacerbate the problem in the\n> areas where it hits worst.\n\nJust don't use it if you don't have 1) a SMP machine and 2) enough ram.\nThreading will be enabled with a command line argument at some point.\n\n\nNicolas\n"},{"id":"52705","messageId":"7vwsv4cm6b.fsf@gitster.siamese.dyndns.org","threadId":"9800","inReplyTo":"1189059193250-git-send-email-nico@cam.org","subject":"Re: [PATCH] basic threaded delta search","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-06T07:01:16Z","receivedAt":"2007-09-06T07:01:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> this is still rough, hence it is disabled by default.  You need to compile\n> with \"make THREADED_DELTA_SEARCH=1 ...\" at the moment.\n>\n> Threading is done on different portions of the object list to be\n> deltified. This is currently done by spliting the list into n parts and\n> then a thread is spawned for each of them.  A better method would consist\n> of spliting the list into more smaller parts and have the n threads\n> pick the next part available.\n\nHmmm.  I wonder how the result is affected by such a partition;\naren't you going to have many objects that could have used\nsomebody else as a delta but gets stored as base because they\nhappen to be a very early part of their partition (and lacking\ndelta base candidates in the window)?  You cannot solve it with\noverlapping partitions without busting the depth limit easily\neither, I suspect.  Also how would this interact with the LRU\ndelta base window we discussed a week or two ago?\n\nSeparating the list into different object types would not have\nany adverse impact coming from the \"horizon\" of delta base\ncandidates window (because we do not deltify across types), but\nthat is not very useful because we cannot gain much parallerism\nfrom such a partition.\n"},{"id":"52757","messageId":"alpine.LFD.0.9999.0709061014280.21186@xanadu.home","threadId":"9800","inReplyTo":"7vwsv4cm6b.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] basic threaded delta search","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-06T14:48:06Z","receivedAt":"2007-09-06T14:48:06Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 6 Sep 2007, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > this is still rough, hence it is disabled by default.  You need to compile\n> > with \"make THREADED_DELTA_SEARCH=1 ...\" at the moment.\n> >\n> > Threading is done on different portions of the object list to be\n> > deltified. This is currently done by spliting the list into n parts and\n> > then a thread is spawned for each of them.  A better method would consist\n> > of spliting the list into more smaller parts and have the n threads\n> > pick the next part available.\n> \n> Hmmm.  I wonder how the result is affected by such a partition;\n> aren't you going to have many objects that could have used\n> somebody else as a delta but gets stored as base because they\n> happen to be a very early part of their partition (and lacking\n> delta base candidates in the window)?  \n\nYes.  On a largish repo that shouldn't be significant though, not worse \nthan repacking multiple packs into one without -f.\n\n> You cannot solve it with\n> overlapping partitions without busting the depth limit easily\n> either, I suspect.\n\nMy plan is to call find_deltas() again over partition boundaries after \nadjacent partitions have been processed.  If delta_child is properly \nmaintained in all cases (trivial) then this should just work.\n\n> Also how would this interact with the LRU\n> delta base window we discussed a week or two ago?\n\nThis is completely orthogonal.\n\n> Separating the list into different object types would not have\n> any adverse impact coming from the \"horizon\" of delta base\n> candidates window (because we do not deltify across types), but\n> that is not very useful because we cannot gain much parallerism\n> from such a partition.\n\nIndeed.  Even with a straight split with equal number of objects, some \nthreads currently complete much faster than others.  This is why a more \nsophisticated distribution of work is still needed to keep the desired \namount of threads busy all the time.\n\n\nNicolas\n"},{"id":"52853","messageId":"20070907061105.GA1379@auto.tuwien.ac.at","threadId":"9800","inReplyTo":"alpine.LFD.0.9999.0709061014280.21186@xanadu.home","subject":"Re: [PATCH] basic threaded delta search","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-09-07T06:11:05Z","receivedAt":"2007-09-07T06:11:05Z","isPatch":true,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"On Thu, Sep 06, 2007 at 10:48:06AM -0400, Nicolas Pitre wrote:\n> On Thu, 6 Sep 2007, Junio C Hamano wrote:\n> > Also how would this interact with the LRU\n> > delta base window we discussed a week or two ago?\n> \n> This is completely orthogonal.\n\nMaybe we should adjust the split point of the the object list so, that\nobjects with the same name hash are processed by one thread, as the LRU\ncould provide the most benefit for these objects.\n\nI think of something like (totally untested):\n        for (i = 0; i < NR_THREADS; i++) {\n                unsigned sublist_size = list_size / (NR_THREADS - i);\n+\t\twhile (sublist_size < list_size && list[0]->hash == list[1]->hash)\n+\t\t\tsublist_size++;\n                p[i].list = list;\n                p[i].list_size = sublist_size;\n                p[i].window = window;\n                p[i].depth = depth;\n                p[i].processed = processed;\n                ret = pthread_create(&p[i].thread, NULL,\n                                     threaded_find_deltas, &p[i]);\n                if (ret)\n                        die(\"unable to create thread: %s\", strerror(ret));\n                list += sublist_size;\n                list_size -= sublist_size;\n        }\n\nmfg Martin Kögler\n"},{"id":"52918","messageId":"alpine.LFD.0.9999.0709071211420.21186@xanadu.home","threadId":"9800","inReplyTo":"20070907061105.GA1379@auto.tuwien.ac.at","subject":"Re: [PATCH] basic threaded delta search","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-07T16:19:26Z","receivedAt":"2007-09-07T16:19:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 7 Sep 2007, Martin Koegler wrote:\n\n> On Thu, Sep 06, 2007 at 10:48:06AM -0400, Nicolas Pitre wrote:\n> > On Thu, 6 Sep 2007, Junio C Hamano wrote:\n> > > Also how would this interact with the LRU\n> > > delta base window we discussed a week or two ago?\n> > \n> > This is completely orthogonal.\n> \n> Maybe we should adjust the split point of the the object list so, that\n> objects with the same name hash are processed by one thread, as the LRU\n> could provide the most benefit for these objects.\n> \n> I think of something like (totally untested):\n>         for (i = 0; i < NR_THREADS; i++) {\n>                 unsigned sublist_size = list_size / (NR_THREADS - i);\n> +\t\twhile (sublist_size < list_size && list[0]->hash == list[1]->hash)\n> +\t\t\tsublist_size++;\n\nI guess you mean list[sublist_size-1]->hash == list[sublist_size]->hash.\nBut yeah that is a good idea.\n\n\nNicolas\n"}]}