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

Poor performance of :+ operator on arrays #5017

Closed
scabug opened this issue Sep 21, 2011 · 9 comments
Closed

Poor performance of :+ operator on arrays #5017

scabug opened this issue Sep 21, 2011 · 9 comments

Comments

@scabug
Copy link

scabug commented Sep 21, 2011

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.

@scabug
Copy link
Author

scabug commented Sep 21, 2011

Imported From: https://issues.scala-lang.org/browse/SI-5017?orig=1
Reporter: Gregor Scheidt (gregor)
Assignee: @JamesIry
Affected Versions: 2.9.0

@scabug
Copy link
Author

scabug commented Oct 18, 2011

Gregor Scheidt (gregor) said:
First off, I am a relative Scala newbie, so my sincerest apologies if this is either completely naive or misguided (e.g. because there is a good reason that this makes absolutely no sense or because there is no way to get the required information at the right place or because there is no way to get this routine called for Array[T] within the generic structure of the collection classes).

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
(b) proposed: 633 ms

@scabug
Copy link
Author

scabug commented Mar 7, 2012

@Blaisorblade said (edited on Mar 7, 2012 1:10:44 PM UTC):
I believe the generic implementation could be sped up by adding, before b \+\+= thisCollection, also b.sizeHint(length \+ 1). Considering that this will be a WrappedArray (IIRC), b should be a WrappedArrayBuilder. To finish the implementation, one should add \+\+= to WrappedArrayBuilder - for instance by copying or reusing ArrayBuffer.\+\+=. I believe the combined effect of these optimizations should be close to or indistinguishable from your proposed implementation, while being more general.

Of course, the same change as for :\+ should also be done for \+:.

@scabug
Copy link
Author

scabug commented Mar 7, 2012

@Blaisorblade said:
A correction: I discussed WrappedArray before, but your example will actually wrap the Array inside ArrayOps, so one should consider that code as well - including the multiple manual specialization of ArrayBuilder. It seems that all ArrayBuilder specializations already has a specialized implementation of ++=, so adding the sizeHint to SeqLike could be enough.

@scabug
Copy link
Author

scabug commented Dec 12, 2012

@retronym said:
scala/scala#1739

@scabug
Copy link
Author

scabug commented Feb 2, 2013

@retronym said:
We'll have to revert this in 2.10.x as the change is not forward binary compatible; libraries compiled against this method in 2.10.1 will not work in 2.10.0.

@scabug
Copy link
Author

scabug commented Feb 2, 2013

@retronym said:
Elevated to blocker for the bin-compat reversion.

@scabug
Copy link
Author

scabug commented Feb 3, 2013

@JamesIry said:
My bad, I should have caught that in review.

@scabug
Copy link
Author

scabug commented Feb 6, 2013

@JamesIry said:
revert for 2.10.x is scala/scala#2080

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant