www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Parallelization issues

reply "ixid" <nuaccount gmail.com> writes:
This is a simple merge sorting implementation, a[0] and a[1] are 
the two halves of the array to be sorted, split into an int[][2] 
a array. This was done because I wanted to try parallel but that 
gives these errors:

	foreach(ref i;parallel(a))
		mergeSort(i);

Error: template std.array.popFront(A) if (!isNarrowString!(A) && 
isDynamicArray!(A) && isMutable!(A) && !is(A == void[])) does not 
match any function template declaration

Error	2	Error: template std.array.popFront(A) if 
(!isNarrowString!(A) && isDynamicArray!(A) && isMutable!(A) && 
!is(A == void[])) cannot deduce template function from argument 
types !()(int[][2u])

Without parallel it works as intended in a single threaded way. 
The same error is given using sort(i).

So I tried (and have probably misunderstood the correct 
syntax/steps required) using task as so:

	auto task1 = task!(mergeSort)(a[0]);
	task1.executeInNewThread();
	//taskPool.put(task1);
	mergeSort(a[1]);
	a[0] = task1.yieldForce();

I tried both the taskPool.put and executeInNewThread() versions, 
they both sort the numbers correctly but it's 3-4 times slower 
than doing it single-threaded. My processor is a Core 2 Duo and 
reports 2 with totalCPUs. I've also used multi-threading 
successfully with C++ before. What am I doing wrong?
Mar 08 2012
parent reply "bearophile" <bearophile lycos.com> writes:
ixid:

 This is a simple merge sorting implementation, a[0] and a[1] 
 are the two halves of the array to be sorted, split into an 
 int[][2] a array. This was done because I wanted to try 
 parallel but that gives these errors:

 	foreach(ref i;parallel(a))
 		mergeSort(i);

 Error: template std.array.popFront(A)
You are trying to do popFront on a fixed sized array. Try to use int[][] instead of int[][2]. Bye, bearophile
Mar 08 2012
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 03/08/2012 07:52 AM, bearophile wrote:
 ixid:

 This is a simple merge sorting implementation, a[0] and a[1] are the
 two halves of the array to be sorted, split into an int[][2] a array.
 This was done because I wanted to try parallel but that gives these
 errors:

 foreach(ref i;parallel(a))
 mergeSort(i);

 Error: template std.array.popFront(A)
You are trying to do popFront on a fixed sized array. Try to use int[][] instead of int[][2]. Bye, bearophile
Indeed. Both of the following work for me: import std.stdio; import std.algorithm; import std.parallelism; void main() { int[] array = [ 6, 3, -5, 9, 0, -1, 10 ]; int[][] slices = [ array[0 .. $/2], array[$/2 .. $] ]; foreach(slice; parallel(slices)) { sort(slice); } writeln("Note: Only partially sorted: ", array); } import std.stdio; import std.algorithm; import std.parallelism; void main() { int[] array = [ 6, 3, -5, 9, 0, -1, 10 ]; auto tasks = [ task!sort(array[0 .. $/2]) ]; tasks ~= task!sort(array[$/2 .. $]); foreach (task; tasks) { task.executeInNewThread(); } foreach (task; tasks) { task.yieldForce(); } writeln("Note: Only partially sorted: ", array); } Ali
Mar 08 2012
parent reply "ixid" <nuaccount gmail.com> writes:
Changing a[][2] to a[][] as suggested made it work. It's not 
clear to me why it should matter that it's not dynamic in that 
axis or are arrays simply static or dynamic globally? It also 
doesn't fix the performance issue, parallel behaves in the same 
manner as the other implementation taking 3-4 times as long as 
doing it single threaded. I ran the students parallel example 
from here: http://ddili.org/ders/d.en/parallelism.html

And it worked correctly, taking half the time in parallel.
Mar 08 2012
next sibling parent "ixid" <nuaccount gmail.com> writes:
Never mind, it must be some hidden effect such as memory use in 
my function, sort works as expected with the parallelization.
Mar 08 2012
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 03/08/2012 12:09 PM, ixid wrote:
 Changing a[][2] to a[][] as suggested made it work. It's not clear to me
 why it should matter that it's not dynamic in that axis or are arrays
 simply static or dynamic globally?
The reason is that fixed-length arrays cannot be ranges themselves because popFront() cannot be implemented on them. Luckily though, we can very easily take a whole slice of a fixed-length array and that would be a range. The following code has the same problem as yours: // WARNING: Cannot be compiled import std.stdio; import std.parallelism; void main() { int[2] array = [ 1, 2 ]; foreach (element; parallel(array)) { writeln(element); } } The fix is to pass a slice of array to parallel(). Now it works: foreach (element; parallel(array[])) { // <-- note [] } Now parallel() will consume the temporary slice that is passed to it. Ali
Mar 08 2012
parent "ixid" <nuaccount gmail.com> writes:
Thank you, that's very helpful.
Mar 08 2012