View mode: basic / threaded / horizontal-split · Log in · Help
March 08, 2012
Parallelization issues
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?
March 08, 2012
Re: Parallelization issues
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
March 08, 2012
Re: Parallelization issues
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
March 08, 2012
Re: Parallelization issues
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.
March 08, 2012
Re: Parallelization issues
Never mind, it must be some hidden effect such as memory use in 
my function, sort works as expected with the parallelization.
March 08, 2012
Re: Parallelization issues
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
March 08, 2012
Re: Parallelization issues
Thank you, that's very helpful.
Top | Discussion index | About this forum | D home