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
Poor performance of :+ operator on arrays #5017
Comments
Imported From: https://issues.scala-lang.org/browse/SI-5017?orig=1 |
Gregor Scheidt (gregor) said: However, on the remote chance that this is simply a minor thing that's slipped through the cracks and it would be possible to do it, here is a little bit more information to clarify the issue: (1) the default implementation for :+() that seems to be called for an Array[T] is on scala.collection.SeqLike. The implementation in 2.9.0.1 is: def :+[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Repr,B,That]): That = {
val b = bf(repr)
b ++= thisCollection
b += elem
b.result
} This constructs a builder, adds the original elements and then the extension element. Seems to not be optimal for an array. (2) here is a sketch of a specialized implementation for Array[T] that uses Array.copy(). I know that this does not have the same structure as the one on SeqLike (simply because I do not know how to get it called for an array - as I said, I'm a newbie), so this is for illustration purposes only: def :+[T: ClassManifest]( xs: Array[T], x: T ) : Array[T] = {
val oldlength = xs.length
val extended = Array.ofDim[T]( oldlength + 1 )
Array.copy( xs, 0, 0, oldlength )
extended( oldlength ) = x
extended
} (3) should something remotely resembling the implementation based on Array.copy() be possible, the gains would possibly be attractive. Here is a naive mini-benchmark: @Test def test() {
val before = Array(1,2,3,4,5,6,7,8)
for( j <- 0 until 10 ) { // do 10 runs, consider only best time out of ten
val t = System.currentTimeMillis
for( i <- 0L until 10000000L )
before +: 9 // (a) SeqLike
// +:( before, 9 ) // (b) proposed
println( System.currentTimeMillis - t )
}
} The results are as follows (with -server, best out of 10 runs to eliminate GC effects and allow optimizer to run): (a) SeqLike: 1496 ms |
@Blaisorblade said (edited on Mar 7, 2012 1:10:44 PM UTC): Of course, the same change as for |
@Blaisorblade said: |
@retronym said: |
@retronym said: |
@retronym said: |
@JamesIry said: |
@JamesIry said: |
See http://stackoverflow.com/questions/7500081/scala-what-is-the-best-way-to-append-an-element-to-an-array
Using the ':+' operator on an array is about 2-3x slower than a simple append() method that uses Array.copy(), both for arrays containing object instances and for arrays containing Long or Int.
Couldn't ':+' in SeqLike[T] be overridden with a custom implementation for arrays? The default implementation creates a builder, adds the original array, then adds the element, then renders the result into a new array.
The text was updated successfully, but these errors were encountered: