• simendsjo (12/12) Jun 04 2011 I just found Project Euler, and tried to solve the first problem.
• simendsjo (4/8) Jun 04 2011 Ehem.. Guess it fails at recursion depth 500 :)
• Steven Schveighoffer (8/16) Jun 06 2011 Not sure if it's documented somewhere, but I think it is dmd's attempt t...
• Timon Gehr (13/23) Jun 04 2011 I just found Project Euler, and tried to solve the first problem.
• simendsjo (3/12) Jun 04 2011 I thought paralellism was using locks behind the scenes. Guess I'll have...
• Ben Grabham (3/18) Jun 04 2011 You can always try reduce and map :) I can't remember whether they are
• Ben Grabham (2/21) Jun 04 2011 Oops, sorry, missed the bit where you said you've already done parallel ...

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.

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?

"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

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

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 :)

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!

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!