www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Template error and parallel foreach bug?

reply simendsjo <simen.endsjo pandavre.com> writes:
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.
Jun 04 2011
next sibling parent reply simendsjo <simen.endsjo pandavre.com> writes:
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?
Jun 04 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Jun 06 2011
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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
Jun 04 2011
parent reply simendsjo <simen.endsjo pandavre.com> writes:
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 :)
Jun 04 2011
parent reply Ben Grabham <Evil.Nebster gmail.com> writes:
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!
Jun 04 2011
parent Ben Grabham <Evil.Nebster gmail.com> writes:
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!
Jun 04 2011