{"thread":{"id":"11188","subject":"[PATCH 2/2] pack-objects: fix threaded load balancing","startedAt":"2007-12-08T05:03:17Z","lastAt":"2007-12-13T07:15:16Z","messageCount":16,"participants":["Nicolas Pitre","Jeff King","Jon Smirl","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"62374","messageId":"alpine.LFD.0.99999.0712080000120.555@xanadu.home","threadId":"11188","inReplyTo":null,"subject":"[PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-08T05:03:17Z","receivedAt":"2007-12-08T05:03:17Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nThe current method consists of a master thread serving chunks of objects\nto work threads when they're done with their previous chunk. The issue\nis to determine the best chunk size: making it too large creates poor\nload balancing, while making it too small has a negative effect on pack\nsize because of the increased number of chunk boundaries and poor delta\nwindow utilization.\n\nThis patch implements a completely different approach by initially\nsplitting the work in large chunks uniformly amongst all threads, and\nwhenever a thread is done then it steals half of the remaining work from\nanother thread with the largest amount of unprocessed objects.\n\nThis has the advantage of greatly reducing the number of chunk boundaries\nwith an almost perfect load balancing.\n\nSigned-off-by: Nicolas Pitre \n---\n builtin-pack-objects.c | 117 +++++++++++++++++++++++++++++++++++-------------\n 1 files changed, 85 insertions(+), 32 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 5002cc6..fcc1901 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1479,10 +1479,10 @@ static unsigned long free_unpacked(struct unpacked *n)\n \treturn freed_mem;\n }\n \n-static void find_deltas(struct object_entry **list, unsigned list_size,\n+static void find_deltas(struct object_entry **list, unsigned *list_size,\n \t\t\tint window, int depth, unsigned *processed)\n {\n-\tuint32_t i = 0, idx = 0, count = 0;\n+\tuint32_t i, idx = 0, count = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n \tunsigned long mem_usage = 0;\n@@ -1490,11 +1490,23 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \tarray = xmalloc(array_size);\n \tmemset(array, 0, array_size);\n \n-\tdo {\n-\t\tstruct object_entry *entry = list[i++];\n+\tfor (;;) {\n+\t\tstruct object_entry *entry = *list++;\n \t\tstruct unpacked *n = array + idx;\n \t\tint j, max_depth, best_base = -1;\n \n+\t\tprogress_lock();\n+\t\tif (!*list_size) {\n+\t\t\tprogress_unlock();\n+\t\t\tbreak;\n+\t\t}\n+\t\t(*list_size)--;\n+\t\tif (!entry->preferred_base) {\n+\t\t\t(*processed)++;\n+\t\t\tdisplay_progress(progress_state, *processed);\n+\t\t}\n+\t\tprogress_unlock();\n+\n \t\tmem_usage -= free_unpacked(n);\n \t\tn->entry = entry;\n \n@@ -1512,11 +1524,6 @@ 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\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 \t\t * objects that depend on the current object into account\n@@ -1576,7 +1583,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\t\tcount++;\n \t\tif (idx >= window)\n \t\t\tidx = 0;\n-\t} while (i < list_size);\n+\t}\n \n \tfor (i = 0; i < window; ++i) {\n \t\tfree_delta_index(array[i].index);\n@@ -1591,6 +1598,7 @@ struct thread_params {\n \tpthread_t thread;\n \tstruct object_entry **list;\n \tunsigned list_size;\n+\tunsigned remaining;\n \tint window;\n \tint depth;\n \tunsigned *processed;\n@@ -1612,10 +1620,10 @@ static void *threaded_find_deltas(void *arg)\n \t\tpthread_mutex_lock(&data_ready);\n \t\tpthread_mutex_unlock(&data_request);\n \n-\t\tif (!me->list_size)\n+\t\tif (!me->remaining)\n \t\t\treturn NULL;\n \n-\t\tfind_deltas(me->list, me->list_size,\n+\t\tfind_deltas(me->list, &me->remaining,\n \t\t\t me->window, me->depth, me->processed);\n \t}\n }\n@@ -1624,57 +1632,102 @@ 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 *target, p[delta_search_threads];\n-\tint i, ret;\n-\tunsigned chunk_size;\n+\tint i, ret, active_threads = 0;\n \n \tif (delta_search_threads <= 1) {\n-\t\tfind_deltas(list, list_size, window, depth, processed);\n+\t\tfind_deltas(list, &list_size, window, depth, processed);\n \t\treturn;\n \t}\n \n \tpthread_mutex_lock(&data_provider);\n \tpthread_mutex_lock(&data_ready);\n \n+\t/* Start work threads. */\n \tfor (i = 0; i < delta_search_threads; i++) {\n \t\tp[i].window = window;\n \t\tp[i].depth = depth;\n \t\tp[i].processed = processed;\n+\t\tp[i].remaining = 0;\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\tactive_threads++;\n \t}\n \n-\t/* this should be auto-tuned somehow */\n-\tchunk_size = window * 1000;\n+\t/* Then partition the work amongst them. */\n+\tfor (i = 0; i < delta_search_threads; i++) {\n+\t\tunsigned sub_size = list_size / (delta_search_threads - i);\n \n-\tdo {\n-\t\tunsigned sublist_size = chunk_size;\n-\t\tif (sublist_size > list_size)\n-\t\t\tsublist_size = list_size;\n+\t\tpthread_mutex_lock(&data_provider);\n+\t\ttarget = data_requester;\n+\t\tif (!sub_size) {\n+\t\t\tpthread_mutex_unlock(&data_ready);\n+\t\t\tpthread_join(target->thread, NULL);\n+\t\t\tactive_threads--;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\t/* try to split chunks on \"path\" boundaries */\n-\t\twhile (sublist_size < list_size && list[sublist_size]->hash &&\n-\t\t list[sublist_size]->hash == list[sublist_size-1]->hash)\n-\t\t\tsublist_size++;\n+\t\twhile (sub_size < list_size && list[sub_size]->hash &&\n+\t\t list[sub_size]->hash == list[sub_size-1]->hash)\n+\t\t\tsub_size++;\n+\n+\t\ttarget->list = list;\n+\t\ttarget->list_size = sub_size;\n+\t\ttarget->remaining = sub_size;\n+\t\tpthread_mutex_unlock(&data_ready);\n \n+\t\tlist += sub_size;\n+\t\tlist_size -= sub_size;\n+\t}\n+\n+\t/*\n+\t * Now let's wait for work completion. Each time a thread is done\n+\t * with its work, we steal half of the remaining work from the\n+\t * thread with the largest number of unprocessed objects and give\n+\t * it to that newly idle thread. This ensure good load balancing\n+\t * until the remaining object list segments are simply too short\n+\t * to be worth splitting anymore.\n+\t */\n+\tdo {\n+\t\tstruct thread_params *victim = NULL;\n+\t\tunsigned sub_size = 0;\n \t\tpthread_mutex_lock(&data_provider);\n \t\ttarget = data_requester;\n-\t\ttarget->list = list;\n-\t\ttarget->list_size = sublist_size;\n+\n+\t\tprogress_lock();\n+\t\tfor (i = 0; i < delta_search_threads; i++)\n+\t\t\tif (p[i].remaining > 2*window &&\n+\t\t\t (!victim || victim->remaining < p[i].remaining))\n+\t\t\t\tvictim = &p[i];\n+\t\tif (victim) {\n+\t\t\tsub_size = victim->remaining / 2;\n+\t\t\tlist = victim->list + victim->list_size - sub_size;\n+\t\t\twhile (sub_size && list[0]->hash &&\n+\t\t\t list[0]->hash == list[-1]->hash) {\n+\t\t\t\tlist++;\n+\t\t\t\tsub_size--;\n+\t\t\t}\n+\t\t\ttarget->list = list;\n+\t\t\tvictim->list_size -= sub_size;\n+\t\t\tvictim->remaining -= sub_size;\n+\t\t}\n+\t\tprogress_unlock();\n+\n+\t\ttarget->list_size = sub_size;\n+\t\ttarget->remaining = sub_size;\n \t\tpthread_mutex_unlock(&data_ready);\n \n-\t\tlist += sublist_size;\n-\t\tlist_size -= sublist_size;\n-\t\tif (!sublist_size) {\n+\t\tif (!sub_size) {\n \t\t\tpthread_join(target->thread, NULL);\n-\t\t\ti--;\n+\t\t\tactive_threads--;\n \t\t}\n-\t} while (i);\n+\t} while (active_threads);\n }\n \n #else\n-#define ll_find_deltas find_deltas\n+#define ll_find_deltas(l, s, w, d, p)\tfind_deltas(l, &s, w, d, p)\n #endif\n \n static void prepare_pack(int window, int depth)\n-- \n1.5.3.7.2184.ge321d-dirty\n"},{"id":"62395","messageId":"20071208091842.GA23489@sigill.intra.peff.net","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712080000120.555@xanadu.home","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-12-08T09:18:44Z","receivedAt":"2007-12-08T09:18:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 08, 2007 at 12:03:17AM -0500, Nicolas Pitre wrote:\n\n> This patch implements a completely different approach by initially\n> splitting the work in large chunks uniformly amongst all threads, and\n> whenever a thread is done then it steals half of the remaining work from\n> another thread with the largest amount of unprocessed objects.\n\nYay! This works great on my \"pack a few hundred very large objects\" repo.\n\n-Peff\n"},{"id":"62538","messageId":"9e4733910712092010m31043915kb6fd0867beefa8f3@mail.gmail.com","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712080000120.555@xanadu.home","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T04:10:58Z","receivedAt":"2007-12-10T04:10:58Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I added a couple of printfs to debug this.\nWhy did the thread exit when there were still 72,000 objects left?\nAnother one exited with 50,000 objects left.\nThe repack is still running, it has been proceeding on two cores for\n10 minutes after the two threads exited.\n\njonsmirl@terra:/video/gcc$ git-repack -a -d -f --depth=250 --window=250\nCounting objects: 828348, done.\n\n starting thread 0\nCompressing objects: 0% (1/809010)\n starting thread 1\n\n starting thread 2\n\n starting thread 3\nCompressing objects: 59% (478011/809010)\n victim 0x7fffc7976480 sub_size 76058\n\nthread 0x7fffc79764f8 sub_size 76058\nCompressing objects: 62% (504273/809010)\n victim 0x7fffc79764a8 sub_size 69967\n\nthread 0x7fffc79764d0 sub_size 69967\nCompressing objects: 82% (664231/809010)\n victim 0x7fffc7976480 sub_size 35308\n\nthread 0x7fffc79764d0 sub_size 35308\nCompressing objects: 91% (736690/809010)\n victim 0x7fffc79764d0 sub_size 0\n\nthread 0x7fffc79764f8 sub_size 0\nCompressing objects: 93% (758922/809010)\n victim 0x7fffc79764d0 sub_size 0\n\nthread 0x7fffc79764a8 sub_size 0\n\n\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62539","messageId":"9e4733910712092030j5cf7dfdcrb3a003fbce391422@mail.gmail.com","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712080000120.555@xanadu.home","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T04:30:54Z","receivedAt":"2007-12-10T04:30:54Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 12/8/07, Nicolas Pitre wrote:\n>\n> The current method consists of a master thread serving chunks of objects\n> to work threads when they're done with their previous chunk. The issue\n> is to determine the best chunk size: making it too large creates poor\n> load balancing, while making it too small has a negative effect on pack\n> size because of the increased number of chunk boundaries and poor delta\n> window utilization.\n>\n> This patch implements a completely different approach by initially\n> splitting the work in large chunks uniformly amongst all threads, and\n> whenever a thread is done then it steals half of the remaining work from\n> another thread with the largest amount of unprocessed objects.\n>\n> This has the advantage of greatly reducing the number of chunk boundaries\n> with an almost perfect load balancing.\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n> builtin-pack-objects.c | 117 +++++++++++++++++++++++++++++++++++-------------\n> 1 files changed, 85 insertions(+), 32 deletions(-)\n>\n> diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> index 5002cc6..fcc1901 100644\n> --- a/builtin-pack-objects.c\n> +++ b/builtin-pack-objects.c\n> @@ -1479,10 +1479,10 @@ static unsigned long free_unpacked(struct unpacked *n)\n> return freed_mem;\n> }\n>\n> -static void find_deltas(struct object_entry **list, unsigned list_size,\n> +static void find_deltas(struct object_entry **list, unsigned *list_size,\n> int window, int depth, unsigned *processed)\n> {\n> - uint32_t i = 0, idx = 0, count = 0;\n> + uint32_t i, idx = 0, count = 0;\n> unsigned int array_size = window * sizeof(struct unpacked);\n> struct unpacked *array;\n> unsigned long mem_usage = 0;\n> @@ -1490,11 +1490,23 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n> array = xmalloc(array_size);\n> memset(array, 0, array_size);\n>\n> - do {\n> - struct object_entry *entry = list[i++];\n> + for (;;) {\n> + struct object_entry *entry = *list++;\n> struct unpacked *n = array + idx;\n> int j, max_depth, best_base = -1;\n>\n> + progress_lock();\n> + if (!*list_size) {\n> + progress_unlock();\n> + break;\n> + }\n> + (*list_size)--;\n> + if (!entry->preferred_base) {\n> + (*processed)++;\n> + display_progress(progress_state, *processed);\n> + }\n> + progress_unlock();\n> +\n> mem_usage -= free_unpacked(n);\n> n->entry = entry;\n>\n> @@ -1512,11 +1524,6 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n> if (entry->preferred_base)\n> goto next;\n>\n> - progress_lock();\n> - (*processed)++;\n> - display_progress(progress_state, *processed);\n> - progress_unlock();\n> -\n> /*\n> * If the current object is at pack edge, take the depth the\n> * objects that depend on the current object into account\n> @@ -1576,7 +1583,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n> count++;\n> if (idx >= window)\n> idx = 0;\n> - } while (i < list_size);\n> + }\n>\n> for (i = 0; i < window; ++i) {\n> free_delta_index(array[i].index);\n> @@ -1591,6 +1598,7 @@ struct thread_params {\n> pthread_t thread;\n> struct object_entry **list;\n> unsigned list_size;\n> + unsigned remaining;\n> int window;\n> int depth;\n> unsigned *processed;\n> @@ -1612,10 +1620,10 @@ static void *threaded_find_deltas(void *arg)\n> pthread_mutex_lock(&data_ready);\n> pthread_mutex_unlock(&data_request);\n>\n> - if (!me->list_size)\n> + if (!me->remaining)\n> return NULL;\n>\n> - find_deltas(me->list, me->list_size,\n> + find_deltas(me->list, &me->remaining,\n> me->window, me->depth, me->processed);\n> }\n> }\n> @@ -1624,57 +1632,102 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n> int window, int depth, unsigned *processed)\n> {\n> struct thread_params *target, p[delta_search_threads];\n> - int i, ret;\n> - unsigned chunk_size;\n> + int i, ret, active_threads = 0;\n>\n> if (delta_search_threads <= 1) {\n> - find_deltas(list, list_size, window, depth, processed);\n> + find_deltas(list, &list_size, window, depth, processed);\n> return;\n> }\n>\n> pthread_mutex_lock(&data_provider);\n> pthread_mutex_lock(&data_ready);\n>\n> + /* Start work threads. */\n> for (i = 0; i < delta_search_threads; i++) {\n> p[i].window = window;\n> p[i].depth = depth;\n> p[i].processed = processed;\n> + p[i].remaining = 0;\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> + active_threads++;\n> }\n>\n> - /* this should be auto-tuned somehow */\n> - chunk_size = window * 1000;\n> + /* Then partition the work amongst them. */\n> + for (i = 0; i < delta_search_threads; i++) {\n> + unsigned sub_size = list_size / (delta_search_threads - i);\n>\n> - do {\n> - unsigned sublist_size = chunk_size;\n> - if (sublist_size > list_size)\n> - sublist_size = list_size;\n> + pthread_mutex_lock(&data_provider);\n> + target = data_requester;\n> + if (!sub_size) {\n> + pthread_mutex_unlock(&data_ready);\n> + pthread_join(target->thread, NULL);\n> + active_threads--;\n> + continue;\n> + }\n>\n> /* try to split chunks on \"path\" boundaries */\n> - while (sublist_size < list_size && list[sublist_size]->hash &&\n> - list[sublist_size]->hash == list[sublist_size-1]->hash)\n> - sublist_size++;\n> + while (sub_size < list_size && list[sub_size]->hash &&\n> + list[sub_size]->hash == list[sub_size-1]->hash)\n> + sub_size++;\n> +\n> + target->list = list;\n> + target->list_size = sub_size;\n> + target->remaining = sub_size;\n> + pthread_mutex_unlock(&data_ready);\n>\n> + list += sub_size;\n> + list_size -= sub_size;\n> + }\n> +\n> + /*\n> + * Now let's wait for work completion. Each time a thread is done\n> + * with its work, we steal half of the remaining work from the\n> + * thread with the largest number of unprocessed objects and give\n> + * it to that newly idle thread. This ensure good load balancing\n> + * until the remaining object list segments are simply too short\n> + * to be worth splitting anymore.\n> + */\n> + do {\n> + struct thread_params *victim = NULL;\n> + unsigned sub_size = 0;\n> pthread_mutex_lock(&data_provider);\n> target = data_requester;\n> - target->list = list;\n> - target->list_size = sublist_size;\n> +\n> + progress_lock();\n> + for (i = 0; i < delta_search_threads; i++)\n> + if (p[i].remaining > 2*window &&\n> + (!victim || victim->remaining < p[i].remaining))\n> + victim = &p[i];\n> + if (victim) {\n> + sub_size = victim->remaining / 2;\n> + list = victim->list + victim->list_size - sub_size;\n> + while (sub_size && list[0]->hash &&\n> + list[0]->hash == list[-1]->hash) {\n> + list++;\n\nI think you needed to copy sub_size to another variable for this loop\n\n> + sub_size--;\n> + }\n> + target->list = list;\n> + victim->list_size -= sub_size;\n> + victim->remaining -= sub_size;\n> + }\n> + progress_unlock();\n> +\n> + target->list_size = sub_size;\n> + target->remaining = sub_size;\n> pthread_mutex_unlock(&data_ready);\n>\n> - list += sublist_size;\n> - list_size -= sublist_size;\n> - if (!sublist_size) {\n> + if (!sub_size) {\n> pthread_join(target->thread, NULL);\n> - i--;\n> + active_threads--;\n> }\n> - } while (i);\n> + } while (active_threads);\n> }\n>\n> #else\n> -#define ll_find_deltas find_deltas\n> +#define ll_find_deltas(l, s, w, d, p) find_deltas(l, &s, w, d, p)\n> #endif\n>\n> static void prepare_pack(int window, int depth)\n> --\n> 1.5.3.7.2184.ge321d-dirty\n>\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62541","messageId":"9e4733910712092123r6987c3edua74a15890ae45a3d@mail.gmail.com","threadId":"11188","inReplyTo":"9e4733910712092030j5cf7dfdcrb3a003fbce391422@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T05:23:36Z","receivedAt":"2007-12-10T05:23:36Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 12/9/07, Jon Smirl wrote:\n> > + if (victim) {\n> > + sub_size = victim->remaining / 2;\n> > + list = victim->list + victim->list_size - sub_size;\n> > + while (sub_size && list[0]->hash &&\n> > + list[0]->hash == list[-1]->hash) {\n> > + list++;\n>\n> I think you needed to copy sub_size to another variable for this loop\n\nCopying sub_size was wrong. I believe you are checking for deltas on\nthe same file. It's probably that chain of 103,817 deltas that can't\nbe broken up.\n\nChainLength Objects Cumulative\n1: 103817 103817\n2: 67332 171149\n3: 57520 228669\n4: 52570 281239\n5: 43910 325149\n6: 37520 362669\n7: 35248 397917\n8: 29819 427736\n9: 27619 455355\n10: 22656 478011\n11: 21073 499084\n...\n\n>\n> > + sub_size--;\n> > + }\n> > + target->list = list;\n> > + victim->list_size -= sub_size;\n> > + victim->remaining -= sub_size;\n> > + }\n\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62542","messageId":"9e4733910712092159s24cf5a7cx4610f797f61b1de5@mail.gmail.com","threadId":"11188","inReplyTo":"9e4733910712092123r6987c3edua74a15890ae45a3d@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T05:59:38Z","receivedAt":"2007-12-10T05:59:38Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I just deleted the section looking for identical hashes.\n\n+ while (sub_size && list[0]->hash &&\n+ list[0]->hash == list[-1]->hash) {\n+ list++;\n+ sub_size--;\n+ }\n\nDoing that allows the long chains to be split over the cores.\n\nMy last 5% of objects is taking over 50% of the total CPU time in the\nrepack. I think these objects are the ones from that 103,817 entry\nchain. It is also causing the explosion in RAM consumption.\n\nAt the end I can only do 20 objects per clock second on four cores. It\ntakes 30 clock minutes (120 CPU minutes) to do the last 3% of objects.\n\nCan the chains be limited to not grow over some reasonable number, say\n5,000? It will make the pack a little bigger but it will help a lot\nwith performance.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62543","messageId":"9e4733910712092206o40e0c748s3796b95f637bf2b3@mail.gmail.com","threadId":"11188","inReplyTo":"9e4733910712092159s24cf5a7cx4610f797f61b1de5@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T06:06:59Z","receivedAt":"2007-12-10T06:06:59Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 12/10/07, Jon Smirl wrote:\n> I just deleted the section looking for identical hashes.\n>\n> + while (sub_size && list[0]->hash &&\n> + list[0]->hash == list[-1]->hash) {\n> + list++;\n> + sub_size--;\n> + }\n>\n> Doing that allows the long chains to be split over the cores.\n>\n> My last 5% of objects is taking over 50% of the total CPU time in the\n> repack. I think these objects are the ones from that 103,817 entry\n> chain. It is also causing the explosion in RAM consumption.\n>\n> At the end I can only do 20 objects per clock second on four cores. It\n> takes 30 clock minutes (120 CPU minutes) to do the last 3% of objects.\n\nIt's all in create_delta...\n\nsamples % symbol name\n10344074 98.5961 create_delta\n138010 1.3155 create_delta_index\n4380 0.0417 find_deltas\n2526 0.0241 patch_delta\n776 0.0074 unpack_entry\n\n\n\n>\n> Can the chains be limited to not grow over some reasonable number, say\n> 5,000? It will make the pack a little bigger but it will help a lot\n> with performance.\n>\n> --\n> Jon Smirl\n> jonsmirl@gmail.com\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62544","messageId":"9e4733910712092219kd86e576k33b11c93179f6475@mail.gmail.com","threadId":"11188","inReplyTo":"9e4733910712092206o40e0c748s3796b95f637bf2b3@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T06:19:26Z","receivedAt":"2007-12-10T06:19:26Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"It seems to be caused by looping over those runs of 100,000 identical\nhash entries.\n5091699 24.6407 : for (entry = index->hash[i];\nentry < index->hash[i+1]; entry++) {\n5301791 25.6575 : const unsigned char\n*ref = entry->ptr;\n\n\n\n228772 1.1071 : while (data < top) {\n223646 1.0823 : if (msize < 4096) {\n : struct index_entry *entry;\n 5862 0.0284 : val ^= U[data[-RABIN_WINDOW]];\n753004 3.6441 : val = ((val << 8) | *data) ^\nT[val >> RABIN_SHIFT];\n1232556 5.9648 : i = val & index->hash_mask;\n5091699 24.6407 : for (entry = index->hash[i];\nentry < index->hash[i+1]; entry++) {\n5301791 25.6575 : const unsigned char\n*ref = entry->ptr;\n : const unsigned char *src = data;\n 25919 0.1254 : unsigned int ref_size\n= ref_top - ref;\n740077 3.5815 : if (entry->val != val)\n : continue;\n 331 0.0016 : if (ref_size > top - src)\n 83804 0.4056 : ref_size = top - src;\n 25059 0.1213 : if (ref_size <= msize)\n : break;\n1269621 6.1442 : while (ref_size-- &&\n*src++ == *ref)\n 42122 0.2038 : ref++;\n 14362 0.0695 : if (msize < ref - entry->ptr) {\n : /* this is our\nbest match so far */\n 10452 0.0506 : msize = ref -\nentry->ptr;\n 6882 0.0333 : moff =\nentry->ptr - ref_data;\n 6382 0.0309 : if (msize >=\n4096) /* good enough */\n : break;\n : }\n : }\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62587","messageId":"alpine.LFD.0.99999.0712101048230.555@xanadu.home","threadId":"11188","inReplyTo":"9e4733910712092219kd86e576k33b11c93179f6475@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-10T16:03:32Z","receivedAt":"2007-12-10T16:03:32Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 10 Dec 2007, Jon Smirl wrote:\n\n> It seems to be caused by looping over those runs of 100,000 identical\n> hash entries.\n\nAs mentioned earlier, there simply can't be 100000 identical hash \nentries.\n\n> 5091699 24.6407 : for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {\n> 5301791 25.6575 : const unsigned char *ref = entry->ptr;\n\nThis loop is the very heart of the delta search code. It is normal to \nsee it high on the graph. In some worst cases, this loop might even be \nentered for every byte in the source buffer.\n\nAnd yet I bring you back to your observation about the fact that the \nsource pack used for the repack (whether it is the 2.1GB pack or the \n300MB pack) has a great influence on the performance outcome. The code \nabove, though, would be executed the very exact number of times, and the \nexact amount of memory allocated, regardless of the source pack used (as \nlong as you use -f with 'git repack' of course).\n\nSo this cannot be the culprit.\n\n\nNicolas\n"},{"id":"62588","messageId":"alpine.LFD.0.99999.0712101104320.555@xanadu.home","threadId":"11188","inReplyTo":"9e4733910712092206o40e0c748s3796b95f637bf2b3@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-10T16:14:44Z","receivedAt":"2007-12-10T16:14:44Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 10 Dec 2007, Jon Smirl wrote:\n\n> On 12/10/07, Jon Smirl wrote:\n> > I just deleted the section looking for identical hashes.\n> >\n> > + while (sub_size && list[0]->hash &&\n> > + list[0]->hash == list[-1]->hash) {\n> > + list++;\n> > + sub_size--;\n> > + }\n> >\n> > Doing that allows the long chains to be split over the cores.\n> >\n> > My last 5% of objects is taking over 50% of the total CPU time in the\n> > repack. I think these objects are the ones from that 103,817 entry\n> > chain. It is also causing the explosion in RAM consumption.\n> >\n> > At the end I can only do 20 objects per clock second on four cores. It\n> > takes 30 clock minutes (120 CPU minutes) to do the last 3% of objects.\n> \n> It's all in create_delta...\n\nHere you're mixing two different hashes with no relation what so ever \nwith each other.\n\nThe hash in create_delta corresponds to chunk of data in a reference \nbuffer that we try to match in a source buffer.\n\nThe hash in the code above has to do with the file names the \ncorresponding objects are coming from.\n\nAnd again, both hash uses are deterministic i.e. they will be the same \nwhen repacking with -f regardless if the source pack is the 2.1GB or the \n300MB one, so they may not explain the huge performance and memory usage \ndiscrepency you see between those two packs.\n\nThe code that do get influenced by the source pack, though, is all \nconcentrated in sha1_file.c.\n\n\nNicolas\n"},{"id":"62599","messageId":"9e4733910712100906g6794e326qf18da4be146f3667@mail.gmail.com","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712101104320.555@xanadu.home","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-12-10T17:06:39Z","receivedAt":"2007-12-10T17:06:39Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 12/10/07, Nicolas Pitre wrote:\n> On Mon, 10 Dec 2007, Jon Smirl wrote:\n>\n> > On 12/10/07, Jon Smirl wrote:\n> > > I just deleted the section looking for identical hashes.\n> > >\n> > > + while (sub_size && list[0]->hash &&\n> > > + list[0]->hash == list[-1]->hash) {\n> > > + list++;\n> > > + sub_size--;\n> > > + }\n> > >\n> > > Doing that allows the long chains to be split over the cores.\n> > >\n> > > My last 5% of objects is taking over 50% of the total CPU time in the\n> > > repack. I think these objects are the ones from that 103,817 entry\n> > > chain. It is also causing the explosion in RAM consumption.\n> > >\n> > > At the end I can only do 20 objects per clock second on four cores. It\n> > > takes 30 clock minutes (120 CPU minutes) to do the last 3% of objects.\n> >\n> > It's all in create_delta...\n>\n> Here you're mixing two different hashes with no relation what so ever\n> with each other.\n>\n> The hash in create_delta corresponds to chunk of data in a reference\n> buffer that we try to match in a source buffer.\n>\n> The hash in the code above has to do with the file names the\n> corresponding objects are coming from.\n\nSo can we change this loop to exit after a max of window_size * 10 or\nsomething like that iterations? Without capping it the threads become\nway unbalanced in the end. In the gcc case one thread is continuing\n30+ minutes past the others exiting.\n\n> And again, both hash uses are deterministic i.e. they will be the same\n> when repacking with -f regardless if the source pack is the 2.1GB or the\n> 300MB one, so they may not explain the huge performance and memory usage\n> discrepency you see between those two packs.\n\nThere is a correlation here but I don't know what it is. The memory\nblow up occurs near the end of repacking. At the same time I move from\nprocessing hundreds of objects per second to just a few per second.\nAnd the threads are getting unbalanced.\n\nI did notice that when I removed the above loop and evened things out\nmemory consumption did not spike as bad as it previously did. I maxed\nout at 3GB instead of 4.5GB.\n\nLinus suggested memory fragmentation could be a culprit. Evening the\nthreads out changed the allocation pattern. It is possible that it\navoided a fragmentation problem. It is also possible that evening\nthings out split the work so that less memory needed to be allocated.\n\nDon't hold any of these numbers to be gospel. I am using the machine\nfor other things while I run these tests and there may be\ninteractions.\n\n>\n> The code that do get influenced by the source pack, though, is all\n> concentrated in sha1_file.c.\n>\n>\n> Nicolas\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"62604","messageId":"alpine.LFD.0.99999.0712101308150.555@xanadu.home","threadId":"11188","inReplyTo":"9e4733910712100906g6794e326qf18da4be146f3667@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-10T18:21:54Z","receivedAt":"2007-12-10T18:21:54Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 10 Dec 2007, Jon Smirl wrote:\n\n> On 12/10/07, Nicolas Pitre wrote:\n> \n> > The hash in the code above has to do with the file names the\n> > corresponding objects are coming from.\n> \n> So can we change this loop to exit after a max of window_size * 10 or\n> something like that iterations? Without capping it the threads become\n> way unbalanced in the end. In the gcc case one thread is continuing\n> 30+ minutes past the others exiting.\n\nIndeed, some more tweaking are needed.\n\nThe object path distribution goes like this for the gcc repo:\n\n105557 gcc\n42537 gcc/ChangeLog\n25210 gcc/config\n20690 gcc/testsuite\n13434 gcc/testsuite/ChangeLog\n12363 libstdc++-v3\n9346 gcc/cp\n8757 libstdc++-v3/include\n8186 gcc/version.c\n7867 gcc/cp/ChangeLog\n7737 libstdc++-v3/include/bits\n7653 libjava\n6577 gcc/testsuite/gcc.dg\n5942 libjava/ChangeLog\n5351 gcc/config/i386\n5260 gcc/testsuite/g++.dg\n4451 gcc/f\n4330 libstdc++-v3/ChangeLog\n4321 libstdc++-v3/include/bits/c++config\n4316 gcc/doc\n[...]\n\nSo... the top entries are most certainly going to create load balancing \nissues if their path hash clustering isn't broken.\n\n\nNicolas\n"},{"id":"62606","messageId":"alpine.LFD.0.99999.0712101407210.555@xanadu.home","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712101308150.555@xanadu.home","subject":"[PATCH] pack-objects: more threaded load balancing fix with often changed paths","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-10T19:19:32Z","receivedAt":"2007-12-10T19:19:32Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nThe code that splits the object list amongst work threads tries to do so\non \"path\" boundaries not to prevent good delta matches. However, in \nsome cases, a few paths may largely dominate the hash distribution and\nit is not possible to have good load balancing without ignoring those \nboundaries.\n\nSigned-off-by: Nicolas Pitre \n---\n\nOn Mon, 10 Dec 2007, Nicolas Pitre wrote:\n\n> On Mon, 10 Dec 2007, Jon Smirl wrote:\n> \n> > On 12/10/07, Nicolas Pitre wrote:\n> > \n> > > The hash in the code above has to do with the file names the\n> > > corresponding objects are coming from.\n> > \n> > So can we change this loop to exit after a max of window_size * 10 or\n> > something like that iterations? Without capping it the threads become\n> > way unbalanced in the end. In the gcc case one thread is continuing\n> > 30+ minutes past the others exiting.\n> \n> Indeed, some more tweaking are needed.\n> \n> The object path distribution goes like this for the gcc repo:\n> \n> 105557 gcc\n> 42537 gcc/ChangeLog\n> 25210 gcc/config\n> 20690 gcc/testsuite\n> 13434 gcc/testsuite/ChangeLog\n> 12363 libstdc++-v3\n> 9346 gcc/cp\n> 8757 libstdc++-v3/include\n> 8186 gcc/version.c\n> 7867 gcc/cp/ChangeLog\n> 7737 libstdc++-v3/include/bits\n> 7653 libjava\n> 6577 gcc/testsuite/gcc.dg\n> 5942 libjava/ChangeLog\n> 5351 gcc/config/i386\n> 5260 gcc/testsuite/g++.dg\n> 4451 gcc/f\n> 4330 libstdc++-v3/ChangeLog\n> 4321 libstdc++-v3/include/bits/c++config\n> 4316 gcc/doc\n> [...]\n> \n> So... the top entries are most certainly going to create load balancing \n> issues if their path hash clustering isn't broken.\n\nHere's the fix.\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 250dc56..7dd0d7f 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1709,6 +1709,16 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \t\t\t\tlist++;\n \t\t\t\tsub_size--;\n \t\t\t}\n+\t\t\tif (!sub_size) {\n+\t\t\t\t/*\n+\t\t\t\t * It is possible for some \"paths\" to have\n+\t\t\t\t * so many objects that no hash boundary\n+\t\t\t\t * might be found. Let's just steal the\n+\t\t\t\t * exact half in that case.\n+\t\t\t\t */\n+\t\t\t\tsub_size = victim->remaining / 2;\n+\t\t\t\tlist -= sub_size;\n+\t\t\t}\n \t\t\ttarget->list = list;\n \t\t\tvictim->list_size -= sub_size;\n \t\t\tvictim->remaining -= sub_size;\n"},{"id":"62746","messageId":"475EC2AB.60702@viscovery.net","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712080000120.555@xanadu.home","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2007-12-11T17:02:35Z","receivedAt":"2007-12-11T17:02:35Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Nicolas Pitre schrieb:\n> @@ -1612,10 +1620,10 @@ static void *threaded_find_deltas(void *arg)\n> \t\tpthread_mutex_lock(&data_ready);\n> \t\tpthread_mutex_unlock(&data_request);\n> \n> -\t\tif (!me->list_size)\n> +\t\tif (!me->remaining)\n> \t\t\treturn NULL;\n> \n> -\t\tfind_deltas(me->list, me->list_size,\n> +\t\tfind_deltas(me->list, &me->remaining,\n> \t\t\t me->window, me->depth, me->processed);\n> \t}\n> }\n\nThis hunk caught my attention. &data_ready is locked, but not released in\nthis function.\n\nLooking more closely at the code surrounding this hunk, it seems that the\nlock is released in a *different* thread than the one that locked it. This\nworks on Linux, but is not portable. We will have to use condition variables\nlike every one else does in a producer-consumer-like scenario.\n\n-- Hannes\n"},{"id":"62750","messageId":"alpine.LFD.0.99999.0712111227080.555@xanadu.home","threadId":"11188","inReplyTo":"475EC2AB.60702@viscovery.net","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-11T17:28:30Z","receivedAt":"2007-12-11T17:28:30Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 11 Dec 2007, Johannes Sixt wrote:\n\n> Nicolas Pitre schrieb:\n> > @@ -1612,10 +1620,10 @@ static void *threaded_find_deltas(void *arg)\n> > \t\tpthread_mutex_lock(&data_ready);\n> > \t\tpthread_mutex_unlock(&data_request);\n> > \n> > -\t\tif (!me->list_size)\n> > +\t\tif (!me->remaining)\n> > \t\t\treturn NULL;\n> > \n> > -\t\tfind_deltas(me->list, me->list_size,\n> > +\t\tfind_deltas(me->list, &me->remaining,\n> > \t\t\t me->window, me->depth, me->processed);\n> > \t}\n> > }\n> \n> This hunk caught my attention. &data_ready is locked, but not released in\n> this function.\n> \n> Looking more closely at the code surrounding this hunk, it seems that the\n> lock is released in a *different* thread than the one that locked it. This\n> works on Linux, but is not portable. We will have to use condition variables\n> like every one else does in a producer-consumer-like scenario.\n\nAre you willing to make a patch for it?\n\n\nNicolas\n"},{"id":"62986","messageId":"4760DC04.6080402@viscovery.net","threadId":"11188","inReplyTo":"alpine.LFD.0.99999.0712111227080.555@xanadu.home","subject":"Re: [PATCH 2/2] pack-objects: fix threaded load balancing","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2007-12-13T07:15:16Z","receivedAt":"2007-12-13T07:15:16Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Nicolas Pitre schrieb:\n> On Tue, 11 Dec 2007, Johannes Sixt wrote:\n> \n>> Nicolas Pitre schrieb:\n>>> @@ -1612,10 +1620,10 @@ static void *threaded_find_deltas(void *arg)\n>>> \t\tpthread_mutex_lock(&data_ready);\n>>> \t\tpthread_mutex_unlock(&data_request);\n>>> \n>>> -\t\tif (!me->list_size)\n>>> +\t\tif (!me->remaining)\n>>> \t\t\treturn NULL;\n>>> \n>>> -\t\tfind_deltas(me->list, me->list_size,\n>>> +\t\tfind_deltas(me->list, &me->remaining,\n>>> \t\t\t me->window, me->depth, me->processed);\n>>> \t}\n>>> }\n>> This hunk caught my attention. &data_ready is locked, but not released in\n>> this function.\n>>\n>> Looking more closely at the code surrounding this hunk, it seems that the\n>> lock is released in a *different* thread than the one that locked it. This\n>> works on Linux, but is not portable. We will have to use condition variables\n>> like every one else does in a producer-consumer-like scenario.\n> \n> Are you willing to make a patch for it?\n\nI'm working on it, slowly.\n\n-- Hannes\n"}]}