collection suprises

[Tiark Rompf]

I'm using parallel collection for a small program and I've hit a few surprises. Is this expected? bugs?

Thanks,
- Tiark


Welcome to Scala version 2.10.0-20120808-162429-b9c3a3b083 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_33).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val xs = new mutable.ArrayBuffer() ++= Seq(1,2,3)
xs: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

scala> val xs = new mutable.ArrayBuffer() ++= Seq(1,2,3).par
<console>:10: error: type mismatch;
found : scala.collection.parallel.ParSeq[Int]
required: scala.collection.TraversableOnce[?]
val xs = new mutable.ArrayBuffer() ++= Seq(1,2,3).par
^

scala> List(1,2,1,1).groupBy(x=>x).map(p => p._2.map(x=>x))
res13: scala.collection.immutable.Iterable[List[Int]] = List(List(2), List(1, 1, 1))

scala> List(1,2,1,1).par.groupBy(x=>x).map(p => p._2.map(x=>x))
scala.collection.parallel.CompositeThrowable: Multiple exceptions thrown during a parallel computation: java.lang.ClassCastException: scala.collection.parallel.immutable.LazyParVectorCombiner cannot be cast to scala.collection.parallel.ParIterableLike
$anonfun$2.apply(<console>:11)
$anonfun$2.apply(<console>:11)
scala.collection.parallel.AugmentedIterableIterator$class.map2combiner(RemainsIterator.scala:120)
scala.collection.parallel.immutable.ParHashMap$ParHashMapIterator.map2combiner(ParHashMap.scala:79)
scala.collection.parallel.ParIterableLike$Map.leaf(ParIterableLike.scala:1057)
scala.collection.parallel.Task$$anonfun$tryLeaf$1.apply$mcV$sp(Tasks.scala:54)
scala.collection.parallel.Task$$anonfun$tryLeaf$1.apply(Tasks.scala:53)
scala.collection.parallel.Task$$anonfun$tryLeaf$1.apply(Tasks.scala:53)

[Josh Suereth]

I'd open bugs.   Especially the second.

[Paul Phillips]

On Thu, Aug 23, 2012 at 10:33 PM, Tiark Rompf <tiark...@epfl.ch> wrote:

scala> val xs = new mutable.ArrayBuffer() ++= Seq(1,2,3).par
<console>:10: error: type mismatch;
 found   : scala.collection.parallel.ParSeq[Int]
 required: scala.collection.TraversableOnce[?]
       val xs = new mutable.ArrayBuffer() ++= Seq(1,2,3).par
                                                         ^

[Note: lists surely not complete.]

Looking at collections methods which accept GenTraversableOnce, I find:

def ++ (elems: GenTraversableOnce[A]): This = (repr /: elems.seq)(_ + _)

def ++(xs: GenTraversableOnce[A]): PriorityQueue[A] = { this.clone() ++= xs.seq }

def ++(xs: GenTraversableOnce[A]): This = clone() ++= xs.seq

def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That

def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {

def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): Map[A, B1] =

def ++[U >: T, That](that: GenTraversableOnce[U])(implicit bf: CanBuildFrom[Repr, U, That]): That = {

def --(xs: GenTraversableOnce[A]): Repr = (repr /: xs.seq) (_ - _)

def corresponds[B](that: GenTraversableOnce[B])(p: (A, B) => Boolean): Boolean = {

def fromTraversables[T](xss: GenTraversableOnce[T]*) = {

For TraversableOnce:

def ++:[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {

def ++=(xs: TraversableOnce[A]): this.type = { xs.seq foreach += ; this }

def ++=:(xs: TraversableOnce[A]): this.type = { insertAll(0, xs.toTraversable); this }

def --=(xs: TraversableOnce[A]): this.type = { xs.seq foreach -= ; this }

def appendAll(xs: TraversableOnce[A]) { this ++= xs }

def appendAll(xs: TraversableOnce[Char]): StringBuilder = appendAll(xs.toArray)

def find[T](futurestravonce: TraversableOnce[Future[T]])(predicate: T => Boolean)(implicit executor: ExecutionContext): Future[Option[T]] = {

def firstCompletedOf[T](futures: TraversableOnce[Future[T]])(implicit executor: ExecutionContext): Future[T] = {

def fold[T, R](futures: TraversableOnce[Future[T]])(zero: R)(foldFun: (R, T) => R)(implicit executor: ExecutionContext): Future[R] = {

def insertAll(index: Int, xs: TraversableOnce[Char]): StringBuilder = insertAll(index, xs.toArray)

def prependAll(xs: TraversableOnce[A]) { xs ++=: this }

def pushAll(xs: TraversableOnce[A]): this.type = { xs.seq foreach push ; this }

def pushAll[B >: A](xs: TraversableOnce[B]): Stack[B] =

def reduce[T, R >: T](futures: TraversableOnce[Future[T]])(op: (R, T) => R)(implicit executor: ExecutionContext): Future[R] = {

def sequence[A, M[_] <: TraversableOnce[_]](in: M[Future[A]])(implicit cbf: CanBuildFrom[M[Future[A]], A, M[A]], executor: ExecutionContext): Future[M[A]] = {

def traverse[A, B, M[_] <: TraversableOnce[_]](in: M[A])(fn: A => Future[B])(implicit cbf: CanBuildFrom[M[A], B, M[B]], executor: ExecutionContext): Future[M[B]] =

def wrapTraversableOnce[A](trav: TraversableOnce[A]) = new MonadOps(trav)

[Tiark Rompf]

done: https://issues.scala-lang.org/browse/SI-6279

- Tiark

[Aleksandar Prokopec]

The second one (CCE) I fixed some time ago.

The `++=` from `Growable` accepting `GenTraversableOnce` instead of `TraversableOnce` is something that was around since 2.9.0.
We could change it now at the very last minute, but that would require reintroducing the @bridge annotation, I believe, which has been deprecated for 2.10.0.

-- 
Aleksandar Prokopec,
Doctoral Assistant
LAMP, IC, EPFL
http://people.epfl.ch/aleksandar.prokopec

[Paul Phillips]

On Fri, Aug 24, 2012 at 3:06 PM, Aleksandar Prokopec <aleksanda...@epfl.ch> wrote:

The second one (CCE) I fixed some time ago.

Looks like the fix is only in master though, missing in 2.10.x.

[Aleksandar Prokopec]

It was here: https://github.com/scala/scala/commit/48b128d2

Should I reopen a pull request?

[Paul Phillips]

On Fri, Aug 24, 2012 at 3:57 PM, Aleksandar Prokopec <aleksanda...@epfl.ch> wrote:

Should I reopen a pull request?

I'm not sure.  Martin estimated there would/should be fewer than 50 commits between now and 2.10.0 final, which I mention because it suggests a high "critical bug" threshold.

[Aleksandar Prokopec]

I see.
Well, I would avoid doing anything about changing the `Growable` interface and the `++=` method now.

As for the `groupBy` fix, in order not to exceed the estimated number of commits until 2.10.0 final, perhaps the change can be sneaked into some other critical (collection) fix commit. It's only this:

309		-      evaluateCombiners(trie)
310		-      trie.asInstanceOf[HashMap[K, Repr]]
	309	+      evaluateCombiners(trie).asInstanceOf[HashMap[K, Repr]]

[Paolo G. Giarrusso]

Il giorno venerdì 24 agosto 2012 15:06:13 UTC+2, Aleksandar Prokopec ha scritto:

The `++=` from `Growable` accepting `GenTraversableOnce` instead of `TraversableOnce` is something that was around since 2.9.0.
We could change it now at the very last minute, but that would require reintroducing the @bridge annotation, I believe, which has been deprecated for 2.10.0.

I thought that @bridge methods existed only for binary compatibility—but aren't you allowed to break that between 2.9 and 2.10?

[Paul Phillips]

On Fri, Aug 24, 2012 at 4:08 PM, Aleksandar Prokopec <aleksanda...@epfl.ch> wrote:

As for the `groupBy` fix, in order not to exceed the estimated number of commits until 2.10.0 final, perhaps the change can be sneaked into some other critical (collection) fix commit. It's only this:

I think the number was intended as a proxy for the number of changes; I don't think we can fool it.  But I agree it looks pretty localized.

[Paolo G. Giarrusso]

Having a high threshold for critical bugs makes sense. But some companies have tried _enforcing_ things similar to the above commit limit, and the results were real-world Dilbert-like recipes for bad software quality. In particular, some studies suggested a certain distribution for the number of new bugs found by testing, and some managers forced testers to reach those counts.

"Later in testing, the expectation is that the bug find rate will decline. [...] In some companies, the testers and the programmers hold the "quality assurance" metrics-gathering staff in contempt and they collaborate to give the QA outsiders the numbers they want in order to get them to go back to Head Office, far away. [...] At one client site, the staff even had a cubicle where they would write bugs up on Post-It notes, posting them on the inside wall until a bug was fixed or the numbers in the tracking system were low enough to admit more new bugs. This system worked fairly well except when Post-Its fell off the wall at night and were swept away by the janitor." ([1], page 9-10).

Of course, I don't see anything that bad here.

Best regards

[1] Cem Kaner and Walter P. Bond. 2004. Software Engineering Metrics: What Do They Measure and How do We Know? — http://testingeducation.org/a/metrics2004.pdf

[Josh Suereth]

The patch is small.  Please submit against 2.10.x.   this is critical.

[Aleksandar Prokopec]

Done:

https://github.com/scala/scala/pull/1190

[martin odersky]

On Fri, Aug 24, 2012 at 3:06 PM, Aleksandar Prokopec <aleksanda...@epfl.ch> wrote:

The second one (CCE) I fixed some time ago.

The `++=` from `Growable` accepting `GenTraversableOnce` instead of `TraversableOnce` is something that was around since 2.9.0.
We could change it now at the very last minute, but that would require reintroducing the @bridge annotation, I believe, which has been deprecated for 2.10.0.

Why @bridge? I am asking because we do not have binary compatibility constraints this time.

I did not put a threshold on commits for 2.10.0, just an estimate where we are. If we have a safe bugfix by all means let's put it in. 

Cheers

 - Martin

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Aleksandar Prokopec]

Well, in that case we can change `++=` to take `GenTraversableOnce` as a parameter.

There are related changes in other methods, most notable of which are:
Shrinkable.--=
TraversableLike.++:
Stack.pushAll
Stream.append
BufferLike.++=:
BufferLike.prependAll
Array.flatten

They are addressed in this pull request:

https://github.com/scala/scala/pull/1198

Cheers,
Alex

[Paul Phillips]

On Mon, Aug 27, 2012 at 6:02 AM, Aleksandar Prokopec <aleksanda...@epfl.ch> wrote:

Well, in that case we can change `++=` to take `GenTraversableOnce` as a parameter.

There are related changes in other methods, most notable of which are:
Shrinkable.--=
TraversableLike.++:
Stack.pushAll
Stream.append
BufferLike.++=:
BufferLike.prependAll
Array.flatten

These will all break source compatibility with 2.9, with no deprecation period, for at least anyone who has subclassed a collection.  You might be able to overload with both signatures with the other one deprecated, but this will probably break other code when it impairs type inference.

[martin odersky]

Question: What is the argument for changing ++=? Consistency? Are there other related methods that take a GenTraversableOne? Or just convenience? If it's the latter I'd say it's not worth the change. Might as well write

  xs ++= parset.seq

Cheers

 - Martin

[Aleksandar Prokopec]

One argument I can see is consistency.
We changed `flatMap`, `patch`, `++`, and many other methods just before 2.9.0 to have `GenTraversableOnce` in their signatures instead of `TraversableOnce`.

The other is convenience of clients not having to call:

  mutable.ArrayBuffer[Int]() ++= parallelCollection.seq

instead of just:

  mutable.ArrayBuffer[Int]() ++= parallelCollection

But I think that alone is not worth the change at this point.

Cheers,
Alex