Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Vector updated, +:, and :+ fall back to slow performance when builder comes from IndexedSeq #6150

Closed
scabug opened this issue Jul 27, 2012 · 20 comments
Assignees
Milestone

Comments

@scabug
Copy link

@scabug scabug commented Jul 27, 2012

When #5937 was fixed, that is in this scala/scala@d8fbd9a commit, a new problem was introduced:

scala> import collection.generic.CanBuildFrom
import collection.generic.CanBuildFrom

scala> import collection.immutable.{IndexedSeq => IIdxSeq}
import collection.immutable.{IndexedSeq=>IIdxSeq}

scala> val cbf1 = implicitly[CanBuildFrom[Vector[Int],Int,IIdxSeq[Int]]]
cbf1: ... = scala.collection.immutable.Vector$VectorReusableCBF@106ac20f

scala> val cbf2 = implicitly[CanBuildFrom[IIdxSeq[Int],Int,IIdxSeq[Int]]]
cbf2: ... = scala.collection.generic.GenTraversableFactory$ReusableCBF@583dfc8b

With cbf2, the check in Vector's methods updated, \+:, and :+ for optimised O(1) algorithms fails.


The suggested solution is as follows: the default implementation of collection.IndexedSeq is collection.immutable.IndexedSeq, and that in turn gives Vector. Vector can thus safely call the optimised methods when the builder target is ndexedSeq. The long-term solution probably is to introduce an IndexedSeqFactory. The direct fix is to move the newly introduced builder factory instance VectorReusableCBF from the Vector module to the IndexedSeq module.

Indeed, I think it would be sufficient, instead of creating a new class, to ensure a fresh instance of ReusableCBF, e.g.

object IndexedSeq extends SeqFactory[IndexedSeq] {
  override lazy val ReusableCBF: GenericCanBuildFrom[Nothing] = new ReusableCBF // ensure a fresh instance
  ...
}

Then, instead of checking the class using pattern matching, one could simply use eq:

  @inline override def :+[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = {
    if(bf eq IndexedSeq.ReusableCBF) {
      appendBack(elem).asInstanceOf[That] // just ignore bf
    } else {
      super.:+(elem)(bf)
    }
  }

Of course, if you prefer a class type check, you may just move VectorReusableCBF to IndexedSeq and keep the pattern match as case _: IndexedSeq.VectorReusableCBF => ...


Finally, it needs to be contemplated whether the new builder factory is safe in collection.IndexedSeq, or would have to be in collection.immutable.IndexedSeq so as not to interfere with collection.mutable.IndexedSeq? I think there is no problem -- if you append an element to a Vector and expect a collection.IndexedSeq, it's correct to return another Vector.

@scabug
Copy link
Author

@scabug scabug commented Jul 27, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6150?orig=1
Reporter: @Sciss
Affected Versions: 2.10.0-M6
See #5937

Loading

@scabug
Copy link
Author

@scabug scabug commented Aug 15, 2012

@axel22 said:
I agree that using eq is a better idea.

Also, given that the default implementation of the collection.IndexedSeq remains a Vector, optimizing :+ and +: on the Vector while expecting an IndexedSeq should not cause a problem as far as I can see.

Loading

@scabug
Copy link
Author

@scabug scabug commented Aug 15, 2012

@axel22 said:
Although, ideally, we'd like to test if the factory produces a VectorBuilder, irrespective of where the factory came from. That, however, requires instantiating an empty VectorBuilder, which is probably (?) prohibitive for smaller vectors.

Loading

@scabug
Copy link
Author

@scabug scabug commented Aug 15, 2012

Loading

@scabug
Copy link
Author

@scabug scabug commented Aug 15, 2012

@Sciss said:
That makes me very happy, thanks!

Loading

@scabug
Copy link
Author

@scabug scabug commented Nov 9, 2012

@Sciss said:
Should I be seeing these commits in 2.10.0-RC2? Because I still get the following horrific picture:

Scala 2.10.0-R2:
For Build+Compare the tests took 2:00.721s
For Slice the tests took 2:22.187s

Scala 2.9.2:
For Build+Compare the tests took 0.481s
For Slice the tests took 18.480s

?

Loading

@scabug
Copy link
Author

@scabug scabug commented Nov 9, 2012

@retronym said:
Currently, it is only in the master branch, ie 2.11.0.

git branch --contains 0308ae8 | egrep '(2.10|master)'
  master

I agree that we should back port for 2.10.1 (it might be too late for 2.10.0).

Loading

@scabug
Copy link
Author

@scabug scabug commented Nov 13, 2012

@retronym said:
Reopening for a back-port to 2.10.1

Loading

@scabug
Copy link
Author

@scabug scabug commented Nov 15, 2012

Loading

@scabug scabug closed this Dec 5, 2012
@scabug
Copy link
Author

@scabug scabug commented Jan 17, 2013

@SethTisue said:
That feeling when you find a bug, and find that not only is there already a ticket, there's already a fix. Thanks guys.

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 24, 2014

Stu Hood (stuhood) said:
I believe that we're seeing a new variant of this same issue in scala 2.10.4. For code looping to grow a Vector using :+, we see a huge amount of time spent in the following stack:

scala.collection.generic.Growable$$anonfun$$plus$plus$eq$1.apply(Growable.scala:48)
scala.collection.generic.Growable$$anonfun$$plus$plus$eq$1.apply(Growable.scala:48)
scala.collection.Iterator$class.foreach(Iterator.scala:727)
scala.collection.AbstractIterator.foreach(Iterator.scala:1157)
scala.collection.IterableLike$class.foreach(IterableLike.scala:72)
scala.collection.AbstractIterable.foreach(Iterable.scala:54)
scala.collection.generic.Growable$class.$plus$plus$eq(Growable.scala:48)
scala.collection.immutable.VectorBuilder.$plus$plus$eq(Vector.scala:716)
scala.collection.immutable.VectorBuilder.$plus$plus$eq(Vector.scala:692)
scala.collection.SeqLike$class.$colon$plus(SeqLike.scala:529)
scala.collection.immutable.Vector.$colon$plus(Vector.scala:153)
<snip>

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 25, 2014

@retronym said (edited on Sep 25, 2014 1:37:35 AM UTC):
Here's a test case that drastically improves from 2.10.0 to 2.10.1

object Test extends App {
  type Upcast = IndexedSeq[String]
  var i = 0
  while (i < 100) {
    var v: Upcast = Vector("")
    var j = 0
    val t = System.nanoTime
    while (j < 100000) {
      v = (v: Upcast) :+ ""
      j += 1
    }
    println(s"${(System.nanoTime - t).toDouble / 1000 / 1000} / ${v.length}")
    i += 1
  }
}
// 2.10.0
...
20382.243 / 100001
20260.872 / 100001
20227.341 / 100001
20231.207 / 100001
24530.945 / 100001
24490.411 / 100001

// 2.10.1
...
5.525 / 100001
7.932 / 100001
8.954 / 100001
6.907 / 100001
5.614 / 100001
5.926 / 100001
5.442 / 100001

Could you please whittle down your problem to something similar that doesn't show the same improvement?

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 25, 2014

@retronym said (edited on Sep 25, 2014 1:46:59 AM UTC):
I should also mention that creating lots of throwaway intermediate Vectors, even with this fix, is always going to be more expensive than using an imperative Builder within the loop. Here's an example that is an order of magnitude faster.

object Test extends App {
  type Upcast = IndexedSeq[String]
  var i = 0
  while (i < 100) {
    var v: Upcast = Vector("")
    var j = 0
    val t = System.nanoTime
    val builder = Vector.newBuilder[String]
    while (j < 100000) {
      builder += ""
      j += 1
    }
    v = builder.result
    println(s"${(System.nanoTime - t).toDouble / 1000 / 1000} / ${v.length}")
    i += 1
  }
}
// 2.10.1
...
0.372 / 100000
0.372 / 100000
0.375 / 100000
0.374 / 100000
0.372 / 100000
0.372 / 100000
0.37 / 100000
0.381 / 100000
0.378 / 100000
0.378 / 100000

If you use a suitable persistent data structure like List that has a free prepend, you can keep things pure. But Vector's append/prepend is more expensive (as a tradeoff to make its indexing faster).

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 25, 2014

Stu Hood (stuhood) said:
Sorry, I wasn't clear: the regression seems to have been between 2.9.3 and 2.10.4, for precisely the same code. But yes, will attempt to gin up a small reproduction.

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 25, 2014

Stu Hood (stuhood) said (edited on Sep 25, 2014 6:16:36 AM UTC):
Making a small edit to your example reproduces the slowdown:

-  type Upcast = IndexedSeq[String]
+  type Upcast = Seq[String]

The runtime with an upcast to Seq is:

55178.384 / 100001
55987.473 / 100001
...

At some level it makes sense that you must declare something as an IndexedSeq to get O(1)ish behaviour. But... was this intended?

Loading

@scabug
Copy link
Author

@scabug scabug commented Oct 7, 2014

@jrudolph said (edited on Oct 7, 2014 3:11:27 PM UTC):
This one is still broken in 2.10.4 and 2.11.2:

Vector.fill(10000000)(0).foldLeft(Vector.empty[Int]: Seq[Int])((a, b) => a :+ b)

Loading

@scabug
Copy link
Author

@scabug scabug commented Oct 8, 2014

@retronym said (edited on Oct 8, 2014 5:49:18 AM UTC):
@axel22 Would your fix for this with when the static type is IndexedSeq generalize to weaker types like Seq?

Loading

@scabug
Copy link
Author

@scabug scabug commented Oct 8, 2014

@jrudolph said:
And how many remaining issues of this kind are lurking in the collections library?

Loading

@scabug
Copy link
Author

@scabug scabug commented Oct 8, 2014

@axel22 said (edited on Oct 8, 2014 10:56:49 PM UTC):
Jason:
As far as I can tell, yes, the fix should work.

The :+ and +: methods must return a collection of type That, where That comes from the CanBuildFrom object.
Since the ReusableCBF that comes from the Seq companion must has Seq[A] for That, and because:

  • the default implementation of :+ will return statically Seq[A]
  • and anyway a Vector at runtime

It should be perfectly fine to use eq, which returns a Vector as an optimization.

Note to bug reporters, though - as Jason suggests, you should really use a VectorBuilder if you care about performance. And if you really, really care about append performance, use an ArrayBuffer, or better yet, a Conc-tree buffer from an external library (published through Sonatype):
https://github.com/storm-enroute/reactive-collections/blob/master/reactive-collections-core/src/main/scala/scala/reactive/core/ConcBuffer.scala

Loading

@scabug
Copy link
Author

@scabug scabug commented Oct 20, 2014

@jrudolph said:
I created #8930 to track the remaining issue so that it doesn't get lost.

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants