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. |
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. |
In reply to this post by kh92
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 |
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 |
In reply to this post by Imam Tashdid ul Alam
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. |
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. |
In reply to this post by David MacIver
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 |
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. |
In reply to this post by kh92
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 |
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. > 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 |
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 |
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. |
In reply to this post by Martin Odersky
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 |
In reply to this post by Martin Odersky
2008/3/31, martin odersky <[hidden email]>:
The one area where optimization might help is in specializing generic 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.
|
In reply to this post by David MacIver
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 |
In reply to this post by Randall R Schulz-2
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 |
In reply to this post by Jamie Webb-2
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. |
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 |
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. |
In reply to this post by kh92
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 |
Free forum by Nabble | Edit this page |