On 3/23/2011 9:09 AM, Jason House wrote:
dsimcha Wrote:
Some discussions about std.parallelism have prompted an examination of
how far D's guarantees against low level data races should extend and
how safety and practicality should be balanced.
I didn't follow the review of std.parallelism, can you give some specific
examples?
Users of languages look to standard libraries as a model for how to write their
own apps. I don't like your proposal and think std.parallelism should use
shared properly. I'd like to understand better what your issues with shared
were. I've done a descent amount of shared-correct code, so I'm pretty sure
it's usable. In fact, the only really nasty bug I had could have been caught if
std.thread had been shared-correct...
I have already decided that, unless shared is drastically improved in
ways I don't foresee (I'm not even sure exactly how, this would need to
be discussed), I will not be making std.parallelism shared correct. I
put some serious thought into this issue before making the proposal and
concluded that, for even moderately fine-grained parallelism, shared
would get in the way more than it helps. shared has its place if you're
primarily using message passing and using shared state in only a very
limited number of places, but IMHO that's the only way it helps more
than it gets in the way.
If it comes down to a choice between the two (I hope I don't have to
make this choice), I'd rather have std.parallelism be a useful 3rd party
lib than an unusable bondage-and-discipline Phobos module. If someone
else wants to fork it and try to make it shared correct, that's their
prerogative.
Remember, D is a **SYSTEMS LANGUAGE**. There is no excuse for it going
out of its way to make certain paradigms as difficult as possible, or
not supporting them, just because they're dangerous. If that's the
direction we're going in, why don't we rip pointer arithmetic, inline
ASM, unsafe casts, manual memory management, etc. out of the language
and call ourselves Java++? IMHO making shared-correctness mandatory
unless you fight the type system every inch of the way would be going in
that direction with regard to concurrency. core.thread is a low-level
druntime module. If you wanted shared-correct multithreading, you
should have been using std.concurrency. If std.concurrency wasn't
enough to get the job done, then that's proof that shared is only useful
if you're mostly using message passing and occasionally shared state.
Some examples:
// This is my example for parallel foreach.
auto logs = new double[1_000_000];
foreach(i, ref elem; parallel(logs)) {
elem = log(i + 1);
}
Here you have multiple threads writing to the same array in parallel.
They're guaranteed never to write to the same element, though, making it
safe except on some obscure/ancient hardware that we don't care about
(e.g. old DEC Alphas) that can't write to memory at byte granularity.
Yes, I'm aware of the false sharing issue with writing to adjacent
addresses from different threads. This is not a problem for this
example because these falsely shared writes will be such a small portion
of all writes that the performance impact is negligible. Making all
updates atomic/fenced/whatever shared does would be a huge performance
hit for no benefit, and would make the code more verbose and type heavy.
// This is a parallel quick sort. Again, it writes to a data
// structures from multiple threads, but in a way that guarantees no
// element is "owned" by two threads at the same time.
void parallelSort(T)(T[] data) {
// Sort small subarrays serially.
if(data.length < 100) {
std.algorithm.sort(data);
return;
}
// Partition the array.
swap(data[$ / 2], data[$ - 1]);
auto pivot = data[$ - 1];
bool lessThanPivot(T elem) { return elem < pivot; }
auto greaterEqual = partition!lessThanPivot(data[0..$ - 1]);
swap(data[$ - greaterEqual.length - 1], data[$ - 1]);
auto less = data[0..$ - greaterEqual.length - 1];
greaterEqual = data[$ - greaterEqual.length..$];
// Execute both recursion branches in parallel.
auto recurseTask = task!(parallelSort)(greaterEqual);
taskPool.put(recurseTask);
parallelSort(less);
recurseTask.yieldForce();
}
// Read in a file in a background thread and return the results in a
// mutable, non-shared array that the caller can then process further.
import std.file, std.parallelism;
void main() {
// Create and submit a Task object for reading foo.txt.
auto file1Task = task(&read, "foo.txt");
file1Task.executeInNewThread();
// Read bar.txt in parallel.
auto file2Data = read("bar.txt");
// Get the results of reading foo.txt.
auto file1Data = file1Task.yieldForce();
}
