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
Comments
Imported From: https://issues.scala-lang.org/browse/SI-6150?orig=1 |
@axel22 said: Also, given that the default implementation of the |
@axel22 said: |
@axel22 said: |
@Sciss said: |
@Sciss said: Scala 2.10.0-R2: Scala 2.9.2: ? |
@retronym said: 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). |
@retronym said: |
@axel22 said: |
@SethTisue said: |
Stu Hood (stuhood) said:
|
@retronym said (edited on Sep 25, 2014 1:37:35 AM UTC): 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
}
}
Could you please whittle down your problem to something similar that doesn't show the same improvement? |
@retronym said (edited on Sep 25, 2014 1:46:59 AM UTC): 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
}
}
If you use a suitable persistent data structure like |
Stu Hood (stuhood) said: |
Stu Hood (stuhood) said (edited on Sep 25, 2014 6:16:36 AM UTC): - type Upcast = IndexedSeq[String]
+ type Upcast = Seq[String] The runtime with an upcast to Seq is:
At some level it makes sense that you must declare something as an IndexedSeq to get O(1)ish behaviour. But... was this intended? |
@jrudolph said (edited on Oct 7, 2014 3:11:27 PM UTC): Vector.fill(10000000)(0).foldLeft(Vector.empty[Int]: Seq[Int])((a, b) => a :+ b) |
@jrudolph said: |
@axel22 said (edited on Oct 8, 2014 10:56:49 PM UTC): The
It should be perfectly fine to use Note to bug reporters, though - as Jason suggests, you should really use a |
When #5937 was fixed, that is in this scala/scala@d8fbd9a54d commit, a new problem was introduced:
With
cbf2
, the check inVector
's methodsupdated
,\+:
, and:+
for optimised O(1) algorithms fails.The suggested solution is as follows: the default implementation of
collection.IndexedSeq
iscollection.immutable.IndexedSeq
, and that in turn givesVector
.Vector
can thus safely call the optimised methods when the builder target isndexedSeq
. The long-term solution probably is to introduce anIndexedSeqFactory
. The direct fix is to move the newly introduced builder factory instanceVectorReusableCBF
from theVector
module to theIndexedSeq
module.Indeed, I think it would be sufficient, instead of creating a new class, to ensure a fresh instance of
ReusableCBF
, e.g.Then, instead of checking the class using pattern matching, one could simply use
eq
:Of course, if you prefer a class type check, you may just move
VectorReusableCBF
toIndexedSeq
and keep the pattern match ascase _: IndexedSeq.VectorReusableCBF => ...
Finally, it needs to be contemplated whether the new builder factory is safe in
collection.IndexedSeq
, or would have to be incollection.immutable.IndexedSeq
so as not to interfere withcollection.mutable.IndexedSeq
? I think there is no problem -- if you append an element to aVector
and expect acollection.IndexedSeq
, it's correct to return anotherVector
.The text was updated successfully, but these errors were encountered: