REPL: null-values in parallel ranges?

Hi Johannes,

On Sun, Apr 10, 2011 at 9:24 AM, Johannes Rudolph
wrote:
> On Fri, Apr 8, 2011 at 7:00 PM, Bill Venners wrote:
>> I'm guessing one of the styles that people will want to use with
>> parallel collections is parallel functional style methods with
>> sequential foreach, because it is easier and less error prone.
>
> I understand where you are getting at, actually that's what I thought
> before myself. But I changed my mind and I think we now disagree
> whether one has to worry about programmers who deliberately used
> '.par' to make their collection parallel and then fail to understand
> the consequences of using `foreach` on this collection. Especially
> when the choice is to give up consistency, instead, I'd wager for
> consistency. Shooting yourself in the foot with concurrency is easy
> enough anyways.
>
There may still be a design that gives you both consistency,
convenience, and safety that hasn't been suggested yet. That would be
ideal.

> The rules I posted before were for the other cases (which I'm more
> worried about to get things right from the beginning): the cases where
> the person calling `.par` is not the one writing the code using the
> collection in the end. Here we should have some advice how to handle
> those cases correctly without running into the parallel foreach trap.
>
> BTW: Given we had `.pfor`: In a library method you want to loop over a
> collection passed into the method. Now you write the loop body and
> know it is thread-safe. Still you don't want to make the traversal
> parallel in every case (as parallel calculations come with a price)
> but you want the caller of the method to decide which that is. How
> would you do that elegantly with `.pfor`?
>
AnySeq would mean a collection that could be either parallel or
sequential, and whose foreach could be parallel or sequential. So that
does let the caller decide. I'm not sure how often people will want to
use AnySeq, AnyMap, etc., on APIs versus letting the parallelism be an
implementation decision taken to improve performance. I'm certainly
not planning on changing the collection types up to AnyX in APIs any
time soon, though I will try and see what kind of performance benefits
I can get from them internally.

The trouble with pfor, though, is not just that it makes .par
inconsistent but that it also complicates the space of possibilities.
If you do take an AnySeq, you may want to make sure it has a
sequential for. So you'd want to be able to call .sfor on it. So
you'd need both sfor and pfor. I'm guessing we might want to use the
Parallel marker trait to recognize a parallel collection in a pattern
match. Well you might reasonably want to be able to recognize a
parallel collection with a sequential foreach also. So you'd need
ParallelForeach and SequentialForeach traits? There are too many
combinations.

Perhaps the best best design seen so far is simply the original one
EPFL had at some point prior to 2.9.0.RC1. Foreach is always
sequential, and parallel collections also have a pforeach that gives
you a parallel foreach. Now the space is just two kinds of collection,
sequential and parallel. Though the contract of foreach still would
allow for parallel collections, as it always has, foreach would always
be sequential on any collection coming from the Scala API.

To those worried about inconsistency of .par, I'd suggest you look at
your existing code and count how many uses of these methods are
already ready to be run in parallel. In my code I'd guess more than 99
out of 100 times my uses of functional-style methods like map,
flatMap, and filter, etc., are already ready to be run in parallel.
But on foreach, more than 99 times out of 100 times it would NOT be
ready to be run in parallel. I think that's not just because I haven't
been thinking about it. It's because that's how I want to use foreach.
99 times out of 100 I actually want a sequential foreach no matter
whether the rest of the collection is sequential or parallel. So to
force people to say .seq .seq .seq .seq .seq .seq .seq in their for
loops 99 times just so they don't have to say it the one time they
want a parallel for lop is inconvenient as well as error prone. Or put
another way, a .par that gives you a parallel foreach is inconsistent
with how people will most often want to *use* parallel collections.

I've seen three examples shown so far that justify the need for a
parallel foreach. There are others, but these are cherry picked. How
often do you think you'd need to use a parallel foreach to scale an
array?

for (i <- (0 until a.length).par)
a(i) = a(i) * scale

Probably in less than 1 out of a 100 for loops. And frankly, except on
large arrays for which you actually have evidence it matters to
performance, it would probably be premature optimization to do it that
way instead of:

a map (_ * scale)

How often would you feel the need to do an exists like this:

@volatile var flag = false
for (i <- (0 until a.length).par)
if (a(i) < 0) flag = true

Instead of:

a exists (_ < 0)

The earlier one is a performance optimization, which if you don't have
actual evidence of a performance problem I'd call a premature
optimization. It is more complicated to read than the latter, and more
error prone. Or how often would you feel the need to do this:

@volatile var sum = 0
for (i <- (0 until a.length).par)
sum += a(i)

Instead of:

a.sum

Again it is a performance optimization that is more verbose and error
prone than the functional alternative. And speaking of error prone,
are you sure you'd want to run that for loop in parallel?

This seems useful:

val cmap = new java.util.concurrent.ConcurrentHashMap[Int, Int]
for (i <- (0 until n).par)
cmap.put(i, i)

But looking at your existing code again, how often have you been
populating a concurrent collection like this? From time to time, but
likely less than 1 in a 100 for loops. Moreover, if you don't actually
have evidence there's a performance problem, I'd say a sequential
population would be just as good:

val cmap = new java.util.concurrent.ConcurrentHashMap[Int, Int]
for (i <- 0 until n)
cmap.put(i, i)

That said, one thing that bugged me about pforeach is I couldn't use a
parallel foreach via a for expression. But truth is, making pforeach a
tad uglier might be good from human factors perspective. It would
discourage its use. But on the other hand, if it is just being used
now and then when there is evidence of a performance problem, this
code isn't too bad looking:

(0 until a.length) pforeach { i =>
a(i) = a(i) * scale
}

Moreover, the pforeach design doesn't mean you absolutely can't get a
parallel foreach out of a for expression, just that you couldn't get
one out of the collections coming from the Scala API. The 2.8
collections design makes it quite straightforward to create your own
collection implementations, and the contract for foreach allows a
parellel implementation. If you're doing some image processing where
you need to do a bunch of scaling on large arrays, with just a few
lines of code you could create your own AnySeq on which foreach
forwards to pforeach. Then you could do this:

val a = MyParallelForeachAnySeq(originalA)
for (i <- 0 until a.length)
a(i) = a(i) * scale

So it would be possible. But requiring people to say pforeach or write
their own wrapper class to get a parallel for loop would be enough
resistence to push people towards using sequential foreach most of the
time, and I think that's important, because people make mistakes.
Making a parallel foreach the default for .par is kind of like putting
the pilot eject button right next to the intercom button on an
airplane cockpit. You probably want to put the eject button behind a
little door at the very least.

Everything has software in it nowadays, and over time more and more
apps will be running on multi-core CPUs, so I expect languages like
Scala, Clojure, Fortress, etc., are going to be used more and more.
The more Scala gets used, the greater chance that programming errors
will do serious harm. Scala code could show up in an airplane someday,
or an nuclear power plant, or a spacecraft, or a chain saw. Scala code
will be written by all kinds of programmers, including ones who don't
quite understand threads well. Even the programmers that do understand
threads well are human and will from time to time make mistakes. If
the convenience argument doesn't sway you, then hopefully the safety
one will.

Bill

>
> --
> Johannes
>
> -----------------------------------------------
> Johannes Rudolph
> http://virtual-void.net
>

Hi Johannes,

On Sun, Apr 10, 2011 at 9:24 AM, Johannes Rudolph
wrote:
> On Fri, Apr 8, 2011 at 7:00 PM, Bill Venners wrote:
>> I'm guessing one of the styles that people will want to use with
>> parallel collections is parallel functional style methods with
>> sequential foreach, because it is easier and less error prone.
>
> I understand where you are getting at, actually that's what I thought
> before myself. But I changed my mind and I think we now disagree
> whether one has to worry about programmers who deliberately used
> '.par' to make their collection parallel and then fail to understand
> the consequences of using `foreach` on this collection. Especially
> when the choice is to give up consistency, instead, I'd wager for
> consistency. Shooting yourself in the foot with concurrency is easy
> enough anyways.
>
There may still be a design that gives you both consistency,
convenience, and safety that hasn't been suggested yet. That would be
ideal.

> The rules I posted before were for the other cases (which I'm more
> worried about to get things right from the beginning): the cases where
> the person calling `.par` is not the one writing the code using the
> collection in the end. Here we should have some advice how to handle
> those cases correctly without running into the parallel foreach trap.
>
> BTW: Given we had `.pfor`: In a library method you want to loop over a
> collection passed into the method. Now you write the loop body and
> know it is thread-safe. Still you don't want to make the traversal
> parallel in every case (as parallel calculations come with a price)
> but you want the caller of the method to decide which that is. How
> would you do that elegantly with `.pfor`?
>
AnySeq would mean a collection that could be either parallel or
sequential, and whose foreach could be parallel or sequential. So that
does let the caller decide. I'm not sure how often people will want to
use AnySeq, AnyMap, etc., on APIs versus letting the parallelism be an
implementation decision taken to improve performance. I'm certainly
not planning on changing the collection types up to AnyX in APIs any
time soon, though I will try and see what kind of performance benefits
I can get from them internally.

The trouble with pfor, though, is not just that it makes .par
inconsistent but that it also complicates the space of possibilities.
If you do take an AnySeq, you may want to make sure it has a
sequential for. So you'd want to be able to call .sfor on it. So
you'd need both sfor and pfor. I'm guessing we might want to use the
Parallel marker trait to recognize a parallel collection in a pattern
match. Well you might reasonably want to be able to recognize a
parallel collection with a sequential foreach also. So you'd need
ParallelForeach and SequentialForeach traits? There are too many
combinations.

Perhaps the best best design seen so far is simply the original one
EPFL had at some point prior to 2.9.0.RC1. Foreach is always
sequential, and parallel collections also have a pforeach that gives
you a parallel foreach. Now the space is just two kinds of collection,
sequential and parallel. Though the contract of foreach still would
allow for parallel collections, as it always has, foreach would always
be sequential on any collection coming from the Scala API.

To those worried about inconsistency of .par, I'd suggest you look at
your existing code and count how many uses of these methods are
already ready to be run in parallel. In my code I'd guess more than 99
out of 100 times my uses of functional-style methods like map,
flatMap, and filter, etc., are already ready to be run in parallel.
But on foreach, more than 99 times out of 100 times it would NOT be
ready to be run in parallel. I think that's not just because I haven't
been thinking about it. It's because that's how I want to use foreach.
99 times out of 100 I actually want a sequential foreach no matter
whether the rest of the collection is sequential or parallel. So to
force people to say .seq .seq .seq .seq .seq .seq .seq in their for
loops 99 times just so they don't have to say it the one time they
want a parallel for lop is inconvenient as well as error prone. Or put
another way, a .par that gives you a parallel foreach is inconsistent
with how people will most often want to *use* parallel collections.

I've seen three examples shown so far that justify the need for a
parallel foreach. There are others, but these are cherry picked. How
often do you think you'd need to use a parallel foreach to scale an
array?

for (i <- (0 until a.length).par)
a(i) = a(i) * scale

Probably in less than 1 out of a 100 for loops. And frankly, except on
large arrays for which you actually have evidence it matters to
performance, it would probably be premature optimization to do it that
way instead of:

a map (_ * scale)

How often would you feel the need to do an exists like this:

@volatile var flag = false
for (i <- (0 until a.length).par)
if (a(i) < 0) flag = true

Instead of:

a exists (_ < 0)

The earlier one is a performance optimization, which if you don't have
actual evidence of a performance problem I'd call a premature
optimization. It is more complicated to read than the latter, and more
error prone. Or how often would you feel the need to do this:

@volatile var sum = 0
for (i <- (0 until a.length).par)
sum += a(i)

Instead of:

a.sum

Again it is a performance optimization that is more verbose and error
prone than the functional alternative. And speaking of error prone,
are you sure you'd want to run that for loop in parallel?

This seems useful:

val cmap = new java.util.concurrent.ConcurrentHashMap[Int, Int]
for (i <- (0 until n).par)
cmap.put(i, i)

But looking at your existing code again, how often have you been
populating a concurrent collection like this? From time to time, but
likely less than 1 in a 100 for loops. Moreover, if you don't actually
have evidence there's a performance problem, I'd say a sequential
population would be just as good:

val cmap = new java.util.concurrent.ConcurrentHashMap[Int, Int]
for (i <- 0 until n)
cmap.put(i, i)

That said, one thing that bugged me about pforeach is I couldn't use a
parallel foreach via a for expression. But truth is, making pforeach a
tad uglier might be good from human factors perspective. It would
discourage its use. But on the other hand, if it is just being used
now and then when there is evidence of a performance problem, this
code isn't too bad looking:

(0 until a.length) pforeach { i =>
a(i) = a(i) * scale
}

Moreover, the pforeach design doesn't mean you absolutely can't get a
parallel foreach out of a for expression, just that you couldn't get
one out of the collections coming from the Scala API. The 2.8
collections design makes it quite straightforward to create your own
collection implementations, and the contract for foreach allows a
parellel implementation. If you're doing some image processing where
you need to do a bunch of scaling on large arrays, with just a few
lines of code you could create your own AnySeq on which foreach
forwards to pforeach. Then you could do this:

val a = MyParallelForeachAnySeq(originalA)
for (i <- 0 until a.length)
a(i) = a(i) * scale

So it would be possible. But requiring people to say pforeach or write
their own wrapper class to get a parallel for loop would be enough
resistence to push people towards using sequential foreach most of the
time, and I think that's important, because people make mistakes.
Making a parallel foreach the default for .par is kind of like putting
the pilot eject button right next to the intercom button on an
airplane cockpit. You probably want to put the eject button behind a
little door at the very least.

Everything has software in it nowadays, and over time more and more
apps will be running on multi-core CPUs, so I expect languages like
Scala, Clojure, Fortress, etc., are going to be used more and more.
The more Scala gets used, the greater chance that programming errors
will do serious harm. Scala code could show up in an airplane someday,
or an nuclear power plant, or a spacecraft, or a chain saw. Scala code
will be written by all kinds of programmers, including ones who don't
quite understand threads well. Even the programmers that do understand
threads well are human and will from time to time make mistakes. If
the convenience argument doesn't sway you, then hopefully the safety
one will.

Bill

>
> --
> Johannes
>
> -----------------------------------------------
> Johannes Rudolph
> http://virtual-void.net
>

Hi Seth,

On Fri, Apr 8, 2011 at 11:59 AM, Seth Tisue wrote:
>>>>>> "Bill" == Bill Venners writes:
>
>  Bill> But certainly if .par gives parallel everything in 2.9, including
>  Bill> foreach, you wouldn't need something like .sfor in 2.9. If it
>  Bill> turned out to be useful after people get real experience, it
>  Bill> could be added later. But once .par gives parallel everything it
>  Bill> can't be changed, and right there is the big decision for 2.9 I
>  Bill> think.
>
> ".par gives parallel everything" is consistent and simple, and did I
> mention consistent?  I'm not seeing the case for doing it any other way.
>
Simple to understand, yes, but to use?

> As you point out:
>
>  Bill> Downside is this code would be misleading:
>  Bill> for (i <- (1 until 10000).par) a(i) = a(i) * scale
>
> For this not to run in parallel would verge on bizarre, IMO.
>
> Parallel is parallel.
>
Yes, it sure looks like that should run in parallel. If .par means
fully parallel, then another method could mean "functional methods in
parallel and foreach sequential". fpar perhaps. 2.9 could provide just
.par and if experience shows people could use a second method it could
be added later.

Bill

> --
> Seth Tisue | Northwestern University | http://tisue.net
> lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/
>