FYI: Price of Abstraction

Christian Szegedy wrote:
> Simple comparison on the overhead of abstraction in Scala, OCaml and C++ :
>
> http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
>
Complex is probably the worst case example for abstraction overhead in
languages built on the JVM. The results might be better if the latest
1.6u14 was used with escape analysis enabled (only in the server version).

Mark Thornton

While we're on the subject:

http://gmarceau.qc.ca/blog/2009/05/speed-size-and-dependability-of.html

On Mon, Jun 1, 2009 at 10:26 AM, Mark Thornton <mthornton@optrak.co.uk> wrote:

Christian Szegedy wrote:

Simple comparison on the overhead of abstraction in Scala, OCaml and C++ :

http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
 

Complex is probably the worst case example for abstraction overhead in languages built on the JVM. The results might be better if the latest 1.6u14 was used with escape analysis enabled (only in the server version).

Mark Thornton

--
Viktor Klang
Rockstar Developer

And the last example uses reflection, which is probably the slowest possible way to achieve the intended level of abstraction.

--j

On Mon, Jun 1, 2009 at 1:26 AM, Mark Thornton <mthornton@optrak.co.uk> wrote:

Christian Szegedy wrote:

Simple comparison on the overhead of abstraction in Scala, OCaml and C++ :

http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
 

Complex is probably the worst case example for abstraction overhead in languages built on the JVM. The results might be better if the latest 1.6u14 was used with escape analysis enabled (only in the server version).

Mark Thornton

On Monday June 1 2009, Mark Thornton wrote:
> Christian Szegedy wrote:
> > Simple comparison on the overhead of abstraction in Scala, OCaml
> > and C++ :
> >
> > http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
>
> Complex is probably the worst case example for abstraction overhead
> in languages built on the JVM. The results might be better if the
> latest 1.6u14 was used with escape analysis enabled (only in the
> server version).

To what use is escape analysis put in this version of the JVM? My
understanding was that escape analysis was used only for eliding
locking operations. Does it now allow bypassing heap allocation in
favor of the stack for allocations that are provably local?

> Mark Thornton

Randall Schulz

Randall R Schulz wrote:
> On Monday June 1 2009, Mark Thornton wrote:
>

> Does it now allow bypassing heap allocation in
> favor of the stack for allocations that are provably local?
>
I understand that it does now convert some heap allocations into stack use.

http://blog.juma.me.uk/tag/scalar-replacement/

Mark Thornton

On Monday June 1 2009, Viktor Klang wrote:
> While we're on the subject:
>
> 

That's certainly interesting. I have to wonder how idiomatic the code
is, given Scala's position on the vertical axis.

Also, I'd like to see a higher resolution picture, 'cause the means that
define the center of each stars are not particularly informative in the
presence of outliers, which Scala apparently has. I'd like to see
individual points and also associate them with the individual benchmark
the represent.

In general, I wonder how good implementations of the benchmarks were
obtained for so many languages. The approach looks informative, but I'm
suspicious that the results are indicative of what would be obtained by
a skilled and experienced programmer familiar with a given language.

Randall Schulz

You are right: I wanted to test the worst case performance hit, as I
pointed out in the introduction of the posting.

I used the example with complex numbers, since the methods are
1) small
2) called very frequently
3) does not need much memory (although the the results of the
operations are allocated on the heap)

The 3rd implementation: I did not want to suggest that it is a good
way to write the complex class. It is simply a case study on how much
performance do we loose if the maximum amount of genericity is
applied. This example is fairly similar to the default OCaml example,
since OCaml uses a structural type system for objects per default.

It is also both syntactically similar and semantically equivalent to
the C++-version, although C++'s implementation is much more efficient
as it resolves templates in compilation time.

On Mon, Jun 1, 2009 at 1:38 AM, Jorge Ortiz wrote:
> And the last example uses reflection, which is probably the slowest possible
> way to achieve the intended level of abstraction.
>
> --j
>
> On Mon, Jun 1, 2009 at 1:26 AM, Mark Thornton
> wrote:
>>
>> Christian Szegedy wrote:
>>>
>>> Simple comparison on the overhead of abstraction in Scala, OCaml and C++
>>> :
>>>
>>> http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
>>>
>>
>> Complex is probably the worst case example for abstraction overhead in
>> languages built on the JVM. The results might be better if the latest 1.6u14
>> was used with escape analysis enabled (only in the server version).
>>
>> Mark Thornton
>>
>
>

Could you show a faster way to achieve the exact same level of abstraction?

(Defining a trait with x and y is less generic as it would require the parameter
to extend or mix in the trait.)

On Mon, Jun 1, 2009 at 1:38 AM, Jorge Ortiz wrote:
> And the last example uses reflection, which is probably the slowest possible
> way to achieve the intended level of abstraction.

At the cost of some boilerplate code, you can use something like the typeclass pattern:

  trait XY[T] {
    def x(t: T): Double
    def y(t: T): Double
  }

  final case class Complex2(x: Double, y: Double) {
    def norm_square = x*x + y*y
    def +[T](other: T)(implicit xy: XY[T]) = new Complex2(x + xy.x(other), y + xy.y(other))
    def *[T](other: T)(implicit xy: XY[T]) = new Complex2(x * xy.x(other), y * xy.y(other))
  }

  implicit val Complex2XY = new XY[Complex2] {
    def x(c: Complex2) = c.x
    def y(c: Complex2) = c.y
  }

You need to define an implicit XY[T] instance for any T you want to use, which is a bit of a drag, but as it can be defined by either the provider of T or the user of T, it shouldn't limit the possible abstraction.

--j

On Mon, Jun 1, 2009 at 10:21 AM, Christian Szegedy <christian.szegedy@gmail.com> wrote:

Could you show a faster way to achieve the exact same level of abstraction?

(Defining a trait with x and y is less generic as it would require the parameter
to extend or mix in the trait.)

On Mon, Jun 1, 2009 at 1:38 AM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:
> And the last example uses reflection, which is probably the slowest possible
> way to achieve the intended level of abstraction.

I do not trust these benchmarks. They run Java with -server. They don't
run Scala with -server. A particular Java program uses a high
performance big integer library via JNI etc.
I have thought about providing better Scala implementations for some
programs in there, but I don't think it has much value, since generally
these benchmarks can't be well trusted.

Erkki

Randall R Schulz wrote:
> In general, I wonder how good implementations of the benchmarks were
> obtained for so many languages. The approach looks informative, but I'm
> suspicious that the results are indicative of what would be obtained by
> a skilled and experienced programmer familiar with a given language.
>

On Monday June 1 2009, Erkki Lindpere wrote:
> Randall R Schulz wrote:
> > In general, I wonder how good implementations of the benchmarks
> > were obtained for so many languages. The approach looks
> > informative, but I'm suspicious that the results are indicative of
> > what would be obtained by a skilled and experienced programmer
> > familiar with a given language.
>
> I do not trust these benchmarks. They run Java with -server. They
> don't run Scala with -server. A particular Java program uses a high
> performance big integer library via JNI etc.
> I have thought about providing better Scala implementations for some
> programs in there, but I don't think it has much value, since
> generally these benchmarks can't be well trusted.
>
> Erkki

Rare is the benchmark that is to be trusted. And JNI is no panacea. Sun
found that the old big integer library that accessed a C library via
JNI performed worse than a pure Java implementation, which is what we
have now.

The pictures are pretty, though. Kind of like a similar matrix of
supernova light-intensity-vs-time plots I saw recently.

RRS

Randall R Schulz wrote:
> Rare is the benchmark that is to be trusted. And JNI is no panacea. Sun
> found that the old big integer library that accessed a C library via
> JNI performed worse than a pure Java implementation, which is what we
> have now.
>
A difficulty with BigInteger/BigDecimal is that there are two very
different use cases. The first concerns not very big numbers where the
developer wants exact or decimal behaviour rather than binary (or
floating point). A typical example of this use is for currency values
(even the national debt is a small number for a mathematician). The
other use is for mathematical purposes (in which I include encryption)
where the numbers can be enormous by any standard. JNI overhead hurts
the first class of use quite badly while being less significant for the
second use case.

Mark Thornton

Thanks, I tried this out. It was about 3 times faster than the reflectivity
based implementation and two times slower than the second (simple
class based) implementation.

Thanks for your hint, it is a good pattern to keep in mind for the case
when a high level of genericity is really necessary.

On Mon, Jun 1, 2009 at 11:32 AM, Jorge Ortiz wrote:
> At the cost of some boilerplate code, you can use something like the
> typeclass pattern:
>
>   trait XY[T] {
>     def x(t: T): Double
>     def y(t: T): Double
>   }
>
>   final case class Complex2(x: Double, y: Double) {
>     def norm_square = x*x + y*y
>     def +[T](other: T)(implicit xy: XY[T]) = new Complex2(x + xy.x(other), y
> + xy.y(other))
>     def *[T](other: T)(implicit xy: XY[T]) = new Complex2(x * xy.x(other), y
> * xy.y(other))
>   }
>
>   implicit val Complex2XY = new XY[Complex2] {
>     def x(c: Complex2) = c.x
>     def y(c: Complex2) = c.y
>   }
>
> You need to define an implicit XY[T] instance for any T you want to use,
> which is a bit of a drag, but as it can be defined by either the provider of
> T or the user of T, it shouldn't limit the possible abstraction.
>
> --j
>
> On Mon, Jun 1, 2009 at 10:21 AM, Christian Szegedy
> wrote:
>>
>> Could you show a faster way to achieve the exact same level of
>> abstraction?
>>
>> (Defining a trait with x and y is less generic as it would require the
>> parameter
>> to extend or mix in the trait.)
>>
>> On Mon, Jun 1, 2009 at 1:38 AM, Jorge Ortiz wrote:
>> > And the last example uses reflection, which is probably the slowest
>> > possible
>> > way to achieve the intended level of abstraction.
>
>

On Tue, Jun 2, 2009 at 9:44 PM, Mark Thornton <mthornton@optrak.co.uk> wrote:

Rüdiger Klaehn wrote:

On Mon, Jun 1, 2009 at 10:26 AM, Mark Thornton <mthornton@optrak.co.uk <mailto:mthornton@optrak.co.uk>> wrote:

   Christian Szegedy wrote:

       Simple comparison on the overhead of abstraction in Scala,
       OCaml and C++ :

       http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
       
   Complex is probably the worst case example for abstraction
   overhead in languages built on the JVM.

I don't think so. Wrapping a single scalar value (e.g. a double) to give different implementations for some operators or to have several distinct types for different physical quantities would be even worse. And that is a quite common and useful scenario.  
   The results might be better if the latest 1.6u14 was used with
   escape analysis enabled (only in the server version).  

Are you sure that 1.6u14 uses stack allocation? Last I heard java 1.6 does escape analysis, but only uses the results to remove or coarsen locks, but not do to stack allocation.

Yes it is new in update 14, but isn't enabled by default.

Mark

Great. According to my tests it makes a huge difference. Do you know the command line parameter to enable it, or is it enabled by default when running with "-server"?

-XX:+DoEscapeAnalysis

--j

On Tue, Jun 2, 2009 at 1:05 PM, Rüdiger Klaehn <rklaehn@googlemail.com> wrote:

On Tue, Jun 2, 2009 at 9:44 PM, Mark Thornton <mthornton@optrak.co.uk> wrote:

Rüdiger Klaehn wrote:

On Mon, Jun 1, 2009 at 10:26 AM, Mark Thornton <mthornton@optrak.co.uk <mailto:mthornton@optrak.co.uk>> wrote:

   Christian Szegedy wrote:

       Simple comparison on the overhead of abstraction in Scala,
       OCaml and C++ :

       http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
       
   Complex is probably the worst case example for abstraction
   overhead in languages built on the JVM.

I don't think so. Wrapping a single scalar value (e.g. a double) to give different implementations for some operators or to have several distinct types for different physical quantities would be even worse. And that is a quite common and useful scenario.  
   The results might be better if the latest 1.6u14 was used with
   escape analysis enabled (only in the server version).  

Are you sure that 1.6u14 uses stack allocation? Last I heard java 1.6 does escape analysis, but only uses the results to remove or coarsen locks, but not do to stack allocation.

Yes it is new in update 14, but isn't enabled by default.

Mark

Great. According to my tests it makes a huge difference. Do you know the command line parameter to enable it, or is it enabled by default when running with "-server"?

On Tue, Jun 2, 2009 at 10:21 PM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

-XX:+DoEscapeAnalysis

Ah yeah, now we're talkin!
 

--j

On Tue, Jun 2, 2009 at 1:05 PM, Rüdiger Klaehn <rklaehn@googlemail.com> wrote:

On Tue, Jun 2, 2009 at 9:44 PM, Mark Thornton <mthornton@optrak.co.uk> wrote:

Rüdiger Klaehn wrote:

On Mon, Jun 1, 2009 at 10:26 AM, Mark Thornton <mthornton@optrak.co.uk <mailto:mthornton@optrak.co.uk>> wrote:

   Christian Szegedy wrote:

       Simple comparison on the overhead of abstraction in Scala,
       OCaml and C++ :

       http://arachnism.blogspot.com/2009/05/price-of-abstraction.html
       
   Complex is probably the worst case example for abstraction
   overhead in languages built on the JVM.

I don't think so. Wrapping a single scalar value (e.g. a double) to give different implementations for some operators or to have several distinct types for different physical quantities would be even worse. And that is a quite common and useful scenario.  
   The results might be better if the latest 1.6u14 was used with
   escape analysis enabled (only in the server version).  

Are you sure that 1.6u14 uses stack allocation? Last I heard java 1.6 does escape analysis, but only uses the results to remove or coarsen locks, but not do to stack allocation.

Yes it is new in update 14, but isn't enabled by default.

Mark

Great. According to my tests it makes a huge difference. Do you know the command line parameter to enable it, or is it enabled by default when running with "-server"?

--
Viktor Klang
Rockstar Developer

On Tue, Jun 2, 2009 at 3:21 PM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

-XX:+DoEscapeAnalysis

I tried it a couple of days ago using a microbenchmark with a simple for/to loop, which is notoriously slow in Scala, and couldn't see any improvement.

On Wed, Jun 3, 2009 at 6:15 PM, Nils Kilden-Pedersen <nilskp@gmail.com> wrote:

On Tue, Jun 2, 2009 at 3:21 PM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

-XX:+DoEscapeAnalysis

I tried it a couple of days ago using a microbenchmark with a simple for/to loop, which is notoriously slow in Scala, and couldn't see any improvement.

Maybe it cannot determine that the reference is not escaping it's scope. I'm not fully sure how advanced the escape analyzer is, or how aggressively it optimizes.
Also, please note that it cannot optimize the valueOf stuff, it must see an actual "new" allocation.

--
Viktor Klang
Rockstar Developer

On Wed, 2009-06-03 at 18:40 +0200, Viktor Klang wrote:
> Maybe it cannot determine that the reference is not escaping it's
> scope. I'm not fully sure how advanced the escape analyzer is, or how
> aggressively it optimizes.
> Also, please note that it cannot optimize the valueOf stuff, it must
> see an actual "new" allocation.

I haven't tried, but I've seen some commits related to this. It does
know about valueOf, but not sure how well it deals with it at this stage
(particularly the version of HotSpot included in JDK6u14). However, the
Scala boxing methods are a different story. Luckily, Scala 2.8.0 will
just use the ones from Java (courtesy of paulp).

Best,
Ismael

On Wed, Jun 3, 2009 at 11:40 AM, Viktor Klang <viktor.klang@gmail.com> wrote:

On Wed, Jun 3, 2009 at 6:15 PM, Nils Kilden-Pedersen <nilskp@gmail.com> wrote:

On Tue, Jun 2, 2009 at 3:21 PM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

-XX:+DoEscapeAnalysis

I tried it a couple of days ago using a microbenchmark with a simple for/to loop, which is notoriously slow in Scala, and couldn't see any improvement.

Maybe it cannot determine that the reference is not escaping it's scope. I'm not fully sure how advanced the escape analyzer is, or how aggressively it optimizes.
Also, please note that it cannot optimize the valueOf stuff, it must see an actual "new" allocation.

It was a simple loop within one method counting from 0 to 100,000,000 (so "new" allocation will dominate), and I was switching between for and while loops, of course while loops being 4-5 times faster, regardless of the escape analysis flag.

On Wed, 2009-06-03 at 11:53 -0500, Nils Kilden-Pedersen wrote:

> It was a simple loop within one method counting from 0 to 100,000,000
> (so "new" allocation will dominate), and I was switching between for
> and while loops, of course while loops being 4-5 times faster,
> regardless of the escape analysis flag.

The problem is that Scala doesn't just call new, it calls BoxesRuntime
that returns cached values if they're within a certain range. In other
words, exactly what Viktor is talking about.

See the following for tests that were done a few months ago (I haven't
had a chance to retest for some time):

http://blog.juma.me.uk/2008/12/17/objects-with-no-allocation-overhead/

A commenter (miau) had the courtesy of pasting the assembly generated so
people can compare.

Best,
Ismael

On Wed, Jun 3, 2009 at 12:01 PM, Ismael Juma <mlists@juma.me.uk> wrote:

On Wed, 2009-06-03 at 11:53 -0500, Nils Kilden-Pedersen wrote:

> It was a simple loop within one method counting from 0 to 100,000,000
> (so "new" allocation will dominate), and I was switching between for
> and while loops, of course while loops being 4-5 times faster,
> regardless of the escape analysis flag.

The problem is that Scala doesn't just call new, it calls BoxesRuntime
that returns cached values if they're within a certain range. In other
words, exactly what Viktor is talking about.

Yes, it caches about a 1024's worth, but in an iteration of 100 million that is not why. I'd be nice if the Scala compiler people could make Scala more efficient by testing with escape analysis and figuring out how to improve some of the more egregious slowness issues.

On Wed, 2009-06-03 at 12:27 -0500, Nils Kilden-Pedersen wrote:

> Yes, it caches about a 1024's worth, but in an iteration of 100
> million that is not why.

I think you're misunderstanding my point. :) The logic for retrieving
cached values makes it harder for escape analysis to detect that the
allocation can be elided.

> I'd be nice if the Scala compiler people could make Scala more
> efficient by testing with escape analysis and figuring out how to
> improve some of the more egregious slowness issues.

As I said, Scala 2.8.0 will use Java's autoboxing methods so one
obstacle is removed. Also, the specialized branch is meant to solve
similar issues but at a different level.

Best,
Ismael

On Wed, Jun 3, 2009 at 12:30 PM, Ismael Juma <mlists@juma.me.uk> wrote:

On Wed, 2009-06-03 at 12:27 -0500, Nils Kilden-Pedersen wrote:

> Yes, it caches about a 1024's worth, but in an iteration of 100
> million that is not why.

I think you're misunderstanding my point. :) The logic for retrieving
cached values makes it harder for escape analysis to detect that the
allocation can be elided.

Only if those methods aren't inlined, but maybe the call stack is too deep, making the inline threshold overflow. I should try increasing the inline threshold too.

On Wed, Jun 3, 2009 at 6:53 PM, Ismael Juma <ismael@juma.me.uk> wrote:

On Wed, 2009-06-03 at 18:40 +0200, Viktor Klang wrote:
> Maybe it cannot determine that the reference is not escaping it's
> scope. I'm not fully sure how advanced the escape analyzer is, or how
> aggressively it optimizes.
> Also, please note that it cannot optimize the valueOf stuff, it must
> see an actual "new" allocation.

I haven't tried, but I've seen some commits related to this. It does
know about valueOf, but not sure how well it deals with it at this stage
(particularly the version of HotSpot included in JDK6u14). However, the
Scala boxing methods are a different story. Luckily, Scala 2.8.0 will
just use the ones from Java (courtesy of paulp).

That's good news! Last I looked at it I got the impression that it only kept track of "new".


 

Best,
Ismael

Best regards
--
Viktor Klang
Rockstar Developer

* On Wed, 2009-06-03 at 13:09 -0500, Nils Kilden-Pedersen wrote:
> On Wed, Jun 3, 2009 at 12:30 PM, Ismael Juma
> wrote:
>
> I think you're misunderstanding my point. :) The logic for
> retrieving
> cached values makes it harder for escape analysis to detect
> that the
> allocation can be elided.
>
>
> Only if those methods aren't inlined, but maybe the call stack is too
> deep, making the inline threshold overflow. I should try increasing
> the inline threshold too.

What I said still stands. It makes it harder. With the implementation of
escape analysis from a few months back, it even defeats it most of the
times (if not all the times). Inlining enables a variety of
optimisations and could help here. Whether it does for HotSpot
currently, that's unclear.

Best,
Ismael