std.parallelism: Final review

[Jonas Drewsen]

On 18/03/11 22.43, dsimcha wrote:
> == Quote from Jonas Drewsen (jdrewsen at nospam.com)'s article
>> On 18/03/11 10.40, Lars T. Kyllingstad wrote:
>>> On Fri, 04 Mar 2011 21:05:39 +0000, Lars T. Kyllingstad wrote:
>>>
>>>> David Simcha has made a proposal for an std.parallelism module to be
>>>> included in Phobos.  We now begin the formal review process.
>>>>
>>>> The code repository and documentation can be found here:
>>>>
>>>>     https://github.com/dsimcha/std.parallelism/wiki
>>>>     http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html
>>>
>>>
>>> I would like to remind everyone that there is now only one week left of
>>> the std.parallelism review period.  If you have any comments, please
>>> speak now, so that David has time to make the changes.
>>>
>>> I realise that the module has been through several review cycles already,
>>> and that it is already in active use (by me, among others), so there
>>> probably won't be any big issues.  However, if it gets voted into Phobos,
>>> that's it -- it will be an official part of the D standard library.  So
>>> start nitpicking, folks!
>>>
>>> The voting will start next Friday, 25 March, and last for a week, until 1
>>> April.
>>>
>>> -Lars
>> I can't say that I've read the code thoroughly but maybe someone can
>> tell me if it supports work stealing?
>> /Jonas
>
> Not in Cilk style.  Everything just goes to a shared queue.  In theory this could
> be a bottleneck in the micro parallelism case.  However, some experimentation I
> did early in the design convinced me that in practice there's so much other
> overhead involved in moving work from one processor to another (cache misses,
> needing to wake up a thread, etc.) that, in cases where a shared queue might be a
> bottleneck, the parallelism is probably too fine-grained anyhow.

I guess that work stealing could be implemented without changing the 
current interface if evidence shows up that would favor work stealing?

Maybe later an extension to the task scheduler for task cpu affinity 
would be nice in order to lower cache misses for certain kinds of tasks.

> std.parallelism does, however, support semantics somewhat similar to work stealing
> in that, when a thread needs the results of a job that has not yet been started,
> said job will be pulled out of the middle of the queue and executed immediately in
> the thread that needs the result.

This is indeed a nice feature.

> Using a shared queue simplifies the design massively and arguably makes more sense
> in that tasks are guaranteed to be started in the order received, except in the
> case described above.

Yes it works very well in general I believe.

Nice work!
/Jonas