std.parallelism: Final review

[dsimcha]

== 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.

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.

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.