If I understand it correctly something like:

range.filter!(...).map!(...)

browse range 2 times, one for filter and one for mapping doesn't it?

Is there a way to "parallelize" this kind of operations?

On 03/04/2013 09:06 PM, Andrea Fontana wrote:
> If I understand it correctly something like:
>
> range.filter!(...).map!(...)
>
> browse range 2 times, one for filter and one for mapping doesn't it?
>

It does not.

> Is there a way to "parallelize" this kind of operations?
>

Interleaving is the default. To perform two traversals you'd have to force evaluation using eg. range.filter!(...).array.map!(...).

On Mon, Mar 04, 2013 at 09:06:18PM +0100, Andrea Fontana wrote:
> If I understand it correctly something like:
> 
> range.filter!(...).map!(...)
> 
> browse range 2 times, one for filter and one for mapping doesn't it?

No, these algorithms are evaluated lazily (unless you put .array at the end). The range is only traversed once.


> Is there a way to "parallelize" this kind of operations?

What do you mean by "parallelize"? Run in multiple threads? I don't think you can do that, because the result of filter depends on what it gets from map.


T

-- 
Skill without imagination is craftsmanship and gives us many useful objects such as wickerwork picnic baskets.  Imagination without skill gives us modern art. -- Tom Stoppard

On Monday, 4 March 2013 at 20:21:31 UTC, Timon Gehr wrote:
> On 03/04/2013 09:06 PM, Andrea Fontana wrote:
>> If I understand it correctly something like:
>>
>> range.filter!(...).map!(...)
>>
>> browse range 2 times, one for filter and one for mapping doesn't it?
>>
>
> It does not.
>
>> Is there a way to "parallelize" this kind of operations?
>>
>
> Interleaving is the default. To perform two traversals you'd have to force evaluation using eg. range.filter!(...).array.map!(...).


Very interesting. IMHO that should be pointed out better in docs/example.
You say interleaving is "default", how can I guess if a function doesn't use the "default" behaviour?

On 03/04/2013 12:06 PM, Andrea Fontana wrote:
> If I understand it correctly something like:
>
> range.filter!(...).map!(...)
>
> browse range 2 times, one for filter and one for mapping doesn't it?
>
> Is there a way to "parallelize" this kind of operations?
>

std.parallelism has lots of cool features to help with range parallelization. Here is map:

  http://dlang.org/phobos/std_parallelism.html#.TaskPool.map

There are some examples of mine at

  http://ddili.org/ders/d.en/parallelism.html

Here is an excerpt from the Summary section at that link:

- parallel() executes the iterations of foreach loops in parallel.

- asyncBuf() iterates the elements of an InputRange semi-eagerly in parallel.

- map() calls functions with the elements of an InputRange semi-eagerly in parallel.

- amap() calls functions with the elements of a RandomAccessRange fully-eagerly in parallel.

- reduce() makes calculations over the elements of a RandomAccessRange in parallel.

Ali

On Monday, 4 March 2013 at 21:22:36 UTC, Ali Çehreli wrote:
> On 03/04/2013 12:06 PM, Andrea Fontana wrote:
>> If I understand it correctly something like:
>>
>> range.filter!(...).map!(...)
>>
>> browse range 2 times, one for filter and one for mapping doesn't it?
>>
>> Is there a way to "parallelize" this kind of operations?
>>
>
> std.parallelism has lots of cool features to help with range parallelization. Here is map:
>
>   http://dlang.org/phobos/std_parallelism.html#.TaskPool.map
>
> There are some examples of mine at
>
>   http://ddili.org/ders/d.en/parallelism.html
>
> Here is an excerpt from the Summary section at that link:
>
> - parallel() executes the iterations of foreach loops in parallel.
>
> - asyncBuf() iterates the elements of an InputRange semi-eagerly in parallel.
>
> - map() calls functions with the elements of an InputRange semi-eagerly in parallel.
>
> - amap() calls functions with the elements of a RandomAccessRange fully-eagerly in parallel.
>
> - reduce() makes calculations over the elements of a RandomAccessRange in parallel.
>
> Ali

Of course I used "parallelism" (with quotes) but i mean something like "interleaving" as guessed by Timon Gehr.

On Mon, 2013-03-04 at 12:24 -0800, H. S. Teoh wrote:
[…]
> > Is there a way to "parallelize" this kind of operations?
> 
> What do you mean by "parallelize"? Run in multiple threads? I don't think you can do that, because the result of filter depends on what it gets from map.

This shows the deficiency in thinking of explicit use of threads as the only way forward. filter → map is a classic pipeline and if processed using a stream model over a thread pool using work stealing leads to code that is good. Alternatively do a parallel filter followed by a parallel map, data paralleism over a thread pool, more good code.

-- 
Russel. ============================================================================= Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder@ekiga.net 41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel@winder.org.uk London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder

On Monday, 4 March 2013 at 20:49:22 UTC, Andrea Fontana wrote:

> Very interesting. IMHO that should be pointed out better in docs/example.
> You say interleaving is "default", how can I guess if a function doesn't use the "default" behaviour?

It doesn't really make sense to point it out in the example since it is kind of fundamental to what ranges are. If it is eager than the docs should mention that.

If an operation requires all its data upfront, sort, then you'll usually see a call for .array().

On Wed, Mar 06, 2013 at 03:11:42AM +0100, Jesse Phillips wrote:
> On Monday, 4 March 2013 at 20:49:22 UTC, Andrea Fontana wrote:
> 
> >Very interesting. IMHO that should be pointed out better in
> >docs/example.
> >You say interleaving is "default", how can I guess if a function
> >doesn't use the "default" behaviour?
> 
> It doesn't really make sense to point it out in the example since it is kind of fundamental to what ranges are. If it is eager than the docs should mention that.
> 
> If an operation requires all its data upfront, sort, then you'll
> usually see a call for .array().

A range is an abstraction akin to C++'s iterators (except better, IMO). Just as iterators do not spontaneously consume the underlying data until you iterate over them, neither do ranges.


T

-- 
In a world without fences, who needs Windows and Gates? -- Christian Surchi

H. S. Teoh:

> A range is an abstraction akin to C++'s iterators (except better, IMO).

Stepanov himself has commented very briefly about Alexandrescu/D Ranges in one of his video lessons. I have not fully understood what Stepanov has said with those few words spoken in a not so good English (not because of language, but because Stepanov is still out of my league, he's a Teacher) but I think he has dismissed the Ranges. A bit like a chemist would dismiss a person that says that molecules are more important than atoms and only molecules should be used.

I think he has said that atoms are there (in a kind of mathematical Platonism), even if you try to ignore them, they are more fundamental. So Ranges are a little abstraction over C++-style iterators. They are maybe more handy, safer, they allow you to reason at a a bit higher lever, but they also forbid you to do few of the useful things that iterators can do.

In the end I think ranges were a success for D. Almost every part of the design of D has problems; sometimes even large problems (like shared, problems with missing head and tail const, missing logic constness, problems with scope, and so on at nauseum), but most times D ranges work, despite some faults they have.

Bye,
bearophile