{"thread":{"id":"30350","subject":"[PATCH] index-pack: avoid false sharing on multicore systems","startedAt":"2012-04-27T16:52:41Z","lastAt":"2012-04-27T16:52:41Z","messageCount":1,"participants":["Nguyễn Thái Ngọc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"190222","messageId":"1335545561-933-1-git-send-email-pclouds@gmail.com","threadId":"30350","inReplyTo":null,"subject":"[PATCH] index-pack: avoid false sharing on multicore systems","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-27T16:52:41Z","receivedAt":"2012-04-27T16:52:41Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"thread_data[] is frequently accessed by all threads and it's\npacked tight. If two threads running on two different processors,\nupdating one \"struct thread_local\" may invalidate the cache line that\nalso contains struct thread_local of the other thread, leading to\ncache misses (aka false sharing [1])\n\nPad it properly. Make sure each \"struct thread_local\" is on a separate\ncache line.\n\nThis only works with real processors though. Multithread on single\nprocessor may be harmed by this change. Keep the tight layout in that\ncase.\n\n[1] http://software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads/\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n My laptop has one physical core with hyperthread, so this patch does\n no good for me. I won't have access to a multicore system until the\n middle of next week, so I'm not sure if it actually helps at the\n moment.\n\n builtin/index-pack.c |   37 +++++++++++++++++++++++++++++++++----\n 1 files changed, 33 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex c1c3c81..598b18e 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -93,7 +93,8 @@ static int input_fd, output_fd, pack_fd;\n \n #ifndef NO_PTHREADS\n \n-static struct thread_local *thread_data;\n+static struct thread_local **thread_data;\n+static char *thread_data_buffer;\n \n static pthread_mutex_t read_mutex;\n #define read_lock()\t\tlock_mutex(&read_mutex)\n@@ -126,11 +127,38 @@ static inline void unlock_mutex(pthread_mutex_t *mutex)\n  */\n static void init_thread(void)\n {\n+\tint i, stripe;\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+\tif (online_cpus() && !getenv(\"GIT_ONE_CPU_CORE\")) {\n+\t\t/*\n+\t\t * A typical cache line is 64 byte long. Avoid false\n+\t\t * sharing by putting thread data of each thread on a\n+\t\t * separate cache line\n+\t\t */\n+\t\tstripe = 64;\n+\t\tassert(sizeof(struct thread_local) <= stripe);\n+\t\tthread_data_buffer = xmalloc((nr_threads + 1) * stripe);\n+#define ALIGN(x, stripe) (((x) + (stripe) - 1) & ~((stripe) - 1))\n+\t\tthread_data[0] = (struct thread_local *)ALIGN((unsigned int)thread_data_buffer, stripe);\n+\t} else {\n+\t\t/*\n+\t\t * On the other hand, on single physical cpu, padding\n+\t\t * wastes cache for nothing. Don't do it.\n+\t\t */\n+\t\tstripe = sizeof(struct thread_local);\n+\t\tthread_data_buffer = xmalloc(nr_threads * stripe);\n+\t\tthread_data[0] = (struct thread_local *)thread_data_buffer;\n+\t}\n+\tmemset(thread_data[0], 0, stripe * nr_threads);\n+\tfor (i = 1; i < nr_threads; i++)\n+\t\tthread_data[i] = (struct thread_local*)((char*)(thread_data[0]) + i * stripe);\n \tthreads_active = 1;\n }\n \n@@ -143,6 +171,7 @@ static void cleanup_thread(void)\n \tpthread_mutex_destroy(&counter_mutex);\n \tpthread_mutex_destroy(&work_mutex);\n \tpthread_key_delete(key);\n+\tfree(thread_data_buffer);\n \tfree(thread_data);\n }\n \n@@ -890,13 +919,13 @@ static void parse_pack_objects(unsigned char *sha1)\n \tif (nr_threads > 1 || getenv(\"GIT_FORCE_THREADS\")) {\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\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+\t\t\tpthread_join(thread_data[i]->thread, NULL);\n \n \t\tcleanup_thread();\n \t\treturn;\n-- \n1.7.8.36.g69ee2\n"}]}