Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
June 04, 2011 Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
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 Re: Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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 Re: Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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 Re: Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 Re: Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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 Re: Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Grabham | 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 Re: Template error and parallel foreach bug? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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
|
Copyright © 1999-2021 by the D Language Foundation