Thread overview
Template error and parallel foreach bug?
Jun 04, 2011
simendsjo
Jun 04, 2011
simendsjo
Jun 04, 2011
Timon Gehr
Jun 04, 2011
simendsjo
Jun 05, 2011
Ben Grabham
Jun 05, 2011
Ben Grabham
June 04, 2011
I just found Project Euler, and tried to solve the first problem.
https://gist.github.com/1007840

I did four implementations: template, ctfe, parallel foreach and parallel map.

The template implementation works on low numbers, but not on 1000 (haven't checked when it fails). It gives me the following error:
euler1.d(23): Error: template instance euler1.SumMultiple3Or5(499LU,Below,57918LU) recursive expansion

The parallel foreach loop works good on low numbers, but when increasing BOLOW it starts giving wrong results. The higher the number, the more often it calculates wrong results.

This is tested on dmd 2.053 on a dual core Win7.
June 04, 2011
On 04.06.2011 14:02, simendsjo wrote:
> The template implementation works on low numbers, but not on 1000
> (haven't checked when it fails). It gives me the following error:
> euler1.d(23): Error: template instance
> euler1.SumMultiple3Or5(499LU,Below,57918LU) recursive expansion

Ehem.. Guess it fails at recursion depth 500 :)
This is perhaps even documented somewhere? Or is it possible to change the value?
June 04, 2011
I just found Project Euler, and tried to solve the first problem.
https://gist.github.com/1007840
simendsjo wrote:
> I did four implementations: template, ctfe, parallel foreach and parallel map.
>
> The template implementation works on low numbers, but not on 1000
> (haven't checked when it fails). It gives me the following error:
> euler1.d(23): Error: template instance
> euler1.SumMultiple3Or5(499LU,Below,57918LU) recursive expansion
>
> The parallel foreach loop works good on low numbers, but when increasing BOLOW it starts giving wrong results. The higher the number, the more often it calculates wrong results.
>
> This is tested on dmd 2.053 on a dual core Win7.

ulong SumMultiple3Or5_parallel(uint below) {
    ulong sum;
    foreach(i; parallel(iota(below))) {
        if(i % 3 == 0 || i % 5 == 0)
            sum += i; // low level data race here.
    }
    return sum;
}

Loop iterations in a parallel foreach loop must be independent of each other.

Timon
June 04, 2011
On 04.06.2011 20:04, Timon Gehr wrote:
> ulong SumMultiple3Or5_parallel(uint below) {
>      ulong sum;
>      foreach(i; parallel(iota(below))) {
>          if(i % 3 == 0 || i % 5 == 0)
>              sum += i; // low level data race here.
>      }
>      return sum;
> }
>
> Loop iterations in a parallel foreach loop must be independent of each other.
>

I thought paralellism was using locks behind the scenes. Guess I'll have to read the documentation then :)
June 05, 2011
On 04/06/11 20:16, simendsjo wrote:
> On 04.06.2011 20:04, Timon Gehr wrote:
>> ulong SumMultiple3Or5_parallel(uint below) {
>> ulong sum;
>> foreach(i; parallel(iota(below))) {
>> if(i % 3 == 0 || i % 5 == 0)
>> sum += i; // low level data race here.
>> }
>> return sum;
>> }
>>
>> Loop iterations in a parallel foreach loop must be independent of each
>> other.
>>
>
> I thought paralellism was using locks behind the scenes. Guess I'll have
> to read the documentation then :)

You can always try reduce and map :) I can't remember whether they are parallel or not though!
June 05, 2011
On 05/06/11 03:55, Ben Grabham wrote:
> On 04/06/11 20:16, simendsjo wrote:
>> On 04.06.2011 20:04, Timon Gehr wrote:
>>> ulong SumMultiple3Or5_parallel(uint below) {
>>> ulong sum;
>>> foreach(i; parallel(iota(below))) {
>>> if(i % 3 == 0 || i % 5 == 0)
>>> sum += i; // low level data race here.
>>> }
>>> return sum;
>>> }
>>>
>>> Loop iterations in a parallel foreach loop must be independent of each
>>> other.
>>>
>>
>> I thought paralellism was using locks behind the scenes. Guess I'll have
>> to read the documentation then :)
>
> You can always try reduce and map :) I can't remember whether they are
> parallel or not though!

Oops, sorry, missed the bit where you said you've already done parallel map!
June 06, 2011
On Sat, 04 Jun 2011 08:11:01 -0400, simendsjo <simen.endsjo@pandavre.com> wrote:

> On 04.06.2011 14:02, simendsjo wrote:
>> The template implementation works on low numbers, but not on 1000
>> (haven't checked when it fails). It gives me the following error:
>> euler1.d(23): Error: template instance
>> euler1.SumMultiple3Or5(499LU,Below,57918LU) recursive expansion
>
> Ehem.. Guess it fails at recursion depth 500 :)
> This is perhaps even documented somewhere? Or is it possible to change the value?

Not sure if it's documented somewhere, but I think it is dmd's attempt to avoid infinite template recursion.  Preventing infinite recursion is equivalent to solving the halting problem, so I don't think it's possible to solve perfectly.

You can likely "fix" it by modifying the source for dmd.

-Steve