[RFC PATCH 0/2] Add support for multi threaded checkout

[RFC PATCH 0/2] Add support for multi threaded checkout

[Pickens, James E]

There was some discussion a while back about improving git performance on
NFS (http://article.gmane.org/gmane.comp.version-control.git/100950).
This led to Linus adding the 'preload_index' function, which improves
performance of several commands using multi threading.  He also briefly
described how to do the same for 'git checkout'.  Well, I finally found
some time to work on it, and will post patches shortly.  This is my first
patch; apologies if I screwed something up.

Patch 1 adds the functionality, and 2 adds a config option to
enable/disable it.

Much of the patch is literally copy/paste from preload-index.c into
unpack-trees.c.  Many of the functions called during checkout are not
thread safe, so I added a mutex in entry.c to serialize basically
everything except writing the files to disk.  I also added a mutex in
unpack-trees.c for the progress meter.

It passes the test suite, and seems fairly safe to my naïve eyes.

Here are some benchmarks, cloning a linux kernel repo I had on an NFS
drive:

                   NFS->NFS    NFS->Local
master (53682f0c)    2:46.1          13.3
with threads           36.6          18.2

So it improved performance on NFS significantly.  Unfortunately it also
degraded performance on the local disk significantly.  I'm hoping someone
will suggest a way to mitigate that... I think it would be reasonable to
disable the threading except when the work dir is on NFS, but I don't
know how to detect that.  Even in that case it will have *some* impact
from locking/unlocking the mutex, but I think it would be in the noise.

James

[PATCH 1/2] Add support for multi threaded checkout

[James Pickens]

This speeds up operations like 'git clone' on NFS drives tremendously, but
slows down the same operations on local disks.

Partitioning the work and launching threads is done in unpack-trees.c.  The code
is mostly copied from preload_index.c.  The maximum number of threads is set to
8, which seemed to give a reasonable tradeoff between performance improvement on
NFS and degradation on local disks.

Some code was added to entry.c for serialization.  Most of the contents of
checkout_entry and write_entry are serialized, except writing the checked out
files to disk.
---
 entry.c        |   42 +++++++++++++++++---
 unpack-trees.c |  115 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 151 insertions(+), 6 deletions(-)

diff --git a/entry.c b/entry.c
index aa2ee46..764d2db 100644
--- a/entry.c
+++ b/entry.c
@@ -1,6 +1,21 @@
 #include "cache.h"
 #include "blob.h"
 
+#ifdef NO_PTHREADS
+
+#define checkout_lock()		(void)0
+#define checkout_unlock()	(void)0
+
+#else
+
+#include <pthread.h>
+
+static pthread_mutex_t checkout_mutex = PTHREAD_MUTEX_INITIALIZER;
+#define checkout_lock()		pthread_mutex_lock(&checkout_mutex)
+#define checkout_unlock()	pthread_mutex_unlock(&checkout_mutex)
+
+#endif
+
 static void create_directories(const char *path, const struct checkout *state)
 {
 	int len = strlen(path);
@@ -100,7 +115,7 @@ static void *read_blob_entry(struct cache_entry *ce, const char *path, unsigned
 
 static int write_entry(struct cache_entry *ce, char *path, const struct checkout *state, int to_tempfile)
 {
-	int fd;
+	int fd, retval;
 	long wrote;
 
 	switch (ce->ce_mode & S_IFMT) {
@@ -109,10 +124,15 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 		unsigned long size;
 
 	case S_IFREG:
+		checkout_lock();
 		new = read_blob_entry(ce, path, &size);
-		if (!new)
-			return error("git checkout-index: unable to read sha1 file of %s (%s)",
+
+		if (!new) {
+			retval = error("git checkout-index: unable to read sha1 file of %s (%s)",
 				path, sha1_to_hex(ce->sha1));
+			checkout_unlock();
+			return retval;
+		}
 
 		/*
 		 * Convert from git internal format to working tree format
@@ -124,6 +144,7 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 			new = strbuf_detach(&buf, &newsize);
 			size = newsize;
 		}
+		checkout_unlock();
 
 		if (to_tempfile) {
 			strcpy(path, ".merge_file_XXXXXX");
@@ -143,10 +164,17 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 			return error("git checkout-index: unable to write file %s", path);
 		break;
 	case S_IFLNK:
+		checkout_lock();
 		new = read_blob_entry(ce, path, &size);
-		if (!new)
-			return error("git checkout-index: unable to read sha1 file of %s (%s)",
+
+		if (!new) {
+			retval = error("git checkout-index: unable to read sha1 file of %s (%s)",
 				path, sha1_to_hex(ce->sha1));
+			checkout_unlock();
+			return retval;
+		}
+		checkout_unlock();
+
 		if (to_tempfile || !has_symlinks) {
 			if (to_tempfile) {
 				strcpy(path, ".merge_link_XXXXXX");
@@ -192,7 +220,7 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 
 int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath)
 {
-	static char path[PATH_MAX + 1];
+	char path[PATH_MAX + 1];
 	struct stat st;
 	int len = state->base_dir_len;
 
@@ -229,6 +257,8 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t
 			return error("unable to unlink old '%s' (%s)", path, strerror(errno));
 	} else if (state->not_new)
 		return 0;
+	checkout_lock();
 	create_directories(path, state);
+	checkout_unlock();
 	return write_entry(ce, path, state, 0);
 }
diff --git a/unpack-trees.c b/unpack-trees.c
index 54f301d..30b9862 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -8,6 +8,10 @@
 #include "progress.h"
 #include "refs.h"
 
+#ifndef NO_PTHREADS
+#include <pthread.h>
+#endif
+
 /*
  * Error messages expected by scripts out of plumbing commands such as
  * read-tree.  Non-scripted Porcelain is not required to use these messages
@@ -85,6 +89,115 @@ static void unlink_entry(struct cache_entry *ce)
 }
 
 static struct checkout state;
+
+#ifdef NO_PTHREADS
+#define progress_lock()		(void)0
+#define progress_unlock()	(void)0
+
+static int threaded_checkout(struct index_state *index, int update, struct progress *prog, unsigned *prog_cnt)
+{
+	return 0; /* do nothing */
+}
+
+#else
+
+#include <pthread.h>
+
+static pthread_mutex_t progress_mutex = PTHREAD_MUTEX_INITIALIZER;
+#define progress_lock()		pthread_mutex_lock(&progress_mutex)
+#define progress_unlock()	pthread_mutex_unlock(&progress_mutex)
+
+/*
+ * Mostly randomly chosen maximum thread counts: we
+ * cap the parallelism to 8 threads, and we want
+ * to have at least 500 files per thread for it to
+ * be worth starting a thread.
+ */
+#define MAX_PARALLEL (8)
+#define THREAD_COST (500)
+
+struct thread_data {
+	pthread_t pthread;
+	struct index_state *index;
+	struct checkout *state;
+	int update, offset, nr, errs;
+	struct progress *progress;
+	unsigned *progress_cnt;
+};
+
+static void *checkout_thread(void *_data)
+{
+	int nr;
+	struct thread_data *p = _data;
+	struct index_state *index = p->index;
+	struct cache_entry **cep = index->cache + p->offset;
+
+	p->errs = 0;
+
+	nr = p->nr;
+	if (0 == nr) {
+		return NULL;
+	}
+
+	if (nr + p->offset > index->cache_nr)
+		nr = index->cache_nr - p->offset;
+
+	do {
+		struct cache_entry *ce = *cep++;
+
+		if (ce->ce_flags & CE_UPDATE) {
+			progress_lock();
+			display_progress(p->progress, ++(*p->progress_cnt));
+			progress_unlock();
+			ce->ce_flags &= ~CE_UPDATE;
+			if (p->update) {
+				p->errs |= checkout_entry(ce, p->state, NULL);
+				fflush(stdout);
+			}
+		}
+	} while (--nr > 0);
+	return NULL;
+}
+
+static int threaded_checkout(struct index_state *index, int update, struct progress *prog, unsigned *prog_cnt)
+{
+	int threads, work, offset, i;
+	struct thread_data data[MAX_PARALLEL];
+	int errs = 0;
+
+	threads = index->cache_nr / THREAD_COST;
+	if (threads > MAX_PARALLEL)
+		threads = MAX_PARALLEL;
+	else if (threads == 0)
+		return 0;
+
+	offset = 0;
+	work = (index->cache_nr + threads - 1) / threads;
+	for (i = 0; i < threads; i++) {
+		struct thread_data *p = data+i;
+		p->index = index;
+		p->offset = offset;
+		p->nr = work;
+		p->state = &state;
+		p->update = update;
+		p->progress = prog;
+		p->progress_cnt = prog_cnt;
+		offset += work;
+		if (pthread_create(&p->pthread, NULL, checkout_thread, p))
+			die("unable to create threaded checkout");
+	}
+	for (i = 0; i < threads; i++) {
+		struct thread_data *p = data+i;
+		if (pthread_join(p->pthread, NULL))
+			die("unable to join threaded checkout");
+		errs |= p->errs;
+	}
+
+	return errs;
+}
+
+#endif
+
 static int check_updates(struct unpack_trees_options *o)
 {
 	unsigned cnt = 0, total = 0;
@@ -118,6 +231,8 @@ static int check_updates(struct unpack_trees_options *o)
 		}
 	}
 
+	errs |= threaded_checkout(index, o->update, progress, &cnt);
+
 	for (i = 0; i < index->cache_nr; i++) {
 		struct cache_entry *ce = index->cache[i];
 
-- 
1.6.0.4.1116.gc5d7

[PATCH 2/2] Add core.threadedcheckout config option

[James Pickens]

Setting it to 'true' enables multi threaded checkout.  Default is false.
---
 Documentation/config.txt |    8 ++++++++
 cache.h                  |    1 +
 config.c                 |    5 +++++
 environment.c            |    3 +++
 unpack-trees.c           |    3 +++
 5 files changed, 20 insertions(+), 0 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index 21ea165..22ac76b 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -422,6 +422,14 @@ relatively high IO latencies.  With this set to 'true', git will do the
 index comparison to the filesystem data in parallel, allowing
 overlapping IO's.
 
+core.threadedcheckout::
+	Enable parallel checkout for operations like 'git checkout'
++
+This can speed up operations like 'git clone' and 'git checkout' especially
+on filesystems like NFS that have relatively high IO latencies.  With this
+set to 'true', git will write the checked out files to disk in parallel,
+allowing overlapping IO's.
+
 alias.*::
 	Command aliases for the linkgit:git[1] command wrapper - e.g.
 	after defining "alias.last = cat-file commit HEAD", the invocation
diff --git a/cache.h b/cache.h
index 231c06d..0777597 100644
--- a/cache.h
+++ b/cache.h
@@ -512,6 +512,7 @@ extern size_t delta_base_cache_limit;
 extern int auto_crlf;
 extern int fsync_object_files;
 extern int core_preload_index;
+extern int core_threaded_checkout;
 
 enum safe_crlf {
 	SAFE_CRLF_FALSE = 0,
diff --git a/config.c b/config.c
index 790405a..819693e 100644
--- a/config.c
+++ b/config.c
@@ -495,6 +495,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.threadedcheckout")) {
+		core_threaded_checkout = git_config_bool(var, value);
+		return 0;
+	}
+
 	/* Add other config variables here and to Documentation/config.txt. */
 	return 0;
 }
diff --git a/environment.c b/environment.c
index e278bce..2450b65 100644
--- a/environment.c
+++ b/environment.c
@@ -46,6 +46,9 @@ enum rebase_setup_type autorebase = AUTOREBASE_NEVER;
 /* Parallel index stat data preload? */
 int core_preload_index = 0;
 
+/* Parallel checkout? */
+int core_threaded_checkout = 0;
+
 /* This is set by setup_git_dir_gently() and/or git_default_config() */
 char *git_work_tree_cfg;
 static char *work_tree;
diff --git a/unpack-trees.c b/unpack-trees.c
index 30b9862..635b7dc 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -165,6 +165,9 @@ static int threaded_checkout(struct index_state *index, int update, struct progr
 	struct thread_data data[MAX_PARALLEL];
 	int errs = 0;
 
+	if (!core_threaded_checkout)
+		return 0;
+
 	threads = index->cache_nr / THREAD_COST;
 	if (threads > MAX_PARALLEL)
 		threads = MAX_PARALLEL;
-- 
1.6.0.4.1116.gc5d7

Re: [PATCH 1/2] Add support for multi threaded checkout

[Linus Torvalds]

On Thu, 18 Dec 2008, James Pickens wrote:
>
> This speeds up operations like 'git clone' on NFS drives tremendously, but
> slows down the same operations on local disks.
> 
> Partitioning the work and launching threads is done in unpack-trees.c.  The code
> is mostly copied from preload_index.c.  The maximum number of threads is set to
> 8, which seemed to give a reasonable tradeoff between performance improvement on
> NFS and degradation on local disks.

Hmm. I don't really like this very much.

Why? Because as your locking shows, we can really only parallelise the 
actual write-out anyway, and rather than do any locking there, wouldn't it 
be better to have a notion of "queued work" (which would be just the 
write-out) to be done in parallel?

So instead of doing all the unpacking etc in parallel (with locking around 
it to serialize it), I'd suggest doing ll the unpacking serially since 
that isn't the problem anyway (and since you have to protect it with a 
lock anyway), and just have a "write out and free the buffer" phase that 
is done in the threads.

The alternative would be to actually do what your patch suggests, but 
actually try to make the code git SHA1 object handling be thread-safe. At 
that point, the ugly locking in write_entry() would go away, and you might 
actually improve performance on SMP thanks to doing the CPU part in 
parallel.

But as-is, I think the patch is a bit ugly. The reason I liked the index 
pre-reading was that it could be done entirely locklessly, so it really 
did parallelize it _fully_ (even if the IO latency part was the much 
bigger issue), and that was also why it actually ended up helping even on 
a local disk (only if you have multiple cores, of course).

		Linus

Re: [PATCH 1/2] Add support for multi threaded checkout

[James Pickens]

On Thu, Dec 18, 2008, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> So instead of doing all the unpacking etc in parallel (with locking around
> it to serialize it), I'd suggest doing ll the unpacking serially since
> that isn't the problem anyway (and since you have to protect it with a
> lock anyway), and just have a "write out and free the buffer" phase that
> is done in the threads.

That's certainly a more elegant way to do it, but unless I'm missing
something, it requires rewriting a good bit of code.  The main reason I
went with the locking was to keep the patch as simple and non-intrusive
as possible.

> The alternative would be to actually do what your patch suggests, but
> actually try to make the code git SHA1 object handling be thread-safe. At
> that point, the ugly locking in write_entry() would go away, and you might
> actually improve performance on SMP thanks to doing the CPU part in
> parallel.

I started down that path at one point, and quickly got in over my head.
Making all that code thread safe looks like a big task to me.  From my
perspective, I get a ~350% speedup from this easy patch, and I might get
an additional 25% (blind guess) from a much more difficult patch.  It
didn't seem worth the effort.

James

Re: [PATCH 1/2] Add support for multi threaded checkout

[Linus Torvalds]

On Thu, 18 Dec 2008, James Pickens wrote:

> On Thu, Dec 18, 2008, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > So instead of doing all the unpacking etc in parallel (with locking around
> > it to serialize it), I'd suggest doing ll the unpacking serially since
> > that isn't the problem anyway (and since you have to protect it with a
> > lock anyway), and just have a "write out and free the buffer" phase that
> > is done in the threads.
> 
> That's certainly a more elegant way to do it, but unless I'm missing
> something, it requires rewriting a good bit of code.  The main reason I
> went with the locking was to keep the patch as simple and non-intrusive
> as possible.

Yeah, I looked a bit more at it, and one problem is that we don't just 
write out the file, we also refresh the cache with the stat information 
after writing it out. If we just write the thing out, it would be simpler: 
we'd just make the thread locklessly write things out and free the data 
from a simple set of lockless threads - no need for any access to git data 
structures.

Ho humm. I'll think about it a bit more.

		Linus

Re: [RFC PATCH 0/2] Add support for multi threaded checkout

[Nicolas Pitre]

On Thu, 18 Dec 2008, Pickens, James E wrote:

>                    NFS->NFS    NFS->Local
> master (53682f0c)    2:46.1          13.3
> with threads           36.6          18.2
> 
> So it improved performance on NFS significantly.

Are those figures repeatable over multiple consecutive runs?


Nicolas

Re: [RFC PATCH 0/2] Add support for multi threaded checkout

[James Pickens]

[Resending since I forgot to copy the list]

On Thu, Dec 18, 2008, Nicolas Pitre <nico@cam.org> wrote:
> On Thu, 18 Dec 2008, Pickens, James E wrote:
>
>>                    NFS->NFS    NFS->Local
>> master (53682f0c)    2:46.1          13.3
>> with threads           36.6          18.2
>>
>> So it improved performance on NFS significantly.
>
> Are those figures repeatable over multiple consecutive runs?

Roughly, yes.  There is some variance of course, probably
more than usual since all these operations involve NFS.
The numbers are the best of several runs in each case.

James

Re: [RFC PATCH 0/2] Add support for multi threaded checkout

[Nicolas Morey-Chaisemartin]

Pickens, James E a écrit :
> Even in that case it will have *some* impact
> from locking/unlocking the mutex, but I think it would be in the noise.
>
> James
> -
I guess you could do something like :

#define checkout_lock()		core_threaded_checkout ?pthread_mutex_lock(&checkout_mutex) : (void) 0
#define checkout_unlock()		core_threaded_checkout ?pthread_mutex_unlock(&checkout_mutex) : (void) 0

It should be faster when you don't actually use threaded checkouts, as you won't unnecessarily lock/unlock your mutex. 

Have you looked at the perf from local to local? I'm just curious.

Nicolas Morey-Chaisemartin

Re: [RFC PATCH 0/2] Add support for multi threaded checkout

[James Pickens]

On Thu, Dec 18, 2008 at 2:16 PM, Nicolas Morey-Chaisemartin
<devel@morey-chaisemartin.com> wrote:
> I guess you could do something like :
>
> #define checkout_lock()         core_threaded_checkout ?pthread_mutex_lock(&checkout_mutex) : (void) 0
> #define checkout_unlock()               core_threaded_checkout ?pthread_mutex_unlock(&checkout_mutex) : (void) 0
>
> It should be faster when you don't actually use threaded checkouts, as you won't unnecessarily lock/unlock your mutex.
>
> Have you looked at the perf from local to local? I'm just curious.


I had looked at it before but didn't record any numbers.  I just took the
following timings (2 runs each):

master             13.78    12.79
threads enabled    16.84    20.45
threads disabled   14.07    13.27

James

Re: [RFC PATCH 0/2] Add support for multi threaded checkout

[James Pickens]

On Thu, Dec 18, 2008, Nicolas Morey-Chaisemartin
<devel@morey-chaisemartin.com> wrote:
> I guess you could do something like :
>
> #define checkout_lock()         core_threaded_checkout ?pthread_mutex_lock(&checkout_mutex) : (void) 0
> #define checkout_unlock()               core_threaded_checkout ?pthread_mutex_unlock(&checkout_mutex) : (void) 0

I tried that, and to make it easier to see the impact, I changed the
'wrote = write_in_full(...)' calls in entry.c to 'wrote = size'.  That
makes git just create a bunch of empty files instead of writing the real
contents to disk.  Here's the result, with core.threadedcheckout set to
false, best of 2 runs:

original patch:     3.19
original + above:   3.18

So the cost of locking/unlocking the mutex looks vanishingly small in the
single thread case.

This also puts an upper bound on the time required for a single thread to
unpack the data.

James