FYI: Reified Generics on the JVM [Kotlin]

476 views
Skip to first unread message

Simon Ochsenreither

unread,
Feb 21, 2013, 4:48:56 PM2/21/13
to scala-i...@googlegroups.com
Looks like the Ceylon people either managed to put some pixie dust on top of HotSpot to make it less slow/memory inefficient or didn't benchmark it yet, but it seems like they added reified Generics in exactly the same way the Kotlin devs eventually gave up on it:

https://groups.google.com/d/topic/ceylon-dev/mIrroqhcf7o/discussion

Simon Ochsenreither

unread,
Feb 21, 2013, 4:54:12 PM2/21/13
to scala-i...@googlegroups.com
LOL, mixed that up ... I meant "FYI: Reified Generics on the JVM [Ceylon]"

Grzegorz Kossakowski

unread,
Feb 21, 2013, 5:36:51 PM2/21/13
to scala-i...@googlegroups.com
On 21 February 2013 13:48, Simon Ochsenreither <simon.och...@gmail.com> wrote:
Looks like the Ceylon people either managed to put some pixie dust on top of HotSpot to make it less slow/memory inefficient or didn't benchmark it yet, but it seems like they added reified Generics in exactly the same way the Kotlin devs eventually gave up on it:

You can easily benchmark it and see that performance impact is very noticeable. Especially memory consumption increases a lot.

I believe the way to go is to have optional reification the way we start to do in Scala with Manifests/TypeTags.

If you can and combine it with runtime specialization you can aim for high performance and generic code. However, that's probably goal for Scala 2.12 or 2.13.

--
Grzegorz Kossakowski
Scalac hacker at Typesafe
twitter: @gkossakowski

Simon Ochsenreither

unread,
Feb 21, 2013, 6:00:00 PM2/21/13
to scala-i...@googlegroups.com
I think in the end we will need runtime support in one way or another.

I talked with Joel, the one of the people working on Avian, earlier this week and figured out an almost cost-free way to retain type information at runtime while being completely compatible to the existing class file format. That way, runtimes supporting the scheme can specialize their code while other runtimes would keep running. I played with ASM to implement the runtime specialization of generic types, which seems doable, just a lot of work.

But anyway, I need to finish the implementation of arrays for unboxed value types first. :-)


Vlad Ureche

unread,
Feb 22, 2013, 12:20:02 PM2/22/13
to scala-internals

2013/2/21 Simon Ochsenreither <simon.och...@gmail.com>

Looks like the Ceylon people either managed to put some pixie dust on top of HotSpot to make it less slow/memory inefficient or didn't benchmark it yet, but it seems like they added reified Generics in exactly the same way the Kotlin devs eventually gave up on it:

https://groups.google.com/d/topic/ceylon-dev/mIrroqhcf7o/discussion


Very interesting, thanks for pointing it out Simon!

Some archeology: I am aware of research by Martin (before he joined EPFL) and Enno Runne on the Pizza compiler, where they experimented with reified types for specialization. I had another look at the paper and it seems at most a 7% slowdown can be attributed to carrying reified types. What's more, this was happening back in version 1.1 of the JVM, so maybe revisiting the common belief that carrying reified types is expensive is warranted.

Now, is anyone aware of more recent attempts of implementing this? (in Scala, maybe)

Cheers,
Vlad

Philipp Haller

unread,
Feb 22, 2013, 1:19:21 PM2/22/13
to scala-i...@googlegroups.com
Hi Vlad,

Some archeology: I am aware of research by Martin (before he joined EPFL) and Enno Runne on the Pizza compiler, where they experimented with reified types for specialization. I had another look at the paper and it seems at most a 7% slowdown can be attributed to carrying reified types. What's more, this was happening back in version 1.1 of the JVM, so maybe revisiting the common belief that carrying reified types is expensive is warranted.

Now, is anyone aware of more recent attempts of implementing this? (in Scala, maybe)

Have a look at the PhD thesis of Michel Schinz (2005): http://infoscience.epfl.ch/record/52211

From the abstract:
Run time types make it possible for a program to examine the type of its values during execution. This possibility is interesting in itself, offering new capabilities to the programmer. Furthermore, run time types are also required to implement other high level concepts, like pattern matching, type-safe serialisation and reflection. We propose an implementation technique based on the representation of types as values, and show how to use the run time types of the underlying virtual machine to implement those of Scala. The techniques presented in this thesis have been implemented in our Scala compiler, scalac. This enabled us to evaluate these techniques, in particular their impact on the performances of programs. This evaluation was performed on several real, non-trivial programs.

Cheers,
Philipp


Vlad Ureche

unread,
Feb 22, 2013, 1:35:43 PM2/22/13
to scala-internals

2013/2/22 Philipp Haller <hal...@gmail.com>


Have a look at the PhD thesis of Michel Schinz (2005): http://infoscience.epfl.ch/record/52211

Thanks Philipp! I wonder how come I didn't come across this before...

Vlad

martin odersky

unread,
Feb 22, 2013, 1:37:31 PM2/22/13
to scala-internals
The research with Enno was different: It was a essentially a C++-like expansion of everything at class loading time. So, more classes were generated yet on the other hand everything was specialized. We had to introduce some severe restrictions in the language to make the expansion process terminate. Essentially, a class could not contain a definition that had a type with a more complicated instance of itself. Things like zip in collections would be impossible. This is enforced by the language spec of C++ but it's definitely not OK for Java or Scala.

We hoped that the scheme would trade larger codesize for better speed. So a 7% slowdown was not exactly considered a success.

Michel Schinz implemented a scheme that looks close to what Ceylon did in his thesis work. His performance results were much worse than 7% (I remember twice as slow in some cases). For this reason we did not pursue it further.

Cheers

 - Martin


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



--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

Pavel Pavlov

unread,
Feb 23, 2013, 11:50:04 AM2/23/13
to scala-i...@googlegroups.com


On Friday, February 22, 2013 5:36:51 AM UTC+7, Grzegorz Kossakowski wrote:

I believe the way to go is to have optional reification the way we start to do in Scala with Manifests/TypeTags.


Optional (user-defined) reification looks good, however now it has at least one major drawback: inability to use TypeTags/ClassTags (or other context bounds) for tparams of traits.
It'd striked me several times in my codebase. For me, this restriction is of the same sort as Java's restriction of not having any code in interfaces. In some cases it prevents traits from being composable units of behavior.

Maybe it's time to consider adding traits constructor arguments to the language?
There is a scheme discussed more that year ago that should work:
https://groups.google.com/forum/#!msg/scala-language/YJjA7BV3NWs/LqHC_0gK4mcJ
https://groups.google.com/forum/#!msg/scala-language/YJjA7BV3NWs/0MBg1L8Jt8sJ

Regards,
Pavel

Eugene Burmako

unread,
Feb 23, 2013, 11:57:16 AM2/23/13
to scala-internals
Context bounds for trait tparams are not pretty, but they are
definitely possible.

trait Foo[T] { implicit def contextBound: Bar[T] }
class C[T: Bar] extends Foo[T] { override def contextBound =
implicitly[Bar[T]] }

On Feb 23, 5:50 pm, Pavel Pavlov <pavel.e.pav...@gmail.com> wrote:
> On Friday, February 22, 2013 5:36:51 AM UTC+7, Grzegorz Kossakowski wrote:
>
> > I believe the way to go is to have optional reification the way we start
> > to do in Scala with Manifests/TypeTags.
>
> Optional (user-defined) reification looks good, however now it has at least
> one major drawback: inability to use TypeTags/ClassTags (or other context
> bounds) for tparams of traits.
> It'd striked me several times in my codebase. For me, this restriction is
> of the same sort as Java's restriction of not having any code in
> interfaces. In some cases it prevents traits from being composable units of
> behavior.
>
> Maybe it's time to consider adding traits constructor arguments to the
> language?
> There is a scheme discussed more that year ago that should work:https://groups.google.com/forum/#!msg/scala-language/YJjA7BV3NWs/LqHC...https://groups.google.com/forum/#!msg/scala-language/YJjA7BV3NWs/0MBg...
>
> Regards,
> Pavel

Pavel Pavlov

unread,
Feb 23, 2013, 12:16:09 PM2/23/13
to scala-i...@googlegroups.com
Yes, and this is exactly such kind of boilerplate code you need to write to overcome restrictions of Java's interfaces:

interface Foo { void doSomething(); }
class C implements Foo { void doSomething() { return FooHelper.doSomething(this); } }
Reply all
Reply to author
Forward
0 new messages