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.
