March 08, 2012
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
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
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
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
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
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
Thank you, that's very helpful.

Top | Discussion index | About this forum | D home