www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - review of std.parallelism

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
0. Overview and vote

I think the library delivers the high-level goods (parallel foreach, 
map, reduce) but is a bit fuzzy in the lower level details.

Documentation hurts understanding of the capabilities of the library and 
essentially is of inadequate quality. Entity documentation and examples 
do little more than give the impression of dispensing with an unpleasant 
chore.

My vote in favor of acceptance is contingent upon a radical improvement 
in the quality of documentation and examples. Most if not all artifacts 
should be motivated by simple, compelling examples. The introductory 
section must contain a brief and attractive synopsis of the flagship 
capabilities. All terms must be defined before being used and introduced 
in a carefully-chosen order. The relationship between various entities 
should be clarified.

I've seen the argument that simple and strong examples are difficult to 
find. Though I agree such examples are not easy to come up with, I also 
believe the author of library is in the best position to produce them.

================

1. Library proper:

* "In the case of non-random access ranges, parallel foreach is still 
usable but buffers lazily to an array..." Wouldn't strided processing 
help? If e.g. 4 threads the first works on 0, 4, 8, ... second works on 
1, 5, 9, ... and so on.

* Example with squares would be better if double replaced uint, and if a 
more complicated operation (sqrt, log...) were involved.

* I'm unclear on the tactics used by lazyMap. I'm thinking the obvious 
method should be better: just use one circular buffer. The presence of 
two dependent parameters makes this abstraction difficult to operate with.

* Same question about asyncBuf. What is wrong with a circular buffer 
filled on one side by threads and on the consumed from the other by the 
client? I can think of a couple of answers but it would be great if they 
were part of the documentation.

* Why not make workerIndex a ulong and be done with it?

* Is stop() really trusted or just unsafe? If it's forcibly killing 
threads then its unsafe.

* uint size() should be size_t for conformity.

* defaultPoolThreads - should it be a  property?

* I don't understand what Task is supposed to do. It is circularly 
defined: "A struct that encapsulates the information about a task, 
including its current status, what pool it was submitted to, and its 
arguments." OK, but what's a task? Could a task be used outside a task 
pool, and if so to what effect(s)?

* If LazyMap is only necessary as the result of lazyMap, could that 
become a local type inside lazyMap?


2. Documentation:

* Documentation unacceptable. It lacks precision and uses terms before 
defining them. For example: "This class encapsulates a task queue and a 
set of worker threads" comes before the notions of "task queue" and 
"worker thread" are defined. Clearly there is an intuition of what those 
are supposed to mean, but in practice each library lays down some fairly 
detailed definition of such.

* "Note: Initializing a pool with zero threads (as would happen in the 
case of a single-core CPU) is well-tested and does work." The absence of 
a bug should not be advertised in so many words. Simpler: "Note: 
Single-CPU machines will operate transparently with zero-sized pools."

* "Allows for custom pool size." I have no idea what pool size means.

* "// Do something interesting." Worst example ever. You are the creator 
of the library. If _you_ can't find a brief compelling example, who could?

* "Immediately after the range argument, an optional block size argument 
may be provided. If none is provided, the default block size is used. An 
optional buffer for returining the results may be provided as the last 
argument. If one is not provided, one will be automatically allocated. 
If one is provided, it must be the same length as the range." An example 
should be inserted after each of these sentences.

* "// Do something expensive with line." Better you do something 
expensive with line.

* "This is not the same thing as commutativity." I think this is obvious 
enough to be left out. The example of matrices (associative but not 
commutative) is nice though.

* "immutable n = 1000000000;" -> use underscores

* Would be great if the documentation examples included some rough 
experimental results, e.g. "3.8 times faster on a 4-core machine than 
the equivalent serial loop".

* No example for workerIndex and why it's useful.

* Is LocalWorker better than WorkerLocal? No, because it's not the 
worker that's local, it's the storage - which is missing from the name! 
WorkerLocalStorage? Also replace "create" with "make" or drop it 
entirely. The example doesn't tell me how I can use bufs. I suspect 
workerIndex has something to do with it but the example fails to divulge 
that relationship.

* No example for join(), which is quite a central primitive.

* No example for put(), which would be interesting to see.

* No example for task().

* No example for run().

* The example for Task uses myFuture without defining it. In case Task 
defines the promise/future idiom, the documentation misses a terrific 
opportunity of clarifying that.

* What is 'run' in the definition of safe task()?

* Why is AsyncBuf's doc far away from the function returning it? Same 
about WorkerLocal.


Andrei
Mar 18 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
Thanks for the advice.  You mentioned in the past that the documentation 
was inadequate but didn't give enough specifics as to how until now.  As 
the author of the library, things seem obvious to me that don't seem 
obvious to anyone else, so I don't feel that I'm in a good position to 
judge the quality of the documentation and where it needs improvement. 
I plan to fix most of the issues you raised, but I've left comments for 
the few that I can't/won't fix or believe are based on misunderstandings 
below.

On 3/18/2011 11:29 PM, Andrei Alexandrescu wrote:

 1. Library proper:

 * "In the case of non-random access ranges, parallel foreach is still
 usable but buffers lazily to an array..." Wouldn't strided processing
 help? If e.g. 4 threads the first works on 0, 4, 8, ... second works on
 1, 5, 9, ... and so on.


You can have this if you want, by setting the work unit size to 1. 
Setting it to a larger size just causes more elements to be buffered, 
which may be more efficient in some cases.


 * I'm unclear on the tactics used by lazyMap. I'm thinking the obvious
 method should be better: just use one circular buffer. The presence of
 two dependent parameters makes this abstraction difficult to operate with.

 * Same question about asyncBuf. What is wrong with a circular buffer
 filled on one side by threads and on the consumed from the other by the
 client? I can think of a couple of answers but it would be great if they
 were part of the documentation.


Are you really suggesting I give detailed rationales for implementation 
decisions in the documentation?  Anyhow, the two reasons for this choice 
are to avoid needing synchronization/atomic ops/etc. on every write to 
the buffer (which we would need since it can be read and written 
concurrently and we need to track whether we have space to write to) and 
because parallel map works best when it operates on relatively large 
buffers, resulting in minimal synchronization overhead per element. 
(Under the hood, the buffer is filled and then eager parallel map is 
called.)


 * Why not make workerIndex a ulong and be done with it?


I doubt anyone's really going to create anywhere near 4 billion TaskPool 
threads over the lifetime of a program.  Part of the point of TaskPool 
is recycling threads rather than paying the overhead of creating and 
destroying them.  Using a ulong on a 32-bit architecture would make 
worker-local storage substantially slower.  workerIndex is how 
worker-local storage works under the hood, so it needs to be fast.


 * No example for workerIndex and why it's useful.


It should just be private.  The fact that it's public is an artifact of 
when I was designing worker-local storage and didn't know how it was 
going to work yet.  I never thought to revisit this until now.  It 
really isn't useful to client code.


 * Is stop() really trusted or just unsafe? If it's forcibly killing
 threads then its unsafe.


It's not forcibly killing threads.  As the documentation states, it has 
no effect on jobs already executing, only ones in the queue. 
Furthermore, it's needed unless makeDaemon is called.  Speaking of 
which, makeDaemon and makeAngel should probably be trusted, too.


 * defaultPoolThreads - should it be a  property?


Yes.  In spirit it's a global variable.  It requires some extra 
machinations, though, to be threadsafe, which is why it's not 
implemented as a simple global variable.


 * No example for task().


???? Yes there is, for both flavors, though these could admittedly be 
improved.  Only the safe version doesn't have an example, and this is 
just a more restricted version of the function pointer case, so it seems 
silly to make a separate example for it.


 * What is 'run' in the definition of safe task()?


It's just the run() adapter function.  Isn't that obvious?
Mar 18 2011
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
On Sat, 19 Mar 2011 05:40:08 +0100, dsimcha <dsimcha yahoo.com> wrote:


 On 3/18/2011 11:29 PM, Andrei Alexandrescu wrote:

 1. Library proper:

 * "In the case of non-random access ranges, parallel foreach is still
 usable but buffers lazily to an array..." Wouldn't strided processing
 help? If e.g. 4 threads the first works on 0, 4, 8, ... second works on
 1, 5, 9, ... and so on.


 You can have this if you want, by setting the work unit size to 1.  
 Setting it to a larger size just causes more elements to be buffered,  
 which may be more efficient in some cases.


Please add an example showing that, too. Sure, the documentation says
that's what's being done, but an example would show it more clearly.


-- 
Simen
Mar 19 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article

 On Sat, 19 Mar 2011 05:40:08 +0100, dsimcha <dsimcha yahoo.com> wrote:

 On 3/18/2011 11:29 PM, Andrei Alexandrescu wrote:

 1. Library proper:

 * "In the case of non-random access ranges, parallel foreach is still
 usable but buffers lazily to an array..." Wouldn't strided processing
 help? If e.g. 4 threads the first works on 0, 4, 8, ... second works on
 1, 5, 9, ... and so on.


 You can have this if you want, by setting the work unit size to 1.
 Setting it to a larger size just causes more elements to be buffered,
 which may be more efficient in some cases.


 Please add an example showing that, too. Sure, the documentation says
 that's what's being done, but an example would show it more clearly.


I don't understand how this can be demonstrated in an example.  It's an
under-the-hood thing.  The only place this appears in the API is in the
workUnitSize parameter.
Mar 19 2011
parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
On Sat, 19 Mar 2011 13:51:56 +0100, dsimcha <dsimcha yahoo.com> wrote:


 == Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article

 On Sat, 19 Mar 2011 05:40:08 +0100, dsimcha <dsimcha yahoo.com> wrote:

 On 3/18/2011 11:29 PM, Andrei Alexandrescu wrote:

 1. Library proper:

 * "In the case of non-random access ranges, parallel foreach is still
 usable but buffers lazily to an array..." Wouldn't strided processing
 help? If e.g. 4 threads the first works on 0, 4, 8, ... second works  




 on

 1, 5, 9, ... and so on.


 You can have this if you want, by setting the work unit size to 1.
 Setting it to a larger size just causes more elements to be buffered,
 which may be more efficient in some cases.


 Please add an example showing that, too. Sure, the documentation says
 that's what's being done, but an example would show it more clearly.


 I don't understand how this can be demonstrated in an example.  It's an
 under-the-hood thing.  The only place this appears in the API is in the
 workUnitSize parameter.


Yeah, scratch that. I for some reason thought the "array of size
workUnitSize" was global, but it's per thread, innit? Seems so logical now.


-- 
Simen
Mar 19 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/18/2011 11:40 PM, dsimcha wrote:

 Thanks for the advice. You mentioned in the past that the documentation
 was inadequate but didn't give enough specifics as to how until now. As
 the author of the library, things seem obvious to me that don't seem
 obvious to anyone else, so I don't feel that I'm in a good position to
 judge the quality of the documentation and where it needs improvement. I
 plan to fix most of the issues you raised, but I've left comments for
 the few that I can't/won't fix or believe are based on misunderstandings
 below.


Great, thanks.


 On 3/18/2011 11:29 PM, Andrei Alexandrescu wrote:

 1. Library proper:

 * "In the case of non-random access ranges, parallel foreach is still
 usable but buffers lazily to an array..." Wouldn't strided processing
 help? If e.g. 4 threads the first works on 0, 4, 8, ... second works on
 1, 5, 9, ... and so on.


 You can have this if you want, by setting the work unit size to 1.
 Setting it to a larger size just causes more elements to be buffered,
 which may be more efficient in some cases.


Got it.


 * Why not make workerIndex a ulong and be done with it?


 I doubt anyone's really going to create anywhere near 4 billion TaskPool
 threads over the lifetime of a program. Part of the point of TaskPool is
 recycling threads rather than paying the overhead of creating and
 destroying them. Using a ulong on a 32-bit architecture would make
 worker-local storage substantially slower. workerIndex is how
 worker-local storage works under the hood, so it needs to be fast.


If you're confident that overflow won't occur, you may want to eliminate 
that detail from the docs. It throws off the reader.


  > * No example for workerIndex and why it's useful.

 It should just be private. The fact that it's public is an artifact of
 when I was designing worker-local storage and didn't know how it was
 going to work yet. I never thought to revisit this until now. It really
 isn't useful to client code.


It could be public and undocumented.


 * Is stop() really trusted or just unsafe? If it's forcibly killing
 threads then its unsafe.


 It's not forcibly killing threads. As the documentation states, it has
 no effect on jobs already executing, only ones in the queue.
 Furthermore, it's needed unless makeDaemon is called. Speaking of which,
 makeDaemon and makeAngel should probably be trusted, too.


Great. The more safe/trusted, the better.


 * defaultPoolThreads - should it be a  property?


 Yes. In spirit it's a global variable. It requires some extra
 machinations, though, to be threadsafe, which is why it's not
 implemented as a simple global variable.


Then it should be a  property. I think ddoc doesn't reflect that, but an 
example could.


 * No example for task().


 ???? Yes there is, for both flavors, though these could admittedly be
 improved. Only the safe version doesn't have an example, and this is
 just a more restricted version of the function pointer case, so it seems
 silly to make a separate example for it.


Towards the bottom of the document there are overloads of task that 
don't have examples.


 * What is 'run' in the definition of safe task()?


 It's just the run() adapter function. Isn't that obvious?


I'm referring to this:

Task!(run,TypeTuple!(F,Args)) task(F, Args...)(scope F delegateOrFp, 
Args args);

What is "run"?


Andrei
Mar 19 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 10:54 AM, Andrei Alexandrescu wrote:

 On 03/18/2011 11:40 PM, dsimcha wrote:

 It should just be private. The fact that it's public is an artifact of
 when I was designing worker-local storage and didn't know how it was
 going to work yet. I never thought to revisit this until now. It really
 isn't useful to client code.


 It could be public and undocumented.


I've already made it private.  I can't see what purpose having it public 
would serve.  The fact that it was public before was **purely** an 
oversight.


 * defaultPoolThreads - should it be a  property?


 Yes. In spirit it's a global variable. It requires some extra
 machinations, though, to be threadsafe, which is why it's not
 implemented as a simple global variable.


 Then it should be a  property. I think ddoc doesn't reflect that, but an
 example could.


Right.  It's always been  property but ddoc doesn't reflect this.  I've 
changed the docs slightly to call it a "property" instead of a 
"function".  It seems like overkill to me to give examples for this, 
though, since it's just a getter and a setter.


 * No example for task().


 ???? Yes there is, for both flavors, though these could admittedly be
 improved. Only the safe version doesn't have an example, and this is
 just a more restricted version of the function pointer case, so it seems
 silly to make a separate example for it.


 Towards the bottom of the document there are overloads of task that
 don't have examples.


You mean TaskPool.task()?  Since these are such slight variations of the 
other overloads, I thought an example would be overkill.  Since people 
less familiar with the library don't think so, though, I've added 
examples that are accordingly slight variations of the examples for the 
other overloads.


 * What is 'run' in the definition of safe task()?


 It's just the run() adapter function. Isn't that obvious?


 I'm referring to this:

 Task!(run,TypeTuple!(F,Args)) task(F, Args...)(scope F delegateOrFp,
 Args args);

 What is "run"?


Ok, I ended up moving the docs for run() directly above the stuff that 
uses it.  run() is described as "Calls a delegate or function pointer 
with args. This is an adapter that makes Task work with delegates, 
function pointers and functors instead of just aliases. It is included 
in the documentation to clarify how this case is handled, but is not 
meant to be used directly by client code."

I know the Higher Principles of Encapsulation say this should be private 
and the relevant overloads should return auto.  I strongly believe, 
though, that being anal about encapsulation of this detail is silly 
since it is so unlikely to change and that exposing it helps to clarify 
what's really going on here.  Encapsulation is good up to a point, but 
sometimes it's just easier to think about things when you know how they 
really work at a concrete level, and this tradeoff needs to be weighted.
Mar 19 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/19/2011 10:28 AM, dsimcha wrote:

 On 3/19/2011 10:54 AM, Andrei Alexandrescu wrote:

 Towards the bottom of the document there are overloads of task that
 don't have examples.


 You mean TaskPool.task()? Since these are such slight variations of the
 other overloads, I thought an example would be overkill. Since people
 less familiar with the library don't think so, though, I've added
 examples that are accordingly slight variations of the examples for the
 other overloads.


A great way to handle bunches of almost-identical overloads is to group 
them together with /// ditto and explain the slight differences in the 
consolidated documentation.

Andrei
Mar 19 2011
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
Ok, thanks again for clarifying **how** the docs could be improved. 
I've implemented the suggestions and generally given the docs a good 
reading over and clean up.  The new docs are at:

http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html

On 3/18/2011 11:29 PM, Andrei Alexandrescu wrote:

 0. Overview and vote

 I think the library delivers the high-level goods (parallel foreach,
 map, reduce) but is a bit fuzzy in the lower level details.

 Documentation hurts understanding of the capabilities of the library and
 essentially is of inadequate quality. Entity documentation and examples
 do little more than give the impression of dispensing with an unpleasant
 chore.

 My vote in favor of acceptance is contingent upon a radical improvement
 in the quality of documentation and examples. Most if not all artifacts
 should be motivated by simple, compelling examples. The introductory
 section must contain a brief and attractive synopsis of the flagship
 capabilities. All terms must be defined before being used and introduced
 in a carefully-chosen order. The relationship between various entities
 should be clarified.

 I've seen the argument that simple and strong examples are difficult to
 find. Though I agree such examples are not easy to come up with, I also
 believe the author of library is in the best position to produce them.

 ================

 1. Library proper:

 * "In the case of non-random access ranges, parallel foreach is still
 usable but buffers lazily to an array..." Wouldn't strided processing
 help? If e.g. 4 threads the first works on 0, 4, 8, ... second works on
 1, 5, 9, ... and so on.

 * Example with squares would be better if double replaced uint, and if a
 more complicated operation (sqrt, log...) were involved.

 * I'm unclear on the tactics used by lazyMap. I'm thinking the obvious
 method should be better: just use one circular buffer. The presence of
 two dependent parameters makes this abstraction difficult to operate with.

 * Same question about asyncBuf. What is wrong with a circular buffer
 filled on one side by threads and on the consumed from the other by the
 client? I can think of a couple of answers but it would be great if they
 were part of the documentation.

 * Why not make workerIndex a ulong and be done with it?

 * Is stop() really trusted or just unsafe? If it's forcibly killing
 threads then its unsafe.

 * uint size() should be size_t for conformity.

 * defaultPoolThreads - should it be a  property?

 * I don't understand what Task is supposed to do. It is circularly
 defined: "A struct that encapsulates the information about a task,
 including its current status, what pool it was submitted to, and its
 arguments." OK, but what's a task? Could a task be used outside a task
 pool, and if so to what effect(s)?

 * If LazyMap is only necessary as the result of lazyMap, could that
 become a local type inside lazyMap?


 2. Documentation:

 * Documentation unacceptable. It lacks precision and uses terms before
 defining them. For example: "This class encapsulates a task queue and a
 set of worker threads" comes before the notions of "task queue" and
 "worker thread" are defined. Clearly there is an intuition of what those
 are supposed to mean, but in practice each library lays down some fairly
 detailed definition of such.

 * "Note: Initializing a pool with zero threads (as would happen in the
 case of a single-core CPU) is well-tested and does work." The absence of
 a bug should not be advertised in so many words. Simpler: "Note:
 Single-CPU machines will operate transparently with zero-sized pools."

 * "Allows for custom pool size." I have no idea what pool size means.

 * "// Do something interesting." Worst example ever. You are the creator
 of the library. If _you_ can't find a brief compelling example, who could?

 * "Immediately after the range argument, an optional block size argument
 may be provided. If none is provided, the default block size is used. An
 optional buffer for returining the results may be provided as the last
 argument. If one is not provided, one will be automatically allocated.
 If one is provided, it must be the same length as the range." An example
 should be inserted after each of these sentences.

 * "// Do something expensive with line." Better you do something
 expensive with line.

 * "This is not the same thing as commutativity." I think this is obvious
 enough to be left out. The example of matrices (associative but not
 commutative) is nice though.

 * "immutable n = 1000000000;" -> use underscores

 * Would be great if the documentation examples included some rough
 experimental results, e.g. "3.8 times faster on a 4-core machine than
 the equivalent serial loop".

 * No example for workerIndex and why it's useful.

 * Is LocalWorker better than WorkerLocal? No, because it's not the
 worker that's local, it's the storage - which is missing from the name!
 WorkerLocalStorage? Also replace "create" with "make" or drop it
 entirely. The example doesn't tell me how I can use bufs. I suspect
 workerIndex has something to do with it but the example fails to divulge
 that relationship.

 * No example for join(), which is quite a central primitive.

 * No example for put(), which would be interesting to see.

 * No example for task().

 * No example for run().

 * The example for Task uses myFuture without defining it. In case Task
 defines the promise/future idiom, the documentation misses a terrific
 opportunity of clarifying that.

 * What is 'run' in the definition of safe task()?

 * Why is AsyncBuf's doc far away from the function returning it? Same
 about WorkerLocal.


 Andrei
Mar 19 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/19/2011 02:32 AM, dsimcha wrote:

 Ok, thanks again for clarifying **how** the docs could be improved. I've
 implemented the suggestions and generally given the docs a good reading
 over and clean up. The new docs are at:

 http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html


* When using "parallelism" as a common noun, prefix is with a '_' so 
ddoc doesn't underline it.

* "Most of this module completely subverts..." Vague characterizations 
("most", "completely", "some") don't belong in a technical 
documentation. (For example there's either subversion going on or there 
isn't.) Also, std.concurrency and std.parallelism address different 
needs so there's little competition between them. Better: "Unless 
explicitly marked as $(D  trusted) or $(D  safe), artifacts in this 
module are not provably memory-safe and cannot be used with SafeD. If 
used as documented, memory safety is guaranteed."

* Speaking of std.concurrency vs. std.parallelism, the first paragraph 
might be something like: "This module implements high-level primitives 
for shared memory SMP parallelism. These include parallel foreach, 
parallel reduce, parallel eager map, pipelining and future/promise 
parallelism primitives. $(D std._parallelism) is best recommended when 
the same operation is to be executed in parallel over different data. 
For communication between arbitrary threads, see $(D std.concurrency)."

* Still no synopsis example that illustrates in a catchy way the most 
attractive artifacts.

* "After creation, Task objects are submitted to a TaskPool for 
execution." I understand it's possible to use Task straight as a 
promise/future, so s/are/may be/. Also it is my understanding that 
TaskPool efficiently adapts the concrete number of CPUs to an arbitrary 
number of tasks. If that's the case, it's worth mentioning.

* "A call to workWait(), yieldWait(), or spinWait() can be used to 
retrive the return value after the function is finished executing." As 
an aside, a spell checking step would be great ("retrieve") - just put 
the text in an editor with spellchecking. I think what this means is: 
"The methods workWait(), yieldWait(), or spinWait() make sure that the 
function finishes execution and then return its result to the initiating 
thread. Each uses a different waiting strategy as detailed below."

* "If a Task has been submitted to a TaskPool instance, is being stored 
in a stack frame, and has not yet finished, the destructor for this 
struct will automatically call yieldWait() so that the task can finish 
and the stack frame can be destroyed safely." At this point in the doc 
the reader doesn't understand that at all because TaskPool has not been 
seen yet. The reader gets worried that she'll be essentially serializing 
the entire process by mistake. Either move this explanation down or 
provide an example.

* "Function results are returned from yieldWait() and friends by ref." 
Someone coming from C++ may be thrown off by this sudden casual use of 
"friends" and think there's a notion of frienship by reference in D. 
Better: "The forcing methods yieldWait(), workWait(), and spinWait() 
return the result by reference."

* Speaking of which, I'd replace "Wait" with "Force". Right now the 
nomenclature is far removed from futures and promises.

* Is done() a property?

* The example that reads two files at the same time should NOT use 
taskPool. It's just one task, why would the pool ever be needed? If you 
also provided an example that reads n files in memory at the same time 
using a pool, that would illustrate nicely why you need it. If a Task 
can't be launched without being put in a pool, there should be a 
possibility to do so. At my work we have a simple function called 
callInNewThread that does what's needed to launch a function in a new 
thread.

* The note below that example gets me thinking: it is an artificial 
limitation to force users of Task to worry about scope and such. One 
should be able to create a Future object (Task I think in your 
terminology), pass it around like a normal value, and ultimately force 
it. This is the case for all other languages that implement futures. I 
suspect the "scope" parameter associated with the delegate a couple of 
definitions below plays a role here, but I think we need to work for 
providing the smoothest interface possible (possibly prompting 
improvements in the language along the way).

* I'm not sure how to interpret the docs for

ReturnType!(F) run(F, Args...)(F fpOrDelegate, ref Args args);

So it's documented but I'm not supposed to care. Why not just remove? 
Surely there must be higher-level examples that clarify that I can use 
delegates etc.

* The examples have code at top-level. That's fine for short snippets 
but not when using import etc. I recommend putting the code inside 
unittests or function bodies for such cases.

* "If you want to escape the Task object from the function in which it 
was created or prefer to heap allocate and automatically submit to the 
pool, see TaskPool.task()." I'm uncomfortable that I need to remember a 
subtle distinction of the same primitive name ("task") depending on 
membership in a TaskPool or not, which is a tenuous relationship to 
remember. How about "scopedTask()" vs. "task()"? Also, it's worth asking 
ourselves what's the relative overhead of closure allocation vs. task 
switching etc. Maybe we get to simplify things a lot at a small cost in 
efficiency.

* As I mentioned, in the definition:

Task!(run,TypeTuple!(F,Args)) task(F, Args...)(F fun, Args args);

I can't tell what "run" is.

* osReportedNcpu - a case of naming convention gone wild... how about 
totalCPUs or reportedCPUs.

* "A goto from inside the parallel foreach loop to a label outside the 
loop will result in undefined behavior." Would this be a bug in dmd?

* I would group these two together:

ParallelForeach!(R) parallel(R)(R range, size_t workUnitSize);
ParallelForeach!(R) parallel(R)(R range);

Just put a /// ditto for the second, use only one code snippet that 
illustrates two foreach loops, one with the explicit parameter and one 
without. In fact swap the two - most of the time people will use the one 
with the default work unit size. At best don't specify 512 because later 
on you may come with better algorithm to determine the optimal block size.

* "workUnitSize: The number of elements to evaluate in a single Task. 
Must be less than or equal to bufSize, and in practice should be a 
fraction of bufSize such that all worker threads can be used." Then why 
not specify a different parameter such a multiplier or something? The 
dependence between bufSize and worUnitSize is a sign that these two 
should be improved. If you have good reasons that the user must have the 
parameters in this form, give an example substantiating that.

* "auto myMax = taskPool.reduce!"a + b * b"(myArr);" This is not 
computing anything meaningful. To compute the sum of squares, you need 
to give the seed 0.0.

* Again: speed of e.g. parallel min/max vs. serial, pi computation etc. 
on a usual machine?

* The join example is fine, but the repetitive code suggests that loops 
should be better:

import std.file;

void main() {
     auto pool = new TaskPool();
     foreach (filename; ["foo.txt", "bar.txt", "baz.txt"]) {
       pool.put(task!read(filename));
     }

     // Call join() to guarantee that all tasks are done running, the worker
     // threads have terminated and that the results of all of the tasks can
     // be accessed without any synchronization primitives.
     pool.join();

     ubyte[][] data; // void[], meh
     // Use spinWait() since the results are guaranteed to have been 
computed
     // and spinWait() is the cheapest of the wait functions.
     foreach (task; pool.howDoIEnumerateTasks()) {
         data ~= task1.spinWait();
     }


Andrei
Mar 19 2011
next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-19 12:03:51 -0400, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 * "Most of this module completely subverts..." Vague characterizations 
 ("most", "completely", "some") don't belong in a technical 
 documentation. (For example there's either subversion going on or there 
 isn't.) Also, std.concurrency and std.parallelism address different 
 needs so there's little competition between them. Better: "Unless 
 explicitly marked as $(D  trusted) or $(D  safe), artifacts in this 
 module are not provably memory-safe and cannot be used with SafeD. If 
 used as documented, memory safety is guaranteed."


Actually, I think this is a bad description of what it subverts. What 
it subverts isn't the memory-safety that SafeD provides, but the safety 
against low-level races that even unsafe D protects against unless you 
cast shared away. For instance:

	void main() {
		int sum = 0;
		foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
			sum += value;
		}
		writeln(sum);
	}

The "+=" would need to be an atomic operation to avoid low-level races.

I think that ParallelForeach's opApply should only accept a shared 
delegate. I define shared delegate as a delegate that does not 
reference any non-shared variables of its outer scope. The problem is 
that DMD currently doesn't know how to determine whether a delegate 
literal is shared or not, thus a delegate literal is never shared and 
if ParallelForeach's opApply asked a shared delegate as it should it 
would just not work. Fix DMD to create shared delegate literals where 
appropriate and everything can be guarantied race-free.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 19 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 1:09 PM, Michel Fortin wrote:

 On 2011-03-19 12:03:51 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> said:


 * "Most of this module completely subverts..." Vague characterizations
 ("most", "completely", "some") don't belong in a technical
 documentation. (For example there's either subversion going on or
 there isn't.) Also, std.concurrency and std.parallelism address
 different needs so there's little competition between them. Better:
 "Unless explicitly marked as $(D  trusted) or $(D  safe), artifacts in
 this module are not provably memory-safe and cannot be used with
 SafeD. If used as documented, memory safety is guaranteed."


 Actually, I think this is a bad description of what it subverts. What it
 subverts isn't the memory-safety that SafeD provides, but the safety
 against low-level races that even unsafe D protects against unless you
 cast shared away. For instance:

 void main() {
 int sum = 0;
 foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 sum += value;
 }
 writeln(sum);
 }

 The "+=" would need to be an atomic operation to avoid low-level races.

 I think that ParallelForeach's opApply should only accept a shared
 delegate. I define shared delegate as a delegate that does not reference
 any non-shared variables of its outer scope. The problem is that DMD
 currently doesn't know how to determine whether a delegate literal is
 shared or not, thus a delegate literal is never shared and if
 ParallelForeach's opApply asked a shared delegate as it should it would
 just not work. Fix DMD to create shared delegate literals where
 appropriate and everything can be guarantied race-free.


If you want pedal-to-metal parallelism without insane levels of 
verbosity, you can't have these safety features.  I thought long and 
hard about this issue before submitting this lib for review and 
concluded that any solution would make std.parallelism so slow, so 
limited and/or such a PITA to use that I'd rather it just punt these 
issues to the programmer.  In practice, parallel foreach is used with 
very small, performance-critical snippets that are fairly easy to reason 
about even without any language-level race safety.  This is a 
fundamental design decision that will not be changing.  If it's 
unacceptable then:

1.  I give up.

2.  I wish someone had told me earlier.
Mar 19 2011
next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-19 13:20:00 -0400, dsimcha <dsimcha yahoo.com> said:


 On 3/19/2011 1:09 PM, Michel Fortin wrote:

 For instance:
 
 void main() {
 int sum = 0;
 foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 sum += value;
 }
 writeln(sum);
 }
 
 The "+=" would need to be an atomic operation to avoid low-level races.
 
 I think that ParallelForeach's opApply should only accept a shared
 delegate. I define shared delegate as a delegate that does not reference
 any non-shared variables of its outer scope. The problem is that DMD
 currently doesn't know how to determine whether a delegate literal is
 shared or not, thus a delegate literal is never shared and if
 ParallelForeach's opApply asked a shared delegate as it should it would
 just not work. Fix DMD to create shared delegate literals where
 appropriate and everything can be guarantied race-free.


 
 If you want pedal-to-metal parallelism without insane levels of 
 verbosity, you can't have these safety features.


I'm not sure where my proposal asks for more verbosity or less 
performance. All I can see is a few less casts in std.parallelism and 
that it'd disallow the case in my example above that is totally wrong. 
Either you're interpreting it wrong or there are things I haven't 
thought about (and I'd be happy to know about them).

But by looking at all the examples in the documentation, I cannot find 
one that would need to be changed... well, except the one I'll discuss 
below.



 I thought long and hard about this issue before submitting this lib for 
 review and concluded that any solution would make std.parallelism so 
 slow, so limited and/or such a PITA to use that I'd rather it just punt 
 these issues to the programmer.  In practice, parallel foreach is used 
 with very small, performance-critical snippets that are fairly easy to 
 reason about even without any language-level race safety.


I'm not too convinced about the "I know what I'm doing" argument when I 
look at this example from asyncBuf's documentation:

    auto lines = File("foo.txt").byLine();
    auto duped = map!"a.idup"(lines);  // Necessary b/c byLine() 
recycles buffer

    // Fetch more lines in the background while we process the lines already
    // read into memory into a matrix of doubles.
    double[][] matrix;
    auto asyncReader = taskPool.asyncBuf(duped);

    foreach(line; asyncReader) {
        auto ls = line.split("\t");
        matrix ~= to!(double[])(ls);
    }

Look at the last line of the foreach. You are appending to a non-shared 
array from many different threads. How is that not a race condition?

With my proposal, the compiler would have caught that because opApply 
would want the foreach body to be  a shared delegate, and 
reading/writing to non-shared variable "matrix" in the outer scope from 
a shared delegate literal would be an error.

I'm not too sure how hard it'd be to do that in the compiler, but I 
think it's the right thing to do. Once the compiler can do this we can 
have safety; until that time I'd agree to see std.parallelism stay 
unsafe.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 19 2011
next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-19 14:14:51 -0400, Michel Fortin <michel.fortin michelf.com> said:


 I'm not too convinced about the "I know what I'm doing" argument when I 
 look at this example from asyncBuf's documentation:
 
     auto lines = File("foo.txt").byLine();
     auto duped = map!"a.idup"(lines);  // Necessary b/c byLine() 
 recycles buffer
 
     // Fetch more lines in the background while we process the lines already
     // read into memory into a matrix of doubles.
     double[][] matrix;
     auto asyncReader = taskPool.asyncBuf(duped);
 
     foreach(line; asyncReader) {
         auto ls = line.split("\t");
         matrix ~= to!(double[])(ls);
     }
 
 Look at the last line of the foreach. You are appending to a non-shared 
 array from many different threads. How is that not a race condition?


... or maybe I just totally misunderstood asyncBuf. Rereading the 
documentation I'm under the impression I'd have to write this to get 
what I expected:

	foreach (line; parallel(asyncReader))
		...

And that would cause a race condition. If that's the case, the example 
is fine. Sorry for the misunderstanding.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 19 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 2:25 PM, Michel Fortin wrote:

 On 2011-03-19 14:14:51 -0400, Michel Fortin <michel.fortin michelf.com>
 said:


 I'm not too convinced about the "I know what I'm doing" argument when
 I look at this example from asyncBuf's documentation:

 auto lines = File("foo.txt").byLine();
 auto duped = map!"a.idup"(lines); // Necessary b/c byLine() recycles
 buffer

 // Fetch more lines in the background while we process the lines already
 // read into memory into a matrix of doubles.
 double[][] matrix;
 auto asyncReader = taskPool.asyncBuf(duped);

 foreach(line; asyncReader) {
 auto ls = line.split("\t");
 matrix ~= to!(double[])(ls);
 }

 Look at the last line of the foreach. You are appending to a
 non-shared array from many different threads. How is that not a race
 condition?


 .... or maybe I just totally misunderstood asyncBuf. Rereading the
 documentation I'm under the impression I'd have to write this to get
 what I expected:

 foreach (line; parallel(asyncReader))
 ...

 And that would cause a race condition. If that's the case, the example
 is fine. Sorry for the misunderstanding.


Right.  And this is pretty obviously a race.  The other example (without 
the parallel) is completely safe.
Mar 19 2011
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 2:14 PM, Michel Fortin wrote:

 On 2011-03-19 13:20:00 -0400, dsimcha <dsimcha yahoo.com> said:


 On 3/19/2011 1:09 PM, Michel Fortin wrote:

 For instance:

 void main() {
 int sum = 0;
 foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 sum += value;
 }
 writeln(sum);
 }

 The "+=" would need to be an atomic operation to avoid low-level races.

 I think that ParallelForeach's opApply should only accept a shared
 delegate. I define shared delegate as a delegate that does not reference
 any non-shared variables of its outer scope. The problem is that DMD
 currently doesn't know how to determine whether a delegate literal is
 shared or not, thus a delegate literal is never shared and if
 ParallelForeach's opApply asked a shared delegate as it should it would
 just not work. Fix DMD to create shared delegate literals where
 appropriate and everything can be guarantied race-free.


 If you want pedal-to-metal parallelism without insane levels of
 verbosity, you can't have these safety features.


 I'm not sure where my proposal asks for more verbosity or less
 performance. All I can see is a few less casts in std.parallelism and
 that it'd disallow the case in my example above that is totally wrong.
 Either you're interpreting it wrong or there are things I haven't
 thought about (and I'd be happy to know about them).

 But by looking at all the examples in the documentation, I cannot find
 one that would need to be changed... well, except the one I'll discuss
 below.


Ok, I've had some time to think about this.  The following example is 
safe, but wouldn't work if I understand correctly what you're proposing:

auto logs = new double[1_000_000];

foreach(i, ref elem; taskPool.parallel(logs)) {
     elem = log(i + 1.0);
}

The problem is that you're writing to the same array from multiple 
threads, which the compiler would interpret as writing to the same 
variable.  However, you can guarantee that no two threads ever write to 
the same element, so it's safe.

Note:  I'm aware of the false sharing issue when writing to adjacent 
memory addresses.  However, when writing to an array this big it occurs 
to a negligible extent.  If you were using a smaller array, then either 
the loop body would be so expensive that the cost of false sharing would 
be negligible, or the whole loop would be too cheap to be worth 
parallelizing.

I'm also aware that word tearing is a concern on some architectures, 
though not x86.  IMHO std.parallelism and its documentation should not 
be pedantic about portability to architectures that a D compiler doesn't 
even exist for yet.

Also, your example can be trivially modified to be safe.

void main() {
     int sum = 0;
     foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
          synchronized sum += value;
      }
      writeln(sum);
}

In this case that kills all parallelism, but in more realistic cases I 
use this pattern often.  I find it very common to have an expensive loop 
body can be performed in parallel, except for a tiny portion that must 
update a shared data structure.  I'm aware that it might be possible, in 
theory, to write this more formally using reduce() or something.  However:

1.  If the portion of the loop that deals with shared data is very small 
(and therefore the serialization caused by the synchronized block is 
negligible), it's often more efficient to only keep one data structure 
in memory and update it concurrently, rather than use stronger isolation 
between threads like reduce() does, and have to maintain one data 
structure for each thread.

2.  In my experience synchronizing on a small portion of the loop body 
works very well in practice.  My general philosophy is that, in a 
library like this, dangerous but useful constructs must be supported and 
treated as innocent until proven guilty, not the other way round.
Mar 20 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-20 11:42:04 -0400, dsimcha <dsimcha yahoo.com> said:


 On 3/19/2011 2:14 PM, Michel Fortin wrote:

 On 2011-03-19 13:20:00 -0400, dsimcha <dsimcha yahoo.com> said:
 

 On 3/19/2011 1:09 PM, Michel Fortin wrote:

 For instance:
 
 void main() {
 int sum = 0;
 foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 sum += value;
 }
 writeln(sum);
 }
 
 The "+=" would need to be an atomic operation to avoid low-level races.
 
 I think that ParallelForeach's opApply should only accept a shared
 delegate. I define shared delegate as a delegate that does not reference
 any non-shared variables of its outer scope. The problem is that DMD
 currently doesn't know how to determine whether a delegate literal is
 shared or not, thus a delegate literal is never shared and if
 ParallelForeach's opApply asked a shared delegate as it should it would
 just not work. Fix DMD to create shared delegate literals where
 appropriate and everything can be guarantied race-free.


 
 If you want pedal-to-metal parallelism without insane levels of
 verbosity, you can't have these safety features.


 
 I'm not sure where my proposal asks for more verbosity or less
 performance. All I can see is a few less casts in std.parallelism and
 that it'd disallow the case in my example above that is totally wrong.
 Either you're interpreting it wrong or there are things I haven't
 thought about (and I'd be happy to know about them).
 
 But by looking at all the examples in the documentation, I cannot find
 one that would need to be changed... well, except the one I'll discuss
 below.
 


 
 Ok, I've had some time to think about this.  The following example is 
 safe, but wouldn't work if I understand correctly what you're proposing:
 
 auto logs = new double[1_000_000];
 
 foreach(i, ref elem; taskPool.parallel(logs)) {
      elem = log(i + 1.0);
 }
 
 The problem is that you're writing to the same array from multiple 
 threads, which the compiler would interpret as writing to the same 
 variable.  However, you can guarantee that no two threads ever write to 
 the same element, so it's safe.


I don't see a problem with the above. The array elements you modify are 
passed through parallel's opApply which can check easily whether it's 
safe or not to pass them by ref to different threads (by checking the 
element's size) and allow or disallow the operation accordingly.

It could even do a clever trick to make it safe to pass things such as 
elements of array of bytes by ref (by coalescing loop iterations for 
all bytes sharing the same word into one task). That might not work for 
ranges which are not arrays however.

That said, feel free to suggest more problematic examples.



 Note:  I'm aware of the false sharing issue when writing to adjacent 
 memory addresses.  However, when writing to an array this big it occurs 
 to a negligible extent.  If you were using a smaller array, then either 
 the loop body would be so expensive that the cost of false sharing 
 would be negligible, or the whole loop would be too cheap to be worth 
 parallelizing.
 
 I'm also aware that word tearing is a concern on some architectures, 
 though not x86.  IMHO std.parallelism and its documentation should not 
 be pedantic about portability to architectures that a D compiler 
 doesn't even exist for yet.


No question there.



 Also, your example can be trivially modified to be safe.
 
 void main() {
      int sum = 0;
      foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
           synchronized sum += value;
       }
       writeln(sum);
 }
 
 In this case that kills all parallelism, but in more realistic cases I 
 use this pattern often.  I find it very common to have an expensive 
 loop body can be performed in parallel, except for a tiny portion that 
 must update a shared data structure.  I'm aware that it might be 
 possible, in theory, to write this more formally using reduce() or 
 something.  However:
 
 1.  If the portion of the loop that deals with shared data is very 
 small (and therefore the serialization caused by the synchronized block 
 is negligible), it's often more efficient to only keep one data 
 structure in memory and update it concurrently, rather than use 
 stronger isolation between threads like reduce() does, and have to 
 maintain one data structure for each thread.
 
 2.  In my experience synchronizing on a small portion of the loop body 
 works very well in practice.  My general philosophy is that, in a 
 library like this, dangerous but useful constructs must be supported 
 and treated as innocent until proven guilty, not the other way round.


Your second example is not really a good justification of anything. 
I'll refer you to how synchronized classes work. It was decided that 
synchronized in a class protects everything that is directly stored in 
the class. Anything behind an indirection is considered shared by the 
compiler. The implication of this is that if you have an array or a 
pointer to something that you want semantically to be protected by the 
class's mutex, you have to cast things to unshared. It was decided that 
things should be safe against low-level races first, and convenience 
was relegated as a secondary concern. I don't like it very much, but 
that's what was decided and written in TDPL.

Now we're in the exact same situation (except that no classes are 
involved) and you're proposing that for this case we make convenience 
prime over low-level race safety? To me this would be an utter lack of 
coherency in the design of D's "synchronized" feature to go that route.

For the case above, wouldn't it be better to use an atomic add instead 
of a synchronized block? In this case you can make "sum" shared and 
have the type system check that everything is safe (using my proposed 
rules). And if your data structure is bigger, likely it'll be a 
synchronized class and you won't have to resort to bypass type-system 
safeties inside your loop (although you might have to inside your 
synchronized class, but that's another matter).

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 20 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/20/2011 10:44 PM, Michel Fortin wrote:

 I don't see a problem with the above. The array elements you modify are
 passed through parallel's opApply which can check easily whether it's
 safe or not to pass them by ref to different threads (by checking the
 element's size) and allow or disallow the operation accordingly.

 It could even do a clever trick to make it safe to pass things such as
 elements of array of bytes by ref (by coalescing loop iterations for all
 bytes sharing the same word into one task). That might not work for
 ranges which are not arrays however.

 That said, feel free to suggest more problematic examples.


Ok, I completely agree in principle, though I question whether it's 
worth actually implementing something like this, especially until we get 
some kind of support for shared delegates.


 Also, your example can be trivially modified to be safe.

 void main() {
 int sum = 0;
 foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 synchronized sum += value;
 }
 writeln(sum);
 }

 In this case that kills all parallelism, but in more realistic cases I
 use this pattern often. I find it very common to have an expensive
 loop body can be performed in parallel, except for a tiny portion that
 must update a shared data structure. I'm aware that it might be
 possible, in theory, to write this more formally using reduce() or
 something. However:

 1. If the portion of the loop that deals with shared data is very
 small (and therefore the serialization caused by the synchronized
 block is negligible), it's often more efficient to only keep one data
 structure in memory and update it concurrently, rather than use
 stronger isolation between threads like reduce() does, and have to
 maintain one data structure for each thread.

 2. In my experience synchronizing on a small portion of the loop body
 works very well in practice. My general philosophy is that, in a
 library like this, dangerous but useful constructs must be supported
 and treated as innocent until proven guilty, not the other way round.


 Your second example is not really a good justification of anything. I'll
 refer you to how synchronized classes work. It was decided that
 synchronized in a class protects everything that is directly stored in
 the class. Anything behind an indirection is considered shared by the
 compiler. The implication of this is that if you have an array or a
 pointer to something that you want semantically to be protected by the
 class's mutex, you have to cast things to unshared. It was decided that
 things should be safe against low-level races first, and convenience was
 relegated as a secondary concern. I don't like it very much, but that's
 what was decided and written in TDPL.


I'd go a little further.  If the guarantees that shared was supposed to 
provide are strong, i.e. apply no matter what threading module is used, 
then I utterly despise it.  It's one of the worst decisions made in the 
design of D.  Making things pedantically strict, so that the type system 
gets in the way more than it helps, encourages the user to reflexively 
circumvent the type system without thinking hard about doing this, thus 
defeating its purpose.  (The alternative of always complying with what 
the type system "expects" you to do is too inflexible to even be worth 
considering.)  Type systems should err on the side of accepting a 
superset of what's correct and treating code as innocent until proven 
guilty, not the other way around.  I still believe this even if some of 
the bugs it could be letting pass through might be very difficult to 
debug.  See the discussion we had a few weeks ago about implicit integer 
casting and porting code to 64.

My excuse for std.parallelism is that it's pedal-to-metal parallelism, 
so it's more acceptable for it to be dangerous than general case 
concurrency.  IMHO when you use the non- safe parts of std.parallelism 
(i.e. most of the library), that's equivalent to casting away shared in 
a whole bunch of places.  Typing "import std.parallelism;" in a 
non- safe module is an explicit enough step here.

The guarantee is still preserved that, if you only use std.concurrency 
(D's flagship "safe" concurrency module) for multithreading and don't 
cast away shared, there can be no low level data races.  IMHO this is 
still a substantial accomplishment in that there exists a way to do 
safe, statically checkable concurrency in D, even if it's not the 
**only** way concurrency can be done.  BTW, core.thread can also be used 
to get around D's type system, not just std.parallelism.  If you want to 
check that only safe concurrency is used, importing std.parallelism and 
core.thread can be grepped just as easily as casting away shared.

If, on the other hand, the guarantees of shared are supposed to be weak 
in that they only apply to programs where only std.concurrency is used 
for multithreading, then I think strictness is the right thing to do. 
The whole point of std.concurrency is to give strong guarantees, but if 
you prefer more dangerous but more flexible multithreading, other 
paradigms should be readily available.


 Now we're in the exact same situation (except that no classes are
 involved) and you're proposing that for this case we make convenience
 prime over low-level race safety? To me this would be an utter lack of
 coherency in the design of D's "synchronized" feature to go that route.

 For the case above, wouldn't it be better to use an atomic add instead
 of a synchronized block?


Yes.  I've used this pattern in much more complicated cases, though, 
where atomic wouldn't cut it.


 In this case you can make "sum" shared and have
 the type system check that everything is safe (using my proposed rules).
 And if your data structure is bigger, likely it'll be a synchronized
 class and you won't have to resort to bypass type-system safeties inside
 your loop (although you might have to inside your synchronized class,
 but that's another matter).


I'm **still** totally confused about how shared is supposed to work, 
because I don't have a fully debugged/implemented implementation or good 
examples of stuff written in this paradigm to play around with.  TDPL 
helps to some degree, but for me it's a lot easier to understand 
something by actually trying to use it.
Mar 20 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-20 23:21:49 -0400, dsimcha <dsimcha yahoo.com> said:


 On 3/20/2011 10:44 PM, Michel Fortin wrote:

 
 I don't see a problem with the above. The array elements you modify are
 passed through parallel's opApply which can check easily whether it's
 safe or not to pass them by ref to different threads (by checking the
 element's size) and allow or disallow the operation accordingly.
 
 It could even do a clever trick to make it safe to pass things such as
 elements of array of bytes by ref (by coalescing loop iterations for all
 bytes sharing the same word into one task). That might not work for
 ranges which are not arrays however.
 
 That said, feel free to suggest more problematic examples.


 
 Ok, I completely agree in principle, though I question whether it's 
 worth actually implementing something like this, especially until we 
 get some kind of support for shared delegates.


Well, it'll work irrespective of whether shared delegates are used or 
not. I think you could add a compile-time check that the array element 
size is a multiple of the word size when the element is passed by ref 
in the loop and leave the clever trick as a possible future 
improvements. Would that work?



 Also, your example can be trivially modified to be safe.
 
 void main() {
 int sum = 0;
 foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 synchronized sum += value;
 }
 writeln(sum);
 }
 
 In this case that kills all parallelism, but in more realistic cases I
 use this pattern often. I find it very common to have an expensive
 loop body can be performed in parallel, except for a tiny portion that
 must update a shared data structure. I'm aware that it might be
 possible, in theory, to write this more formally using reduce() or
 something. However:
 
 1. If the portion of the loop that deals with shared data is very
 small (and therefore the serialization caused by the synchronized
 block is negligible), it's often more efficient to only keep one data
 structure in memory and update it concurrently, rather than use
 stronger isolation between threads like reduce() does, and have to
 maintain one data structure for each thread.
 
 2. In my experience synchronizing on a small portion of the loop body
 works very well in practice. My general philosophy is that, in a
 library like this, dangerous but useful constructs must be supported
 and treated as innocent until proven guilty, not the other way round.


 
 Your second example is not really a good justification of anything. I'll
 refer you to how synchronized classes work. It was decided that
 synchronized in a class protects everything that is directly stored in
 the class. Anything behind an indirection is considered shared by the
 compiler. The implication of this is that if you have an array or a
 pointer to something that you want semantically to be protected by the
 class's mutex, you have to cast things to unshared. It was decided that
 things should be safe against low-level races first, and convenience was
 relegated as a secondary concern. I don't like it very much, but that's
 what was decided and written in TDPL.


 
 I'd go a little further.  If the guarantees that shared was supposed to 
 provide are strong, i.e. apply no matter what threading module is used, 
 then I utterly despise it.  It's one of the worst decisions made in the 
 design of D.  Making things pedantically strict, so that the type 
 system gets in the way more than it helps, encourages the user to 
 reflexively circumvent the type system without thinking hard about 
 doing this, thus defeating its purpose.  (The alternative of always 
 complying with what the type system "expects" you to do is too 
 inflexible to even be worth considering.)  Type systems should err on 
 the side of accepting a superset of what's correct and treating code as 
 innocent until proven guilty, not the other way around.  I still 
 believe this even if some of the bugs it could be letting pass through 
 might be very difficult to debug.  See the discussion we had a few 
 weeks ago about implicit integer casting and porting code to 64.


I agree with you that this is a serious problem. I think part of why it 
hasn't been talked much yet is that nobody is currently using D2 
seriously for multithreaded stuff at this time (apart from you I 
guess), so we're missing experience with it. Andrei seems to think it's 
fine to required casts as soon as you need to protect something beyond 
an indirection inside synchronized classes, with the mitigation measure 
that you can make classes share their mutex (not implemented yet I 
think) so if the indirection leads to a class it is less of a problem. 
Personally, I don't.



 My excuse for std.parallelism is that it's pedal-to-metal parallelism, 
 so it's more acceptable for it to be dangerous than general case 
 concurrency.  IMHO when you use the non- safe parts of std.parallelism 
 (i.e. most of the library), that's equivalent to casting away shared in 
 a whole bunch of places.  Typing "import std.parallelism;" in a 
 non- safe module is an explicit enough step here.


I still think this "pedal-to-metal" qualification needs to be 
justified. Not having shared delegates in the language seems like an 
appropriate justification to me. Wanting to bypass casts you normally 
have to do around synchronized as the sole reason seems like a bad 
justification to me.

It's not that I like how synchronized works, it's just that I think it 
should work the same everywhere.



 The guarantee is still preserved that, if you only use std.concurrency 
 (D's flagship "safe" concurrency module) for multithreading and don't 
 cast away shared, there can be no low level data races. IMHO this is 
 still a substantial accomplishment in that there exists a way to do 
 safe, statically checkable concurrency in D, even if it's not the 
 **only** way concurrency can be done.  BTW, core.thread can also be 
 used to get around D's type system, not just std.parallelism.  If you 
 want to check that only safe concurrency is used, importing 
 std.parallelism and core.thread can be grepped just as easily as 
 casting away shared.


Unless I'm mistaken, the only thing that bypasses race-safety in 
core.thread is the Thread constructor that takes a delegate. Which 
means it could easily be made race-safe by making that delegate 
parameter shared (once shared delegates are implemented).



 If, on the other hand, the guarantees of shared are supposed to be weak 
 in that they only apply to programs where only std.concurrency is used 
 for multithreading, then I think strictness is the right thing to do. 
 The whole point of std.concurrency is to give strong guarantees, but if 
 you prefer more dangerous but more flexible multithreading, other 
 paradigms should be readily available.


I think the language as a whole is designed to have strong guaranties, 
otherwise synchronized classes wouldn't require out-of-guaranty casts 
at every indirection.

I'm not too pleased with the way synchronized classes are supposed to 
work, nor am I too pleased with how it impacts the rest of the 
language. But if this is a problem (and I think it is), it ought to be 
fixed globally, not by shutting down safeties in every module dealing 
with multithreading that isn't std.concurrency.



 I'm **still** totally confused about how shared is supposed to work, 
 because I don't have a fully debugged/implemented implementation or 
 good examples of stuff written in this paradigm to play around with.


I think nobody have played much with the paradigm at this point, or 
we'd have heard some feedback. Well, actually we have your feedback 
which seem to indicate that it's better to shut off safeties than to 
play nice with them.

 - - -

Quoting Andrei, February 4 of 2010 in "there is no escape" on the 
dmd-concurrency mailing list:


 As we already knew, shared/synchronized limit quite drastically the 
 range of lock-based designs without casts. Fortunately, using a class 
 reference member inside a synchronized object will be possible 
 because... well I'll explain in the text.
 
 I continue to believe this is the right bet to make, but I expect push 
 back from experienced lock-based programmers.


Now is the beginning of that push back, I guess.


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 21 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/21/2011 8:37 AM, Michel Fortin wrote:

 Well, it'll work irrespective of whether shared delegates are used or
 not. I think you could add a compile-time check that the array element
 size is a multiple of the word size when the element is passed by ref in
 the loop and leave the clever trick as a possible future improvements.
 Would that work?


On second thought, no, but for practical, not theoretical reasons:  One, 
you can't introspect whether a foreach loop is using a ref or a value 
parameter.  This is an issue with how opApply works.  Two, AFAIK there's 
no way to get the native word size.


 I'd go a little further. If the guarantees that shared was supposed to
 provide are strong, i.e. apply no matter what threading module is
 used, then I utterly despise it. It's one of the worst decisions made
 in the design of D. Making things pedantically strict, so that the
 type system gets in the way more than it helps, encourages the user to
 reflexively circumvent the type system without thinking hard about
 doing this, thus defeating its purpose. (The alternative of always
 complying with what the type system "expects" you to do is too
 inflexible to even be worth considering.) Type systems should err on
 the side of accepting a superset of what's correct and treating code
 as innocent until proven guilty, not the other way around. I still
 believe this even if some of the bugs it could be letting pass through
 might be very difficult to debug. See the discussion we had a few
 weeks ago about implicit integer casting and porting code to 64.


 I agree with you that this is a serious problem. I think part of why it
 hasn't been talked much yet is that nobody is currently using D2
 seriously for multithreaded stuff at this time (apart from you I guess),
 so we're missing experience with it. Andrei seems to think it's fine to
 required casts as soon as you need to protect something beyond an
 indirection inside synchronized classes, with the mitigation measure
 that you can make classes share their mutex (not implemented yet I
 think) so if the indirection leads to a class it is less of a problem.
 Personally, I don't.



 My excuse for std.parallelism is that it's pedal-to-metal parallelism,
 so it's more acceptable for it to be dangerous than general case
 concurrency. IMHO when you use the non- safe parts of std.parallelism
 (i.e. most of the library), that's equivalent to casting away shared
 in a whole bunch of places. Typing "import std.parallelism;" in a
 non- safe module is an explicit enough step here.


 I still think this "pedal-to-metal" qualification needs to be justified.
 Not having shared delegates in the language seems like an appropriate
 justification to me. Wanting to bypass casts you normally have to do
 around synchronized as the sole reason seems like a bad justification to
 me.

 It's not that I like how synchronized works, it's just that I think it
 should work the same everywhere.


This is where you and I disagree.  I think that the type system's 
guarantees should be weak, i.e. only apply to std.concurrency.  IMHO the 
strictness is reasonable when using message passing as your primary 
method of multithreading and only very little shared state.  However, 
it's completely unreasonable if you want to use a paradigm where shared 
state is more heavily used.  D, being a systems language, needs to allow 
other styles of multithreading without making them a huge PITA that 
requires casts everywhere.


 The guarantee is still preserved that, if you only use std.concurrency
 (D's flagship "safe" concurrency module) for multithreading and don't
 cast away shared, there can be no low level data races. IMHO this is
 still a substantial accomplishment in that there exists a way to do
 safe, statically checkable concurrency in D, even if it's not the
 **only** way concurrency can be done. BTW, core.thread can also be
 used to get around D's type system, not just std.parallelism. If you
 want to check that only safe concurrency is used, importing
 std.parallelism and core.thread can be grepped just as easily as
 casting away shared.


 Unless I'm mistaken, the only thing that bypasses race-safety in
 core.thread is the Thread constructor that takes a delegate. Which means
 it could easily be made race-safe by making that delegate parameter
 shared (once shared delegates are implemented).


And then you'd only need one cast to break it if you wanted to, not 
casts everywhere.  Just cast an unshared delegate to shared when passing 
it to core.thread.


 If, on the other hand, the guarantees of shared are supposed to be
 weak in that they only apply to programs where only std.concurrency is
 used for multithreading, then I think strictness is the right thing to
 do. The whole point of std.concurrency is to give strong guarantees,
 but if you prefer more dangerous but more flexible multithreading,
 other paradigms should be readily available.


 I think the language as a whole is designed to have strong guaranties,
 otherwise synchronized classes wouldn't require out-of-guaranty casts at
 every indirection.


Well, there's an easy way around that, too.  Just declare the whole 
method body synchronized, but don't declare the method synchronized in 
the signature.


 I'm not too pleased with the way synchronized classes are supposed to
 work, nor am I too pleased with how it impacts the rest of the language.
 But if this is a problem (and I think it is), it ought to be fixed
 globally, not by shutting down safeties in every module dealing with
 multithreading that isn't std.concurrency.


Again, I completely disagree.  IMHO it's not fixable globally such that 
both of the following are achieved:

1.  The strong guarantees when using only std.concurrency are preserved.

2.  More shared state-intensive multithreading can be done without the 
type system getting in the way more than it helps.


 I'm **still** totally confused about how shared is supposed to work,
 because I don't have a fully debugged/implemented implementation or
 good examples of stuff written in this paradigm to play around with.


 I think nobody have played much with the paradigm at this point, or we'd
 have heard some feedback. Well, actually we have your feedback which
 seem to indicate that it's better to shut off safeties than to play nice
 with them.


I agree that it's better to shut off the safeties **unless** you're 
doing very coarse-grained multithreading with very little shared state 
like std.concurrency had in mind.  If this is what you want, then the 
safeties are great.

Unfortunately, I'm going to have to take a hard line on this one.  The 
issue of integrating std.parallelism into the race safety system had 
been discussed a bunch in the past and it was basically agreed that 
std.parallelism is a "here be dragons" module that cannot reasonably be 
made to conform to such a model.  Given the choice (and I hope I'm not 
forced to make this choice) I'd rather std.parallelism be a third-party 
module that's actually usable than a Phobos module that is such a PITA 
to use that noone does in practice.
Mar 21 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-21 09:50:09 -0400, dsimcha <dsimcha yahoo.com> said:


 On 3/21/2011 8:37 AM, Michel Fortin wrote:

 Well, it'll work irrespective of whether shared delegates are used or
 not. I think you could add a compile-time check that the array element
 size is a multiple of the word size when the element is passed by ref in
 the loop and leave the clever trick as a possible future improvements.
 Would that work?


 
 On second thought, no, but for practical, not theoretical reasons:  
 One, you can't introspect whether a foreach loop is using a ref or a 
 value parameter.  This is an issue with how opApply works.


Indeed a problem. Either we fix the compiler to support that, or we 
change the syntax to something like this:

	taskPool.apply(range, (ref int value) {
		...
	});

Or we leave things as they are.


 Two, AFAIK there's no way to get the native word size.


Right. That's a problem too... you could probably alleviate this by 
doing a runtime check with some fancy instructions to get the native 
word size, but I'd expect that to be rather convoluted.

I'd like to check if I understand that well. For instance this code:

	int[100] values;
	foreach (i, ref value; parallel(values))
		value = i;

would normally run fine on a 32-bit processor, but it'd create 
low-level a race on a 64-bit processor (even a 64-bit processor running 
a 32-bit program in 32-bit compatibility mode). And even that is a 
generalization, some 32-bit processors out there *might* have 64-bit 
native words. So the code above isn't portable. Is that right?

Which makes me think... we need to document those pitfalls somewhere. 
Perhaps std.parallelism's documentation should link to a related page 
about what you can and what you can't do safely. People who read that 
"all the safeties are off" in std.parallelism aren't going to 
understand what you're talking about unless you explain the pitfalls 
with actual examples (like the one above).



 Unfortunately, I'm going to have to take a hard line on this one.  The 
 issue of integrating std.parallelism into the race safety system had 
 been discussed a bunch in the past and it was basically agreed that 
 std.parallelism is a "here be dragons" module that cannot reasonably be 
 made to conform to such a model.


About the "cannot reasonably be made to conform to such a model" part: 
that is certainly true today, but might turn out not to be true as the 
model evolves. It certainly is true as long as we don't have shared 
delegates. Beyond that it becomes more fuzzy. The final goal of the 
module shouldn't be to bypass safeties but to provide good parallelism 
primitives. By all means, if safeties can be enabled reasonably they 
should be (but as of today, they can't).

And I totally agree with you that it's quite silly to require casts 
everywhere to use synchronized. I'll be the first to admit that it's 
hard to see synchronized classes being very practical as they're 
implemented today. There's room for improvements there too.



 Given the choice (and I hope I'm not forced to make this choice) I'd 
 rather std.parallelism be a third-party module that's actually usable 
 than a Phobos module that is such a PITA to use that noone does in 
 practice.


Which is understandable.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 21 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Michel Fortin (michel.fortin michelf.com)'s article

 On second thought, no, but for practical, not theoretical reasons:
 One, you can't introspect whether a foreach loop is using a ref or a
 value parameter.  This is an issue with how opApply works.


 Indeed a problem. Either we fix the compiler to support that, or we
 change the syntax to something like this:
 	taskPool.apply(range, (ref int value) {
 		...
 	});
 Or we leave things as they are.

 Two, AFAIK there's no way to get the native word size.


 Right. That's a problem too... you could probably alleviate this by
 doing a runtime check with some fancy instructions to get the native
 word size, but I'd expect that to be rather convoluted.
 I'd like to check if I understand that well. For instance this code:
 	int[100] values;
 	foreach (i, ref value; parallel(values))
 		value = i;
 would normally run fine on a 32-bit processor, but it'd create
 low-level a race on a 64-bit processor (even a 64-bit processor running
 a 32-bit program in 32-bit compatibility mode). And even that is a
 generalization, some 32-bit processors out there *might* have 64-bit
 native words. So the code above isn't portable. Is that right?
 Which makes me think... we need to document those pitfalls somewhere.
 Perhaps std.parallelism's documentation should link to a related page
 about what you can and what you can't do safely. People who read that
 "all the safeties are off" in std.parallelism aren't going to
 understand what you're talking about unless you explain the pitfalls
 with actual examples (like the one above).


This problem is **much** less severe than you are suggesting.  x86 can address
single bytes, so it's not a problem even if you're iterating over bytes on a
64-bit machine.  CPUs like Alpha (which no D compiler even exists for) can't
natively address individual bytes.  Therefore, writing to a byte would be
implemented much like writing to a bit is on x86:  You'd read the full word in,
change one byte, write the full word back.  I'm not sure exactly how it would be
implemented at the compiler level, or whether you'd even be allowed to have a
reference to a byte in such an implementation.  This is why I consider this
more a
theoretical problem than a serious practical issue.



 Unfortunately, I'm going to have to take a hard line on this one.  The
 issue of integrating std.parallelism into the race safety system had
 been discussed a bunch in the past and it was basically agreed that
 std.parallelism is a "here be dragons" module that cannot reasonably be
 made to conform to such a model.


 About the "cannot reasonably be made to conform to such a model" part:
 that is certainly true today, but might turn out not to be true as the
 model evolves. It certainly is true as long as we don't have shared
 delegates. Beyond that it becomes more fuzzy. The final goal of the
 module shouldn't be to bypass safeties but to provide good parallelism
 primitives. By all means, if safeties can be enabled reasonably they
 should be (but as of today, they can't).


I'll agree that, if the model evolves sufficiently, everything I've said
deserves
to be reconsidered.  My comments only apply to the model as it exists currently
or
will exist in the foreseeable future.  It's just that I have **serious** doubts
that it will evolve much and I don't want to delay things to have an academic
discussion about what-ifs with regard to this.


 And I totally agree with you that it's quite silly to require casts
 everywhere to use synchronized. I'll be the first to admit that it's
 hard to see synchronized classes being very practical as they're
 implemented today. There's room for improvements there too.


This is the point I'm trying to make:  Requiring these casts is perfectly
reasonable if you assume that shared state is going to be rare, as it is in the
std.concurrency model.  When the user is looking for a more fine-grained, more
shared state-heavy paradigm, I don't think it's possible to make it safe without
also making it virtually unusable.  This is why we punted and decided to go with
message passing and very limited shared data as the flagship multithreading
model.
 On the other hand, in a systems language, we can't virtually prohibit shared
state-heavy multithreading by making it virtually unusable.  Thus, the no low
level race guarantee needs to apply to std.concurrency only.
Mar 21 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from dsimcha (dsimcha yahoo.com)'s article

 == Quote from Michel Fortin (michel.fortin michelf.com)'s article

 On second thought, no, but for practical, not theoretical reasons:
 One, you can't introspect whether a foreach loop is using a ref or a
 value parameter.  This is an issue with how opApply works.


 Indeed a problem. Either we fix the compiler to support that, or we
 change the syntax to something like this:
 	taskPool.apply(range, (ref int value) {
 		...
 	});
 Or we leave things as they are.

 Two, AFAIK there's no way to get the native word size.


 Right. That's a problem too... you could probably alleviate this by
 doing a runtime check with some fancy instructions to get the native
 word size, but I'd expect that to be rather convoluted.
 I'd like to check if I understand that well. For instance this code:
 	int[100] values;
 	foreach (i, ref value; parallel(values))
 		value = i;
 would normally run fine on a 32-bit processor, but it'd create
 low-level a race on a 64-bit processor (even a 64-bit processor running
 a 32-bit program in 32-bit compatibility mode). And even that is a
 generalization, some 32-bit processors out there *might* have 64-bit
 native words. So the code above isn't portable. Is that right?
 Which makes me think... we need to document those pitfalls somewhere.
 Perhaps std.parallelism's documentation should link to a related page
 about what you can and what you can't do safely. People who read that
 "all the safeties are off" in std.parallelism aren't going to
 understand what you're talking about unless you explain the pitfalls
 with actual examples (like the one above).


 This problem is **much** less severe than you are suggesting.  x86 can address
 single bytes, so it's not a problem even if you're iterating over bytes on a
 64-bit machine.  CPUs like Alpha (which no D compiler even exists for) can't
 natively address individual bytes.  Therefore, writing to a byte would be
 implemented much like writing to a bit is on x86:  You'd read the full word in,
 change one byte, write the full word back.  I'm not sure exactly how it would
be
 implemented at the compiler level, or whether you'd even be allowed to have a
 reference to a byte in such an implementation.  This is why I consider this
more a
 theoretical problem than a serious practical issue.


Actually, just remembered that word tearing is also an issue with unaligned
memory
access.  I guess I could just include a warning that says not to do this with
unaligned memory.
Mar 21 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 3/21/2011 11:58 AM, dsimcha wrote:

 == Quote from dsimcha (dsimcha yahoo.com)'s article

 == Quote from Michel Fortin (michel.fortin michelf.com)'s article

 On second thought, no, but for practical, not theoretical reasons:
 One, you can't introspect whether a foreach loop is using a ref or a
 value parameter.  This is an issue with how opApply works.


 Indeed a problem. Either we fix the compiler to support that, or we
 change the syntax to something like this:
 	taskPool.apply(range, (ref int value) {
 		...
 	});
 Or we leave things as they are.

 Two, AFAIK there's no way to get the native word size.


 Right. That's a problem too... you could probably alleviate this by
 doing a runtime check with some fancy instructions to get the native
 word size, but I'd expect that to be rather convoluted.
 I'd like to check if I understand that well. For instance this code:
 	int[100] values;
 	foreach (i, ref value; parallel(values))
 		value = i;
 would normally run fine on a 32-bit processor, but it'd create
 low-level a race on a 64-bit processor (even a 64-bit processor running
 a 32-bit program in 32-bit compatibility mode). And even that is a
 generalization, some 32-bit processors out there *might* have 64-bit
 native words. So the code above isn't portable. Is that right?
 Which makes me think... we need to document those pitfalls somewhere.
 Perhaps std.parallelism's documentation should link to a related page
 about what you can and what you can't do safely. People who read that
 "all the safeties are off" in std.parallelism aren't going to
 understand what you're talking about unless you explain the pitfalls
 with actual examples (like the one above).


 This problem is **much** less severe than you are suggesting.  x86 can address
 single bytes, so it's not a problem even if you're iterating over bytes on a
 64-bit machine.  CPUs like Alpha (which no D compiler even exists for) can't
 natively address individual bytes.  Therefore, writing to a byte would be
 implemented much like writing to a bit is on x86:  You'd read the full word in,
 change one byte, write the full word back.  I'm not sure exactly how it would
be
 implemented at the compiler level, or whether you'd even be allowed to have a
 reference to a byte in such an implementation.  This is why I consider this
more a
 theoretical problem than a serious practical issue.


 Actually, just remembered that word tearing is also an issue with unaligned
memory
 access.  I guess I could just include a warning that says not to do this with
 unaligned memory.


s/is/may be .  I'm trying to read up on word tearing and post questions 
here and to StackOverflow.  Good documentation about it seems 
ridiculously hard to come by.  About the only solid pieces of 
information I've found are that x86 definitely **can** do byte 
granularity (which doesn't mean it always does) and that Java makes 
these guarantees (which is only useful if you're writing in Java).  The 
general gut feeling people here and on StackOverflow seem to have is 
that it's not an issue, but there doesn't seem to be much backing up of 
this.

Maybe I'm just being paranoid and this is a complete non-issue except on 
the most obscure/ancient hardware and/or most stupidly implemented 
compilers, which is why few people even think of it.
Mar 21 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
dsimcha:


 1.  I give up.
 
 2.  I wish someone had told me earlier.


Please, don't give up. It's a lot of time from the first time I've asked a
parallel map in Phobos :-)

Bye,
bearophile
Mar 19 2011
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sat, 19 Mar 2011 13:09:23 -0400, Michel Fortin  
<michel.fortin michelf.com> wrote:


 On 2011-03-19 12:03:51 -0400, Andrei Alexandrescu  
 <SeeWebsiteForEmail erdani.org> said:


 * "Most of this module completely subverts..." Vague characterizations  
 ("most", "completely", "some") don't belong in a technical  
 documentation. (For example there's either subversion going on or there  
 isn't.) Also, std.concurrency and std.parallelism address different  
 needs so there's little competition between them. Better: "Unless  
 explicitly marked as $(D  trusted) or $(D  safe), artifacts in this  
 module are not provably memory-safe and cannot be used with SafeD. If  
 used as documented, memory safety is guaranteed."


 Actually, I think this is a bad description of what it subverts. What it  
 subverts isn't the memory-safety that SafeD provides, but the safety  
 against low-level races that even unsafe D protects against unless you  
 cast shared away. For instance:

 	void main() {
 		int sum = 0;
 		foreach (int value; taskPool.parallel([0,2,3,6,1,4,6,3,3,3,6])) {
 			sum += value;
 		}
 		writeln(sum);
 	}

 The "+=" would need to be an atomic operation to avoid low-level races.

 I think that ParallelForeach's opApply should only accept a shared  
 delegate. I define shared delegate as a delegate that does not reference  
 any non-shared variables of its outer scope. The problem is that DMD  
 currently doesn't know how to determine whether a delegate literal is  
 shared or not, thus a delegate literal is never shared and if  
 ParallelForeach's opApply asked a shared delegate as it should it would  
 just not work. Fix DMD to create shared delegate literals where  
 appropriate and everything can be guarantied race-free.


Technically, you'd only need a shared delegate or a const delegate to  
guarantee race safety for parallel foreach.
Mar 20 2011
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 12:03 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 02:32 AM, dsimcha wrote:

 Ok, thanks again for clarifying **how** the docs could be improved. I've
 implemented the suggestions and generally given the docs a good reading
 over and clean up. The new docs are at:

 http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html


 * Still no synopsis example that illustrates in a catchy way the most
 attractive artifacts.


I don't see what I could put here that isn't totally redundant with the 
rest of the documentation.  Anything I could think of would basically 
just involve concatentating all the examples.  Furthermore, none of the 
other Phobos modules have this, so I don't know what one should look 
like.  In general I feel like std.parallelism is being held to a 
ridiculously high standard that none of the other Phobos modules 
currently meet.


 * "After creation, Task objects are submitted to a TaskPool for
 execution." I understand it's possible to use Task straight as a
 promise/future, so s/are/may be/.


No.  The only way Task is useful is by submitting it to a pool to be 
executed.  (Though this may change, see below.)


 Also it is my understanding that
 TaskPool efficiently adapts the concrete number of CPUs to an arbitrary
 number of tasks. If that's the case, it's worth mentioning.


Isn't this kind of obvious from the examples, etc.?


 * "If a Task has been submitted to a TaskPool instance, is being stored
 in a stack frame, and has not yet finished, the destructor for this
 struct will automatically call yieldWait() so that the task can finish
 and the stack frame can be destroyed safely." At this point in the doc
 the reader doesn't understand that at all because TaskPool has not been
 seen yet. The reader gets worried that she'll be essentially serializing
 the entire process by mistake. Either move this explanation down or
 provide an example.


This is getting ridiculous.  There are too many circular dependencies 
between Task and TaskPool that are impossible to remove here that I'm 
not even going to try.  One or the other has to be introduced first, but 
neither can be explained without mentioning the other.  This is why I 
explain the relationship briefly in the module level summary, so that 
the user has at least some idea.  I think this is about the best I can do.


 * Is done() a property?


Yes.  DDoc sucks.


 * The example that reads two files at the same time should NOT use
 taskPool. It's just one task, why would the pool ever be needed? If you
 also provided an example that reads n files in memory at the same time
 using a pool, that would illustrate nicely why you need it. If a Task
 can't be launched without being put in a pool, there should be a
 possibility to do so. At my work we have a simple function called
 callInNewThread that does what's needed to launch a function in a new
 thread.


I guess I could add something like this to Task.  Under the hood it 
would (for implementation simplicity, to reuse a bunch of code from 
TaskPool) fire up a new single-thread pool, submit the task, call 
TaskPool.finish(), and then return.  Since you're already creating a new 
thread, the extra overhead of creating a new TaskPool for the thread 
would be negligible and it would massively simplify the implementation. 
  My only concern is that, when combined with scoped versus non-scoped 
tasks (which are definitely here to stay, see below) this small 
convenience function would add way more API complexity than it's worth. 
  Besides, task pools don't need to be created explicitly anyhow. 
That's what the default instantiation is for.  I don't see how 
callInNewThread would really solve much.

Secondly, I think you're reading **WAY** too much into what was meant to 
be a simple example to illustrate usage mechanics.  This is another case 
where I can't think of a small, cute example of where you'd really need 
the pool.  There are plenty of larger examples, but the smallest/most 
self-contained one I can think of is a parallel sort.  I decided to use 
file reading because it was good enough to illustrate the mechanics of 
usage, even if it didn't illustrate a particularly good use case.


 * The note below that example gets me thinking: it is an artificial
 limitation to force users of Task to worry about scope and such. One
 should be able to create a Future object (Task I think in your
 terminology), pass it around like a normal value, and ultimately force
 it. This is the case for all other languages that implement futures. I
 suspect the "scope" parameter associated with the delegate a couple of
 definitions below plays a role here, but I think we need to work for
 providing the smoothest interface possible (possibly prompting
 improvements in the language along the way).


This is what TaskPool.task is for.  Maybe this should be moved to the 
top of the definition of TaskPool and emphasized, and the scoped/stack 
allocated versions should be moved below TaskPool and de-emphasized?

At any rate, though, anyone who's playing with parallelism should be an 
advanced enough programmer that concepts like scope and destructors are 
second nature.


 * I'm not sure how to interpret the docs for

 ReturnType!(F) run(F, Args...)(F fpOrDelegate, ref Args args);

 So it's documented but I'm not supposed to care. Why not just remove?
 Surely there must be higher-level examples that clarify that I can use
 delegates etc.


Yes, and there are such examples.  It's just that I want to explicitly 
state what type is returned in this case rather than returning auto.  If 
I omitted the docs for run(), you'd ask what run() is.


 * "If you want to escape the Task object from the function in which it
 was created or prefer to heap allocate and automatically submit to the
 pool, see TaskPool.task()." I'm uncomfortable that I need to remember a
 subtle distinction of the same primitive name ("task") depending on
 membership in a TaskPool or not, which is a tenuous relationship to
 remember. How about "scopedTask()" vs. "task()"? Also, it's worth asking
 ourselves what's the relative overhead of closure allocation vs. task
 switching etc. Maybe we get to simplify things a lot at a small cost in
 efficiency.


We absolutely **need** scope delegates for calling stuff where a closure 
can't be allocated due to objects on the stack frame having scoped 
destruction.  This is not going anywhere.  Also, I **much** prefer to 
have everything that does conceptually the same thing have the same 
name.  I think this is clearer, not less clear.


 * As I mentioned, in the definition:

 Task!(run,TypeTuple!(F,Args)) task(F, Args...)(F fun, Args args);

 I can't tell what "run" is.


run() is just the adapter function described right above this code.  I 
cannot for the life of me understand how this could possibly be unclear.


 * "A goto from inside the parallel foreach loop to a label outside the
 loop will result in undefined behavior." Would this be a bug in dmd?


No, it's because a goto of this form has no reasonable, useful 
semantics.  I should probably mention in the docs that the same applies 
to labeled break and continue.

I have no idea what semantics these should have, and even if I did, 
given the long odds that even one person would actually need them, I 
think they'd be more trouble than they're worth to implement.  For 
example, once you break out of a parallel foreach loop to some arbitrary 
address (and different threads can goto different labels, etc.), well, 
it's no longer a parallel foreach loop.  It's just a bunch of completely 
unstructured threading doing god-knows-what.

Therefore, I slapped undefined behavior on it as a big sign that says, 
"Just don't do it."  This also has the advantage that, if anyone ever 
thinks of any good, clearly useful semantics, these will be 
implementable without breaking code later.

 * Again: speed of e.g. parallel min/max vs. serial, pi computation etc.
 on a usual machine?


I **STRONGLY** believe this does not belong in API documentation because 
it's too machine specific, compiler specific, stack alignment specific, 
etc. and almost any benchmark worth doing takes up more space than an 
example should. Furthermore, anyone who wants to know this can easily 
time it themselves.  I have absolutely no intention of including this. 
While in general I appreciate and have tried to accommodate your 
suggestions, this is one I'll be standing firm on.


 * The join example is fine, but the repetitive code suggests that loops
 should be better:

 import std.file;

 void main() {
 auto pool = new TaskPool();
 foreach (filename; ["foo.txt", "bar.txt", "baz.txt"]) {
 pool.put(task!read(filename));
 }

 // Call join() to guarantee that all tasks are done running, the worker
 // threads have terminated and that the results of all of the tasks can
 // be accessed without any synchronization primitives.
 pool.join();

 ubyte[][] data; // void[], meh
 // Use spinWait() since the results are guaranteed to have been computed
 // and spinWait() is the cheapest of the wait functions.
 foreach (task; pool.howDoIEnumerateTasks()) {
 data ~= task1.spinWait();
 }


You can't enumerate the tasks like this, but there's a good reason for 
this limitation.  The design requires the pool not hold onto any 
references to the tasks after they're out of the queue, so that they can 
be safely destroyed as soon as the caller wants to destroy them.  If you 
need to enumerate over them like this, then:

1.  You're probably doing something wrong and parallel foreach would be 
a better choice.

2.  If you insist on doing this, you need to explicitly store them in an 
array or something.

As a more general comment, I know the join() example sucks.  join() is 
actually a seldom-used primitive, not a frequently used one as you 
suggest.  Most of the time you wait for individual tasks (explicitly or 
implicitly through the higher level functions), not the whole pool, to 
finish executing.  I feel like it's obligatory that join() and finish() 
exist, but I never use them myself.  They were much more useful in 
pre-release versions of this lib, when parallel foreach didn't exist and 
it made sense to have explicit arrays of Tasks.  The difficulty I've had 
in coming up with a decent example for them makes me halfway tempted to
Mar 19 2011
next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-19 13:16:02 -0400, dsimcha <dsimcha yahoo.com> said:


 * "A goto from inside the parallel foreach loop to a label outside the
 loop will result in undefined behavior." Would this be a bug in dmd?


 
 No, it's because a goto of this form has no reasonable, useful 
 semantics.  I should probably mention in the docs that the same applies 
 to labeled break and continue.
 
 I have no idea what semantics these should have, and even if I did, 
 given the long odds that even one person would actually need them, I 
 think they'd be more trouble than they're worth to implement.  For 
 example, once you break out of a parallel foreach loop to some 
 arbitrary address (and different threads can goto different labels, 
 etc.), well, it's no longer a parallel foreach loop.  It's just a bunch 
 of completely unstructured threading doing god-knows-what.
 
 Therefore, I slapped undefined behavior on it as a big sign that says, 
 "Just don't do it."  This also has the advantage that, if anyone ever 
 thinks of any good, clearly useful semantics, these will be 
 implementable without breaking code later.


I think an improvement over undefined behaviour would be to throw an exception.

Also, what happens if one of the tasks throws an exception?

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 19 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 2:35 PM, Michel Fortin wrote:

 On 2011-03-19 13:16:02 -0400, dsimcha <dsimcha yahoo.com> said:


 * "A goto from inside the parallel foreach loop to a label outside the
 loop will result in undefined behavior." Would this be a bug in dmd?


 No, it's because a goto of this form has no reasonable, useful
 semantics. I should probably mention in the docs that the same applies
 to labeled break and continue.

 I have no idea what semantics these should have, and even if I did,
 given the long odds that even one person would actually need them, I
 think they'd be more trouble than they're worth to implement. For
 example, once you break out of a parallel foreach loop to some
 arbitrary address (and different threads can goto different labels,
 etc.), well, it's no longer a parallel foreach loop. It's just a bunch
 of completely unstructured threading doing god-knows-what.

 Therefore, I slapped undefined behavior on it as a big sign that says,
 "Just don't do it." This also has the advantage that, if anyone ever
 thinks of any good, clearly useful semantics, these will be
 implementable without breaking code later.


 I think an improvement over undefined behaviour would be to throw an
 exception.


The only problem is that there's no easy, well-documented way to tell 
from the return value of opApply whether it was a break, a goto, a 
labeled break/continue, etc.  This would be implementable only if I 
changed the semantics of break to also throw.  This might not be a bad 
thing (IMHO any type of breaking out of a parallel foreach loop is just 
silly) but others had asked for different semantics for break.


 Also, what happens if one of the tasks throws an exception?


It gets rethrown when yieldWait()/spinWait()/workWait() is called.  In 
the case of the higher-level primitives, it gets re-thrown to the 
calling thread at some non-deterministic point in the execution of these 
functions.  I didn't see the need to document this explicitly because it 
"just works".
Mar 19 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 3:36 PM, dsimcha wrote:

 On 3/19/2011 2:35 PM, Michel Fortin wrote:
 It gets rethrown when yieldWait()/spinWait()/workWait() is called. In
 the case of the higher-level primitives, it gets re-thrown to the
 calling thread at some non-deterministic point in the execution of these
 functions. I didn't see the need to document this explicitly because it
 "just works".


...Though now that you make me think of it I need to support exception 
chaining for the case of multiple concurrently thrown exceptions instead 
of just arbitrarily and non-deterministically rethrowing one.  The code 
that handles this was written before exception chaining existed.  Will 
get on that.
Mar 19 2011
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-03-19 15:36:24 -0400, dsimcha <dsimcha yahoo.com> said:


 On 3/19/2011 2:35 PM, Michel Fortin wrote:

 On 2011-03-19 13:16:02 -0400, dsimcha <dsimcha yahoo.com> said:
 

 * "A goto from inside the parallel foreach loop to a label outside the
 loop will result in undefined behavior." Would this be a bug in dmd?


 
 No, it's because a goto of this form has no reasonable, useful
 semantics. I should probably mention in the docs that the same applies
 to labeled break and continue.
 
 I have no idea what semantics these should have, and even if I did,
 given the long odds that even one person would actually need them, I
 think they'd be more trouble than they're worth to implement. For
 example, once you break out of a parallel foreach loop to some
 arbitrary address (and different threads can goto different labels,
 etc.), well, it's no longer a parallel foreach loop. It's just a bunch
 of completely unstructured threading doing god-knows-what.
 
 Therefore, I slapped undefined behavior on it as a big sign that says,
 "Just don't do it." This also has the advantage that, if anyone ever
 thinks of any good, clearly useful semantics, these will be
 implementable without breaking code later.


 
 I think an improvement over undefined behaviour would be to throw an
 exception.


 
 The only problem is that there's no easy, well-documented way to tell 
 from the return value of opApply whether it was a break, a goto, a 
 labeled break/continue, etc.  This would be implementable only if I 
 changed the semantics of break to also throw.  This might not be a bad 
 thing (IMHO any type of breaking out of a parallel foreach loop is just 
 silly) but others had asked for different semantics for break.


It's not that silly.

Essentially, what you'd express like this with a normal function taking 
a delegate:

	taskPool.apply([1,2,3], (int i) {
		if (i == 1)
			return;
		// do some things
	});

you'd express like this in a parallel foreach:

	foreach (int i; parallel([1,2,3])) {
		if (i == 1)
			break;
		// do some things
	}

It's not following the semantics of break within a foreach, but it's 
still useful to be able to return early from a function (from a loop 
iteration in this case), so I see the use case for making 'break' do 
what it does.

My only gripe is that the semantics are distorted. In fact, just making 
foreach parallel distorts its semantics. I was confused earlier about a 
foreach being parallel when it was not, someone could also be confused 
in the other direction, thinking foreach is the normal foreach when it 
actually is parallel. This makes code harder to review. Don't consider 
only my opinion on this, but in my opinion the first form above 
(taskPool.apply) is preferable because you absolutely can't mistake it 
with a normal foreach. And I think it's especially important to make it 
stand out given that the compiler can't check for low-level races.



 Also, what happens if one of the tasks throws an exception?


 
 It gets rethrown when yieldWait()/spinWait()/workWait() is called.  In 
 the case of the higher-level primitives, it gets re-thrown to the 
 calling thread at some non-deterministic point in the execution of 
 these functions.  I didn't see the need to document this explicitly 
 because it "just works".


That's indeed what I'd expect. But I think it'd still be worth 
mentioning in a short sentense in yeildWait()/spinWait()/workWait()'s 
documentation. It's comforting when the documentation confirms your 
expectations.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 19 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 5:33 PM, Michel Fortin wrote:

 On 2011-03-19 15:36:24 -0400, dsimcha <dsimcha yahoo.com> said:

 The only problem is that there's no easy, well-documented way to tell
 from the return value of opApply whether it was a break, a goto, a
 labeled break/continue, etc. This would be implementable only if I
 changed the semantics of break to also throw. This might not be a bad
 thing (IMHO any type of breaking out of a parallel foreach loop is
 just silly) but others had asked for different semantics for break.


 It's not that silly.

 Essentially, what you'd express like this with a normal function taking
 a delegate:

 taskPool.apply([1,2,3], (int i) {
 if (i == 1)
 return;
 // do some things
 });

 you'd express like this in a parallel foreach:

 foreach (int i; parallel([1,2,3])) {
 if (i == 1)
 break;
 // do some things
 }

 It's not following the semantics of break within a foreach, but it's
 still useful to be able to return early from a function (from a loop
 iteration in this case), so I see the use case for making 'break' do
 what it does.


Using continue is well defined behavior and does exactly what I think 
you're suggesting.  The problem with break is that it's supposed to stop 
all subsequent iterations of the loop from being executed, not just end 
the current one early.  This only makes sense in a serial context, where 
"subsequent iterations" is well-defined.  Currently break breaks from 
the current work unit but continues executing all other work units.  I 
put this semantic in because I couldn't think of anything else to make 
it do and someone (I don't remember who) asked for it.  I have never 
encountered a use case for it.

IMHO all early termination that affects subsequent loop iterations as 
well (break, goto, labeled break and continue, but not regular continue) 
should just throw because they make absolutely no sense in a parallel 
context.
Mar 19 2011
parent reply Daniel Gibson <metalcaedes gmail.com> writes:
Am 19.03.2011 22:45, schrieb dsimcha:

 IMHO all early termination that affects subsequent loop iterations as well
 (break, goto, labeled break and continue, but not regular continue) should just
 throw because they make absolutely no sense in a parallel context.


What about some kind of parallel search? You just want to know if something is
there and on first sight you're done, so you want to break out of this iteration
and don't want any new parallel iterations to be done.
(Not sure what should be done with currently running iterations.. should they be
killed or go on until they're done - anyway, the executing thread shouldn't
start a new iteration after that)
Mar 19 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 7:33 PM, Daniel Gibson wrote:

 Am 19.03.2011 22:45, schrieb dsimcha:

 IMHO all early termination that affects subsequent loop iterations as well
 (break, goto, labeled break and continue, but not regular continue) should just
 throw because they make absolutely no sense in a parallel context.


 What about some kind of parallel search? You just want to know if something is
 there and on first sight you're done, so you want to break out of this
iteration
 and don't want any new parallel iterations to be done.
 (Not sure what should be done with currently running iterations.. should they
be
 killed or go on until they're done - anyway, the executing thread shouldn't
 start a new iteration after that)


It's an interesting suggestion, and I'll give some thought to it, but on 
first glance it sounds **very** difficult to implement efficiently.  To 
avoid doing a lot of extra work after you've found what you need, you'd 
need to use very small work units.  To avoid excessive overhead you'd 
need to use fairly large work units.  The only case I can think of where 
this would be do-able is when evaluating the predicate is very expensive.
Mar 19 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/19/2011 12:16 PM, dsimcha wrote:

 On 3/19/2011 12:03 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 02:32 AM, dsimcha wrote:

 Ok, thanks again for clarifying **how** the docs could be improved. I've
 implemented the suggestions and generally given the docs a good reading
 over and clean up. The new docs are at:

 http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html


 * Still no synopsis example that illustrates in a catchy way the most
 attractive artifacts.


 I don't see what I could put here that isn't totally redundant with the
 rest of the documentation. Anything I could think of would basically
 just involve concatentating all the examples. Furthermore, none of the
 other Phobos modules have this, so I don't know what one should look
 like.


I'm thinking along the lines of:

http://www.digitalmars.com/d/2.0/phobos/std_exception.html

A nice synopsis would be the pi computation. Just move that up to the 
synopsis. It's simple, clean, and easy to relate to. Generally, you'd 
put here not all details but the stuff you think would make it easiest 
for people to get into your library.


 In general I feel like std.parallelism is being held to a
 ridiculously high standard that none of the other Phobos modules
 currently meet.


I agree, but that goes without saying. This is not a double standard; 
it's a simple means to improve quality of Phobos overall. Clearly 
certain modules that are already in Phobos would not make it if proposed 
today. And that's a good thing! Comparing our current ambitions to the 
quality of the average Phobos module would not help us.
	
Generally it seems you have grown already tired of the exchange and it 
would take only a few more exchanges for you to say, "you know what, 
either let's get it over it or forget about it."

Please consider for a minute how this is the wrong tone and attitude to 
be having on several levels. This is not a debate and not the place to 
get defensive. Your role in the discussion is not symmetric with the 
others' and at best you'd use the review as an opportunity to improve 
your design, not stick heels in the ground to defend its current 
incarnation (within reason). Your potential customers are attempting to 
help you by asking questions (some of which no doubt are silly) and by 
making suggestions (some of which, again, are ill-founded). 
Nevertheless, we _are_ your potential customers and in a way the 
customer is always right. Your art is to steer customers from what they 
think they want to what you know they need - because you're the expert! 
- and to improve design, nomenclature, and implementation to the extent 
that would help them.

Furthermore, you should expect that the review process will prompt 
changes. My perception is that you consider the submission more or less 
final modulo possibly a few minor nits. You shouldn't. I'm convinced you 
know much more about SMP than most or all others in this group, but in 
no way that means your design has reached perfection and is beyond 
improvement even from a non-expert.

I know you'd have no problem finding the right voice in this discussion 
if you only frame it in the right light. Again, people are trying to 
help (however awkwardly) and in no way is that ridiculous.


 * "After creation, Task objects are submitted to a TaskPool for
 execution." I understand it's possible to use Task straight as a
 promise/future, so s/are/may be/.


 No. The only way Task is useful is by submitting it to a pool to be
 executed. (Though this may change, see below.)


I very much hope this does change. Otherwise the role of Task in the 
design could be drastically reduced (e.g. nested type inside of 
TaskPool) without prejudice. At the minimum I want to be able to create 
a task, launch it, and check its result later without involving a pool. 
A pool is when I have many tasks that may exceed the number of CPUs etc. 
Simplicity would be great.

// start three reads
auto readFoo = task!readText("foo.txt");
auto readBar = task!readText("bar.txt");
auto readBaz = task!readText("baz.txt");
// join'em all
auto foo = readFoo.yieldWait();
auto bar = readBar.yieldWait();
auto baz = readBaz.yieldWait();

There's no need at this level for a task pool. What would be nice would 
be to have a join() that joins all tasks spawned by the current thread:

// start three reads
auto readFoo = task!readText("foo.txt");
auto readBar = task!readText("bar.txt");
auto readBaz = task!readText("baz.txt");
// join'em all
join();
// fetch results
auto foo = readFoo.spinWait();
auto bar = readBar.spinWait();
auto baz = readBaz.spinWait();

The way I see it is, task pools are an advanced means that coordinate m 
threads over n CPUs. If I don't care about that (as above) there should 
be no need for a pool at all. (Of course it's fine if used by the 
implementation.)


 Also it is my understanding that
 TaskPool efficiently adapts the concrete number of CPUs to an arbitrary
 number of tasks. If that's the case, it's worth mentioning.


 Isn't this kind of obvious from the examples, etc.?


It wasn't to me. I had an intuition that that might be the case, but 
obvious - far from it. The fact that I need a task pool even when I 
don't care about m:n issues made me doubtful.


 * "If a Task has been submitted to a TaskPool instance, is being stored
 in a stack frame, and has not yet finished, the destructor for this
 struct will automatically call yieldWait() so that the task can finish
 and the stack frame can be destroyed safely." At this point in the doc
 the reader doesn't understand that at all because TaskPool has not been
 seen yet. The reader gets worried that she'll be essentially serializing
 the entire process by mistake. Either move this explanation down or
 provide an example.


 This is getting ridiculous. There are too many circular dependencies
 between Task and TaskPool that are impossible to remove here that I'm
 not even going to try. One or the other has to be introduced first, but
 neither can be explained without mentioning the other. This is why I
 explain the relationship briefly in the module level summary, so that
 the user has at least some idea. I think this is about the best I can do.


Perhaps cross-references could help (see macro XREF). As I mentioned, an 
example here could go a long way, too.


 * The example that reads two files at the same time should NOT use
 taskPool. It's just one task, why would the pool ever be needed? If you
 also provided an example that reads n files in memory at the same time
 using a pool, that would illustrate nicely why you need it. If a Task
 can't be launched without being put in a pool, there should be a
 possibility to do so. At my work we have a simple function called
 callInNewThread that does what's needed to launch a function in a new
 thread.


 I guess I could add something like this to Task. Under the hood it would
 (for implementation simplicity, to reuse a bunch of code from TaskPool)
 fire up a new single-thread pool, submit the task, call
 TaskPool.finish(), and then return. Since you're already creating a new
 thread, the extra overhead of creating a new TaskPool for the thread
 would be negligible and it would massively simplify the implementation.
 My only concern is that, when combined with scoped versus non-scoped
 tasks (which are definitely here to stay, see below) this small
 convenience function would add way more API complexity than it's worth.
 Besides, task pools don't need to be created explicitly anyhow. That's
 what the default instantiation is for. I don't see how callInNewThread
 would really solve much.


If we sit down for a second and think outside of the current design, the 
simplest Task use would be as such: "I start a task and get a sort of a 
future. I do something else. Then when I nede the result of the future I 
call some method force() against it." Nowhere is the notion of a task 
pool to be found. To me this looks like an artifact of the 
implementation has spilled into the API, which I understand how is 
natural to you. But also it's unnatural to me.


 Secondly, I think you're reading **WAY** too much into what was meant to
 be a simple example to illustrate usage mechanics. This is another case
 where I can't think of a small, cute example of where you'd really need
 the pool. There are plenty of larger examples, but the smallest/most
 self-contained one I can think of is a parallel sort. I decided to use
 file reading because it was good enough to illustrate the mechanics of
 usage, even if it didn't illustrate a particularly good use case.


It's impossible to not have a good small example. Sorting is great. You 
have the partition primitive already in std.algorithm, then off you go 
with tasks. Dot product on dense vectors is another good one. There's 
just plenty of operations that people understand are important to make fast.

So to me it looks like this:

* there are already some good examples of "I want 1-3 of tasks but don't 
care about pooling them": file reading and processing etc.

* there should be 1-2 good example of partitioning a large chunk of work 
into many tasks and let taskPool carry them.

With such, people would clearly understand the capabilities of the 
library and what they can achieve with various levels of involvement.


 * The note below that example gets me thinking: it is an artificial
 limitation to force users of Task to worry about scope and such. One
 should be able to create a Future object (Task I think in your
 terminology), pass it around like a normal value, and ultimately force
 it. This is the case for all other languages that implement futures. I
 suspect the "scope" parameter associated with the delegate a couple of
 definitions below plays a role here, but I think we need to work for
 providing the smoothest interface possible (possibly prompting
 improvements in the language along the way).


 This is what TaskPool.task is for. Maybe this should be moved to the top
 of the definition of TaskPool and emphasized, and the scoped/stack
 allocated versions should be moved below TaskPool and de-emphasized?

 At any rate, though, anyone who's playing with parallelism should be an
 advanced enough programmer that concepts like scope and destructors are
 second nature.


I agree. That's not a reason to not find good names for entities. To me 
the relationship "global task() <=> scoped delegate; TaskPool method 
task() <=> closure" is inscrutable. I see no way of remembering it 
except rote memorization.


 We absolutely **need** scope delegates for calling stuff where a closure
 can't be allocated due to objects on the stack frame having scoped
 destruction. This is not going anywhere. Also, I **much** prefer to have
 everything that does conceptually the same thing have the same name. I
 think this is clearer, not less clear.


I agree in principle, but this case is just not that.


 * As I mentioned, in the definition:

 Task!(run,TypeTuple!(F,Args)) task(F, Args...)(F fun, Args args);

 I can't tell what "run" is.


 run() is just the adapter function described right above this code. I
 cannot for the life of me understand how this could possibly be unclear.


OK.


 * "A goto from inside the parallel foreach loop to a label outside the
 loop will result in undefined behavior." Would this be a bug in dmd?


 No, it's because a goto of this form has no reasonable, useful
 semantics. I should probably mention in the docs that the same applies
 to labeled break and continue.

 I have no idea what semantics these should have, and even if I did,
 given the long odds that even one person would actually need them, I
 think they'd be more trouble than they're worth to implement. For
 example, once you break out of a parallel foreach loop to some arbitrary
 address (and different threads can goto different labels, etc.), well,
 it's no longer a parallel foreach loop. It's just a bunch of completely
 unstructured threading doing god-knows-what.

 Therefore, I slapped undefined behavior on it as a big sign that says,
 "Just don't do it." This also has the advantage that, if anyone ever
 thinks of any good, clearly useful semantics, these will be
 implementable without breaking code later.


Yah, I was actually thinking of disabling goto outside a local delegate 
everywhere.


 * Again: speed of e.g. parallel min/max vs. serial, pi computation etc.
 on a usual machine?


 I **STRONGLY** believe this does not belong in API documentation because
 it's too machine specific, compiler specific, stack alignment specific,
 etc. and almost any benchmark worth doing takes up more space than an
 example should. Furthermore, anyone who wants to know this can easily
 time it themselves. I have absolutely no intention of including this.
 While in general I appreciate and have tried to accommodate your
 suggestions, this is one I'll be standing firm on.


If scalability information is present in however a non-committal form, 
then people would be compelled ("ok, so this shape of the loop would 
actually scale linearly with CPUs... neat").

Speaking of efficiency, I assume parallel foreach uses opApply with a 
delegate and the inherent overhead. So I'm thinking that a practical way 
to take advantage of parallel foreach would be to parallelize at some 
block level and then do a regular foreach inside the block?

foreach (i, ref elem; taskPool.parallel(logs)) {
     foreach (???)
         elem = log(i + 1.0);
}

How can I arrange things such that I compute e.g. 64 logs serially 
inside each pass?


 * The join example is fine, but the repetitive code suggests that loops
 should be better:

 import std.file;

 void main() {
 auto pool = new TaskPool();
 foreach (filename; ["foo.txt", "bar.txt", "baz.txt"]) {
 pool.put(task!read(filename));
 }

 // Call join() to guarantee that all tasks are done running, the worker
 // threads have terminated and that the results of all of the tasks can
 // be accessed without any synchronization primitives.
 pool.join();

 ubyte[][] data; // void[], meh
 // Use spinWait() since the results are guaranteed to have been computed
 // and spinWait() is the cheapest of the wait functions.
 foreach (task; pool.howDoIEnumerateTasks()) {
 data ~= task1.spinWait();
 }


 You can't enumerate the tasks like this, but there's a good reason for
 this limitation. The design requires the pool not hold onto any
 references to the tasks after they're out of the queue, so that they can
 be safely destroyed as soon as the caller wants to destroy them. If you
 need to enumerate over them like this, then:

 1. You're probably doing something wrong and parallel foreach would be a
 better choice.

 2. If you insist on doing this, you need to explicitly store them in an
 array or something.

 As a more general comment, I know the join() example sucks. join() is
 actually a seldom-used primitive, not a frequently used one as you
 suggest. Most of the time you wait for individual tasks (explicitly or
 implicitly through the higher level functions), not the whole pool, to
 finish executing. I feel like it's obligatory that join() and finish()
 exist, but I never use them myself. They were much more useful in
 pre-release versions of this lib, when parallel foreach didn't exist and
 it made sense to have explicit arrays of Tasks. The difficulty I've had
 in coming up with a decent example for them makes me halfway tempted to




I'm confused here. I use join() pretty much all the time. I launch stuff 
(e.g. run a large matrix-vector multiplication for distinct vectors) and 
then I join that. Then again and again. The thread of execution has a 
repeated hourglass shape - it fans out and then becomes single-threaded 
at join points. I assume some of those computations are indeed the 
charter of parallel foreach, but I'd guess not all. But then what do I 
know - I'm the customer :o).


Andrei
Mar 19 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 12:16 PM, dsimcha wrote:

 On 3/19/2011 12:03 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 02:32 AM, dsimcha wrote:

 Ok, thanks again for clarifying **how** the docs could be improved.
 I've
 implemented the suggestions and generally given the docs a good reading
 over and clean up. The new docs are at:

 http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html


 * Still no synopsis example that illustrates in a catchy way the most
 attractive artifacts.


 I don't see what I could put here that isn't totally redundant with the
 rest of the documentation. Anything I could think of would basically
 just involve concatentating all the examples. Furthermore, none of the
 other Phobos modules have this, so I don't know what one should look
 like.


 I'm thinking along the lines of:

 http://www.digitalmars.com/d/2.0/phobos/std_exception.html

 A nice synopsis would be the pi computation. Just move that up to the
 synopsis. It's simple, clean, and easy to relate to. Generally, you'd
 put here not all details but the stuff you think would make it easiest
 for people to get into your library.


 In general I feel like std.parallelism is being held to a
 ridiculously high standard that none of the other Phobos modules
 currently meet.


 I agree, but that goes without saying. This is not a double standard;
 it's a simple means to improve quality of Phobos overall. Clearly
 certain modules that are already in Phobos would not make it if proposed
 today. And that's a good thing! Comparing our current ambitions to the
 quality of the average Phobos module would not help us.

 Generally it seems you have grown already tired of the exchange and it
 would take only a few more exchanges for you to say, "you know what,
 either let's get it over it or forget about it."

 Please consider for a minute how this is the wrong tone and attitude to
 be having on several levels. This is not a debate and not the place to
 get defensive. Your role in the discussion is not symmetric with the
 others' and at best you'd use the review as an opportunity to improve
 your design, not stick heels in the ground to defend its current
 incarnation (within reason). Your potential customers are attempting to
 help you by asking questions (some of which no doubt are silly) and by
 making suggestions (some of which, again, are ill-founded).
 Nevertheless, we _are_ your potential customers and in a way the
 customer is always right. Your art is to steer customers from what they
 think they want to what you know they need - because you're the expert!
 - and to improve design, nomenclature, and implementation to the extent
 that would help them.

 Furthermore, you should expect that the review process will prompt
 changes. My perception is that you consider the submission more or less
 final modulo possibly a few minor nits. You shouldn't. I'm convinced you
 know much more about SMP than most or all others in this group, but in
 no way that means your design has reached perfection and is beyond
 improvement even from a non-expert.

 I know you'd have no problem finding the right voice in this discussion
 if you only frame it in the right light. Again, people are trying to
 help (however awkwardly) and in no way is that ridiculous.


Fair enough.  Now that I think of it most of my frustration is that 
these details are only getting looked at now, when I have a week (and an 
otherwise very busy week) to fix all this stuff, when this module has 
been officially in review for the past two weeks and unofficially for 
several months.  I would be much more open to this process if the issues 
raised could be fixed at my leisure rather than on a hard and tight 
deadline.  This is exacerbated by the fact that I have another 
important, unrelated deadline, also next Friday.

At the same time, though, I'm afraid that if we didn't fix a vote date 
and put some urgency into things, the pace of the reviews would be 
glacial at best, like it was for the first two weeks of official review 
and the months of unofficial review.

How about we make next Friday a soft deadline/start of voting?  It can 
be extended as necessary by mutual agreement of me and Lars (the review 
manager), and likely will be if the review process is still yielding 
good suggestions and/or I haven't had time to implement/clean up some 
key things.  Having a deadline breathing down your neck like this is 
really not conducive to being open to suggestions and thoughtful 
consideration, especially for issues that seem like fairly minor details.

Also increasing the deadline pressure issue, Michael Fortin just caused 
me to rethink the issue of exception handling in parallel foreach.  I 
had more-or-less working code for this, but I realized it's severely 
broken in subtle ways that I've (knock on wood) never actually run into 
in real world code.  It's gonna take some time to fix.  These kinds of 
issues with error handling code can very easily slip under the radar in 
a library with only a few users, and unfortunately, one has.  I 
definitely know how to fix it, but I have to implement the fix and it's 
somewhat non-trivial, i.e. I'm debugging it now and it's looking like a 
marathon debugging session.
Mar 19 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/19/2011 04:25 PM, dsimcha wrote:

 On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 I know you'd have no problem finding the right voice in this discussion
 if you only frame it in the right light. Again, people are trying to
 help (however awkwardly) and in no way is that ridiculous.


 Fair enough. Now that I think of it most of my frustration is that these
 details are only getting looked at now, when I have a week (and an
 otherwise very busy week) to fix all this stuff, when this module has
 been officially in review for the past two weeks and unofficially for
 several months. I would be much more open to this process if the issues
 raised could be fixed at my leisure rather than on a hard and tight
 deadline. This is exacerbated by the fact that I have another important,
 unrelated deadline, also next Friday.

 At the same time, though, I'm afraid that if we didn't fix a vote date
 and put some urgency into things, the pace of the reviews would be
 glacial at best, like it was for the first two weeks of official review
 and the months of unofficial review.


Exactly. I understand. Well here's a suggestion. How about we "git 
stash" this review? I recall another submission was vying for the queue 
so we can proceed with that while you have time to operate the changes 
you want. If not, we can simply wait 2-3 weeks and then have you 
resubmit for a shorter process (1-2 weeks) that would gather more 
feedback (hopefully minor that time) and votes.

Lars?


 Also increasing the deadline pressure issue, Michael Fortin just caused
 me to rethink the issue of exception handling in parallel foreach. I had
 more-or-less working code for this, but I realized it's severely broken
 in subtle ways that I've (knock on wood) never actually run into in real
 world code. It's gonna take some time to fix. These kinds of issues with
 error handling code can very easily slip under the radar in a library
 with only a few users, and unfortunately, one has. I definitely know how
 to fix it, but I have to implement the fix and it's somewhat
 non-trivial, i.e. I'm debugging it now and it's looking like a marathon
 debugging session.


Fixing these sooner rather than later would be great, so  all the better 
for suspending the review.

Andrei
Mar 19 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 6:58 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 04:25 PM, dsimcha wrote:

 On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 I know you'd have no problem finding the right voice in this discussion
 if you only frame it in the right light. Again, people are trying to
 help (however awkwardly) and in no way is that ridiculous.


 Fair enough. Now that I think of it most of my frustration is that these
 details are only getting looked at now, when I have a week (and an
 otherwise very busy week) to fix all this stuff, when this module has
 been officially in review for the past two weeks and unofficially for
 several months. I would be much more open to this process if the issues
 raised could be fixed at my leisure rather than on a hard and tight
 deadline. This is exacerbated by the fact that I have another important,
 unrelated deadline, also next Friday.

 At the same time, though, I'm afraid that if we didn't fix a vote date
 and put some urgency into things, the pace of the reviews would be
 glacial at best, like it was for the first two weeks of official review
 and the months of unofficial review.


 Exactly. I understand. Well here's a suggestion. How about we "git
 stash" this review? I recall another submission was vying for the queue
 so we can proceed with that while you have time to operate the changes
 you want. If not, we can simply wait 2-3 weeks and then have you
 resubmit for a shorter process (1-2 weeks) that would gather more
 feedback (hopefully minor that time) and votes.


Sounds like a plan.
Mar 19 2011
prev sibling parent "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Sat, 19 Mar 2011 17:58:46 -0500, Andrei Alexandrescu wrote:


 On 03/19/2011 04:25 PM, dsimcha wrote:

 On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 I know you'd have no problem finding the right voice in this
 discussion if you only frame it in the right light. Again, people are
 trying to help (however awkwardly) and in no way is that ridiculous.


 Fair enough. Now that I think of it most of my frustration is that
 these details are only getting looked at now, when I have a week (and
 an otherwise very busy week) to fix all this stuff, when this module
 has been officially in review for the past two weeks and unofficially
 for several months. I would be much more open to this process if the
 issues raised could be fixed at my leisure rather than on a hard and
 tight deadline. This is exacerbated by the fact that I have another
 important, unrelated deadline, also next Friday.

 At the same time, though, I'm afraid that if we didn't fix a vote date
 and put some urgency into things, the pace of the reviews would be
 glacial at best, like it was for the first two weeks of official review
 and the months of unofficial review.


 
 Exactly. I understand. Well here's a suggestion. How about we "git
 stash" this review? I recall another submission was vying for the queue
 so we can proceed with that while you have time to operate the changes
 you want. If not, we can simply wait 2-3 weeks and then have you
 resubmit for a shorter process (1-2 weeks) that would gather more
 feedback (hopefully minor that time) and votes.
 
 Lars?


Sounds good.  I'll make the announcement.

-Lars
Mar 20 2011
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 Furthermore, you should expect that the review process will prompt
 changes. My perception is that you consider the submission more or less
 final modulo possibly a few minor nits. You shouldn't. I'm convinced you
 know much more about SMP than most or all others in this group, but in
 no way that means your design has reached perfection and is beyond
 improvement even from a non-expert.


In addition the the deadline issues already mentioned and resolved, I 
did misunderstand the review process somewhat.  I didn't participate in 
the reviews for std.datetime (because I know nothing about what makes a 
good date/time lib) or for std.unittest (because I was fairly ambivalent 
about it), so I didn't learn anything from them.  I was under the 
impression that the module is **expected** to be very close to its final 
form and that, if a lot of issues are found, then that basically means 
the proposal is going to be rejected.
Mar 19 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 19 March 2011 17:31:18 dsimcha wrote:

 On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 Furthermore, you should expect that the review process will prompt
 changes. My perception is that you consider the submission more or less
 final modulo possibly a few minor nits. You shouldn't. I'm convinced you
 know much more about SMP than most or all others in this group, but in
 no way that means your design has reached perfection and is beyond
 improvement even from a non-expert.


 
 In addition the the deadline issues already mentioned and resolved, I
 did misunderstand the review process somewhat.  I didn't participate in
 the reviews for std.datetime (because I know nothing about what makes a
 good date/time lib) or for std.unittest (because I was fairly ambivalent
 about it), so I didn't learn anything from them.  I was under the
 impression that the module is **expected** to be very close to its final
 form and that, if a lot of issues are found, then that basically means
 the proposal is going to be rejected.


Both std.datetime and std.unittests underwent a fair number of changes over the 
course the review process. A lot of the stuff stayed the same, but a lot of it 
changed too. On the whole, though, the end results were much better for it.

- Jonathan M Davis
Mar 19 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 19 March 2011 17:31:18 dsimcha wrote:

 On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 Furthermore, you should expect that the review process will prompt
 changes. My perception is that you consider the submission more or less
 final modulo possibly a few minor nits. You shouldn't. I'm convinced you
 know much more about SMP than most or all others in this group, but in
 no way that means your design has reached perfection and is beyond
 improvement even from a non-expert.


 
 In addition the the deadline issues already mentioned and resolved, I
 did misunderstand the review process somewhat.  I didn't participate in
 the reviews for std.datetime (because I know nothing about what makes a
 good date/time lib) or for std.unittest (because I was fairly ambivalent
 about it), so I didn't learn anything from them.  I was under the
 impression that the module is **expected** to be very close to its final
 form and that, if a lot of issues are found, then that basically means
 the proposal is going to be rejected.


Both std.datetime and std.unittests underwent a fair number of changes over the 
course the review process. A lot of the stuff stayed the same, but a lot of it 
changed too. On the whole, though, the end results were much better for it.

- Jonathan M Davis
Mar 19 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 8:48 PM, Jonathan M Davis wrote:

 On Saturday 19 March 2011 17:31:18 dsimcha wrote:

 On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 Furthermore, you should expect that the review process will prompt
 changes. My perception is that you consider the submission more or less
 final modulo possibly a few minor nits. You shouldn't. I'm convinced you
 know much more about SMP than most or all others in this group, but in
 no way that means your design has reached perfection and is beyond
 improvement even from a non-expert.


 In addition the the deadline issues already mentioned and resolved, I
 did misunderstand the review process somewhat.  I didn't participate in
 the reviews for std.datetime (because I know nothing about what makes a
 good date/time lib) or for std.unittest (because I was fairly ambivalent
 about it), so I didn't learn anything from them.  I was under the
 impression that the module is **expected** to be very close to its final
 form and that, if a lot of issues are found, then that basically means
 the proposal is going to be rejected.


 Both std.datetime and std.unittests underwent a fair number of changes over the
 course the review process. A lot of the stuff stayed the same, but a lot of it
 changed too. On the whole, though, the end results were much better for it.

 - Jonathan M Davis


Please check your newsreader settings.  You've been double-posting a lot 
lately.
Mar 19 2011
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 4:35 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 12:16 PM, dsimcha wrote:

 On 3/19/2011 12:03 PM, Andrei Alexandrescu wrote:

 On 03/19/2011 02:32 AM, dsimcha wrote:

 Ok, thanks again for clarifying **how** the docs could be improved.
 I've
 implemented the suggestions and generally given the docs a good reading
 over and clean up. The new docs are at:

 http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html


 * Still no synopsis example that illustrates in a catchy way the most
 attractive artifacts.


 I don't see what I could put here that isn't totally redundant with the
 rest of the documentation. Anything I could think of would basically
 just involve concatentating all the examples. Furthermore, none of the
 other Phobos modules have this, so I don't know what one should look
 like.


 I'm thinking along the lines of:

 http://www.digitalmars.com/d/2.0/phobos/std_exception.html

 A nice synopsis would be the pi computation. Just move that up to the
 synopsis. It's simple, clean, and easy to relate to. Generally, you'd
 put here not all details but the stuff you think would make it easiest
 for people to get into your library.


Good example, will do.


 * "After creation, Task objects are submitted to a TaskPool for
 execution." I understand it's possible to use Task straight as a
 promise/future, so s/are/may be/.


 No. The only way Task is useful is by submitting it to a pool to be
 executed. (Though this may change, see below.)


 I very much hope this does change. Otherwise the role of Task in the
 design could be drastically reduced (e.g. nested type inside of
 TaskPool) without prejudice. At the minimum I want to be able to create
 a task, launch it, and check its result later without involving a pool.
 A pool is when I have many tasks that may exceed the number of CPUs etc.
 Simplicity would be great.

 // start three reads
 auto readFoo = task!readText("foo.txt");
 auto readBar = task!readText("bar.txt");
 auto readBaz = task!readText("baz.txt");
 // join'em all
 auto foo = readFoo.yieldWait();
 auto bar = readBar.yieldWait();
 auto baz = readBaz.yieldWait();


This is definitely feasible in principle.  I'd like to implement it, but 
there's a few annoying, hairy details standing in the way.  For reasons 
I detailed previously, we need both scoped and non-scoped tasks.  We 
also have alias vs. callable (i.e. function pointer or delegate) tasks. 
  Now we're adding pool vs. new-thread tasks.  This is turning into a 
combinatorial explosion and needs to be simplified somehow.  I propose 
the following:

1.  I've reconsidered and actually like the idea of task() vs. 
scopedTask().  task() returns a pointer on the heap.  scopedTask() 
returns a struct on the stack.  Neither would be a member function of 
TaskPool.

2.  Non-scoped Task pointers would need to be explicitly submitted to 
the task pool via the put() method.  This means getting rid of 
TaskPool.task().

3.  The Task struct would grow a function runInNewThread() or something 
similar.  (If you think this would be a common case, even just execute() 
might cut it.)

The work flow would now be that you call task() to get a heap-allocated 
Task*, or scopedTask to get a stack-allocated Task.  You then call 
either TaskPool.put() to execute it on a pool or Task.runInNewThread() 
to run it in a new thread.  The creation of the Task is completely 
orthogonal to how it's run.


 There's no need at this level for a task pool. What would be nice would
 be to have a join() that joins all tasks spawned by the current thread:

 // start three reads
 auto readFoo = task!readText("foo.txt");
 auto readBar = task!readText("bar.txt");
 auto readBaz = task!readText("baz.txt");
 // join'em all
 join();
 // fetch results
 auto foo = readFoo.spinWait();
 auto bar = readBar.spinWait();
 auto baz = readBaz.spinWait();


I don't understand how this would be a substantial improvement over the 
first example, where you just call yieldWait() on all three. 
Furthermore, implementing join() as shown in this example would require 
some kind of central registry of all tasks/worker threads/task 
pools/something similar, which would be a huge PITA to implement 
efficiently.


 Secondly, I think you're reading **WAY** too much into what was meant to
 be a simple example to illustrate usage mechanics. This is another case
 where I can't think of a small, cute example of where you'd really need
 the pool. There are plenty of larger examples, but the smallest/most
 self-contained one I can think of is a parallel sort. I decided to use
 file reading because it was good enough to illustrate the mechanics of
 usage, even if it didn't illustrate a particularly good use case.


 It's impossible to not have a good small example. Sorting is great. You
 have the partition primitive already in std.algorithm, then off you go
 with tasks. Dot product on dense vectors is another good one. There's
 just plenty of operations that people understand are important to make
 fast.


I forgot about std.algorithm.partition.  This makes a parallel quick 
sort so trivial to implement (ignoring the issue of selecting a good 
pivot, which I think can be safely ignored in example code) that it 
might actually make a good example.



 * "A goto from inside the parallel foreach loop to a label outside the
 loop will result in undefined behavior." Would this be a bug in dmd?


 No, it's because a goto of this form has no reasonable, useful
 semantics. I should probably mention in the docs that the same applies
 to labeled break and continue.

 I have no idea what semantics these should have, and even if I did,
 given the long odds that even one person would actually need them, I
 think they'd be more trouble than they're worth to implement. For
 example, once you break out of a parallel foreach loop to some arbitrary
 address (and different threads can goto different labels, etc.), well,
 it's no longer a parallel foreach loop. It's just a bunch of completely
 unstructured threading doing god-knows-what.

 Therefore, I slapped undefined behavior on it as a big sign that says,
 "Just don't do it." This also has the advantage that, if anyone ever
 thinks of any good, clearly useful semantics, these will be
 implementable without breaking code later.


 Yah, I was actually thinking of disabling goto outside a local delegate
 everywhere.


See the discussion I'm having with Michael Fortin.  My latest idea is 
that break, labeled break/continue, return, and goto should all throw 
exceptions when found inside a parallel foreach loop.  They affect the 
flow of subsequent iterations, and "subsequent iterations" only makes 
sense when the loop is being executed in serial.


 * Again: speed of e.g. parallel min/max vs. serial, pi computation etc.
 on a usual machine?


 I **STRONGLY** believe this does not belong in API documentation because
 it's too machine specific, compiler specific, stack alignment specific,
 etc. and almost any benchmark worth doing takes up more space than an
 example should. Furthermore, anyone who wants to know this can easily
 time it themselves. I have absolutely no intention of including this.
 While in general I appreciate and have tried to accommodate your
 suggestions, this is one I'll be standing firm on.


 If scalability information is present in however a non-committal form,
 then people would be compelled ("ok, so this shape of the loop would
 actually scale linearly with CPUs... neat").


Ok, I thought you were asking for something much more rigorous than 
this.  I therefore didn't want to provide it because I figured that, no 
matter what I did, someone would be able to say that the benchmark is 
flawed some how, yada, yada, yada.  Given how inexact a science 
benchmarking is, I'm still hesitant to put such results in API docs, but 
I can see where you're coming from here.


 Speaking of efficiency, I assume parallel foreach uses opApply with a
 delegate and the inherent overhead. So I'm thinking that a practical way
 to take advantage of parallel foreach would be to parallelize at some
 block level and then do a regular foreach inside the block?

 foreach (i, ref elem; taskPool.parallel(logs)) {
 foreach (???)
 elem = log(i + 1.0);
 }

 How can I arrange things such that I compute e.g. 64 logs serially
 inside each pass?


Three things here:

1.  For this kind of nano-parallelism, map() might be better suited.  To 
fill an existing array, just use map's explicit buffer feature.

taskPool.map!log(iota(1, logs.length + 1), logs);

The option of using map() for nano-parallelism is part of my rationale 
for keeping the pretty but mildly inefficient delegate call in parallel 
foreach.

2.  You're severely overestimating the overhead of the delegate call.
log() is a pretty cheap function and even so speedups are decent with 
parallel foreach compared to a regular foreach loop.

import std.stdio, std.parallelism, std.datetime, std.math;


void main() {
     auto logs = new float[10_000_000];
     taskPool();  // Initialize TaskPool before timing.

     auto sw = StopWatch(autoStart);
     foreach(i, ref elem; logs) {
         elem = log(i + 1);
     }
     writeln("Serial:  ", sw.peek.msecs);

     sw.reset();
     foreach(i, ref elem; parallel(logs)) {
         elem = log(i + 1);
     }
     writeln("Parallel Foreach:  ", sw.peek.msecs);
}


Results:

Serial:  619
Parallel Foreach:  388

I'd include parallel map, too, but for some reason (probably stack 
alignment or something) including it changes the results for parallel 
foreach.

3.  If you really want to do as you suggest, just make a chunks range or 
something (maybe this should be in std.range) that iterates over all 
non-overlapping size N slices of a sliceable range.  Use this for the 
parallel loop, then loop over the individual elements of the slice inside.


 I'm confused here. I use join() pretty much all the time. I launch stuff
 (e.g. run a large matrix-vector multiplication for distinct vectors) and
 then I join that. Then again and again. The thread of execution has a
 repeated hourglass shape - it fans out and then becomes single-threaded
 at join points. I assume some of those computations are indeed the
 charter of parallel foreach, but I'd guess not all. But then what do I
 know - I'm the customer :o).


Yes, parallel foreach is idiomatic here, or maybe parallel map.

In the pre-release versions of std.parallelism (my experimentation with 
parallelism libraries in D goes back to mid-2008, over a year before I 
released the first version as Parallelfuture), only the task primitive 
existed.  I discovered that, in practice, creating Task objects in a 
loop is almost always a PITA.  It can also be inefficient in that, in a 
naive implementation all of these exist in memory simultaneously when 
this might be completely unnecessary.  I decided to create higher level 
primitives to handle all the use cases I could think of where you might 
otherwise want to create Task objects in a loop.  If you're explicitly 
creating Task objects in a loop in std.parallelism, I can just about 
guarantee that there's an easier and at least equally efficient way to 
accomplish what you want to accomplish.  If there are any important use 
cases I missed, I'd be much more interested in creating a few more 
high-level primitives rather than making it easier to work with Task 
objects created in a loop.
Mar 19 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 10:16 PM, dsimcha wrote:

 * Again: speed of e.g. parallel min/max vs. serial, pi computation etc.
 on a usual machine?


 I **STRONGLY** believe this does not belong in API documentation because
 it's too machine specific, compiler specific, stack alignment specific,
 etc. and almost any benchmark worth doing takes up more space than an
 example should. Furthermore, anyone who wants to know this can easily
 time it themselves. I have absolutely no intention of including this.
 While in general I appreciate and have tried to accommodate your
 suggestions, this is one I'll be standing firm on.


 If scalability information is present in however a non-committal form,
 then people would be compelled ("ok, so this shape of the loop would
 actually scale linearly with CPUs... neat").


 Ok, I thought you were asking for something much more rigorous than
 this. I therefore didn't want to provide it because I figured that, no
 matter what I did, someone would be able to say that the benchmark is
 flawed some how, yada, yada, yada. Given how inexact a science
 benchmarking is, I'm still hesitant to put such results in API docs, but
 I can see where you're coming from here.


I tried putting a few benchmarks in for the performance of parallel 
foreach, map and reduce.  Basically, I just put the timings in for the 
examples on my dual core machine, and for an equivalent serial version 
that is not shown in the interest of brevity but is easily inferred.  I 
didn't do this for the pipelining or future/promise primitives because 
these aren't as capable of automatically taking full advantage of as 
many cores as you can throw at them as map, reduce and foreach.  This 
means that coming up with a benchmark that shows where a good speedup 
can be obtained is a much more difficult art.
Mar 20 2011
prev sibling next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 3/19/2011 12:03 PM, Andrei Alexandrescu wrote:

 * "workUnitSize: The number of elements to evaluate in a single Task.
 Must be less than or equal to bufSize, and in practice should be a
 fraction of bufSize such that all worker threads can be used." Then why
 not specify a different parameter such a multiplier or something? The
 dependence between bufSize and worUnitSize is a sign that these two
 should be improved. If you have good reasons that the user must have the
 parameters in this form, give an example substantiating that.


I did this for consistency with all the other functions, where work unit 
size is specified directly.  I don't want lazyMap to be the oddball 
function where it's specified in a completely different way.
Mar 19 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 19 March 2011 09:03:51 Andrei Alexandrescu wrote:

 On 03/19/2011 02:32 AM, dsimcha wrote:

 Ok, thanks again for clarifying **how** the docs could be improved. I've
 implemented the suggestions and generally given the docs a good reading
 over and clean up. The new docs are at:
 
 http://cis.jhu.edu/~dsimcha/d/phobos/std_parallelism.html


 
 * When using "parallelism" as a common noun, prefix is with a '_' so
 ddoc doesn't underline it.


Oooh. That's a neat trick. I didn't know that you could do that.

- Jonathan M Davis
Mar 19 2011