REPL: null-values in parallel ranges?

Hi Again,

In thinking further, I think the way this would have to work is the
extra method idea that was proposed earlier, and Martin said they
considered but rejected. The approach would be:

Tighten the foreach contract to require in-order execution.

Add a pareach method or something that does foreach but in a parallel
way. Maybe this is in trait Parallel so all Parallel things have to
implement it. And this is the method a for expression would translate
to invocations of if the generator type is Parallel, not invocations
of foreach.

Bill

On Sat, Apr 2, 2011 at 8:07 PM, Bill Venners wrote:
> Hi Paul,
>
> Actually I said that wrongly. I meant that if I really want to do a
> parallel foreach on a Seq type that doesn't extend Parallel, I could
> write it like this:
>
> for (e <- ls.par) {
>  // some thread-safe side-effecting code
> }
>
> The example I showed was a method that took a Parallel Seq already.
>
> Bill
>
> On Sat, Apr 2, 2011 at 8:03 PM, Bill Venners wrote:
>> Hi Paul,
>>
>> I'm not sure how to implement it, but I wonder if the following
>> behavior would make sense: have for expression rewriting rules for
>> foreach take into account whether the generator mixes in the Parallel
>> marker trait.
>>
>> scala> import scala.collection.Parallel
>> import scala.collection.Parallel
>>
>> scala> val ls = List(1, 2, 3, 4)
>> ls: List[Int] = List(1, 2, 3, 4)
>>
>> scala> ls.isInstanceOf[Parallel]
>> res3: Boolean = false
>>
>> scala> val pls = ls.par
>> pls: scala.collection.parallel.immutable.ParSeq[Int] = ParVector(1, 2, 3, 4)
>>
>> scala> pls.isInstanceOf[Parallel]
>> res5: Boolean = true
>>
>> If I do this:
>>
>> for (e <- ls) println(e)
>>
>> This would somehow cause a an in-order execution, because the type of
>> ls doesn't mix in Parallel.
>>
>> But if I do this:
>>
>> for (e <- pls) println(e)
>>
>> It would happen in Parallel, because the type of generator pls mixes
>> in Parallel. That way if people have a method that takes a Seq[T],
>> say, and uses that in a for expression, then because Seq[T] isn't a
>> subtype of Parallel, it would do it in order (somehow). That means all
>> old code should not break.
>>
>> def oldMethod(seq: Seq[String]) { for (e <- seq) println(e) }
>>
>> But new code that really wants parallel execution could just do .par
>> on that Seq[T], which would somehow kick it into parallel execution.
>>
>> def newMethod(pSeq: Seq[String] with Parallel) { for (e <- pSeq) println(e) }
>>
>> By saying the method takes a Seq[String] with Parallel, it is
>> announcing that it might do foreaches in parallel.
>>
>> I think it would be fine to let flatMap, filter, withFilter, map be
>> rewritten in the same way, because most times people wouldn't have
>> side effects in those. But foreach is all about the side effects.
>>
>> Bill
>>
>> On Sat, Apr 2, 2011 at 7:49 PM, Paul Phillips wrote:
>>> On 4/2/11 1:00 PM, martin odersky wrote:
>>>>
>>>> But yes, it is a worry that we'll have to think about this issue now
>>>> everywhere. Hopefully, it will translate into a much stronger push to be
>>>> fully functional.
>>>
>>> For the record I don't mind worrying about it everywhere from now on. I'm
>>> all for it.  I just don't want to spend the rest of my life fixing bugs in
>>> pre-existing code.
>>>
>>>> If you write
>>>>
>>>> for  { x <- pxs } ...
>>>>
>>>> where pxs is a parallel collection you expect the loop to be parallel.
>>>> So foreach needs to be parallel.
>>>
>>> That tells me the foreach at the base of the parallel collections has to be
>>> parallel, but not that the foreach we already have has to be.  If that's the
>>> main motivation then we can re-root the parallel collections around a
>>> parallel foreach.  I already pushed foreach backward for TraversableOnce,
>>> I'd be glad to push it sideways for this one.
>>>
>>> There's another interesting tie-in here, which I already had on my agenda
>>> for a while, ever since looking too closely at slice.  There is a real issue
>>> with having the same trait provide default implementations for both mutable
>>> and immutable collections.  The default implementation is either outright
>>> wrong or grossly inefficient half the time.  So the side which was not
>>> chosen as the favorite side has to be sure every method implementation is
>>> overridden (and many bugs have been the result of not achieving this.) But
>>> what is the point of having default implementations if they are menaces
>>> which must be guarded against half the time?
>>>
>>> Example.  What is the default implementation of tail? There are pretty much
>>> two choices.
>>>
>>>  // if this is a mutable seq, you're now sharing mutable cells
>>>  def tail = pointer to the second element of this collection
>>>  // if this is an immutable seq, you're now copying a billion
>>>  // elements for no reason
>>>  def tail = copy this entire collection except the first
>>>
>>> For almost every method in TraversableLike this same issue arises.  (The
>>> methods where one can safely use the same implementation are generally folds
>>> and other chew-up-the-sequence methods, and those are in TraversableOnce.)
>>> The conclusion I drew is that the mutable and immutable collections should
>>> not share any code past TraversableOnce. They should (according to this
>>> theory) share a pure interface in TraversableLike and each have their own
>>> default implementations.
>>>
>>> So back to the parallel foreach problem: same thing.
>>>
>>>  trait MutableTraversableLike extends TraversableMethods
>>>  trait ImmutableTraversableLike extends TraversableMethods
>>>  trait ParallelTraversableLike extends TraversableMethods
>>>
>>> (I won't speculate on whether it should really be
>>> ParallelImmutableTraversableLike and so on or how these might compose unless
>>> I see a glimmer of hope we could go this way.)
>>>
>>>
>>
>>
>>
>> --
>> Bill Venners
>> Artima, Inc.
>> http://www.artima.com
>>
>
>
>
> --
> Bill Venners
> Artima, Inc.
> http://www.artima.com
>

Hi All,

On Sat, Apr 2, 2011 at 11:55 PM, HamsterofDeath wrote:
> that is convincing that something has to be fixed. the question is what.
> making foreach sequencial pretty much makes any parallel collection
> sequencial again because many methods are based on foreach.
>
I think that's OK, because those implementations can be changed so
they don't rely on foreach, either prior to 2.9.0.final or after. The
penalty before that is they wouldn't be as fast as the parallel
foreach versions, but they'd be as fast as they are now in 2.8. I can
live with that.

I slept on this and fleshed this proposal out a bit more in my mind.
Traversable is at the top of the hierarchy, and its abstract method is
foreach. So there's nothing to define the order other than foreach
itself. So there I think it's contract would need to stay the same:

Applies a function f to all elements of this collection.

Or, state that it will run sequentially not in parallel, but without
specifying any order:

Applies a function f to all elements of this collection sequentially
in an undefined order (but not in parallel).

Iterable however adds the iterator method, and that defines an order.
The contract of foreach in both Iterator could be changed from:

Applies a function f to all values produced by this iterator.

to:

Applies a function f to all values produced by this iterator
sequentially in the order returned by repeated invocations of the next
method.

And the contract of Iterable's foreach could be changed from:

Applies a function f to all elements of this iterable collection.

to:

Applies a function f to all elements of this iterable collection
sequentially in the order returned by repeated invocations of the next
method on the iterator returned by the iterator method.

Add a foreachParallel method to Iterator that has the contract:

Applies a function f to all elements of this collection in parallel.

And add a foreachParallel method to Iterable that has the contract:

Applies a function f to all elements of this iterable collection in parallel.

The rules for for expression translation could be left alone, at least
for now. What that would mean is that anytime you don't have a yield,
which would result in a foreach called, you'd get sequential behavior,
at least for the foreach part. That again could mean some things might
run more slowly than if they were parallelized, but I'm OK with that.
They'd run as fast as they are running now. And if someone wants to
really parallelize a side effecting loop, they could just invoke
foreachParallel passing in a function rather than using a for
expression.

I don't have a problem with map, flatMap, filter, withFilter, and any
other "data transformation" style higher order functions on
collections doing things sequentially or in parallel depending on the
type of the object. Most likely some people have written code that
does a map, for example, and passes a transformation function to it
that has a side effect. That code will break and I think we should
allow that to happen. It should be very little code I'd guess, because
people usually just pass data transformers to methods like map. And it
is worth it.

But foreach is not about data transformation. It's about side effects.
Because it doesn't have a result, if it doesn't have a side effect it
has no impact on the program other than heating up the CPU. And to do
that kind of loop in parallel means you have to write thread safe
code. No one has been doing that, and it would be very hard to do in
the future. And it would be non-intuitive because this looks like
sequential-in-order for loops in any other language anyone would be
coming from:

for (arg <- args)
println(arg)

I think this really ought to keep working like it always has, printing
out args in iterator order, no matter the type of args. Yesterday I
was asking how I would get sequential behavior out of a for
expression. Well the above bit of code should be how. That's how
everyone expects to get an in-order execution.

Narrowing the contracts of foreach in Traversable, Iterator, and
Iterable could break some code, but I doubt much. What it in effect
does is change it to the contract that's been in people's heads, which
they've been programming to. I think much more code could break, and
sometimes in hard -to-catch, subtle ways, if a collection you are
passed does foreach in parallel.

I don't know the details of how parallel collections are implemented,
but I'm hopeful that the places where data transformation methods are
implemented in terms of foreach, an invocation of foreachParallel
could easily be substituted. Then you'd get your same parallel
behavior back for those method that we have now in RC1.

What do folks think? Would that address the problem sufficiently?

Bill

> creating a branched (singlethreadtravlike, parthreadtravlike) hierachy
> would make it impossible to use parallel collections where the api
> designer wanted to use single threaded ones but on the other hand
> sacrifice compatibility with old code. the old collections would all be
> single threaded ones, and in old code you could not use parallel ones,
> even if you knew it would work.
>
> the solution could be something like:
> some collection methods could be annotated with @OnlySeq (like "zipped"
> in the broken example), which would add a compile time conversion and a
> runtime assertion. in the case of zipped, it's clear you want to keep
> the order of both ranges so you annotate the method with @OnlySeq. the
> compiler knows using parallel ranges makes no sense here -> compiler
> warning and/or compiler inserted conversion to seq if you do it anyway.
> if the collection is not explicitly declared as parallel, the compiler
> cannot warn -> runtime type assertion
>
> still , you'd have to be careful, but everyone knows that.
>
>
>
>
> Am 03.04.2011 02:12, schrieb Paul Phillips:
>> I looked around trunk a little bit for stuff which is broken because
>> of this.  Here are the first couple examples I found.
>>
>> // more "dynamic" hashcodes
>> scala> val x = (1 to 10).par
>> x: scala.collection.parallel.immutable.ParRange = ParRange(1, 2, 3, 4,
>> 5, 6, 7, 8, 9, 10)
>>
>> scala> x.hashCode
>> res0: Int = 1137090302
>>
>> scala> x.hashCode
>> res1: Int = -555212555
>>
>> scala> x.hashCode
>> res2: Int = -1216588130
>>
>>
>> // grab your partner, do-sa-do
>> scala> (1 to 10 par, 1 to 10).zipped foreach ((x, y) => println(x + "
>> " + y))
>> 3 2
>> 6 3
>> 2 4
>> 7 6
>> 1 1
>> 8 7
>> 4 5
>> 5 9
>> 9 8
>> 10 10
>>
>>
>
>

Hi,
I am glad we are discussing all this because I am expecting severe
trouble ahead with the current outline.

> creating a branched (singlethreadtravlike, parthreadtravlike) hierachy
> would make it impossible to use parallel collections where the api
> designer wanted to use single threaded ones but on the other hand

I think it's a good and highly appreciable thing to have easy to use
parallel collections which can be easily introduced instead of
sequencial ones.
For what it's worth I don't think that "transparent" parallel
collections instead of sequencial collections is the way to go.
Sneaking in parallel behaviour means sneaking in errors as the code
being forcefully parallelized might never have been intended for
parallelization.

I would try to go for a design where all hitherto existing ordered /
sequencial traits / classes are a special case of unordered tolerant /
parallelizable collections. That is Seq and co. is narrowing down the
degree of freedom to sequencial behaviour. This way existing code
could continue to operate as expected.

A redesigner could review code in question and relax the type
signature of methods to allow for parallel stuff to come in. That way
the contract is clear and there is an easy road to adopt
parallelization. (I'm sure there are drawback to this approach as well
- but at least there is no automagical parallelization which will
cause automagic indeterministic errors).

The main problem I currently see is that we're a bit late with this
discussion as RC1 is already released. But better late than never...

Greetings
Bernd

On 03/04/11 16:55, HamsterofDeath wrote:
> something has to be fixed. the question is what.
> ...
> many methods are based on foreach.

I think I know where the problem is.

Tony Morris
http://tmorris.net/