Re: [PATCH] pack-objects: don't use too many threads with few objects

"Mike Ralphson" [off-list ref] writes:

2008/12/13 Nicolas Pitre [off-list ref]

quoted

If there are few objects to deltify, they might be split amongst threads
so that there is simply no other objects left to delta against within
the same thread.  Let's use the same 2*window treshold as used for the
final load balancing to allow extra threads to be created.

This fixes the benign t5300 test failure.

Even with this I'm seeing failures in t5302 which I think are probably
related to 43cc2b42
...
*   ok 2: pack-objects with index version 1

* expecting success: pack2=$(git pack-objects --index-version=2 test-2
<obj-list) &&
     git verify-pack -v "test-2-${pack2}.pack"
0106e17481932f5c223fafadc1d26abc6adf40d6 blob   57 90 850531 1
69e0b8ef8cda369575b6801c6ed47daf09aa3c62
...
fff3a3a92d2268a464dbdcd00fc055885ee3cba9 blob   8196 8210 187404
chain length = 1: 109 objects
chain length = 2: 10 objects
chain length = 3: 10 objects
chain length = 4: 10 objects
chain length = 5: 10 objects
chain length = 6: 10 objects
chain length = 7: 10 objects
chain length = 8: 10 objects
chain length = 9: 9 objects
test-2-9108b6dfd43bf36ccbfc2839fe62d1503bf84292.pack: ok
*   ok 3: pack-objects with index version 2

* expecting success: cmp "test-1-${pack1}.pack" "test-2-${pack2}.pack"
test-1-9108b6dfd43bf36ccbfc2839fe62d1503bf84292.pack
test-2-9108b6dfd43bf36ccbfc2839fe62d1503bf84292.pack differ: char
10236, line 32
* FAIL 4: both packs should be identical
	cmp "test-1-${pack1}.pack" "test-2-${pack2}.pack"

This is interesting.  The same set of objects are packed with the
identical list of objects stored in obj-list and the only difference
between test #2 and test #3 are the format of the .idx file they produce.
Yet they are producing different .pack file?

And this does not fail with 'master' on Mike's AIX, but with 'next' that
has the threaded delta search.

Since the list of objects packed (obj-list in the test script) contains
302 objects, which is way bigger than the window size, I can understand
that packing with or without threading would produce different results.

Even though depending on the timings of how worker threads complete
assigned work and grab more work for them, two otherwise identical runs,
even with the same set of parameters, could assign different set of
objects to different threads.  But as far as I can see, the same set of
objects should go to the same chunk, and the only difference should be
which thread gets which chunk, and I do not see how that could affect the
outcome.  Puzzled...

Perhaps the two runs are seeing different number of CPUs (hence threads)
available?  That would then change the distribution of the work itself
(i.e. what slice of obj-list goes as a single chunk to be processed) and
would affect the outcome.

Does the second test this patch adds fail?

 t/t5302-pack-index.sh |   11 +++++++++++
 1 files changed, 11 insertions(+), 0 deletions(-)

diff --git i/t/t5302-pack-index.sh w/t/t5302-pack-index.sh
index 884e242..bd5db03 100755
--- i/t/t5302-pack-index.sh
+++ w/t/t5302-pack-index.sh

@@ -39,6 +39,17 @@ test_expect_success \
      git verify-pack -v "test-1-${pack1}.pack"'
 
 test_expect_success \
+    'pack-objects with index version 1 (again)' \
+    'pack1=$(git pack-objects --index-version=1 test-1again <obj-list) &&
+     git verify-pack -v "test-1again-${pack1}.pack"'
+
+test_expect_success 'both should match' '
+	cmp "test-1-${pack1}.pack" "test-1again-${pack1}.pack"
+'
+
+exit
+
+test_expect_success \
     'pack-objects with index version 2' \
     'pack2=$(git pack-objects --index-version=2 test-2 <obj-list) &&
      git verify-pack -v "test-2-${pack2}.pack"'

On Mon, Dec 15, 2008 at 05:15:44PM -0800, Junio C Hamano wrote:

Perhaps the two runs are seeing different number of CPUs (hence threads)
available?  That would then change the distribution of the work itself
(i.e. what slice of obj-list goes as a single chunk to be processed) and
would affect the outcome.

I am seeing the same failure as Mike on one of my boxen.  Each run sees
the same number of threads (4 in my case).

Does the second test this patch adds fail?

With your patch, the added "both should match" test fails. So it seems
to be about doing a second run at all, not the difference in index
versions.

-Peff

On Mon, 15 Dec 2008, Junio C Hamano wrote:

"Mike Ralphson" [off-list ref] writes:

quoted

2008/12/13 Nicolas Pitre [off-list ref]

quoted

If there are few objects to deltify, they might be split amongst threads
so that there is simply no other objects left to delta against within
the same thread.  Let's use the same 2*window treshold as used for the
final load balancing to allow extra threads to be created.

This fixes the benign t5300 test failure.

Even with this I'm seeing failures in t5302 which I think are probably
related to 43cc2b42
...
*   ok 2: pack-objects with index version 1

* expecting success: pack2=$(git pack-objects --index-version=2 test-2
<obj-list) &&
     git verify-pack -v "test-2-${pack2}.pack"
0106e17481932f5c223fafadc1d26abc6adf40d6 blob   57 90 850531 1
69e0b8ef8cda369575b6801c6ed47daf09aa3c62
...
fff3a3a92d2268a464dbdcd00fc055885ee3cba9 blob   8196 8210 187404
chain length = 1: 109 objects
chain length = 2: 10 objects
chain length = 3: 10 objects
chain length = 4: 10 objects
chain length = 5: 10 objects
chain length = 6: 10 objects
chain length = 7: 10 objects
chain length = 8: 10 objects
chain length = 9: 9 objects
test-2-9108b6dfd43bf36ccbfc2839fe62d1503bf84292.pack: ok
*   ok 3: pack-objects with index version 2

* expecting success: cmp "test-1-${pack1}.pack" "test-2-${pack2}.pack"
test-1-9108b6dfd43bf36ccbfc2839fe62d1503bf84292.pack
test-2-9108b6dfd43bf36ccbfc2839fe62d1503bf84292.pack differ: char
10236, line 32
* FAIL 4: both packs should be identical
	cmp "test-1-${pack1}.pack" "test-2-${pack2}.pack"

This is interesting.  The same set of objects are packed with the
identical list of objects stored in obj-list and the only difference
between test #2 and test #3 are the format of the .idx file they produce.
Yet they are producing different .pack file?

Indeed, this is really strange.

Even though depending on the timings of how worker threads complete
assigned work and grab more work for them, two otherwise identical runs,
even with the same set of parameters, could assign different set of
objects to different threads.  But as far as I can see, the same set of
objects should go to the same chunk, and the only difference should be
which thread gets which chunk, and I do not see how that could affect the
outcome.  Puzzled...

You probably have the explanation here: worker threads are not 
necessarily completing their own chunks alwais at the same time relative 
with each other.  Hence, a thread stealing more work from another thread 
might or might not interrupt that other thread always at the same point 
between runs, and therefore the final delta chain might get shifted a 
bit.

I think the best "fix" is actually to configure only one thread for this 
test.  The point here is to make sure different index versions don't 
introduce variations in pack generation, but multiple threads do defeat 
that because of the inner randomness in thread scheduling.

I'm therefore giving my ACK to Johannes' patch posted earlier.


Nicolas