[PATCH] straighten the list of objects to deltify

[PATCH] straighten the list of objects to deltify

[Nicolas Pitre]

Not all objects are subject to deltification, so avoid carrying those
along, and provide the real count to progress display.

Signed-off-by: Nicolas Pitre <nico@cam.org>
---
 builtin-pack-objects.c |   77 ++++++++++++++++++++++++++----------------------
 1 files changed, 42 insertions(+), 35 deletions(-)

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index e64e3a0..b1c64be 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1313,12 +1313,6 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 	if (trg_entry->type != src_entry->type)
 		return -1;
 
-	/* We do not compute delta to *create* objects we are not
-	 * going to pack.
-	 */
-	if (trg_entry->preferred_base)
-		return -1;
-
 	/*
 	 * We do not bother to try a delta that we discarded
 	 * on an earlier try, but only when reusing delta data.
@@ -1443,43 +1437,24 @@ static void free_unpacked(struct unpacked *n)
 	n->depth = 0;
 }
 
-static void find_deltas(struct object_entry **list, int window, int depth)
+static void find_deltas(struct object_entry **list, unsigned list_size,
+			unsigned nr_deltas, int window, int depth)
 {
-	uint32_t i = nr_objects, idx = 0, count = 0, processed = 0;
+	uint32_t i = list_size, idx = 0, count = 0, processed = 0;
 	unsigned int array_size = window * sizeof(struct unpacked);
 	struct unpacked *array;
 	int max_depth;
 
-	if (!nr_objects)
-		return;
 	array = xmalloc(array_size);
 	memset(array, 0, array_size);
 	if (progress)
-		start_progress(&progress_state, "Deltifying %u objects...", "", nr_result);
+		start_progress(&progress_state, "Deltifying %u objects...", "", nr_deltas);
 
 	do {
 		struct object_entry *entry = list[--i];
 		struct unpacked *n = array + idx;
 		int j, best_base = -1;
 
-		if (!entry->preferred_base)
-			processed++;
-
-		if (progress)
-			display_progress(&progress_state, processed);
-
-		if (entry->delta)
-			/* This happens if we decided to reuse existing
-			 * delta from a pack.  "!no_reuse_delta &&" is implied.
-			 */
-			continue;
-
-		if (entry->size < 50)
-			continue;
-
-		if (entry->no_try_delta)
-			continue;
-
 		free_unpacked(n);
 		n->entry = entry;
 
@@ -1491,6 +1466,15 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 			count--;
 		}
 
+		/* We do not compute delta to *create* objects we are not
+		 * going to pack.
+		 */
+		if (entry->preferred_base)
+			goto next;
+
+		if (progress)
+			display_progress(&progress_state, ++processed);
+
 		/*
 		 * If the current object is at pack edge, take the depth the
 		 * objects that depend on the current object into account
@@ -1565,18 +1549,41 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 static void prepare_pack(int window, int depth)
 {
 	struct object_entry **delta_list;
-	uint32_t i;
+	uint32_t i, n, nr_deltas;
 
 	get_object_details();
 
-	if (!window || !depth)
+	if (!nr_objects || !window || !depth)
 		return;
 
 	delta_list = xmalloc(nr_objects * sizeof(*delta_list));
-	for (i = 0; i < nr_objects; i++)
-		delta_list[i] = objects + i;
-	qsort(delta_list, nr_objects, sizeof(*delta_list), type_size_sort);
-	find_deltas(delta_list, window+1, depth);
+	nr_deltas = n = 0;
+
+	for (i = 0; i < nr_objects; i++) {
+		struct object_entry *entry = objects + i;
+
+		if (entry->delta)
+			/* This happens if we decided to reuse existing
+			 * delta from a pack.  "!no_reuse_delta &&" is implied.
+			 */
+			continue;
+
+		if (entry->size < 50)
+			continue;
+
+		if (entry->no_try_delta)
+			continue;
+
+		if (!entry->preferred_base)
+			nr_deltas++;
+
+		delta_list[n++] = entry;
+	}
+
+	if (nr_deltas) {
+		qsort(delta_list, n, sizeof(*delta_list), type_size_sort);
+		find_deltas(delta_list, n, nr_deltas, window+1, depth);
+	}
 	free(delta_list);
 }
 
-- 
1.5.3.1.844.g0a05-dirty

[PATCH] localize window memory usage accounting

[Nicolas Pitre]

This is to help threadification of delta searching.

Signed-off-by: Nicolas Pitre <nico@cam.org>
---
 builtin-pack-objects.c |   28 ++++++++++++++--------------
 1 files changed, 14 insertions(+), 14 deletions(-)

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index b1c64be..b8495bf 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -78,7 +78,6 @@ static unsigned long delta_cache_size = 0;
 static unsigned long max_delta_cache_size = 0;
 static unsigned long cache_max_small_delta_size = 1000;
 
-static unsigned long window_memory_usage = 0;
 static unsigned long window_memory_limit = 0;
 
 /*
@@ -1300,7 +1299,7 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
  * one.
  */
 static int try_delta(struct unpacked *trg, struct unpacked *src,
-		     unsigned max_depth)
+		     unsigned max_depth, unsigned long *mem_usage)
 {
 	struct object_entry *trg_entry = trg->entry;
 	struct object_entry *src_entry = src->entry;
@@ -1356,7 +1355,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 		if (sz != trg_size)
 			die("object %s inconsistent object length (%lu vs %lu)",
 			    sha1_to_hex(trg_entry->idx.sha1), sz, trg_size);
-		window_memory_usage += sz;
+		*mem_usage += sz;
 	}
 	if (!src->data) {
 		src->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);
@@ -1366,7 +1365,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 		if (sz != src_size)
 			die("object %s inconsistent object length (%lu vs %lu)",
 			    sha1_to_hex(src_entry->idx.sha1), sz, src_size);
-		window_memory_usage += sz;
+		*mem_usage += sz;
 	}
 	if (!src->index) {
 		src->index = create_delta_index(src->data, src_size);
@@ -1376,7 +1375,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 				warning("suboptimal pack - out of memory");
 			return 0;
 		}
-		window_memory_usage += sizeof_delta_index(src->index);
+		*mem_usage += sizeof_delta_index(src->index);
 	}
 
 	delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
@@ -1423,18 +1422,19 @@ static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
 	return m;
 }
 
-static void free_unpacked(struct unpacked *n)
+static unsigned long free_unpacked(struct unpacked *n)
 {
-	window_memory_usage -= sizeof_delta_index(n->index);
+	unsigned long freed_mem = sizeof_delta_index(n->index);
 	free_delta_index(n->index);
 	n->index = NULL;
 	if (n->data) {
+		freed_mem += n->entry->size;
 		free(n->data);
 		n->data = NULL;
-		window_memory_usage -= n->entry->size;
 	}
 	n->entry = NULL;
 	n->depth = 0;
+	return freed_mem;
 }
 
 static void find_deltas(struct object_entry **list, unsigned list_size,
@@ -1443,7 +1443,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 	uint32_t i = list_size, idx = 0, count = 0, processed = 0;
 	unsigned int array_size = window * sizeof(struct unpacked);
 	struct unpacked *array;
-	int max_depth;
+	unsigned long mem_usage = 0;
 
 	array = xmalloc(array_size);
 	memset(array, 0, array_size);
@@ -1453,16 +1453,16 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 	do {
 		struct object_entry *entry = list[--i];
 		struct unpacked *n = array + idx;
-		int j, best_base = -1;
+		int j, max_depth, best_base = -1;
 
-		free_unpacked(n);
+		mem_usage -= free_unpacked(n);
 		n->entry = entry;
 
 		while (window_memory_limit &&
-		       window_memory_usage > window_memory_limit &&
+		       mem_usage > window_memory_limit &&
 		       count > 1) {
 			uint32_t tail = (idx + window - count) % window;
-			free_unpacked(array + tail);
+			mem_usage -= free_unpacked(array + tail);
 			count--;
 		}
 
@@ -1497,7 +1497,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 			m = array + other_idx;
 			if (!m->entry)
 				break;
-			ret = try_delta(n, m, max_depth);
+			ret = try_delta(n, m, max_depth, &mem_usage);
 			if (ret < 0)
 				break;
 			else if (ret > 0)
-- 
1.5.3.1.844.g0a05-dirty

[PATCH] rearrange delta search progress reporting

[Nicolas Pitre]

This is to help threadification of the delta search code, with a bonus
consistency check.

Signed-off-by: Nicolas Pitre <nico@cam.org>
---
 builtin-pack-objects.c |   23 ++++++++++++++---------
 1 files changed, 14 insertions(+), 9 deletions(-)

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index b8495bf..9d56592 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1438,17 +1438,15 @@ static unsigned long free_unpacked(struct unpacked *n)
 }
 
 static void find_deltas(struct object_entry **list, unsigned list_size,
-			unsigned nr_deltas, int window, int depth)
+			int window, int depth, unsigned *processed)
 {
-	uint32_t i = list_size, idx = 0, count = 0, processed = 0;
+	uint32_t i = list_size, idx = 0, count = 0;
 	unsigned int array_size = window * sizeof(struct unpacked);
 	struct unpacked *array;
 	unsigned long mem_usage = 0;
 
 	array = xmalloc(array_size);
 	memset(array, 0, array_size);
-	if (progress)
-		start_progress(&progress_state, "Deltifying %u objects...", "", nr_deltas);
 
 	do {
 		struct object_entry *entry = list[--i];
@@ -1472,8 +1470,9 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 		if (entry->preferred_base)
 			goto next;
 
+		(*processed)++;
 		if (progress)
-			display_progress(&progress_state, ++processed);
+			display_progress(&progress_state, *processed);
 
 		/*
 		 * If the current object is at pack edge, take the depth the
@@ -1536,9 +1535,6 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 			idx = 0;
 	} while (i > 0);
 
-	if (progress)
-		stop_progress(&progress_state);
-
 	for (i = 0; i < window; ++i) {
 		free_delta_index(array[i].index);
 		free(array[i].data);
@@ -1581,8 +1577,17 @@ static void prepare_pack(int window, int depth)
 	}
 
 	if (nr_deltas) {
+		unsigned nr_done = 0;
+		if (progress)
+			start_progress(&progress_state,
+				       "Deltifying %u objects...", "",
+				       nr_deltas);
 		qsort(delta_list, n, sizeof(*delta_list), type_size_sort);
-		find_deltas(delta_list, n, nr_deltas, window+1, depth);
+		find_deltas(delta_list, n, window+1, depth, &nr_done);
+		if (progress)
+			stop_progress(&progress_state);
+		if (nr_done != nr_deltas)
+			die("inconsistency with delta count");
 	}
 	free(delta_list);
 }
-- 
1.5.3.1.844.g0a05-dirty

[PATCH] basic threaded delta search

[Nicolas Pitre]

this is still rough, hence it is disabled by default.  You need to compile
with "make THREADED_DELTA_SEARCH=1 ..." at the moment.

Threading is done on different portions of the object list to be
deltified. This is currently done by spliting the list into n parts and
then a thread is spawned for each of them.  A better method would consist
of spliting the list into more smaller parts and have the n threads
pick the next part available.

Signed-off-by: Nicolas Pitre <nico@cam.org>
---
 Makefile               |    8 +++++
 builtin-pack-objects.c |   83 +++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 90 insertions(+), 1 deletions(-)

diff --git a/Makefile b/Makefile
index 51af531..a92fb31 100644
--- a/Makefile
+++ b/Makefile
@@ -122,6 +122,9 @@ all::
 # If not set it defaults to the bare 'wish'. If it is set to the empty
 # string then NO_TCLTK will be forced (this is used by configure script).
 #
+# Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit
+# parallel delta searching when packing objects.
+#
 
 GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE
 	@$(SHELL_PATH) ./GIT-VERSION-GEN
@@ -662,6 +665,11 @@ ifdef NO_HSTRERROR
 	COMPAT_OBJS += compat/hstrerror.o
 endif
 
+ifdef THREADED_DELTA_SEARCH
+	BASIC_CFLAGS += -DTHREADED_DELTA_SEARCH
+	EXTLIBS += -lpthread
+endif
+
 ifeq ($(TCLTK_PATH),)
 NO_TCLTK=NoThanks
 endif
diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 9d56592..1bcee23 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -15,6 +15,10 @@
 #include "list-objects.h"
 #include "progress.h"
 
+#ifdef THREADED_DELTA_SEARCH
+#include <pthread.h>
+#endif
+
 static const char pack_usage[] = "\
 git-pack-objects [{ -q | --progress | --all-progress }] \n\
 	[--max-pack-size=N] [--local] [--incremental] \n\
@@ -1290,6 +1294,25 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
 	return 0;
 }
 
+#ifdef THREADED_DELTA_SEARCH
+
+static pthread_mutex_t read_mutex = PTHREAD_MUTEX_INITIALIZER;
+#define read_lock()		pthread_mutex_lock(&read_mutex)
+#define read_unlock()		pthread_mutex_unlock(&read_mutex)
+
+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)
+
+#else
+
+#define read_lock()		0
+#define read_unlock()		0
+#define progress_lock()		0
+#define progress_unlock()	0
+
+#endif
+
 /*
  * We search for deltas _backwards_ in a list sorted by type and
  * by size, so that we see progressively smaller and smaller files.
@@ -1348,7 +1371,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 
 	/* Load data if not already done */
 	if (!trg->data) {
+		read_lock();
 		trg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz);
+		read_unlock();
 		if (!trg->data)
 			die("object %s cannot be read",
 			    sha1_to_hex(trg_entry->idx.sha1));
@@ -1358,7 +1383,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 		*mem_usage += sz;
 	}
 	if (!src->data) {
+		read_lock();
 		src->data = read_sha1_file(src_entry->idx.sha1, &type, &sz);
+		read_unlock();
 		if (!src->data)
 			die("object %s cannot be read",
 			    sha1_to_hex(src_entry->idx.sha1));
@@ -1470,9 +1497,11 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 		if (entry->preferred_base)
 			goto next;
 
+		progress_lock();
 		(*processed)++;
 		if (progress)
 			display_progress(&progress_state, *processed);
+		progress_unlock();
 
 		/*
 		 * If the current object is at pack edge, take the depth the
@@ -1542,6 +1571,58 @@ static void find_deltas(struct object_entry **list, unsigned list_size,
 	free(array);
 }
 
+#ifdef THREADED_DELTA_SEARCH
+
+struct thread_params {
+	pthread_t thread;
+	struct object_entry **list;
+	unsigned list_size;
+	int window;
+	int depth;
+	unsigned *processed;
+};
+
+static void *threaded_find_deltas(void *arg)
+{
+	struct thread_params *p = arg;
+	if (p->list_size)
+		find_deltas(p->list, p->list_size,
+			    p->window, p->depth, p->processed);
+	return NULL;
+}
+
+#define NR_THREADS	8
+
+static void ll_find_deltas(struct object_entry **list, unsigned list_size,
+			   int window, int depth, unsigned *processed)
+{
+	struct thread_params p[NR_THREADS];
+	int i, ret;
+
+	for (i = 0; i < NR_THREADS; i++) {
+		unsigned sublist_size = list_size / (NR_THREADS - i);
+		p[i].list = list;
+		p[i].list_size = sublist_size;
+		p[i].window = window;
+		p[i].depth = depth;
+		p[i].processed = processed;
+		ret = pthread_create(&p[i].thread, NULL,
+				     threaded_find_deltas, &p[i]);
+		if (ret)
+			die("unable to create thread: %s", strerror(ret));
+		list += sublist_size;
+		list_size -= sublist_size;
+	}
+
+	for (i = 0; i < NR_THREADS; i++) {
+		pthread_join(p[i].thread, NULL);
+	}
+}
+
+#else
+#define ll_find_deltas find_deltas
+#endif
+
 static void prepare_pack(int window, int depth)
 {
 	struct object_entry **delta_list;
@@ -1583,7 +1664,7 @@ static void prepare_pack(int window, int depth)
 				       "Deltifying %u objects...", "",
 				       nr_deltas);
 		qsort(delta_list, n, sizeof(*delta_list), type_size_sort);
-		find_deltas(delta_list, n, window+1, depth, &nr_done);
+		ll_find_deltas(delta_list, n, window+1, depth, &nr_done);
 		if (progress)
 			stop_progress(&progress_state);
 		if (nr_done != nr_deltas)
-- 
1.5.3.1.844.g0a05-dirty

Re: [PATCH] basic threaded delta search

[David Kastrup]

Nicolas Pitre <nico@cam.org> writes:

> this is still rough, hence it is disabled by default.  You need to compile
> with "make THREADED_DELTA_SEARCH=1 ..." at the moment.
>
> Threading is done on different portions of the object list to be
> deltified. This is currently done by spliting the list into n parts and
> then a thread is spawned for each of them.  A better method would consist
> of spliting the list into more smaller parts and have the n threads
> pick the next part available.

In my experience, the worst performance hit happens when the real
memory is exhausted and things start paging.  Threading on different
portions of the object list is going to exacerbate the problem in the
areas where it hits worst.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: [PATCH] basic threaded delta search

[Nicolas Pitre]

On Thu, 6 Sep 2007, David Kastrup wrote:

> Nicolas Pitre <nico@cam.org> writes:
> 
> > this is still rough, hence it is disabled by default.  You need to compile
> > with "make THREADED_DELTA_SEARCH=1 ..." at the moment.
> >
> > Threading is done on different portions of the object list to be
> > deltified. This is currently done by spliting the list into n parts and
> > then a thread is spawned for each of them.  A better method would consist
> > of spliting the list into more smaller parts and have the n threads
> > pick the next part available.
> 
> In my experience, the worst performance hit happens when the real
> memory is exhausted and things start paging.  Threading on different
> portions of the object list is going to exacerbate the problem in the
> areas where it hits worst.

Just don't use it if you don't have 1) a SMP machine and 2) enough ram.
Threading will be enabled with a command line argument at some point.


Nicolas

Re: [PATCH] basic threaded delta search

[Junio C Hamano]

Nicolas Pitre <nico@cam.org> writes:

> this is still rough, hence it is disabled by default.  You need to compile
> with "make THREADED_DELTA_SEARCH=1 ..." at the moment.
>
> Threading is done on different portions of the object list to be
> deltified. This is currently done by spliting the list into n parts and
> then a thread is spawned for each of them.  A better method would consist
> of spliting the list into more smaller parts and have the n threads
> pick the next part available.

Hmmm.  I wonder how the result is affected by such a partition;
aren't you going to have many objects that could have used
somebody else as a delta but gets stored as base because they
happen to be a very early part of their partition (and lacking
delta base candidates in the window)?  You cannot solve it with
overlapping partitions without busting the depth limit easily
either, I suspect.  Also how would this interact with the LRU
delta base window we discussed a week or two ago?

Separating the list into different object types would not have
any adverse impact coming from the "horizon" of delta base
candidates window (because we do not deltify across types), but
that is not very useful because we cannot gain much parallerism
from such a partition.

Re: [PATCH] basic threaded delta search

[Nicolas Pitre]

On Thu, 6 Sep 2007, Junio C Hamano wrote:

> Nicolas Pitre <nico@cam.org> writes:
> 
> > this is still rough, hence it is disabled by default.  You need to compile
> > with "make THREADED_DELTA_SEARCH=1 ..." at the moment.
> >
> > Threading is done on different portions of the object list to be
> > deltified. This is currently done by spliting the list into n parts and
> > then a thread is spawned for each of them.  A better method would consist
> > of spliting the list into more smaller parts and have the n threads
> > pick the next part available.
> 
> Hmmm.  I wonder how the result is affected by such a partition;
> aren't you going to have many objects that could have used
> somebody else as a delta but gets stored as base because they
> happen to be a very early part of their partition (and lacking
> delta base candidates in the window)?  

Yes.  On a largish repo that shouldn't be significant though, not worse 
than repacking multiple packs into one without -f.

> You cannot solve it with
> overlapping partitions without busting the depth limit easily
> either, I suspect.

My plan is to call find_deltas() again over partition boundaries after 
adjacent partitions have been processed.  If delta_child is properly 
maintained in all cases (trivial) then this should just work.

> Also how would this interact with the LRU
> delta base window we discussed a week or two ago?

This is completely orthogonal.

> Separating the list into different object types would not have
> any adverse impact coming from the "horizon" of delta base
> candidates window (because we do not deltify across types), but
> that is not very useful because we cannot gain much parallerism
> from such a partition.

Indeed.  Even with a straight split with equal number of objects, some 
threads currently complete much faster than others.  This is why a more 
sophisticated distribution of work is still needed to keep the desired 
amount of threads busy all the time.


Nicolas

Re: [PATCH] basic threaded delta search

[Martin Koegler]

On Thu, Sep 06, 2007 at 10:48:06AM -0400, Nicolas Pitre wrote:
> On Thu, 6 Sep 2007, Junio C Hamano wrote:
> > Also how would this interact with the LRU
> > delta base window we discussed a week or two ago?
> 
> This is completely orthogonal.

Maybe we should adjust the split point of the the object list so, that
objects with the same name hash are processed by one thread, as the LRU
could provide the most benefit for these objects.

I think of something like (totally untested):
        for (i = 0; i < NR_THREADS; i++) {
                unsigned sublist_size = list_size / (NR_THREADS - i);
+		while (sublist_size < list_size && list[0]->hash == list[1]->hash)
+			sublist_size++;
                p[i].list = list;
                p[i].list_size = sublist_size;
                p[i].window = window;
                p[i].depth = depth;
                p[i].processed = processed;
                ret = pthread_create(&p[i].thread, NULL,
                                     threaded_find_deltas, &p[i]);
                if (ret)
                        die("unable to create thread: %s", strerror(ret));
                list += sublist_size;
                list_size -= sublist_size;
        }

mfg Martin Kögler

Re: [PATCH] basic threaded delta search

[Nicolas Pitre]

On Fri, 7 Sep 2007, Martin Koegler wrote:

> On Thu, Sep 06, 2007 at 10:48:06AM -0400, Nicolas Pitre wrote:
> > On Thu, 6 Sep 2007, Junio C Hamano wrote:
> > > Also how would this interact with the LRU
> > > delta base window we discussed a week or two ago?
> > 
> > This is completely orthogonal.
> 
> Maybe we should adjust the split point of the the object list so, that
> objects with the same name hash are processed by one thread, as the LRU
> could provide the most benefit for these objects.
> 
> I think of something like (totally untested):
>         for (i = 0; i < NR_THREADS; i++) {
>                 unsigned sublist_size = list_size / (NR_THREADS - i);
> +		while (sublist_size < list_size && list[0]->hash == list[1]->hash)
> +			sublist_size++;

I guess you mean list[sublist_size-1]->hash == list[sublist_size]->hash.
But yeah that is a good idea.


Nicolas