Scala for scientific computing

[kh92]

Hi everyone,

I have been checking out lots of programming languages for their  
suitability for scientific computing over the years. Recently I  
discovered Scala, whose mix of OO and functional features looks very  
interesting for this field. Has anyone else already looked at  
scientific applications of Scala? In that case, I would appreciate  
comments on the following points:

- Multidimensional arrays. Scala doesn't have them as part of the  
language definition. Would it be possible to implement them in a  
library in terms of unidimensional arrays, with optional bounds  
checking, reasonable syntax for retrieving and setting elements, and  
without a prohibitive runtime overhead?

- Small immutable objects. Many scientific applications need number-
like types that are characterized by being small (in terms of  
memory), immutable, and very frequently created in mathematical  
expressions. Examples are complex numbers, points in 2D or 3D space,  
or physical quantities represented by a value and a unit. For such  
types, the overhead of object handling (creation, destruction,  
garbage collection) is often very high and the object models of most  
OO languages do not permit the compiler to optimize away the creation  
the temporary objects, because it cannot know that the objects are  
immutable and their creation/destruction free of side effects. Since  
immutability and absence of side effects are cornerstones of  
functional programming, I wonder if Scala does better there.

Konrad.

[David MacIver]

On Mon, Mar 31, 2008 at 9:39 AM, Konrad Hinsen
<[hidden email]> wrote:

> Hi everyone,
>
>  I have been checking out lots of programming languages for their
>  suitability for scientific computing over the years. Recently I
>  discovered Scala, whose mix of OO and functional features looks very
>  interesting for this field. Has anyone else already looked at
>  scientific applications of Scala? In that case, I would appreciate
>  comments on the following points:
>
>  - Multidimensional arrays. Scala doesn't have them as part of the
>  language definition. Would it be possible to implement them in a
>  library in terms of unidimensional arrays, with optional bounds
>  checking, reasonable syntax for retrieving and setting elements, and
>  without a prohibitive runtime overhead?

There are various Java libraries for this, and their performance seems
to be adequate. It should be possible to reskin them to a more
acceptable syntax for Scala.

>  - Small immutable objects. Many scientific applications need number-
>  like types that are characterized by being small (in terms of
>  memory), immutable, and very frequently created in mathematical
>  expressions. Examples are complex numbers, points in 2D or 3D space,
>  or physical quantities represented by a value and a unit. For such
>  types, the overhead of object handling (creation, destruction,
>  garbage collection) is often very high and the object models of most
>  OO languages do not permit the compiler to optimize away the creation
>  the temporary objects, because it cannot know that the objects are
>  immutable and their creation/destruction free of side effects. Since
>  immutability and absence of side effects are cornerstones of
>  functional programming, I wonder if Scala does better there.

As far as I know, it doesn't. The JVM makes it pretty difficult to do
and Scala's semantics encourage but don't require immutability and a
lack of side effects. So what you end up with is the same per object
overhead as Java (occasionally slightly more if you use features like
laziness) and a lot more small objects. The JVM allocator performance
and GC are pretty good, so this isn't as big an issue as it could be,
but it can hurt your memory consumption pretty badly.

[Imam Tashdid ul Alam]

Hi Konrad,
I'm not sure what you are asking for here.
I see two alternative:
1) You want to do some scientific computing in Scala.
You are checking if libraries are available.
2) You want to contribute to the basic building blocks
of a scientific computing library written in Scala.
If it's #2, I'm in! Let's start a project!
If it's #1, then I'll be glad to answer the questions.

--- Konrad Hinsen <...> wrote:

> Hi everyone,
>
> I have been checking out lots of programming
> languages for their  
> suitability for scientific computing over the years.
> Recently I  
> discovered Scala, whose mix of OO and functional
> features looks very  
> interesting for this field. Has anyone else already
> looked at  
> scientific applications of Scala? In that case, I
> would appreciate  
> comments on the following points:
>
> - Multidimensional arrays. Scala doesn't have them
> as part of the  
> language definition. Would it be possible to
> implement them in a  
> library in terms of unidimensional arrays, with
> optional bounds  
> checking, reasonable syntax for retrieving and
> setting elements, and  
> without a prohibitive runtime overhead?

Yes it would indeed. Here's one possible
implementation.

2-dimensional array:

<scala>
class Array2D[A](val N1: Int, val N2: Int) extends
((Int, Int) => A) {
  private val holder = Array[A](N1 * N2)

  def apply(i: Int, j: Int) = holder(i * N1 + j)
  def update(i: Int, j: Int, a: A) = {
    holder(i * N1 + j) = a
  }
}
</scala>

[Note: don't complain if it doesn't complain. I
haven't tried it]

You got to decide which higher-order functions you
want.

>
> - Small immutable objects. Many scientific
> applications need number-
> like types that are characterized by being small (in
> terms of  
> memory), immutable, and very frequently created in
> mathematical  
> expressions. Examples are complex numbers, points in
> 2D or 3D space,  
> or physical quantities represented by a value and a
> unit. For such  
> types, the overhead of object handling (creation,
> destruction,  
> garbage collection) is often very high and the
> object models of most  
> OO languages do not permit the compiler to optimize
> away the creation  
> the temporary objects, because it cannot know that
> the objects are  
> immutable and their creation/destruction free of
> side effects. Since  
> immutability and absence of side effects are
> cornerstones of  
> functional programming, I wonder if Scala does
> better there.
>

This is what Scala is made of.

> Konrad.
>
>

Cheers,
Imam


      ____________________________________________________________________________________
Special deal for Yahoo! users & friends - No Cost. Get a month of Blockbuster Total Access now
http://tc.deals.yahoo.com/tc/blockbuster/text3.com

[Imam Tashdid ul Alam]

I think a little correction is required...
--- Imam Tashdid ul Alam <...> wrote:

> > For such  
> > types, the overhead of object handling (creation,
> > destruction,  
> > garbage collection) is often very high and the
> > object models of most  
> > OO languages do not permit the compiler to
> optimize
> > away the creation  
> > the temporary objects, because it cannot know that
> > the objects are  
> > immutable and their creation/destruction free of
> > side effects. Since  
> > immutability and absence of side effects are
> > cornerstones of  
> > functional programming, I wonder if Scala does
> > better there.
> >

> This is what Scala is made of.
>
> Cheers,
> Imam

I meant "made for" instead of "made for" [what a typo]
What I meant to say is that the need to optimize the
VM is up to the people involved with the VM. A
programming language like Scala is there to emphasize
the notion of purity [meaning: referential
transparency whenever possible]. With heaps and heaps
of objects being created on the heap by heaps and
heaps of Scala programs will definitely put the
pressure!

:-)


      ____________________________________________________________________________________
Like movies? Here's a limited-time offer: Blockbuster Total Access for one month at no cost.
http://tc.deals.yahoo.com/tc/blockbuster/text4.com

[kh92]

On 31.03.2008, at 13:55, Imam Tashdid ul Alam wrote:

> I'm not sure what you are asking for here.
> I see two alternative:
> 1) You want to do some scientific computing in Scala.
> You are checking if libraries are available.
> 2) You want to contribute to the basic building blocks
> of a scientific computing library written in Scala.

I am both interested in existing work/libraries for scientific  
computing and in possibilities for the future. My main objective at  
this time is evaluating if Scala is a serious candidate for a  
scientific computing language, i.e. if the important abstractions of  
scientific computing can be implemented in a way that makes them both  
efficient and convenient to use. I don't expect that question to have  
a simple yes/no answer.


On 31.03.2008, at 11:44, David MacIver wrote:

>>  - Multidimensional arrays. Scala doesn't have them as part of the
>>  language definition. Would it be possible to implement them in a
>>  library in terms of unidimensional arrays, with optional bounds
>>  checking, reasonable syntax for retrieving and setting elements, and
>>  without a prohibitive runtime overhead?
>
> There are various Java libraries for this, and their performance seems
> to be adequate. It should be possible to reskin them to a more
> acceptable syntax for Scala.

That sounds reasonable.

>>  - Small immutable objects. Many scientific applications need number-
>>  like types that are characterized by being small (in terms of
>>  memory), immutable, and very frequently created in mathematical
>>  expressions. Examples are complex numbers, points in 2D or 3D space,
...
>>  functional programming, I wonder if Scala does better there.
>
> As far as I know, it doesn't. The JVM makes it pretty difficult to do
> and Scala's semantics encourage but don't require immutability and a
> lack of side effects.

I don't see how the JVM could be an obstacle. In the situations I am  
thinking off, an optimizing compiler would optimize the whole class  
away and replace its methods by inlined code operating on basic data  
types. For example, arithmetic on complex numbers would be replaced  
by operations on the real and complex parts, represented by floats.  
The JVM would never see the original class, although it might be  
necessary/desirable to have a class version of "complex" around as  
well for specific situations.

> So what you end up with is the same per object
> overhead as Java (occasionally slightly more if you use features like
> laziness) and a lot more small objects. The JVM allocator performance
> and GC are pretty good, so this isn't as big an issue as it could be,
> but it can hurt your memory consumption pretty badly.

It's not good news for performance either. I'll take again the  
example of complex numbers. A complex number addition requires two  
float additions. As a method in a complex class, it requires one  
object creation/destruction/gc cycle in addition. I am pretty sure  
that the overhead is more than 100% of the real work. It gets worse  
if you consider lost optimization opportunities, both at (Scala)  
compile time and at run (JIT compile) time. For example, a  
multiplication by the imaginary unit written as a constant can be  
optimized to a sign change, and most often in the context of a larger  
expression it can be optimized away completely.

Physical units are an even more drastic example as the corresponding  
classes exist for nothing else but type checking. At run time, only  
the basic numerical operations on the values should remain, i.e. zero  
overhead. Of the programming languages I know, only C++ permits such  
a definition (for example in boost::pqs), but it is sufficiently ugly  
that hardly anyone uses it in practice.

Konrad.

[David MacIver]

On Mon, Mar 31, 2008 at 1:37 PM, Konrad Hinsen
<[hidden email]> wrote:

>  >>  - Small immutable objects. Many scientific applications need number-
>  >>  like types that are characterized by being small (in terms of
>  >>  memory), immutable, and very frequently created in mathematical
>  >>  expressions. Examples are complex numbers, points in 2D or 3D space,
>  ...
>
> >>  functional programming, I wonder if Scala does better there.
>  >
>
> > As far as I know, it doesn't. The JVM makes it pretty difficult to do
>  > and Scala's semantics encourage but don't require immutability and a
>  > lack of side effects.
>
>  I don't see how the JVM could be an obstacle. In the situations I am
>  thinking off, an optimizing compiler would optimize the whole class
>  away and replace its methods by inlined code operating on basic data
>  types. For example, arithmetic on complex numbers would be replaced
>  by operations on the real and complex parts, represented by floats.
>  The JVM would never see the original class, although it might be
>  necessary/desirable to have a class version of "complex" around as
>  well for specific situations.

Well, for example "basic data types" doesn't include any sort of
compound data type. There's no VM level concept of a struct type data
type - a method must return either one of the standard numeric
primitives or an object. It can't for example return a pair of floats.

The sort of optimising compiler you want should certainly be
*possible* for the JVM, but I'm not aware of any examples.  Scalac
certainly doesn't. Maybe some of the bytecode optimization frameworks
will do something like this, but I doubt it. I think it's a sufficient
amount of work to achieve these results that people who are going to
put in the effort just go straight to generating machine code.

>  > So what you end up with is the same per object
>  > overhead as Java (occasionally slightly more if you use features like
>  > laziness) and a lot more small objects. The JVM allocator performance
>  > and GC are pretty good, so this isn't as big an issue as it could be,
>  > but it can hurt your memory consumption pretty badly.
>
>  It's not good news for performance either. I'll take again the
>  example of complex numbers. A complex number addition requires two
>  float additions. As a method in a complex class, it requires one
>  object creation/destruction/gc cycle in addition. I am pretty sure
>  that the overhead is more than 100% of the real work. It gets worse
>  if you consider lost optimization opportunities, both at (Scala)
>  compile time and at run (JIT compile) time. For example, a
>  multiplication by the imaginary unit written as a constant can be
>  optimized to a sign change, and most often in the context of a larger
>  expression it can be optimized away completely.
>
>  Physical units are an even more drastic example as the corresponding
>  classes exist for nothing else but type checking. At run time, only
>  the basic numerical operations on the values should remain, i.e. zero

Sure. I'm not disputing that you can do better than Scala currently
does. But it's an awful lot of work to do so, and I'm afraid Scala
isn't designed for high performance numerical computing. All I'm
saying is that the current performance is not too bad.

>  overhead. Of the programming languages I know, only C++ permits such
>  a definition (for example in boost::pqs), but it is sufficiently ugly
>  that hardly anyone uses it in practice.

Haskell has newtype definitions, which are guaranteed not to introduce
any runtime overhead (although often you will end up using boxed
integers - I don't know how good GHC's unboxing is). MLTon should be
able to optimise away any single constructor data types. C++
definitely isn't alone in this.

[Jamie Webb-2]

On 2008-03-31 10:44:29 David MacIver wrote:
> As far as I know, it doesn't. The JVM makes it pretty difficult to do
> and Scala's semantics encourage but don't require immutability and a
> lack of side effects. So what you end up with is the same per object
> overhead as Java (occasionally slightly more if you use features like
> laziness) and a lot more small objects. The JVM allocator performance
> and GC are pretty good, so this isn't as big an issue as it could be,
> but it can hurt your memory consumption pretty badly.

I've had some thoughts about this, and I think this situation can
actually be fixed relatively painlessly in Scala. I have two
motivations: new value types such as complex numbers and units, and to
improve the performance of the 'pimp my library' pattern.

The change is to add an @transparent annotation to classes. This has no
semantic effect, but imposes a number of restrictions on the class:

 - No fields
 - No constructors (but may have class parameters)
 - No overridden methods (except to override Object?)
 - Can inherit only from other transparent classes

Transparent class methods are compiled into static methods in the same
way as traits. Transparent classes are never instantiated. Instead,
every use of a transparent class value is replaced by a list of values
corresponding to the class parameters. This can take place late in
compilation since it does not impact type-checking.

This should make transparent classes with a single parameter about as
efficient as it's possible to be. There is a caveat with multiple
parameters in that Java doesn't permit multiple returns. There may
be workarounds that might be preferable to returning a tuple, e.g.
encoding two Floats into a Double or using ThreadLocal static storage.
This needs more thought.

I think this can be implemented almost entirely as an independent
phase/plugin. The only difficulty is that the type-checker needs to see
the untranslated forms of the method signatures of already-compiled
classes in order to behave correctly. I don't know enough about the
type-checker to know how big a problem that is, but I suspect it's not
too bad since traits and erasure have the same requirements.

Example:

  @transparent class RichInt(x : Int) {
      def abs = if(x < 0) -x else x
  }

  object Test {
      implicit def richInt(x : Int) = new RichInt(x)
      def main(argv : Array[String]) = {
          val x = -5
          println(x.abs)
      }
  }

Would be translated to be equivalent to the following Java code:

  public class RichInt {
      public static Int abs(Int x) {
          if(x < 0) return -x;
          else return x;
      }
  }

  public class Test {
      public static Int richInt(Int x) { return x; }
      public static void main(String[] argv) {
          Int x = -5;
          System.out.println(RichInt.abs(x));
      }
  }

/J

[David MacIver]

On Mon, Mar 31, 2008 at 2:22 PM, Jamie Webb <[hidden email]> wrote:
>  This should make transparent classes with a single parameter about as
>  efficient as it's possible to be. There is a caveat with multiple
>  parameters in that Java doesn't permit multiple returns. There may
>  be workarounds that might be preferable to returning a tuple, e.g.
>  encoding two Floats into a Double or using ThreadLocal static storage.
>  This needs more thought.

ThreadLocals are a bad idea I think - the lookup overhead is
comparable to the allocation cost you're trying to avoid. Similarly, I
suspect you'll find bit twiddling floats into doubles is more
expensive than one would want.

I thought about solutions to this a while ago and came up with the
conclusion that there were two solutions that worked pretty well for
this (I've not tried either of them it has to be said). They basically
involve moderately aggressive inlining.

Suppose f returns a tuple. We can change

def foo = { val (x, y) = f; g(x, y) }

in two ways to avoid the allocation.

The options are

- inline f into foo.
- Convert into continuation passing style and make f instead accept a
two argument function into which to pass its results. This still
creates an allocation cost for the function, but is amenable to
defunctionalisation optimisations (which may be a good idea anyway)

The first is a lot easier. The second is probably more suitable as
part of a general optimisation framework.

[Martin Orr]

On 31/03/08 13:37, Konrad Hinsen wrote:

>>>  - Small immutable objects. Many scientific applications need number-
>>>  like types that are characterized by being small (in terms of
>>>  memory), immutable, and very frequently created in mathematical
>>>  expressions. Examples are complex numbers, points in 2D or 3D space,
> ...
>>>  functional programming, I wonder if Scala does better there.
>>
>> As far as I know, it doesn't. The JVM makes it pretty difficult to do
>> and Scala's semantics encourage but don't require immutability and a
>> lack of side effects.
>
> I don't see how the JVM could be an obstacle. In the situations I am
> thinking off, an optimizing compiler would optimize the whole class away
> and replace its methods by inlined code operating on basic data types.
> For example, arithmetic on complex numbers would be replaced by
> operations on the real and complex parts, represented by floats. The JVM
> would never see the original class, although it might be
> necessary/desirable to have a class version of "complex" around as well
> for specific situations.

Well the JVM is an obstacle in that methods can only return objects or
primitive values.  So as soon as you return the value from a function, you
have to construct the object.  And if you are programming in a functional
style, you will probably have lots of small functions.

So this would only be useful if you can inline the functions.  (Hmm, now
that I think about it, there is no point talking about optimising a Complex
class if the +, *, etc methods are not inlined too.)  By default, Scala does
no inlining, although there is an optional inliner.  I don't know much about
how it works, but I suspect it can only inline methods being compiled as
part of the same compile run, which would prevent packaging your Complex
class up in a jar.

Best wishes,

--
Martin Orr

[Martin Odersky]

On Mon, Mar 31, 2008 at 3:50 PM, Martin Orr <[hidden email]> wrote:

> On 31/03/08 13:37, Konrad Hinsen wrote:
>
>  >>>  - Small immutable objects. Many scientific applications need number-
>  >>>  like types that are characterized by being small (in terms of
>  >>>  memory), immutable, and very frequently created in mathematical
>  >>>  expressions. Examples are complex numbers, points in 2D or 3D space,
>  > ...
>  >>>  functional programming, I wonder if Scala does better there.
>  >>
>  >> As far as I know, it doesn't. The JVM makes it pretty difficult to do
>  >> and Scala's semantics encourage but don't require immutability and a
>  >> lack of side effects.
>  >
>  > I don't see how the JVM could be an obstacle. In the situations I am
>  > thinking off, an optimizing compiler would optimize the whole class away
>  > and replace its methods by inlined code operating on basic data types.
>  > For example, arithmetic on complex numbers would be replaced by
>  > operations on the real and complex parts, represented by floats. The JVM
>  > would never see the original class, although it might be
>  > necessary/desirable to have a class version of "complex" around as well
>  > for specific situations.
>
>  Well the JVM is an obstacle in that methods can only return objects or
>  primitive values.  So as soon as you return the value from a function, you
>  have to construct the object.  And if you are programming in a functional
>  style, you will probably have lots of small functions.
>

I am fairly sure that recent JVM implementations do an escape analysis
to detect opportunities when objects can be allocated on the stack. In
that case the performance gain of rolling your own scheme would
probably be negative.

The one area where optimization might help is in specializing generic
types. For instance, replacing List[Int] by a special IntList would
avoid having to box all list elements. Optimizations like that might
be necessary to make generic multi-dimensional arrays efficient for
common cases (where the elements are primitive types).

Cheers

 -- Martin

[Jamie Webb-2]

On 2008-03-31 15:58:09 martin odersky wrote:
> I am fairly sure that recent JVM implementations do an escape analysis
> to detect opportunities when objects can be allocated on the stack. In
> that case the performance gain of rolling your own scheme would
> probably be negative.

Yes, the 1.6 JVM claims to be able to do this, but when benchmarking
I've yet to see any evidence of it actually happening.

> The one area where optimization might help is in specializing generic
> types. For instance, replacing List[Int] by a special IntList would
> avoid having to box all list elements. Optimizations like that might
> be necessary to make generic multi-dimensional arrays efficient for
> common cases (where the elements are primitive types).

That would be very welcome.

/J

[David MacIver]

On Mon, Mar 31, 2008 at 3:09 PM, Jamie Webb <[hidden email]> wrote:
> On 2008-03-31 15:58:09 martin odersky wrote:
>  > I am fairly sure that recent JVM implementations do an escape analysis
>  > to detect opportunities when objects can be allocated on the stack. In
>  > that case the performance gain of rolling your own scheme would
>  > probably be negative.
>
>  Yes, the 1.6 JVM claims to be able to do this, but when benchmarking
>  I've yet to see any evidence of it actually happening.

I was under the impression that what escape analysis was there wasn't
very smart and was mainly for stack allocating arrays for varargs and
similar.

>  > The one area where optimization might help is in specializing generic
>  > types. For instance, replacing List[Int] by a special IntList would
>  > avoid having to box all list elements. Optimizations like that might
>  > be necessary to make generic multi-dimensional arrays efficient for
>  > common cases (where the elements are primitive types).
>
>  That would be very welcome.

+1 meelyun. I would really appreciate better (and more transparent
ideally) optimisations for primitive types.

[Randall R Schulz-2]

On Monday 31 March 2008 06:58, martin odersky wrote:
> On Mon, Mar 31, 2008 at 3:50 PM, Martin Orr <[hidden email]>
wrote:
> > ...
>
> I am fairly sure that recent JVM implementations do an escape
> analysis to detect opportunities when objects can be allocated on the
> stack. In that case the performance gain of rolling your own scheme
> would probably be negative.

The last I heard, the analysis is implemented in the JVM but it is not
used to effect local / stack / activation-frame allocations even if it
can be proved that a value's extent is bounded by that of the frame.

Perhaps Java 7 will implement stack-based allocation when possible.


> ...
>
> Cheers
>
>  -- Martin


Randall Schulz

[Enno]

2008/3/31, martin odersky <[hidden email]>:

The one area where optimization might help is in specializing generic
types. For instance, replacing List[Int] by a special IntList would
avoid having to box all list elements. Optimizations like that might
be necessary to make generic multi-dimensional arrays efficient for
common cases (where the elements are primitive types).

Sounds pretty much like my heterogenous generics implementation we did back in 2001: A special classloader created specific classes for generic classes with the requested basic types. e.g. List[int] out of List[T]

 

But it comes at the high price of a specific classloader... an after-compile might be more attractive: generate requested specific classes out of generic classes in separate tool and package them with the code.

 

Enno.

--
[hidden email]

[Jamie Webb-2]

On 2008-03-31 14:41:28 David MacIver wrote:

> On Mon, Mar 31, 2008 at 2:22 PM, Jamie Webb <[hidden email]>
> wrote:
> >  This should make transparent classes with a single parameter about
> > as efficient as it's possible to be. There is a caveat with multiple
> >  parameters in that Java doesn't permit multiple returns. There may
> >  be workarounds that might be preferable to returning a tuple, e.g.
> >  encoding two Floats into a Double or using ThreadLocal static
> > storage. This needs more thought.
>
> ThreadLocals are a bad idea I think - the lookup overhead is
> comparable to the allocation cost you're trying to avoid. Similarly, I
> suspect you'll find bit twiddling floats into doubles is more
> expensive than one would want.

Ok then, allocate a mutable object in the caller and use it as an
out-parameter. Since the optimisation is most important in tight loops,
we can potentially re-use the single allocation a large number of
times. The rest of the time, performance should be no worse than it
is currently.

> I thought about solutions to this a while ago and came up with the
> conclusion that there were two solutions that worked pretty well for
> this (I've not tried either of them it has to be said). They basically
> involve moderately aggressive inlining.
>
> Suppose f returns a tuple. We can change
>
> def foo = { val (x, y) = f; g(x, y) }
>
> in two ways to avoid the allocation.
>
> The options are
>
> - inline f into foo.

Breaks modular compilation quite badly.

> - Convert into continuation passing style and make f instead accept a
> two argument function into which to pass its results. This still
> creates an allocation cost for the function, but is amenable to
> defunctionalisation optimisations (which may be a good idea anyway)

Not really an option until the JVM gets tail-calls.

/J

[Ismael Juma]

Randall R Schulz <rschulz@...> writes:

>
> On Monday 31 March 2008 06:58, martin odersky wrote:
> > On Mon, Mar 31, 2008 at 3:50 PM, Martin Orr <martin@...>
> wrote:
> > > ...
> >
> > I am fairly sure that recent JVM implementations do an escape
> > analysis to detect opportunities when objects can be allocated on the
> > stack. In that case the performance gain of rolling your own scheme
> > would probably be negative.
>
> The last I heard, the analysis is implemented in the JVM but it is not
> used to effect local / stack / activation-frame allocations even if it
> can be proved that a value's extent is bounded by that of the frame.

Indeed, last I heard JDK6 only uses escape analysis for lock elision and escape
analysis is not even enabled by default (-XX:+DoEscapeAnalysis to enable it).

> Perhaps Java 7 will implement stack-based allocation when possible.

There was a message on one of the openjdk mailing lists saying that they were
planning to do this and there have been many commits related to escape analysis
recently (improvements to lock elision, but also scalar replacement optimization
commits).

Regards,
Ismael

[David MacIver]

On Mon, Mar 31, 2008 at 3:37 PM, Jamie Webb <[hidden email]> wrote:

> On 2008-03-31 14:41:28 David MacIver wrote:
>  > On Mon, Mar 31, 2008 at 2:22 PM, Jamie Webb <[hidden email]>
>  > wrote:
>  > >  This should make transparent classes with a single parameter about
>  > > as efficient as it's possible to be. There is a caveat with multiple
>  > >  parameters in that Java doesn't permit multiple returns. There may
>  > >  be workarounds that might be preferable to returning a tuple, e.g.
>  > >  encoding two Floats into a Double or using ThreadLocal static
>  > > storage. This needs more thought.
>  >
>  > ThreadLocals are a bad idea I think - the lookup overhead is
>  > comparable to the allocation cost you're trying to avoid. Similarly, I
>  > suspect you'll find bit twiddling floats into doubles is more
>  > expensive than one would want.
>
>  Ok then, allocate a mutable object in the caller and use it as an
>  out-parameter. Since the optimisation is most important in tight loops,
>  we can potentially re-use the single allocation a large number of
>  times. The rest of the time, performance should be no worse than it
>  is currently.

Yes, that's not a bad idea.

>  > I thought about solutions to this a while ago and came up with the
>  > conclusion that there were two solutions that worked pretty well for
>  > this (I've not tried either of them it has to be said). They basically
>  > involve moderately aggressive inlining.
>  >
>  > Suppose f returns a tuple. We can change
>  >
>  > def foo = { val (x, y) = f; g(x, y) }
>  >
>  > in two ways to avoid the allocation.
>  >
>  > The options are
>  >
>  > - inline f into foo.
>
>  Breaks modular compilation quite badly.

No, it actually doesn't, because the bytecode format is eminently inlinable.

>  > - Convert into continuation passing style and make f instead accept a
>  > two argument function into which to pass its results. This still
>  > creates an allocation cost for the function, but is amenable to
>  > defunctionalisation optimisations (which may be a good idea anyway)
>
>  Not really an option until the JVM gets tail-calls.

It is unless you're doing it recursively. I'm not suggesting turning
the entire thing into tail calls, just the cases where you need to
return multiple values.

[Jamie Webb-2]

On 2008-03-31 15:51:43 David MacIver wrote:
> >  > - inline f into foo.
> >
> >  Breaks modular compilation quite badly.
>
> No, it actually doesn't, because the bytecode format is eminently
> inlinable.

Yes, but changes to the implementation of f will require a recompile of
every caller. The Scala 1.x traits implementation had this problem and
it was a PITA. It's also a frequently-cited flaw in C++.

I suppose a solution like ApectJs weaver would work here too, but
that's a pretty big hammer.

> >  > - Convert into continuation passing style and make f instead
> >  > accept a two argument function into which to pass its results.
> >  > This still creates an allocation cost for the function, but is
> >  > amenable to defunctionalisation optimisations (which may be a
> >  > good idea anyway)
> >
> >  Not really an option until the JVM gets tail-calls.
>
> It is unless you're doing it recursively. I'm not suggesting turning
> the entire thing into tail calls, just the cases where you need to
> return multiple values.

But if we want a loop, inside which we call a function returning
multiple values, aren't we going to need a new stack frame for each
iteration?

/J

[David MacIver]

On Mon, Mar 31, 2008 at 4:18 PM, Jamie Webb <[hidden email]> wrote:

> On 2008-03-31 15:51:43 David MacIver wrote:
>  > >  > - inline f into foo.
>  > >
>  > >  Breaks modular compilation quite badly.
>  >
>  > No, it actually doesn't, because the bytecode format is eminently
>  > inlinable.
>
>  Yes, but changes to the implementation of f will require a recompile of
>  every caller. The Scala 1.x traits implementation had this problem and
>  it was a PITA. It's also a frequently-cited flaw in C++.
>
>  I suppose a solution like ApectJs weaver would work here too, but
>  that's a pretty big hammer.

This is true, but not a massive issue because it's easy to transform
between separately compiled and optimised solutions with a compiler
flag. You can get correct behaviour by returning tuples, then client
code compiled with a suitable optimisation flag can inline. Requiring
whole program compilation of your project in order to get full
performance benefits doesn't seem like a huge problem to me.

>  > >  > - Convert into continuation passing style and make f instead
>  > >  > accept a two argument function into which to pass its results.
>  > >  > This still creates an allocation cost for the function, but is
>  > >  > amenable to defunctionalisation optimisations (which may be a
>  > >  > good idea anyway)
>  > >
>  > >  Not really an option until the JVM gets tail-calls.
>  >
>  > It is unless you're doing it recursively. I'm not suggesting turning
>  > the entire thing into tail calls, just the cases where you need to
>  > return multiple values.
>
>  But if we want a loop, inside which we call a function returning
>  multiple values, aren't we going to need a new stack frame for each
>  iteration?

Fair point. Ok, this probably doesn't work without full blown tail
call optimisation.

[Patrick Wright]

This is not Scala-specific, but I thought it might be interesting in
the discussion, specifically as regard JVM limitations for scientific
computing.

The Multi-Language VM (aka Da Vinci Machine) project is investigating
a number of changes to the VM which would improve support for
languages other than Java running on the JVM.

http://openjdk.java.net/projects/mlvm/

John Rose, HotSpot engineer and project lead, has been blogging for
awhile now on addressing different issues (including fixnums, tuples,
dynamic invocation, etc.):

http://blogs.sun.com/jrose/category/JVM

It has a low-volume mailing list but the team is very open to
discussion as well as input.

There was also work a few years back under the Java Grande
meta-project which included ideas for optimizing numeric and
scientific computing on the JVM. Google returns a bunch of stuff, for
example
http://math.nist.gov/javanumerics/

There were several JSRs proposed in this area as well, but withdrawn
Floating-point Extensions: http://jcp.org/en/jsr/detail?id=084
Multi-array package: http://jcp.org/en/jsr/detail?id=083

etc.

HTH
Patrick