This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Parallel collections breaking subtype polymorphism

10 replies
hseeberger
Joined: 2008-12-27,
User offline. Last seen 1 year 25 weeks ago.

If I use a parallel collection directly, it executes in parallel (as expected):
scala> (1 to 8).par map { _ => Thread.currentThread.getName }res12: scala.collection.parallel.immutable.ParSeq[java.lang.String] = ParVector(ForkJoinPool-1-worker-6, ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-5, ForkJoinPool-1-worker-2, ForkJoinPool-1-worker-3, ForkJoinPool-1-worker-4, ForkJoinPool-1-worker-9, ForkJoinPool-1-worker-7)
If I abstract over sequential / parallel collections, it doesn't:
scala> val numbers: GenSeq[Int] = (1 to 8).parnumbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7, 8)
scala> numbers map { _ => Thread.currentThread.getName }res13: scala.collection.GenSeq[java.lang.String] = ParVector(Thread-34, Thread-34, Thread-34, Thread-34, Thread-34, Thread-34, Thread-34, Thread-34)
Now, is this a deliberate design choice? Or a bug? In my opinion subtype polymorphism is broken here, i.e. I expect the underlying implementation to determine whether the execution happens sequentially or parallel. 
Heiko
--

Heiko SeebergerTwitter: hseeberger
Blog: heikoseeberger.name
Company: Typesafe - Enterprise-Grade Scala from the ExpertsAuthor of Durchstarten mit Scala, a German tutorial-style Scala book

extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.
Re: Parallel collections breaking subtype polymorphism

On 7/27/11 12:51 AM, Heiko Seeberger wrote:
> Now, is this a deliberate design choice? Or a bug? In my opinion
> subtype polymorphism is broken here, i.e. I expect the underlying
> implementation to determine whether the execution happens sequentially
> or parallel.

I think that somehow it didn't clearly emerge from that ticket that it
is a bug and it is already fixed. That's why I was able to comment with
transcripts showing obviously parallel behavior. It's just that for me
when a bug is fixed in trunk, it's fixed, and I forget sometimes to
perform the situational translations.

Johannes Rudolph 2
Joined: 2010-02-12,
User offline. Last seen 42 years 45 weeks ago.
Re: Parallel collections breaking subtype polymorphism

We would therefore promote commit r25235 containing the fix (is that
all that is needed, Aleksandar?) to be included into 2.9.1.

On Wed, Jul 27, 2011 at 9:57 AM, Paul Phillips wrote:
> On 7/27/11 12:51 AM, Heiko Seeberger wrote:
>> Now, is this a deliberate design choice? Or a bug? In my opinion
>> subtype polymorphism is broken here, i.e. I expect the underlying
>> implementation to determine whether the execution happens sequentially
>> or parallel.
>
> I think that somehow it didn't clearly emerge from that ticket that it
> is a bug and it is already fixed. That's why I was able to comment with
> transcripts showing obviously parallel behavior. It's just that for me
> when a bug is fixed in trunk, it's fixed, and I forget sometimes to
> perform the situational translations.
>

prokopec
Joined: 2010-02-19,
User offline. Last seen 34 weeks 5 days ago.
Re: Parallel collections breaking subtype polymorphism

On 27/07/11 10:00, Johannes Rudolph wrote:
> We would therefore promote commit r25235 containing the fix (is that
> all that is needed, Aleksandar?) to be included into 2.9.1.

It should be, yes.

Alex

extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.
Re: Parallel collections breaking subtype polymorphism

On 7/27/11 2:14 AM, Aleksandar Prokopec wrote:
>> We would therefore promote commit r25235 containing the fix (is that
>> all that is needed, Aleksandar?) to be included into 2.9.1.
>
> It should be, yes.

As written it is highly binary incompatible and can't go in.

Mariso
Joined: 2010-06-09,
User offline. Last seen 44 weeks 3 days ago.
Re: Parallel collections breaking subtype polymorphism

I can reproduce it in 2.9.1

Welcome to Scala version 2.9.1.final (Java HotSpot(TM) Server VM, Java
1.6.0_26)

scala> (1 to 8).par map { _ => Thread.currentThread.getName }
res0: scala.collection.parallel.immutable.ParSeq[java.lang.String] =
ParVector(ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-1,
ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-1, ForkJoinPool-1-
worker-0, ForkJoinPool-1-worker-3, ForkJoinPool-1-worker-2,
ForkJoinPool-1-worker-2)

scala> val numbers: scala.collection.GenSeq[Int] = (1 to 8).par
numbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7,
8)

scala> numbers map { _ => Thread.currentThread.getName }
res1: scala.collection.GenSeq[java.lang.String] = ParVector(Thread-10,
Thread-10, Thread-10, Thread-10, Thread-10, Thread-10, Thread-10,
Thread-10)

Maris

On Jul 27, 5:49 pm, Paul Phillips wrote:
> On 7/27/11 2:14 AM, Aleksandar Prokopec wrote:
>
> >> We would therefore promote commit r25235 containing the fix (is that
> >> all that is needed, Aleksandar?) to be included into 2.9.1.
>
> > It should be, yes.
>
> As written it is highly binary incompatible and can't go in.

hseeberger
Joined: 2008-12-27,
User offline. Last seen 1 year 25 weeks ago.
Re: Parallel collections breaking subtype polymorphism
It is fixed in 2.10:
tmp$ scala-2.10 Welcome to Scala version 2.10.0.r25517-b20110816020342 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_26).Type in expressions to have them evaluated.Type :help for more information.
scala> val numbers: scala.collection.GenSeq[Int] = (1 to 8).parnumbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7, 8)
scala> numbers map { _ => Thread.currentThread.getName }res1: scala.collection.GenSeq[java.lang.String] = ParVector(ForkJoinPool-1-worker-2, ForkJoinPool-1-worker-5, ForkJoinPool-1-worker-3, ForkJoinPool-1-worker-6, ForkJoinPool-1-worker-0, ForkJoinPool-1-worker-5, ForkJoinPool-1-worker-7, ForkJoinPool-1-worker-3)
ASAIK it introduced a breaking change (at least breaking binary comp) and therefore could not be added to 2.9.x
Heiko
--
Heiko SeebergerTwitter: hseebergerBlog: heikoseeberger.nameCompany: Typesafe - Enterprise-Grade Scala from the ExpertsAuthor of Durchstarten mit Scala, a German tutorial-style Scala book
On Sep 13, 2011, at 1:50 PM, Maaruks wrote:
I can reproduce it in 2.9.1

Welcome to Scala version 2.9.1.final (Java HotSpot(TM) Server VM, Java
1.6.0_26)

scala>  (1 to 8).par map { _ => Thread.currentThread.getName }
res0: scala.collection.parallel.immutable.ParSeq[java.lang.String] =
ParVector(ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-1,
ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-1, ForkJoinPool-1-
worker-0, ForkJoinPool-1-worker-3, ForkJoinPool-1-worker-2,
ForkJoinPool-1-worker-2)

scala> val numbers: scala.collection.GenSeq[Int] = (1 to 8).par
numbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7,
8)

scala>  numbers map { _ => Thread.currentThread.getName }
res1: scala.collection.GenSeq[java.lang.String] = ParVector(Thread-10,
Thread-10, Thread-10, Thread-10, Thread-10, Thread-10, Thread-10,
Thread-10)




Maris


On Jul 27, 5:49 pm, Paul Phillips <pa [dot] [dot] [dot] [at] improving [dot] org> wrote:
On 7/27/11 2:14 AM, Aleksandar Prokopec wrote:

We would therefore promote commit r25235 containing the fix (is that
all that is needed, Aleksandar?) to be included into 2.9.1.

It should be, yes.

As written it is highly binary incompatible and can't go in.

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: Parallel collections breaking subtype polymorphism

As I wrote before, we could not fix this in 2.9.1 because the fix
breaks binary compatibility. As Heiko remarks, it's fixed in 2.10.

DaveScala
Joined: 2011-03-18,
User offline. Last seen 1 year 21 weeks ago.
Re: Parallel collections breaking subtype polymorphism

Hi,

Why isn't the above a consequence of the "expected to conform" rule
and widening?
Because when overloading f with A1 <: A and calling f with an A1
object the same thing happens basically.
Subtype polymorphism is here also lost. Calling f(a1) is different
from f(a1pure). In the first a1 has become an A object and the latter
it is still an A1 object.

In the above there is an explicit type annotation which is a point of
"expected to conform" in the Language Specification:
val numbers: GenSeq[Int] = (1 to 8).par

and map is a infix function with the collection and a mapping function
as arguments so the collection has been widened the same way and map
always gives the same collection back what was put in.

scala> class A
defined class A

scala> class A1 extends A
defined class A1

scala> class B { def f(x:A) =println("1")
| def f(x:A1) =println("2")
| }
defined class B

scala> val a = new A
a: A = A@2e5b83

scala> val a1: A = new A1
a1: A = A1@16f4b70

scala> val b = new B
b: B = B@113f73e

scala> b.f(a)
1

scala> b.f(a1)
1

scala> val a1pure = new A1
a1pure: A1 = A1@7b00e0

scala> b.f(a1pure)
2

scala> val a1pure2 :A1 = new A1
a1pure2: A1 = A1@12eaba4

scala> b.f(a1pure2)
2

On 13 sep, 16:27, martin odersky wrote:
> As I wrote before, we could not fix this in 2.9.1 because the fix
> breaks binary compatibility. As Heiko remarks, it's fixed in 2.10.
>
>  -- Martin
>
> On Tue, Sep 13, 2011 at 4:20 PM, Heiko Seeberger
>
>
>
>
>
> wrote:
> > It is fixed in 2.10:
> > tmp$ scala-2.10
> > Welcome to Scala version 2.10.0.r25517-b20110816020342 (Java HotSpot(TM)
> > 64-Bit Server VM, Java 1.6.0_26).
> > Type in expressions to have them evaluated.
> > Type :help for more information.
> > scala> val numbers: scala.collection.GenSeq[Int] = (1 to 8).par
> > numbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7, 8)
> > scala> numbers map { _ => Thread.currentThread.getName }
> > res1: scala.collection.GenSeq[java.lang.String] =
> > ParVector(ForkJoinPool-1-worker-2, ForkJoinPool-1-worker-5,
> > ForkJoinPool-1-worker-3, ForkJoinPool-1-worker-6, ForkJoinPool-1-worker-0,
> > ForkJoinPool-1-worker-5, ForkJoinPool-1-worker-7, ForkJoinPool-1-worker-3)
> > ASAIK it introduced a breaking change (at least breaking binary comp) and
> > therefore could not be added to 2.9.x
> > Heiko
> > --
> > Heiko Seeberger
> > Twitter: hseeberger
> > Blog: heikoseeberger.name
> > Company: Typesafe - Enterprise-Grade Scala from the Experts
> > Author of Durchstarten mit Scala, a German tutorial-style Scala book
> > On Sep 13, 2011, at 1:50 PM, Maaruks wrote:
>
> > I can reproduce it in 2.9.1
>
> > Welcome to Scala version 2.9.1.final (Java HotSpot(TM) Server VM, Java
> > 1.6.0_26)
>
> > scala>  (1 to 8).par map { _ => Thread.currentThread.getName }
> > res0: scala.collection.parallel.immutable.ParSeq[java.lang.String] =
> > ParVector(ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-1,
> > ForkJoinPool-1-worker-1, ForkJoinPool-1-worker-1, ForkJoinPool-1-
> > worker-0, ForkJoinPool-1-worker-3, ForkJoinPool-1-worker-2,
> > ForkJoinPool-1-worker-2)
>
> > scala> val numbers: scala.collection.GenSeq[Int] = (1 to 8).par
> > numbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7,
> > 8)
>
> > scala>  numbers map { _ => Thread.currentThread.getName }
> > res1: scala.collection.GenSeq[java.lang.String] = ParVector(Thread-10,
> > Thread-10, Thread-10, Thread-10, Thread-10, Thread-10, Thread-10,
> > Thread-10)
>
> > Maris
>
> > On Jul 27, 5:49 pm, Paul Phillips wrote:
>
> > On 7/27/11 2:14 AM, Aleksandar Prokopec wrote:
>
> > We would therefore promote commit r25235 containing the fix (is that
>
> > all that is needed, Aleksandar?) to be included into 2.9.1.
>
> > It should be, yes.
>
> > As written it is highly binary incompatible and can't go in.
>
> --
> Martin Odersky
> Prof., EPFL and Chairman, Typesafe
> PSED, 1015 Lausanne, Switzerland
> Tel. EPFL: +41 21 693 6863
> Tel. Typesafe: +41 21 691 4967- Tekst uit oorspronkelijk bericht niet weergeven -
>
> - Tekst uit oorspronkelijk bericht weergeven -

Aleksandar Prokopec
Joined: 2010-04-04,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Parallel collections breaking subtype polymorphism

On 13/09/11 17:36, Dave wrote:
> Hi,
>
> Why isn't the above a consequence of the "expected to conform" rule
> and widening?
> Because when overloading f with A1<: A and calling f with an A1
> object the same thing happens basically.
> Subtype polymorphism is here also lost. Calling f(a1) is different
> from f(a1pure). In the first a1 has become an A object and the latter
> it is still an A1 object.
>
> In the above there is an explicit type annotation which is a point of
> "expected to conform" in the Language Specification:
> val numbers: GenSeq[Int] = (1 to 8).par
>
> and map is a infix function with the collection and a mapping function
> as arguments so the collection has been widened the same way and map
> always gives the same collection back what was put in.
>
>

The function `map` is a function with the collection, the mapping
function _and_ an implicit argument called a builder factory or
'CanBuildFrom'. Depending on the type of the collection, different
builder factories were being resolved in 2.8. Fixing this required
breaking binary compatibility.

DaveScala
Joined: 2011-03-18,
User offline. Last seen 1 year 21 weeks ago.
Re: Parallel collections breaking subtype polymorphism

But is map the right place to do a downcast?
Because map is also a monadic function that guarantees no side-
effects. Isn't downcasting (which is like applying LSP) considered a
side-effect?

scala> val numbers: scala.collection.GenSeq[Int] = (1 to 8).par
numbers: scala.collection.GenSeq[Int] = ParRange(1, 2, 3, 4, 5, 6, 7,
8)

scala>
numbers.asInstanceOf[scala.collection.parallel.immutable.ParRange] map
{
_ => Thread.currentThread.getName }
res2: scala.collection.parallel.immutable.ParSeq[java.lang.String] =
ParVector(p
c-thread-2, pc-thread-2, pc-thread-2, pc-thread-2, pc-thread-2, pc-
thread-2, pc-
thread-2, pc-thread-2)

which is the same output as directly:

scala> (1 to 8).par map { _ => Thread.currentThread.getName }
res3: scala.collection.parallel.immutable.ParSeq[java.lang.String] =
ParVector(p
c-thread-1, pc-thread-1, pc-thread-1, pc-thread-1, pc-thread-1, pc-
thread-1, pc-
thread-1, pc-thread-1)

On 13 sep, 17:45, Aleksandar Prokopec
wrote:
> On 13/09/11 17:36, Dave wrote:
>
>
>
>
>
> > Hi,
>
> > Why isn't the above a consequence of the "expected to conform" rule
> > and widening?
> > Because when overloading f with A1<: A and calling f with an A1
> > object the same thing happens basically.
> > Subtype polymorphism is here also lost. Calling f(a1) is different
> > from f(a1pure). In the first a1 has become an A object and the latter
> > it is still an A1 object.
>
> > In the above there is an explicit type annotation which is a point of
> > "expected to conform" in the Language Specification:
> > val numbers: GenSeq[Int] = (1 to 8).par
>
> > and map is a infix function with the collection and a mapping function
> > as arguments so the collection has been widened the same way and map
> > always gives the same collection back what was put in.
>
> The function `map` is a function with the collection, the mapping
> function _and_ an implicit argument called a builder factory or
> 'CanBuildFrom'. Depending on the type of the collection, different
> builder factories were being resolved in 2.8. Fixing this required
> breaking binary compatibility.- Tekst uit oorspronkelijk bericht niet weergeven -
>
> - Tekst uit oorspronkelijk bericht weergeven -

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland