Functional performance on primitive Arrays

[Robert Kohlenberger]

Like others I've wondered whether performance of collections might be improved "under the hood" without changing the API.

My interest is "big data" visualization where large collections of primitive (AnyVal) data are common.  Scala's FP seems like the right approach for parallel (many-core) analysis of large data sets.  Scala Arrays, as they are backed by compact Java arrays, seem like the best choice for fast random access.  Yet applying functions over large primitive arrays was so slow compared with the equivalent imperative code that I did some investigating to find out why.

Here is a summary of results.  I can post the stats and benchmark code if there's interested.  After finding the root cause, I searched the lists to find who else has seen this.  While boxing and unboxing are discussed elsewhere, I was surprised to find no one describing just how big is the performance hit, why it exists, or how to eliminate it.

What first struck me was the wide gap between two different implementations of summing an Int array.  First, a 1 million element Int array was created using

<code>val ia = Array.range(0,sz)</code>

, where sz is 1,000,000.  Next, the time to sum the array with foldLeft was measured

<code>ia.foldLeft(0)(_ + _)</code>

, and compared to the time using a plain old imperative while loop.  Using foldLeft was a startling 33x slower than the while loop.  Other stats of interest:

1. Same result using Array method "sum" (inherited from TraversableOnce, invokes foldLeft) instead of a local foldLeft
2. The Scala while loop is about 20% faster than the equivalent Java code!
   
3. Using a while loop to sum Array[java.lang.Integer] is 9.6x slower than the Array[Int] while loop
4. Summing an Array[java.lang.Integer], foldLeft is 26x slower than Array[Int] while loop
   

(These figures are on a Core 2 Duo, WiFi disabled, no browsers, and reflect hotspot performance with gc reset over 100 reps.  StdDev < 1%.)

Of course many apps are not data intensive, and spend more time in IO or network operations, so even a 33x slowdown would not be noticed.  For those data intensive apps where array performance does matter, the choice is between imperative style on few cores, or functional style to utilize many cores.  This is an obstacle to the DRY principle.

What then is the reason for this disparity in functional versus imperative performance?  I only looked in detail at foldLeft, but I suspect similar issues underly other collection methods.  By slowly morphing the generic foldLeft code into a fast while loop, and examining javap disassembled code where a small change made a big speed difference, the culprit turns out to be a Function2 wrapper on the function literal passed to foldLeft.

In byte code, I clearly see primitive ints coming from the array, and the functional literal "_ + _" is compiled to a method <code>public final int apply(int, int)</code> that simply iadds the 2 ints.  Unfortunately, that apply method is called by a Function2 apply method with the signature of <code>public final Object apply(Object, Object)</code>.  Regardless of the types of the array or the "visitor" function literal, the compiler always creates a Function2 apply that forces boxing, both coming and going!

This even explained #4 above, in which summing an array of Integer objects is faster than summing an array of ints, because it means that one less int needs boxing before calling Function2.apply.

Despite my attention here to Array, I'm also interested in better performance for ArrayBuffer, ResizableArray and ParArray.  Here's what I'd like to know:

• Does anybody know of a workaround that lets me apply functions to primitive arrays without boxing?
  
• Would will a future scalac compile to more polymorphic Function2 types that better match the Array type, when known?
  
• Any other ideas for faster functions on collections?
  

I did see that Erik has an alternative to Scala collections, https://github.com/non/debox . Are these APIs considered stable?  I also attended Paul's Valentines Day talk, http://www.youtube.com/watch?v=o2WtIroR7Ag&feature=youtu.be , where he mentioned the lack of specialization support for Arrays, since they don't know about ClassTags.  (None of what I've said will be surprising to Paul, and I don't imply that there's an easy fix!)

Hope this sparks some productive discussion.  - Bob K. (aka Kabob)

[Erik Osheim]

Hi Bob,

So I'll give you my perspective on this issue:

Unfortunately, the Scala collections API (and almost all of the
standard library) is not specialized. This means that any generic type
will be boxed in these operations. This means that operations like
foldLeft, sum, etc will usually be slower than equivalent operations
"by hand" like you noticed.

You can always write your own specialized versions of these methods and
implicitly add them to Array, ArrayBuffer, etc. However, all the
non-array collections (including ArrayBuffer) box as well, so as you
observed specialized methods won't be of any benefit unless you create
your own specialized versions of the collections themselves.

Debox's current design is not stable (I haven't worked on it a bit, and
it was initially just a proof-of-concept). But I do think something
like it is necessary. You might also be interested in Basis [1] which
seems to be coming up with an alternate standard library design. I
haven't used it but it looks interesting.

If I get Debox into a state where it's ready to be released I'll
definitely email the list and let people know. It is definitely
possible to do much better in this area!

-- Erik

[1] https://github.com/ReifyIt/basis/

> 1. Same result using Array method "sum" (inherited from TraversableOnce,

> invokes foldLeft) instead of a local foldLeft

> 2. The Scala while loop is about 20% faster than the equivalent Java
> code!
> 3. Using a while loop to sum Array[java.lang.Integer] is 9.6x slower

> than the Array[Int] while loop

> 4. Summing an Array[java.lang.Integer], foldLeft is 26x slower than

> Array[Int] while loop
>
> (These figures are on a Core 2 Duo, WiFi disabled, no browsers, and reflect
> hotspot performance with gc reset over 100 reps. StdDev < 1%.)
>
>
> Of course many apps are not data intensive, and spend more time in IO or
> network operations, so even a 33x slowdown would not be noticed. For those
> data intensive apps where array performance does matter, the choice is

> between imperative style on few cores, *or* functional style to utilize

> many cores. This is an obstacle to the DRY principle.
>
>
> What then is the reason for this disparity in functional versus imperative
> performance? I only looked in detail at foldLeft, but I suspect similar
> issues underly other collection methods. By slowly morphing the generic
> foldLeft code into a fast while loop, and examining javap disassembled code
> where a small change made a big speed difference, the culprit turns out to
> be a Function2 wrapper on the function literal passed to foldLeft.
>
>
> In byte code, I clearly see primitive ints coming from the array, and the
> functional literal "_ + _" is compiled to a method <code>public final int
> apply(int, int)</code> that simply iadds the 2 ints. Unfortunately, that
> apply method is called by a Function2 apply method with the signature of
> <code>public final Object apply(Object, Object)</code>. Regardless of the
> types of the array or the "visitor" function literal, the compiler always
> creates a Function2 apply that forces boxing, both coming and going!
>
>
> This even explained #4 above, in which summing an array of Integer objects
> is faster than summing an array of ints, because it means that one less int
> needs boxing before calling Function2.apply.
>
>
> Despite my attention here to Array, I'm also interested in better
> performance for ArrayBuffer, ResizableArray and ParArray. Here's what I'd
> like to know:
>
>

> - Does anybody know of a workaround that lets me apply functions to
> primitive arrays without boxing?
> - Would will a future scalac compile to more polymorphic Function2 types

> that better match the Array type, when known?

> - Any other ideas for faster functions on collections?

>
> I did see that Erik has an alternative to Scala collections,
> https://github.com/non/debox . Are these APIs considered stable? I also
> attended Paul's Valentines Day talk,
> http://www.youtube.com/watch?v=o2WtIroR7Ag&feature=youtu.be , where he
> mentioned the lack of specialization support for Arrays, since they don't
> know about ClassTags. (None of what I've said will be surprising to Paul,
> and I don't imply that there's an easy fix!)
>
>
> Hope this sparks some productive discussion. - Bob K. (aka Kabob)
>
>

> --
> You received this message because you are subscribed to the Google Groups "scala-debate" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scala-debate...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Rex Kerr]

Goodness--you haven't seen this mentioned at all?  I guess it's all ended up buried in other discussions; at this point I was considering it so well known that it wasn't even worth mentioning.

One idea would be to use value classes to wrap primitive arrays with useful methods:

scala> class AWrap[@specialized T](val a: Array[T]) extends AnyVal {}
<console>:7: error: type parameter of value class may not be specialized
       class AWrap[@specialized T](val a: Array[T]) extends AnyVal {}

Well, so much for that.

So use debox or roll your own.  It is pretty easy to write Scala code that outputs Scala code:

def primitiveFoldGen(prim: String, acc: String) = s"""

  def pfold(a0: $acc)(f: ($acc,$prim) => $acc) = {

    var a = a0

    var i = 0

    while (i < xs.length) {

      a = f(a, xs(i))

      i += 1
    }

    a
  }
"""

def primitiveWrapperGen(prim: String) = s"""
implicit class RichArray$prim(val xs: Array[$prim]) extends AnyVal {

  ${List("Int", "Float", "Double", "Long").map(x => primitiveFoldGen(prim,x)).mkString}

}
"""

Let's give it a whirl:

val xs = Array.range(0,10000)

scala> th.pbenchOff()(xs.sum)(xs.pfold(0)(_ + _))
Benchmark comparison (in 1.381 s)
Significantly different (p ~= 0)
  Time ratio:    0.03484   95% CI 0.03440 - 0.03528   (n=30)
    First     115.5 us   95% CI 114.4 us - 116.6 us
    Second    4.024 us   95% CI 3.990 us - 4.057 us
res17: Int = 49995000

scala> th.pbenchOff(){var i,s=0; while(i<xs.length) { s+=xs(i); i += 1 }; s }(xs.pfold(0)(_ + _))
Benchmark comparison (in 791.7 ms)
Not significantly different (p ~= 0.6405)
  Time ratio:    0.99783   95% CI 0.98858 - 1.00709   (n=20)
    First     4.015 us   95% CI 3.988 us - 4.041 us
    Second    4.006 us   95% CI 3.980 us - 4.032 us
res18: Int = 49995000

Yup, looks like it works.

  --Rex

[Erik Osheim]

On Wed, Apr 10, 2013 at 10:26:46AM -0400, Rex Kerr wrote:
> One idea would be to use value classes to wrap primitive arrays with useful
> methods:
>
> scala> class AWrap[@specialized T](val a: Array[T]) extends AnyVal {}
> <console>:7: error: type parameter of value class may not be specialized
> class AWrap[@specialized T](val a: Array[T]) extends AnyVal {}
>
> Well, so much for that.

In this case we can do what Spire does and actually remap the implicit
ops conversion directly to the object methods at compile-time. For
instance:

object SpecializedArrayMethods {
def fastmap[@sp A, @sp B: ClassTag](arr: Array[A], f: A => B): Array[B] = ...

implicit class SpecializedArrayOps[A](arr: Array[A]) {
def fastmap[B: ClassTag](f: A => B) = macro Ops.rewrite1
}
}

The Ops.rewrite1 macro turn this:

val arr = Array(1,2,3,4,5)
new SpecializedArrayOps[Int](arr).fastmap[Double](n => math.pow(n, 2))(classTag)

into:

val arr = Array(1,2,3,4,5)
SpecializedArrayMethods.fastmap[Int, Double](arr, n => math.pow(n, 2))(classTag)

In fact, if we want we can also implement fastmap as a macro that
manually inlines anonymous functions into a custom while loop. Although
with the new work on the optimizer and closure elimination this may not
be necessary.

Anyway, since 2.10 has come out there have been a lot of exciting
developments. At this point we definitely have the tools to tackel the
problem, although I don't expect a solution in the standard library
soon.

-- Erik

[Robert Kohlenberger]

Thanks guys.

> Goodness--you haven't seen this mentioned at all?  I guess it's all ended up buried in other discussions;

> at this point I was considering it so well known that it wasn't even worth mentioning.

Well yes I've seen discussions, but not specific numbers like 33x slower functional performance over imperative, and not identifying a single wrapper as the reason for the boxing/unboxing.  Ultimately, I would like not to sacrifice functional parallelism for serial speed.  Although there is always some overhead, 33x seems excessive.  And I would like this integrated in the standard libs.  And I think it's doable.  The question is, at what effort?

> You can always write your own specialized versions of these methods and 

> implicitly add them to Array, ArrayBuffer, etc. However, all the 

> non-array collections (including ArrayBuffer) box as well, so as you 

> observed specialized methods won't be of any benefit unless you create 

> your own specialized versions of the collections themselves.

Actually I began my investigation of Array from the standpoint of creating fast replacements for ArrayBuffer and ResizableArray, without sacrificing their genericity or inheritance hierarchy. In this I actually succeeded.  My replacements use primitive arrays "under the covers" if the underlying types are primitive.  It was then that I belatedly saw that the underlying primitive arrays are not themselves functionally fast.

The goal of my post was actually to prompt us thinking about how to make the standard library fast (esp. regarding primitive arrays), yet without breaking the APIs.  Like I said, "Regardless of the types of the array or the "visitor" function literal, the compiler always creates a Function2 apply [signature: (Object, Object) => Object] that forces boxing, both coming and going!"  It seems like replacing this default wrapper with a Specialized-like solution would gain a lot of bang for the buck.  If the concern is code bloat in the libraries, combinatorial explosion can at least be avoided for common cases like (Int, Int) => Int.

Martin expressed somewhere (can't find the link) a concern that performance is a factor in the adoption decision for a technology.

If the choice Scala offers developers is always to reinvent the wheel or suffer poor performance, Scala's detractors have a valid argument.  As mentioned earlier, imperative Scala code can outperform Java (at least in my limited experiments), so I think there is an opportunity to actually flip the argument.  Can the standard libs be the performance champs without sacrificing either functionality or genericity?  This would be (yet another) major selling point for the language, and from what I've seen, it should be possible without a huge investment.  I could of course be wrong about the investment, but that's where I'm looking for more knowledgeable opinions.

> Anyway, since 2.10 has come out there have been a lot of exciting 

> developments. At this point we definitely have the tools to tackel the 

> problem, although I don't expect a solution in the standard library 

> soon.

Agreed, although I would like to lend my voice to goose the priority for the standard libs.

Thanks for your time talking about this!  - Bob

[Rex Kerr]

On Wed, Apr 10, 2013 at 6:11 PM, Robert Kohlenberger <kohl...@bdumail.com> wrote:

Thanks guys.

> Goodness--you haven't seen this mentioned at all?  I guess it's all ended up buried in other discussions;

> at this point I was considering it so well known that it wasn't even worth mentioning.

Well yes I've seen discussions, but not specific numbers like 33x slower functional performance over imperative

I guess we need to repeat history every now and again so we don't forget it.

From: Rex Kerr <ich...@gmail.com>
To: scala...@listes.epfl.ch

On Sat, Jan 23, 2010 at 2:00 PM, Ismael Juma <mli...@juma.me.uk> wrote:

> On Sat, 2010-01-23 at 13:54 -0500, Jonathan Shore wrote:
>
> Create a micro-benchmark suited to the JVM that compares a for
> comprehension with -optimise (and possibly specialized) and a while loop
> and show that the performance difference is still large.


I'd already done something much like this when I was working on a fast
vector library.  For example, comparing:
  - while loop with primitives
  - custom IntRange class with dedicated foreach
  - regular Range (extends Projection[Int])
  - for loop
  - reduceLeft
gives the following answers

$ scalac -optimise DoNotUseForOrReduce.scala
$ scala DoNotUseForOrReduce
Time (seconds): while=0.56 custom=4.81 foreach=4.67 for=6.13 reduce=13.82
Time (seconds): while=0.56 custom=4.72 foreach=4.67 for=6.13 reduce=13.97
Time (seconds): while=0.56 custom=4.66 foreach=4.73 for=6.15 reduce=14.14
Time (seconds): while=0.56 custom=4.65 foreach=4.71 for=6.13 reduce=14.11
Time (seconds): while=0.56 custom=4.69 foreach=4.61 for=6.14 reduce=14.16
(etc.)

which shows that a bare while is 8-25x faster than anything else.  That was
for 2.7.3; 2.8.0.r20326 is a bit better:

I suppose I should update this for 2.9 and 2.10 and 2.11 when it comes out.

, and not identifying a single wrapper as the reason for the boxing/unboxing

Well, wrapping is important if you want to reuse code.

 

The goal of my post was actually to prompt us thinking about how to make the standard library fast (esp. regarding primitive arrays), yet without breaking the APIs.  Like I said, "Regardless of the types of the array or the "visitor" function literal, the compiler always creates a Function2 apply [signature: (Object, Object) => Object] that forces boxing, both coming and going!"  It seems like replacing this default wrapper with a Specialized-like solution would gain a lot of bang for the buck.  If the concern is code bloat in the libraries, combinatorial explosion can at least be avoided for common cases like (Int, Int) => Int.

Indeed.  I mentioned this years ago, though maybe not quite as directly as you're stating here.  The issue right now is that you cannot independently specify which specialized types are okay, so you're left with more combinatorial explosion than you might like.

Anyway, I definitely would prefer a faster wheel, whether re-invented or modified.

  --Rex

 

[Robert Kohlenberger]

Just thinking "out of the box".

This may be a nutty idea (okay, it is), but hear me out.  What I observe in the foldLeft byte code is a kind of a "box sandwich" where the two slices of bread are my primitive Array[Int] and my function literal that compiles to (Int, Int) => Int.  In between them is the library code with its boxy Function2 apply(Object, Object) => Object.  Now all that apply method does is unbox the Integers that its own signature forced to be boxed, call my function literal with "invokevirtual  #33; //Method apply:(II)I", and then box the result back up again.

Suppose we leave the library code as it is, but have the compiler be smart enough to "erase" that pesky boxing apply in the middle?  I wouldn't even mind adding annotations in my code telling the compiler it's okay to do this.  Conceptually it's a little like type erasure, except that it's not types in source code being erased, but library code.  Call it "box erasure".

Okay I said it was a nutty idea.  But tell me what's wrong with it.

Thanks,

Bob

[Matthew Pocock]

Hi Bob,

This is called 'fusion' in the Haskell world. I think in scala it is only legal in the cases where the constructor has no side-effects and where any logic in the constructor can be in-lined. Also, we would need to ensure that the object identity does not escape and is not used e.g. via a synchronized block or by putting the object in a map or sending it to an actor or something. There may well be a whole load of obvious cases on a core set of boxed types where we could come up with a good heuristic to spot cases where this optimization is safe. However, I don't know enough about the scalac guts to be making more than a general guess.

Matthew

--

You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-debate...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Dr Matthew Pocock

Turing ate my hamster LTD

mailto: turingate...@gmail.com

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: matthew...@ncl.ac.uk

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Rex Kerr]

I think Miguel Garcia's optimizer will be able to do exactly this with adequate @inline annotations.  So someone's already outside of that particular box!

Another way to escape the box is to introduce the idea of  scratch space.  The collection doesn't need to know anything about all those other ints in order to do its job--it just has to stuff its items somewhere one at a time and be able to assume that the proper thing will happen.  So the collection code itself--which might be large and hairy and complex and not well-suited for specialization--only really needs to specialize on one parameter and take a FoldInput[@specialized A] { def apply(a: A): Unit }.  It then returns the exact same parameter

  def fold(fi: FoldInput[A]): fi.type

which lo and behold is actually a compiler-generated

  anon$1 extends FoldInput[Int] with Accumulator[Byte]

and we're all good.  The anonymous class provides the scratch space and does the appropriate operation on the apply, and the compiler would add sugar to retrieve the result from the accumulator.  This _does_ require one object creation per fold, but that's a lot better than an object creation per step.  (It also prevents some JVM optimization strategies, since the intermediate value does have to be stored in a place inaccessible to the calling code, so that can't really be optimized away.)

  --Rex

Bob

--

[Robert Kohlenberger]

Rex, I see where you're going with the scratch space idea.  A universal 64-bit space would accommodate any primitive value from Boolean to Long/Double.  The foldLeft (or other) lib code just puts the next collection element, whatever the type, into the scratch space provided by the compiled client, which already knows the type so there's no boxing.  This would be a revamp of the collections lib and cooperation from the compiler.

That's quite different from the "box erasure" idea, which would seem to require a post-compile rewriting of byte-codes.

However this is accomplished, the benchmarks indicate that the the payoff would be huge.  Functional programming on its own, without collections, has its uses, but any kind of scientific or analytical computing (my interest) is going to need efficient operations on large collections.  The whole reason I was drawn to Scala was the promise of fast functional parallelism, so this discovery was sobering for me.

I move making a SIP out of this.  Anyone agree?  Disagree? Ambivalent? Comatose?

[Robert Kohlenberger]

Hi Matthew,

I'm no expert on Haskell's fusion, but I believe it avoids not just boxing, but creation of intermediate collections altogether, which is very cool btw.  However I'm calling functions on existing collections, so I'm not sure it's the same thing.  The boxed values are local and without side effects.  The only reason boxing is done here is to have a universal interface so collections can be generic.  But it seems there are better ways to be generic without taking the tremendous performance hit.

[Jason Zaugg]

You might be interested in Vlad Ulreche's current research into miniboxing [1]. I believe that the associated paper is due for publication shortly.

I recently worked on a large code base for financial math. Efficiency with Array[Double] was indeed paramount in the tight loops. We ended up rolling our own library of functions for mapping, zipping, and transforming these. At times, this means you must leave FunctionN behind, and instead use your own callback interfaces (e.g. abstract class DoubleDoubleAnyFunction[A] { def apply(a: Double, b: Double): A }), so as to avoid boxing. In the end, we didn't need a vast library of these, and it wan't too onerous to define them ourselves. But standardization would be nice, and even better, it would be great to program these generically.

-jason

[1] https://github.com/miniboxing 

[Dan Shryock]

I know it isn't likely to happen any time soon, but I've felt for a while now that of scala should have a native binary form for library distribution. 

It should still contain all of the scala type information, and be ready to be transformed into bytecode, CIL, JavaScript, etc...

This could allow custom specialization for only used types during a linking phase, and if there were some proof of referential integrity and finality, it could even do some aggressive inlining. 

Something like this could even be used to mitigate the recent problems with the addition of generics to the Swing libraries by using some sort of customized stub library that hides the generics. 

Dan