- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Size of standard library and possible tricks to reduce its size
Tue, 2011-10-18, 22:20
So, the library jar is getting kinda bulky, especially after the addition of parallel collections. I've been noticing that there's a whole lot of repetitive trait-stub instantiations -- scala/collection/Iterator$$anon$* are great examples of these (they're all different subtypes of Iterator itself) -- and I wonder if anyone has thought to create some library-private abstract classes to flatten some of the bytecode bloat.
For instance, my personal library has the following tree of private-use types tucked away in a package object. You'll note that they are basically a parallel to the corresponding traits, inheriting from the largest abstract superclass available "with" the more specific trait.
Effectively, these let me create multiple custom subtypes of the corresponding traits, but the swath of trait stubs are only compiled to bytecode exactly once (at the abstract class level). So instead of consuming 21k of bytecode for every subtype of Iterator that I need, it only takes about 1k each. I get similar savings from the other classes in the tree.
These abstract classes for my use take up ~240k of classfile space with 2.9.1, but that hit is only taken once, not upon creation of every subtype. This saves a pretty significant chunk of bytecode, and the same trick would likely work well in the standard library. Thoughts?
package object collection { import scala.collection._
private[collection] abstract class AbstractTraversableOnce[T] extends TraversableOnce[T]
private[collection] abstract class AbstractTraversable[T] extends AbstractTraversableOnce[T] with Traversable[T]
private[collection] abstract class AbstractTraversableProxy[T] extends AbstractTraversable[T] with TraversableProxy[T]
private[collection] abstract class AbstractIterable[T] extends AbstractTraversable[T] with Iterable[T]
private[collection] abstract class AbstractIterableProxy[T] extends AbstractIterable[T] with IterableProxy[T]
private[collection] abstract class AbstractIterator[T] extends AbstractTraversableOnce[T] with Iterator[T]
private[collection] abstract class AbstractMap[A, B] extends AbstractIterable[(A, B)] with Map[A, B]
private[collection] abstract class AbstractMapProxy[A, B] extends AbstractMap[A, B] with MapProxy[A, B]
private[collection] abstract class AbstractSeq[T] extends AbstractIterable[T] with Seq[T]
private[collection] abstract class AbstractSeqProxy[T] extends AbstractSeq[T] with SeqProxy[T]
private[collection] abstract class AbstractSet[T] extends AbstractIterable[T] with Set[T]
private[collection] abstract class AbstractSetProxy[T] extends AbstractSet[T] with SetProxy[T]}
For instance, my personal library has the following tree of private-use types tucked away in a package object. You'll note that they are basically a parallel to the corresponding traits, inheriting from the largest abstract superclass available "with" the more specific trait.
Effectively, these let me create multiple custom subtypes of the corresponding traits, but the swath of trait stubs are only compiled to bytecode exactly once (at the abstract class level). So instead of consuming 21k of bytecode for every subtype of Iterator that I need, it only takes about 1k each. I get similar savings from the other classes in the tree.
These abstract classes for my use take up ~240k of classfile space with 2.9.1, but that hit is only taken once, not upon creation of every subtype. This saves a pretty significant chunk of bytecode, and the same trick would likely work well in the standard library. Thoughts?
package object collection { import scala.collection._
private[collection] abstract class AbstractTraversableOnce[T] extends TraversableOnce[T]
private[collection] abstract class AbstractTraversable[T] extends AbstractTraversableOnce[T] with Traversable[T]
private[collection] abstract class AbstractTraversableProxy[T] extends AbstractTraversable[T] with TraversableProxy[T]
private[collection] abstract class AbstractIterable[T] extends AbstractTraversable[T] with Iterable[T]
private[collection] abstract class AbstractIterableProxy[T] extends AbstractIterable[T] with IterableProxy[T]
private[collection] abstract class AbstractIterator[T] extends AbstractTraversableOnce[T] with Iterator[T]
private[collection] abstract class AbstractMap[A, B] extends AbstractIterable[(A, B)] with Map[A, B]
private[collection] abstract class AbstractMapProxy[A, B] extends AbstractMap[A, B] with MapProxy[A, B]
private[collection] abstract class AbstractSeq[T] extends AbstractIterable[T] with Seq[T]
private[collection] abstract class AbstractSeqProxy[T] extends AbstractSeq[T] with SeqProxy[T]
private[collection] abstract class AbstractSet[T] extends AbstractIterable[T] with Set[T]
private[collection] abstract class AbstractSetProxy[T] extends AbstractSet[T] with SetProxy[T]}
Tue, 2011-10-18, 22:47
#2
Re: Size of standard library and possible tricks to reduce its
"This week, on Behind the Bytecode... remember 200K meant something?"
https://lampsvn.epfl.ch/trac/scala/changeset/20311
Date: Wed Dec 23 17:57:36 2009 +0000
Created team of private[collection] abstract classes
and traits in scala.collection.views. Factored boilerplate
and base Transformed traits out of *ViewLike classes.
Executive summary and motivation:
4812029 Dec 23 09:47 scala-library.jar // before
4604150 Dec 23 09:24 scala-library.jar // after
Direct size savings of 4.5%. Review by odersky.
% date
Tue Oct 18 14:39:09 PDT 2011
% ls -l lib/scala-library.jar
-rw-r--r-- 1 paulp admin 9824041 Oct 16 09:02 lib/scala-library.jar
Tue, 2011-10-18, 22:57
#3
Re: Size of standard library and possible tricks to reduce its
On Tue, Oct 18, 2011 at 11:31 PM, Paul Phillips <paulp@improving.org> wrote:
On Tue, Oct 18, 2011 at 2:19 PM, Todd Vierling <tv@duh.org> wrote:
> So, the library jar is getting kinda bulky, especially after the addition of
> parallel collections. I've been noticing that there's a whole lot of
> repetitive trait-stub instantiations -- scala/collection/Iterator$$anon$*
> are great examples of these (they're all different subtypes of Iterator
> itself) -- and I wonder if anyone has thought to create some library-private
> abstract classes to flatten some of the bytecode bloat.
https://lampsvn.epfl.ch/trac/scala/changeset/20311
https://issues.scala-lang.org/browse/SI-2876
https://lampsvn.epfl.ch/trac/scala/changeset/20490
That was for views. The issue in 2876 doesn't look so bad from this
vantage, but as I recall there was a more serious compiler bug which
was never resolved which made the whole process too tedious.
It's probably doable, but in my experience one tends to discover new
or (worse) old and unfixed compiler bugs when attempting these things,
so you need to be prepared for battle.
I believe it's most likely a linearization problem. That is, I believe the change in 20311 affected linearization so that the wrong method (the one raising the UnsupportedOperationException) was called. Linearization can be tricky in a library that uses traits in intricate ways and Scala collections and in particular views are an example of that. Calling it a compiler bug is a bit premature without further evidence.
-- Martin
Tue, 2011-10-18, 23:27
#4
Re: Size of standard library and possible tricks to reduce its
On Tue, Oct 18, 2011 at 2:50 PM, martin odersky wrote:
> I believe it's most likely a linearization problem. That is, I believe the
> change in 20311 affected linearization so that the wrong method (the one
> raising the UnsupportedOperationException) was called. Linearization can be
> tricky in a library that uses traits in intricate ways and Scala collections
> and in particular views are an example of that. Calling it a compiler bug is
> a bit premature without further evidence.
The bug I was talking about is this.
https://issues.scala-lang.org/browse/SI-2897
I trust I'm allowed to call that a bug.
Tue, 2011-10-18, 23:37
#5
Re: Size of standard library and possible tricks to reduce its
On Tuesday, October 18, 2011 5:40:06 PM UTC-4, Paul Phillips wrote:
Should I take your responses to mean that it would be worth pulling HEAD and making a candidate diff, if it trimmed things notably? My aim would only be to provide library-private abstract classes -- no new traits, as was done in the changesets you linked -- which should, in theory, not further confuse the compiler. (I hope. At least in my private library, it's working fine... fingers crossed.)
"This week, on Behind the Bytecode... remember 200K meant something?"Based on my snooping around, I can see that there would be substantial savings just by providing Iterator, Traversable, and Iterable. Those three traits account for a pretty big chunk of anon class trait stubs.
Should I take your responses to mean that it would be worth pulling HEAD and making a candidate diff, if it trimmed things notably? My aim would only be to provide library-private abstract classes -- no new traits, as was done in the changesets you linked -- which should, in theory, not further confuse the compiler. (I hope. At least in my private library, it's working fine... fingers crossed.)
Tue, 2011-10-18, 23:37
#6
Re: Size of standard library and possible tricks to reduce its
On Tue, Oct 18, 2011 at 3:26 PM, Todd Vierling wrote:
> Based on my snooping around, I can see that there would be substantial
> savings just by providing Iterator, Traversable, and Iterable. Those three
> traits account for a pretty big chunk of anon class trait stubs.
> Should I take your responses to mean that it would be worth pulling HEAD and
> making a candidate diff, if it trimmed things notably?
Yes, absolutely. (But also take my responses to mean: please see that
the test suite completely passes from scratch, that is "ant all.clean
test" gets all the way to the part where it says yay.)
Tue, 2011-10-18, 23:47
#7
Re: Size of standard library and possible tricks to reduce its
On Wed, Oct 19, 2011 at 12:26 AM, Todd Vierling <tv@duh.org> wrote:
On Tuesday, October 18, 2011 5:40:06 PM UTC-4, Paul Phillips wrote:Yes, I think that would be very worthwhile doing."This week, on Behind the Bytecode... remember 200K meant something?"Based on my snooping around, I can see that there would be substantial savings just by providing Iterator, Traversable, and Iterable. Those three traits account for a pretty big chunk of anon class trait stubs.
Should I take your responses to mean that it would be worth pulling HEAD and making a candidate diff, if it trimmed things notably? My aim would only be to provide library-private abstract classes -- no new traits, as was done in the changesets you linked -- which should, in theory, not further confuse the compiler. (I hope. At least in my private library, it's working fine... fingers crossed.)
Thanks!
-- Martin
Tue, 2011-10-18, 23:57
#8
Re: Size of standard library and possible tricks to reduce its
On Wed, Oct 19, 2011 at 12:22 AM, Paul Phillips <paulp@improving.org> wrote:
On Tue, Oct 18, 2011 at 2:50 PM, martin odersky <martin.odersky@epfl.ch> wrote:
> I believe it's most likely a linearization problem. That is, I believe the
> change in 20311 affected linearization so that the wrong method (the one
> raising the UnsupportedOperationException) was called. Linearization can be
> tricky in a library that uses traits in intricate ways and Scala collections
> and in particular views are an example of that. Calling it a compiler bug is
> a bit premature without further evidence.
The bug I was talking about is this.
https://issues.scala-lang.org/browse/SI-2897
I trust I'm allowed to call that a bug.
You certainly are. But I do not see yet what it has to do with the problem that was reported earlier. That problem manifested itself with an UnsupportedOperationException at runtime whereas 2897 is a crash at compile time. Also, I do not see how locally defined traits as shown in 2897 enter the picture. There's no use I can see of them in the collection library. But given enough time, I am sure we'll figure it out.
-- Martin
Wed, 2011-10-19, 06:57
#9
Re: Size of standard library and possible tricks to reduce its
On Tuesday, October 18, 2011 6:28:22 PM UTC-4, Paul Phillips wrote:
$ ls -l dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 8697074 2011-10-18 23:13 dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar
$ ls -l build/pack/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 7825478 2011-10-19 01:48 build/pack/lib/scala-library.jar
The main changes so far: adding AbstractIterator, AbstractIterable, AbstractSet, and some *ViewLike.AbstractTransformed.
Looks like I can probably trim another 200-400k from what I see remaining so far in the collections tree. Will post more status later in the week after giving it some hefty workouts with both the tests and eyeball-glazing proofreading (mainly to ensure that the Abstract* types don't accidentally leak out into public API through methods' return type signatures).
Some of this leads me to wonder whether certain specific types (e.g., AbstractIterator) should be part of the public API after all, as convenience classes for the user. For now, they're confined to private[collection], but if they prove useful and not a speed burden, that's another debate we can have after-the-fact.
Oh, of course. Well, after throwing only a couple hours of tweaking at it:Yes, absolutely. (But also take my responses to mean: please see that
the test suite completely passes from scratch, that is "ant all.clean
test" gets all the way to the part where it says yay.)
$ ls -l dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 8697074 2011-10-18 23:13 dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar
$ ls -l build/pack/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 7825478 2011-10-19 01:48 build/pack/lib/scala-library.jar
The main changes so far: adding AbstractIterator, AbstractIterable, AbstractSet, and some *ViewLike.AbstractTransformed.
Looks like I can probably trim another 200-400k from what I see remaining so far in the collections tree. Will post more status later in the week after giving it some hefty workouts with both the tests and eyeball-glazing proofreading (mainly to ensure that the Abstract* types don't accidentally leak out into public API through methods' return type signatures).
Some of this leads me to wonder whether certain specific types (e.g., AbstractIterator) should be part of the public API after all, as convenience classes for the user. For now, they're confined to private[collection], but if they prove useful and not a speed burden, that's another debate we can have after-the-fact.
Wed, 2011-10-19, 08:07
#10
Re: Size of standard library and possible tricks to reduce its
On Wed, Oct 19, 2011 at 7:49 AM, Todd Vierling <tv@duh.org> wrote:
Hi Todd,
Very encouraging results so far!
Martin suggested [1] that one reason for the slowdowns in compilation with Scala 2.9.0 might have been the longer base type sequence for commonly used types after the addition of the GenXxx traits. A bunch of optimizations followed that restored (nay, bettered!) performance for 2.9.1. But you ought to verify that building the compiler with your new compiler isn't slower than before.
-jason
[1] http://www.scala-lang.org/node/9869#comment-42374
Oh, of course. Well, after throwing only a couple hours of tweaking at it:
$ ls -l dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 8697074 2011-10-18 23:13 dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar
$ ls -l build/pack/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 7825478 2011-10-19 01:48 build/pack/lib/scala-library.jar
The main changes so far: adding AbstractIterator, AbstractIterable, AbstractSet, and some *ViewLike.AbstractTransformed.
Looks like I can probably trim another 200-400k from what I see remaining so far in the collections tree. Will post more status later in the week after giving it some hefty workouts with both the tests and eyeball-glazing proofreading (mainly to ensure that the Abstract* types don't accidentally leak out into public API through methods' return type signatures).
Some of this leads me to wonder whether certain specific types (e.g., AbstractIterator) should be part of the public API after all, as convenience classes for the user. For now, they're confined to private[collection], but if they prove useful and not a speed burden, that's another debate we can have after-the-fact.
Hi Todd,
Very encouraging results so far!
Martin suggested [1] that one reason for the slowdowns in compilation with Scala 2.9.0 might have been the longer base type sequence for commonly used types after the addition of the GenXxx traits. A bunch of optimizations followed that restored (nay, bettered!) performance for 2.9.1. But you ought to verify that building the compiler with your new compiler isn't slower than before.
-jason
[1] http://www.scala-lang.org/node/9869#comment-42374
Wed, 2011-10-19, 13:07
#11
Re: Size of standard library and possible tricks to reduce its
On Wed, Oct 19, 2011 at 6:49 AM, Todd Vierling wrote:
> Oh, of course. Well, after throwing only a couple hours of tweaking at it:
Great!
I am hopeful that the reduced indirection will also lead to improved
runtime performance. It will be interesting to do some benchmarking.
Best,
Ismael
Wed, 2011-10-19, 17:07
#12
Re: Size of standard library and possible tricks to reduce its
On Wednesday, October 19, 2011 1:49:37 AM UTC-4, Todd Vierling wrote:
Another hour of tweaking brought this to:
$ ls -l build/pack/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 7229411 2011-10-19 11:39 build/pack/lib/scala-library.jar
Yep, that's a ~17% drop so far. Also, by marking a few Abstract*s as private[scala] rather than private[collection], I trimmed scalap, swing, and the compiler a tiny bit too.
There's still more to trim and other tasks to do. After I'm done injecting all the 'Abstract...' layers, I'll review it for possible type linearization issues, run the ant tests, then post it for review and community benchmarking (hell, I'm not sure what to test!) on my webserver: a vanilla dist, the source diff, and a dist with the diff applied.
While doing this, I ran across some cases outside of scala.collection that were pretty useful as well. In particular, the compiler, upon seeing { (x) => foo }, emits an anon class that extends scala.runtime.AbstractFunction1; but explicit inheritances from (A => B) instantiate all the trait stubs in Function1 (and there are a lot of them, thanks to @specialized). So I was able to trim even more by making use of AbstractFunction1 explicitly in a few places.
More news to come...
$ ls -l dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar
-rw-r--r-- 1 tvierling tvierling 8697074 2011-10-18 23:13 dists/scala-2.10.0.r25850-b20111018225736/lib/scala-library.jar
Another hour of tweaking brought this to:
$ ls -l build/pack/lib/scala-library.jar -rw-r--r-- 1 tvierling tvierling 7229411 2011-10-19 11:39 build/pack/lib/scala-library.jar
Yep, that's a ~17% drop so far. Also, by marking a few Abstract*s as private[scala] rather than private[collection], I trimmed scalap, swing, and the compiler a tiny bit too.
There's still more to trim and other tasks to do. After I'm done injecting all the 'Abstract...' layers, I'll review it for possible type linearization issues, run the ant tests, then post it for review and community benchmarking (hell, I'm not sure what to test!) on my webserver: a vanilla dist, the source diff, and a dist with the diff applied.
While doing this, I ran across some cases outside of scala.collection that were pretty useful as well. In particular, the compiler, upon seeing { (x) => foo }, emits an anon class that extends scala.runtime.AbstractFunction1; but explicit inheritances from (A => B) instantiate all the trait stubs in Function1 (and there are a lot of them, thanks to @specialized). So I was able to trim even more by making use of AbstractFunction1 explicitly in a few places.
More news to come...
Wed, 2011-10-19, 17:47
#13
Re: Size of standard library and possible tricks to reduce its
On Wednesday, October 19, 2011 11:57:55 AM UTC-4, Todd Vierling wrote:
I forgot to mention one pretty big caveat with this size-optimization work: It's going to make scaladoc a little more annoying.
Today, there are some cases where library-private classes exist in a class/trait hierarchy, but they're fairly rare. These changes will make that happen quite a bit more, meaning that some of the supertypes in the type declaration won't be clickable. In practice, all the types are available via the expandable linearization, but as you probably know, that list is pretty huge for a collection class.
I'm open to opinions on how this will affect users in practice. A workaround would be to continue to include the trait immediately after the abstract class type, even if the abstract class is an instantiation of exactly that trait ("extends AbstractSeq[A] with Seq[A] with ..."). This means a little more verbosity in the code, but no bytecode changes in practice -- would you all prefer to see it done this way?
There's still more to trim and other tasks to do. After I'm done injecting all the 'Abstract...' layers, I'll review it for possible type linearization issues, run the ant tests, then post it for review and community benchmarking (hell, I'm not sure what to test!) on my webserver: a vanilla dist, the source diff, and a dist with the diff applied.
I forgot to mention one pretty big caveat with this size-optimization work: It's going to make scaladoc a little more annoying.
Today, there are some cases where library-private classes exist in a class/trait hierarchy, but they're fairly rare. These changes will make that happen quite a bit more, meaning that some of the supertypes in the type declaration won't be clickable. In practice, all the types are available via the expandable linearization, but as you probably know, that list is pretty huge for a collection class.
I'm open to opinions on how this will affect users in practice. A workaround would be to continue to include the trait immediately after the abstract class type, even if the abstract class is an instantiation of exactly that trait ("extends AbstractSeq[A] with Seq[A] with ..."). This means a little more verbosity in the code, but no bytecode changes in practice -- would you all prefer to see it done this way?
Wed, 2011-10-19, 17:57
#14
Re: Size of standard library and possible tricks to reduce its
On Wed, Oct 19, 2011 at 4:57 PM, Todd Vierling <tv@duh.org> wrote:
Yes, this is a known issue. Great that you're looking into it too!
Best,Ismael
While doing this, I ran across some cases outside of scala.collection that were pretty useful as well. In particular, the compiler, upon seeing { (x) => foo }, emits an anon class that extends scala.runtime.AbstractFunction1; but explicit inheritances from (A => B) instantiate all the trait stubs in Function1 (and there are a lot of them, thanks to @specialized). So I was able to trim even more by making use of AbstractFunction1 explicitly in a few places.
Yes, this is a known issue. Great that you're looking into it too!
Best,Ismael
Mon, 2011-11-07, 22:57
#15
Re: Size of standard library and possible tricks to reduce its s
On Tuesday, October 18, 2011 5:19:26 PM UTC-4, Todd Vierling wrote:
So after some public and private discussion, and a bit of fiddly work in the scala source tree (mmm, "manual search and replace"), a lot of the ideas here were implemented and committed to trunk today.
To explain what I did, how it managed to reduce scala-library.jar by about a meg and a half, and how this could be applicable to other codebases, I blogged the gory details here: http://blog.duh.org/2011/11/scala-pitfalls-trait-bloat.html
So, the library jar is getting kinda bulky, especially after the addition of parallel collections. I've been noticing that there's a whole lot of repetitive trait-stub instantiations -- scala/collection/Iterator$$anon$* are great examples of these (they're all different subtypes of Iterator itself) -- and I wonder if anyone has thought to create some library-private abstract classes to flatten some of the bytecode bloat.
So after some public and private discussion, and a bit of fiddly work in the scala source tree (mmm, "manual search and replace"), a lot of the ideas here were implemented and committed to trunk today.
To explain what I did, how it managed to reduce scala-library.jar by about a meg and a half, and how this could be applicable to other codebases, I blogged the gory details here: http://blog.duh.org/2011/11/scala-pitfalls-trait-bloat.html
Tue, 2011-11-08, 02:27
#16
Re: Re: Size of standard library and possible tricks to reduce
On Mon, Nov 7, 2011 at 2:48 PM, Todd Vierling <tv@duh.org> wrote:
Good info in there. Thanks for blogging it.
--
Derek Williams
To explain what I did, how it managed to reduce scala-library.jar by about a meg and a half, and how this could be applicable to other codebases, I blogged the gory details here: http://blog.duh.org/2011/11/scala-pitfalls-trait-bloat.html
Good info in there. Thanks for blogging it.
--
Derek Williams
Wed, 2011-11-09, 10:17
#17
Re: Re: Size of standard library and possible tricks to reduce
Amazing. Interesting, can compiler compute common minimal set of
traits for set of classes, to do such optimization authomatically [?]
On Tue, Nov 8, 2011 at 4:19 AM, Derek Williams wrote:
> On Mon, Nov 7, 2011 at 2:48 PM, Todd Vierling wrote:
>>
>> To explain what I did, how it managed to reduce scala-library.jar by about
>> a meg and a half, and how this could be applicable to other codebases, I
>> blogged the gory details
>> here: http://blog.duh.org/2011/11/scala-pitfalls-trait-bloat.html
>
> Good info in there. Thanks for blogging it.
>
> --
> Derek Williams
>
Wed, 2011-11-09, 10:37
#18
Re: Re: Size of standard library and possible tricks to reduce
On Wed, Nov 9, 2011 at 10:11 AM, Ruslan Shevchenko <ruslan.s.shevchenko@gmail.com> wrote:
Separate compilation probably rules this out.
-jason
Amazing. Interesting, can compiler compute common minimal set of
traits for set of classes, to do such optimization authomatically [?]
Separate compilation probably rules this out.
-jason
Wed, 2011-11-09, 23:07
#19
Re: Re: Size of standard library and possible tricks to reduce
On Wednesday, November 9, 2011 4:33:29 AM UTC-5, Jason Zaugg wrote:
That, and multiple inheritance. The traits chosen for explicit instantiation were picked carefully by hand, to get maximum benefit with minimal overhead. The compiler may not be able to figure out, efficiently, where the "best" place to insert the abstract class layer is.
On Wed, Nov 9, 2011 at 10:11 AM, Ruslan Shevchenko <ruslan.s....@gmail.com> wrote:Amazing. Interesting, can compiler compute common minimal set of
traits for set of classes, to do such optimization authomatically [?]
Separate compilation probably rules this out.
That, and multiple inheritance. The traits chosen for explicit instantiation were picked carefully by hand, to get maximum benefit with minimal overhead. The compiler may not be able to figure out, efficiently, where the "best" place to insert the abstract class layer is.
Thu, 2011-11-10, 09:17
#20
Re: Size of standard library and possible tricks to reduce its s
On 9 Lis, 16:58, Todd Vierling wrote:
> The compiler may not be able to figure out, efficiently,
> where the "best" place to insert the abstract class layer is.
I'm wondering if the compiler can do such thing at all. I was not
reading through the whole scala spec, but in case of Java some
standards clearly say what is the mapping of some language constructs
to classes generated from the compiler (how to name anonymous classes
for example). If it is also the case for scala I don't think we can
freely generate additional classes just because it might be more
efficient from the memory and disk usage point of view.
Moreover such automatically generated classes might need to be somehow
hidden. When you look at the inheritance tree you don't want to see
classes you don't inherit from or ones that were never in any code.
Roman
Thu, 2011-12-01, 11:57
#21
Re: Re: Size of standard library and possible tricks to reduce
What if the compiler will create 'abstract class Foo$AC extends Foo' for every trait Foo?
Then it will be able to rewrite every definition of the form 'class C extends Foo ...' to 'class C extends Foo$AC ...', i.e. replace only the first supertrait by generated superclass.
This will catch all the uses like 'new Iterator {...}' or 'C extends A => B' in both library and user's code.
Comparing to the now used scheme, extra code will be generated only for those traits which are never used as first superclass.
Moreover, it makes sense to combine Foo$class and Foo$AC into one class. This will help to futher reduce bytecode size, as most of constant pool entries will be unified in these classes.
So, Foo$class will contain two versions of every non-abstract Foo's method: static method with original method's body (as now) and instance method with stub that invokes that static.
What do you think of this?
Thu, 2011-12-01, 17:27
#22
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 2:48 AM, Pavel Pavlov wrote:
> What do you think of this?
Offhand, I think that's a freaking great idea.
Thu, 2011-12-01, 17:37
#23
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 5:48 AM, Pavel Pavlov wrote:
> What if the compiler will create 'abstract class Foo$AC extends Foo' for
> every trait Foo?
I'm wary of this increasing size in the standard library, though it
would indeed help the case of user code.
It makes me wonder if perhaps an annotation to enable this behavior
per-trait might be a better choice.
Thu, 2011-12-01, 17:47
#24
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 5:25 PM, Todd Vierling <tv@duh.org> wrote:
On Thu, Dec 1, 2011 at 5:48 AM, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:
> What if the compiler will create 'abstract class Foo$AC extends Foo' for
> every trait Foo?
I'm wary of this increasing size in the standard library, though it
would indeed help the case of user code.
It makes me wonder if perhaps an annotation to enable this behavior
per-trait might be a better choice.
The point is the other way around, avoiding splicing in implementations in all subtypes.
It wouldn't need to emit the Foo$AC if it's a purely virtual trait.
--
Thu, 2011-12-01, 17:47
#25
Re: Re: Size of standard library and possible tricks to reduce
Note that all redirection stubs will disappear from all classes (and traits) which implement trait Foo as first supertrait (super-supertrait etc.), only one copy of these stubs will remain - in the class Foo$AC.
So I doubt the library size has any chance to be increased.
Thu, 2011-12-01, 17:57
#26
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 11:29 AM, √iktor Ҡlang wrote:
>> I'm wary of this increasing size in the standard library, though it
>> would indeed help the case of user code.
>>
>> It makes me wonder if perhaps an annotation to enable this behavior
>> per-trait might be a better choice.
>
> The point is the other way around, avoiding splicing in implementations in
> all subtypes.
Yes, I know. I like the idea, but I wonder if it will cause more
strangeness than it solves. Proof of concept would probably be the
only way to find out.
> It wouldn't need to emit the Foo$AC if it's a purely virtual trait.
True, but nearly all traits in the standard library have at least one
implemented method. I would definitely prefer overloading Foo$class
instead, though, since it will already be in use (for static methods)
and would mean one less class file added to the mix.
Thu, 2011-12-01, 18:07
#27
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 8:43 AM, Pavel Pavlov wrote:
> Note that all redirection stubs will disappear from all classes (and traits)
> which implement trait Foo as first supertrait (super-supertrait etc.), only
> one copy of these stubs will remain - in the class Foo$AC.
> So I doubt the library size has any chance to be increased.
I agree, it was this aspect which was so immediately appealing. All
those forwarders add a ton of weight. Also, my (unsubstantiated)
guess is hotspot will do much better at optimizing with an instance
method calling static in the same class vs. a forwarder passing 'this'
to a separate class. At least, I seriously doubt it'll do worse.
Thu, 2011-12-01, 18:17
#28
Re: Re: Size of standard library and possible tricks to reduce
Yes, I know. I like the idea, but I wonder if it will cause more strangeness than it solves.
To keep inheritance hierarchy consistent it can be done in slightly different manner:
1) Compiler generates "abstract class Foo$class extends Foo" with instance stubs and static impl. methods as proposed above.
2) Scala's "class C extends Foo with Bar { ... }" is translated to Java's "class C extends Foo$class implements Foo, Bar { ... }"
instead of "class C extends Object implements Foo, Bar { ... }" as it's done now.
This way we'll have symmetric interface inheritance at JVM level: "C <: Foo, C <: Bar", instead of "C <: Foo$class, Foo$class <: Foo, C <: Bar" as I proposed at first.
Thu, 2011-12-01, 18:27
#29
Re: Re: Size of standard library and possible tricks to reduce
As regards to JIT/HotSpot optimizations and overall performance:
1) Having one forwarder method instead of many leads to faster warm-up of these forwarder(s) and thus earlier compilation and optimization of these forwarders by JIT.
2) More polymorfic/megamorfic call sites (virtual/interface calls to forwarders) became monomorfic at run-time, it will directly improve aggressivenes of inline and other optimizations.
3) Because of (2) and well-known optimistic optimization strategy of HotSpot's JIT the number of deoptimization/repeated recompilation cases may somewhat decrease.
4) At the hardware level, pollution of code cache and branch prediction cache should somewhat decrease.
5) Small static methods (getters/setters) will be inlined by HotSpot into forwarders early, at the first compilation of the forwarder, if they will reside in the same class.
Thu, 2011-12-01, 18:47
#30
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 11:48 AM, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:
What if the compiler will create 'abstract class Foo$AC extends Foo' for every trait Foo? Then it will be able to rewrite every definition of the form 'class C extends Foo ...' to 'class C extends Foo$AC ...', i.e. replace only the first supertrait by generated superclass. This will catch all the uses like 'new Iterator {...}' or 'C extends A => B' in both library and user's code. Comparing to the now used scheme, extra code will be generated only for those traits which are never used as first superclass. Moreover, it makes sense to combine Foo$class and Foo$AC into one class. This will help to futher reduce bytecode size, as most of constant pool entries will be unified in these classes. So, Foo$class will contain two versions of every non-abstract Foo's method: static method with original method's body (as now) and instance method with stub that invokes that static. What do you think of this?I don't know about doing it everywhere. Many traits are meant to be mixed into other traits before they are instantiated. Examples are all ...Like traits in the collection classes. Generating an abstract class for each of them would be pure waste, since no class ever inherits from them in first position.
On the other hand, maybe an annotation could do the trick of giving more precise control to implementers without having to do a lot of typing. Something like
@classbacked trait Iterator { ... }
And in that case, I agree we should try to combine the abstract class with the implementation class. So both abstract class and implementation class could be called Iterator$class, which is neat - no new classfiles!
There's one tricky issue: A static method (like the ones in the implementation class) may not collide with a dynamic method (like the ones in the abstract class), where collide means "have the same name and type signature". Collisions are possible, for instance in the following case:
@classbacked trait T {
def foo(x: T) = ???
def foo() = ???
}
This will generate:
class T$class {
def foo(x: T) = T$class.foo(this, x)
def foo() = T$class.foo(this)
static def foo(_this: T, x: T) = ???
static def foo(_this: T) = ???
}
Note the collision between the first instance foo and the last static foo.
The compiler needs to check for collisions when generating T$class.
Fortunately, there's a remedy: In case of collision, simply do not generate the instance member.
Cheers
-- Martin
--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967
Thu, 2011-12-01, 18:47
#31
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 9:38 AM, martin odersky wrote:
> And in that case, I agree we should try to combine the abstract class with
> the implementation class. So both abstract class and implementation class
> could be called Iterator$class, which is neat - no new classfiles!
One issue with this is that it makes it unavailable to users unless
they're willing to extend a class with a '$' in the name, which should
definitely make them very nervous. So I think there should be a non-$
class which extends the $class class, the name of which could be
derived automatically or could be supplied by the annotation.
Thu, 2011-12-01, 18:57
#32
Re: Re: Size of standard library and possible tricks to reduce
Such scheme also solves previously discussed problem with scaladoc and private classes in the collections hierarchy:
Foo$class is superclass of C only at JVM level. At Scala level, it is invisible at all, just like interface ScalaObject is invisible now.
Thu, 2011-12-01, 18:57
#33
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 12:44 PM, Paul Phillips wrote:
> One issue with this is that it makes it unavailable to users unless
> they're willing to extend a class with a '$' in the name, which should
> definitely make them very nervous. So I think there should be a non-$
> class which extends the $class class, the name of which could be
> derived automatically or could be supplied by the annotation.
I believe the point would be for the compiler to detect the presence*
of the backing class and pull it in automatically by linearization
order: first inheritance entry. So inheritance would still be simply
"class MyClass extends MyTrait ...".
(* assuming that this pre-instantiation might not be universal to all
traits - see my and Martin's notes about possibly controlling this
code generation via annotation.)
Thu, 2011-12-01, 19:07
#34
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 9:43 AM, Pavel Pavlov wrote:
> Foo$class is superclass of C only at JVM level. At Scala level, it is
> invisible at all, just like interface ScalaObject is invisible now.
Oh, and that reminds me, it might give us a shot at a subset of these:
https://issues.scala-lang.org/browse/SI-2296
Basically, we get burned on accessing protected members in java
classes because the jvm requires you be in a subclass of the actual
class whereas in scala the code performing the access, if defined in a
trait, will not be in a subclass but called through a forwarder.
Thu, 2011-12-01, 19:17
#35
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 6:49 PM, Todd Vierling <tv@duh.org> wrote:
On Thu, Dec 1, 2011 at 12:44 PM, Paul Phillips <paulp@improving.org> wrote:
> One issue with this is that it makes it unavailable to users unless
> they're willing to extend a class with a '$' in the name, which should
> definitely make them very nervous. So I think there should be a non-$
> class which extends the $class class, the name of which could be
> derived automatically or could be supplied by the annotation.
I believe the point would be for the compiler to detect the presence*
of the backing class and pull it in automatically by linearization
order: first inheritance entry. So inheritance would still be simply
"class MyClass extends MyTrait ...".
I agree. It would be best if we did not need to invent a user-visible name for the class.
Cheers
-- Martin
Thu, 2011-12-01, 19:27
#36
Re: Re: Size of standard library and possible tricks to reduce
On Friday, December 2, 2011 12:38:02 AM UTC+7, martin odersky wrote:
It would be great to measure effect of both techniques (annotation-based and generate-forwarders-by-default). I am not a big fan of generating useless code but generate-by-default approach have one appealing property, I think: No matter how many times you use (extend) a trait you'll have only one copy of forwarders. So you never will run into the situation as with Iterator now: one simple line "new Iterator { ...}" in the source code leads to generation of unpredictable large amount of bytecode (how many methods will have Iterator in Scala 3.33?). Yes, when we generate forwarders by default the size of bytecode can increase comparing to what we have now, but overall bytecode size will remain proportional to source code size. On the other hand, we never see disproportional/unpredictable code size bloat (in case of single trait inheritance) as we have now. Annotation-based scheme will not cure this problem. Also, generate-by-default scheme will somewhat weaken binary incompatibility: In case of adding new concrete method to the Iterator, you won't need to recompile all the code that single-inherit Iterator.I don't know about doing it everywhere. Many traits are meant to be mixed into other traits before they are instantiated. Examples are all ...Like traits in the collection classes. Generating an abstract class for each of them would be pure waste, since no class ever inherits from them in first position.
On the other hand, maybe an annotation could do the trick of giving more precise control to implementers without having to do a lot of typing. Something like
@classbacked trait Iterator { ... }
...or use some sort of mangling magic: class T$class {
There's one tricky issue: A static method (like the ones in the implementation class) may not collide with a dynamic method (like the ones in the abstract class), where collide means "have the same name and type signature". Collisions are possible, for instance in the following case:
@classbacked trait T {
def foo(x: T) = ???
def foo() = ???
}
This will generate:
class T$class {
def foo(x: T) = T$class.foo(this, x)
def foo() = T$class.foo(this)
static def foo(_this: T, x: T) = ???
static def foo(_this: T) = ???
}
Note the collision between the first instance foo and the last static foo.
The compiler needs to check for collisions when generating T$class.
Fortunately, there's a remedy: In case of collision, simply do not generate the instance member.
def foo(x: T) = T$class.foo$(this, x)
def foo() = T$class.foo$(this)
static def foo$(_this: T, x: T) = ???
static def foo$(_this: T) = ???
}
Thu, 2011-12-01, 20:07
#37
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 1:23 PM, Pavel Pavlov wrote:
> I am not a big fan of generating useless code but generate-by-default
> approach have one appealing property, I think:
> No matter how many times you use (extend) a trait you'll have only one copy
> of forwarders.
Only in cases where it's the first trait. For multiple inheritance
cases, the additional traits will always have additional forwarders
(there's no way around this).
Thu, 2011-12-01, 20:27
#38
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 1:23 PM, Pavel Pavlov <pavel.e...@gmail.com> wrote:
Interesting, how many there are such cases comparing to single inheritance of traits?
Note that if you have
trait A extends B with C
trait D extends A with E
class F extends D with G with A with E
then inheritance of A and D will be "single" in the terms of generating forwarders, i.e. in this sample:
forwarders for A, B, D will be generated once;
for C - twice (in C$class & A$class);
for E - twice (in E$class & D$class);
for G - twice (in G$class & F).
> I am not a big fan of generating useless code but generate-by-defaultOf course.
> approach have one appealing property, I think:
> No matter how many times you use (extend) a trait you'll have only one copy
> of forwarders.Only in cases where it's the first trait. For multiple inheritance
cases, the additional traits will always have additional forwarders
(there's no way around this).
Interesting, how many there are such cases comparing to single inheritance of traits?
Note that if you have
trait A extends B with C
trait D extends A with E
class F extends D with G with A with E
then inheritance of A and D will be "single" in the terms of generating forwarders, i.e. in this sample:
forwarders for A, B, D will be generated once;
for C - twice (in C$class & A$class);
for E - twice (in E$class & D$class);
for G - twice (in G$class & F).
Thu, 2011-12-01, 20:57
#39
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 2:17 PM, Pavel Pavlov wrote:
>> Only in cases where it's the first trait. For multiple inheritance
>> cases, the additional traits will always have additional forwarders
>> (there's no way around this).
>
> Of course.
>
> Interesting, how many there are such cases comparing to single inheritance
> of traits?
Look at any collection class's inheritance hierarchy. :)
That doesn't make the idea bad; it just clarifies that the generated
forwarders will still happen in some cases.
Thu, 2011-12-01, 21:17
#40
Re: Re: Size of standard library and possible tricks to reduce
> Interesting, how many there are such cases comparing to single inheritanceOk, I just noted that even in case of multiple inheritance there are still some "good cases" like in the example above.
> of traits?Look at any collection class's inheritance hierarchy. :)
That doesn't make the idea bad; it just clarifies that the generated
forwarders will still happen in some cases.
Anyway, we always have the "ultimate" method available: to rewrite the code manually like you already did with collection classes :)
Thu, 2011-12-01, 21:27
#41
Re: Re: Size of standard library and possible tricks to reduce
Out of general curiosity, two questions:
Is it jar-size or permgen-size that is the issue?
If the former, why not generate the classes at runtime?
BR,
John
On Friday, December 2, 2011 12:38:02 AM UTC+7, martin odersky wrote:It would be great to measure effect of both techniques (annotation-based and generate-forwarders-by-default). I am not a big fan of generating useless code but generate-by-default approach have one appealing property, I think: No matter how many times you use (extend) a trait you'll have only one copy of forwarders. So you never will run into the situation as with Iterator now: one simple line "new Iterator { ...}" in the source code leads to generation of unpredictable large amount of bytecode (how many methods will have Iterator in Scala 3.33?). Yes, when we generate forwarders by default the size of bytecode can increase comparing to what we have now, but overall bytecode size will remain proportional to source code size. On the other hand, we never see disproportional/unpredictable code size bloat (in case of single trait inheritance) as we have now. Annotation-based scheme will not cure this problem. Also, generate-by-default scheme will somewhat weaken binary incompatibility: In case of adding new concrete method to the Iterator, you won't need to recompile all the code that single-inherit Iterator.I don't know about doing it everywhere. Many traits are meant to be mixed into other traits before they are instantiated. Examples are all ...Like traits in the collection classes. Generating an abstract class for each of them would be pure waste, since no class ever inherits from them in first position.
On the other hand, maybe an annotation could do the trick of giving more precise control to implementers without having to do a lot of typing. Something like
@classbacked trait Iterator { ... }...or use some sort of mangling magic: class T$class {
There's one tricky issue: A static method (like the ones in the implementation class) may not collide with a dynamic method (like the ones in the abstract class), where collide means "have the same name and type signature". Collisions are possible, for instance in the following case:
@classbacked trait T {
def foo(x: T) = ???
def foo() = ???
}
This will generate:
class T$class {
def foo(x: T) = T$class.foo(this, x)
def foo() = T$class.foo(this)
static def foo(_this: T, x: T) = ???
static def foo(_this: T) = ???
}
Note the collision between the first instance foo and the last static foo.
The compiler needs to check for collisions when generating T$class.
Fortunately, there's a remedy: In case of collision, simply do not generate the instance member.
def foo(x: T) = T$class.foo$(this, x)
def foo() = T$class.foo$(this)
static def foo$(_this: T, x: T) = ???
static def foo$(_this: T) = ???
}
Thu, 2011-12-01, 21:37
#42
Re: Re: Size of standard library and possible tricks to reduce
Out of general curiosity, two questions:
If you ask me, then I'm is very strongly biased against this idea.Is it jar-size or permgen-size that is the issue?
If the former, why not generate the classes at runtime?
Maybe because I'm writing AOT native compiler in Scala and loosing self-applicability is my worst nightmare (we will be constrained to downgrade our codebase from Scala to Java in that case), maybe it is just a matter of taste. :)
Thu, 2011-12-01, 21:57
#43
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 3:10 PM, John Nilsson wrote:
> Out of general curiosity, two questions:
>
> Is it jar-size or permgen-size that is the issue?
>
> If the former, why not generate the classes at runtime?
Bytecode generation should be avoided if possible, as it prevents:
- targeting alternative VMs (Android Dalvik)
- ahead-of-time compilation (gcj)
- linkage needed to run obfuscation/optimization tools (RetroGuard)
It can also make debugging significantly more difficult, and may bloat
JIT memory footprint.
Thu, 2011-12-01, 23:07
#44
Re: Re: Size of standard library and possible tricks to reduce
Ok, fair enough. I guess most concerns could be addressed by different compilation backends or an optional postprocessing step, but I can see how its enough of an issue to not warrant the added complexity.
Thanks for the info!
John
On Thu, Dec 1, 2011 at 3:10 PM, John Nilsson <john@milsson.nu> wrote:
> Out of general curiosity, two questions:
>
> Is it jar-size or permgen-size that is the issue?
>
> If the former, why not generate the classes at runtime?
Bytecode generation should be avoided if possible, as it prevents:
- targeting alternative VMs (Android Dalvik)
- ahead-of-time compilation (gcj)
- linkage needed to run obfuscation/optimization tools (RetroGuard)
It can also make debugging significantly more difficult, and may bloat
JIT memory footprint.
--
Fri, 2011-12-02, 03:47
#45
Re: Re: Size of standard library and possible tricks to reduce
I don't know about doing it everywhere. Many traits are meant to be mixed into other traits before they are instantiated. Examples are all ...Like traits in the collection classes. Generating an abstract class for each of them would be pure waste, since no class ever inherits from them in first position.
I've just noticed that I haven't stated this clearly enough:
There's no need to generate forwarders for traits used as first supertrait in another traits, as well as in classes.
Maybe someone will be able to collect some stats on the forwarders counts?
I place the sketch of (pseudo)code here:
======================================
type Klazz // class or trait
type Trait <: Klazz
type Class <: Klazz
type MethodHost = Klazz
type Method = (MethodName, MethodSig, MethodHost)
def methodDecls(k: Klazz): Set[Method] = ??? // builds set of all non-abstract methods for k; linearization magic works here
def klazzFwdCount(k: Klazz, skipFirstSuperTrait: Boolean): Int = {
var mset = methodDecls(k)
val sup = k.supers.toList
sup match {
case (s1: Trait) :: _ if skipFirstSuperTrait =>
mset = mset &~ methodDecls(s1) // filter out non-overriden methods from first supertrait
case (s1: Class) :: _ =>
mset = mset &~ methodDecls(s1) // filter out non-overriden methods from the superclass
case _ =>
}
k match {
case _: Class =>
mset = mset collect { case m@(_, _, host) if host != k => m } // filter out methods declared in k
case _ =>
}
mset.size
}
def allClasses = allKlazzes collect { case c: Class => c }
def allTraits = allKlazzes collect { case t: Trait => t }
def notUsedAsFirstSuper: Seq[Trait] = {
var notUsed: Set[Trait] = Set.empty
def isFirstSuper(t: Trait) = {
val p = allKlazzes find { k => !notUsed(k) && k.supers startsWith Seq(t) }
!p.isEmpty
}
var changed = true
while (changed) {
changed = false
for (t <- allTraits; if !isFirstSuper(t)) {
notUsed += t
changed = true
}
}
notUsed.toSeq
}
def countStat() {
val currFwds = allClasses.map(klazzFwdCount(_, false)).sum
val smartFwds = allKlazzes.map(klazzFwdCount(_, true)).sum
val notUsedFwds = notUsedAsFirstSuper.map(klazzFwdCount(_, true)).sum
println("Forwarders count: %d; expected: %d, of which not used: %d", currFwds, smartFwds, notUsedFwds)
}
======================================
Fri, 2011-12-02, 08:57
#46
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 7:23 PM, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:
On Friday, December 2, 2011 12:38:02 AM UTC+7, martin odersky wrote:It would be great to measure effect of both techniques (annotation-based and generate-forwarders-by-default). I am not a big fan of generating useless code but generate-by-default approach have one appealing property, I think: No matter how many times you use (extend) a trait you'll have only one copy of forwarders. So you never will run into the situation as with Iterator now: one simple line "new Iterator { ...}" in the source code leads to generation of unpredictable large amount of bytecode (how many methods will have Iterator in Scala 3.33?). Yes, when we generate forwarders by default the size of bytecode can increase comparing to what we have now, but overall bytecode size will remain proportional to source code size. On the other hand, we never see disproportional/unpredictable code size bloat (in case of single trait inheritance) as we have now. Annotation-based scheme will not cure this problem. Also, generate-by-default scheme will somewhat weaken binary incompatibility: In case of adding new concrete method to the Iterator, you won't need to recompile all the code that single-inherit Iterator.I don't know about doing it everywhere. Many traits are meant to be mixed into other traits before they are instantiated. Examples are all ...Like traits in the collection classes. Generating an abstract class for each of them would be pure waste, since no class ever inherits from them in first position.
On the other hand, maybe an annotation could do the trick of giving more precise control to implementers without having to do a lot of typing. Something like
@classbacked trait Iterator { ... }...or use some sort of mangling magic: class T$class {
There's one tricky issue: A static method (like the ones in the implementation class) may not collide with a dynamic method (like the ones in the abstract class), where collide means "have the same name and type signature". Collisions are possible, for instance in the following case:
@classbacked trait T {
def foo(x: T) = ???
def foo() = ???
}
This will generate:
class T$class {
def foo(x: T) = T$class.foo(this, x)
def foo() = T$class.foo(this)
static def foo(_this: T, x: T) = ???
static def foo(_this: T) = ???
}
Note the collision between the first instance foo and the last static foo.
The compiler needs to check for collisions when generating T$class.
Fortunately, there's a remedy: In case of collision, simply do not generate the instance member.
def foo(x: T) = T$class.foo$(this, x)
def foo() = T$class.foo$(this)
static def foo$(_this: T, x: T) = ???
static def foo$(_this: T) = ???
}
I prefer not to mangle the static foo's because sometimes Java interop depends on them. But either way it's not a big problem.
Cheers
-- Martin
Fri, 2011-12-02, 12:17
#47
Re: Size of standard library and possible tricks to reduce its s
Btw will all those problems be solved easily by introduction of java 8
and modified JVM?
There is this feature with default interface implementations [1] that
AFAIK requires modified JVM, but... should drastically reduce the size
of scala library.
Maybe it's better to wait a little for java 8 and have it solved
ultimatelly? Or then at least have separate java8 version or standard
scala library?
Roman
[1] http://stackoverflow.com/questions/7857832/are-defaults-in-jdk-8-a-form-...
Fri, 2011-12-02, 12:47
#48
Re: Re: Size of standard library and possible tricks to reduce
Here are the corresponding slides:
http://www.wiki.jvmlangsummit.com/images/a/a1/2011_Goetz_Extension_Slide...
Scala may benefit from this feature but it will be some years until
the Java 8 JVM would feasibly be a target for Scala.
On Fri, Dec 2, 2011 at 12:10 PM, RomKal wrote:
> Btw will all those problems be solved easily by introduction of java 8
> and modified JVM?
>
> There is this feature with default interface implementations [1] that
> AFAIK requires modified JVM, but... should drastically reduce the size
> of scala library.
>
> Maybe it's better to wait a little for java 8 and have it solved
> ultimatelly? Or then at least have separate java8 version or standard
> scala library?
>
> Roman
>
> [1] http://stackoverflow.com/questions/7857832/are-defaults-in-jdk-8-a-form-...
Fri, 2011-12-02, 12:57
#49
Re: Size of standard library and possible tricks to reduce its
In addition, consider that this problem most severely affects limited platforms like Android/Dalvik. I suspect that Java 8 will take even longer to become available on that kind of platform.
On 2 Dec 2011, at 11:37, Johannes Rudolph wrote:
> Here are the corresponding slides:
>
> http://www.wiki.jvmlangsummit.com/images/a/a1/2011_Goetz_Extension_Slide...
>
> Scala may benefit from this feature but it will be some years until
> the Java 8 JVM would feasibly be a target for Scala.
>
> On Fri, Dec 2, 2011 at 12:10 PM, RomKal wrote:
>> Btw will all those problems be solved easily by introduction of java 8
>> and modified JVM?
>>
>> There is this feature with default interface implementations [1] that
>> AFAIK requires modified JVM, but... should drastically reduce the size
>> of scala library.
>>
>> Maybe it's better to wait a little for java 8 and have it solved
>> ultimatelly? Or then at least have separate java8 version or standard
>> scala library?
>>
>> Roman
>>
>> [1] http://stackoverflow.com/questions/7857832/are-defaults-in-jdk-8-a-form-...
>
>
>
Fri, 2011-12-02, 15:57
#50
Re: Re: Size of standard library and possible tricks to reduce
On Thu, Dec 1, 2011 at 9:43 PM, Pavel Pavlov wrote:
> I've just noticed that I haven't stated this clearly enough:
> There's no need to generate forwarders for traits used as first supertrait
> in another traits, as well as in classes.
How would the compiler know the difference?
In my (maybe temporary?) changes to the collection classes, there is a
hierarchy that looks like this:
abstract class AbstractTraversable[+A] extends Traversable[A]
abstract class AbstractIterable[+A] extends AbstractTraversable[A]
with Iterable[A]
abstract class AbstractSeq[+A] extends AbstractIterable[A] with Seq[A]
This does involve an inheritance hierarchy because the number of new
forwarders at each level is non-trivial. However, I didn't create an
AbstractTraversableOnce because its methods are almost completely
overridden at both the Iterator and Traversable subtrait levels. I
also didn't create classes for Gen* because those are also mostly
overridden, and not directly inherited.
If this were done only as the following, the bytecode (and number of
redundant forwarders) would be notably larger:
abstract class AbstractTraversable[+A] extends Traversable[A]
abstract class AbstractIterable[+A] extends Iterable[A]
abstract class AbstractSeq[+A] extends Seq[A]
This is the I prefer the idea of a compiler annotation. It allows for
finer-grain control over the process, so that there is not a
proliferation of either extra superclasses or redundant forwarders.
On Tue, Oct 18, 2011 at 2:19 PM, Todd Vierling wrote:
> So, the library jar is getting kinda bulky, especially after the addition of
> parallel collections. I've been noticing that there's a whole lot of
> repetitive trait-stub instantiations -- scala/collection/Iterator$$anon$*
> are great examples of these (they're all different subtypes of Iterator
> itself) -- and I wonder if anyone has thought to create some library-private
> abstract classes to flatten some of the bytecode bloat.
https://lampsvn.epfl.ch/trac/scala/changeset/20311
https://issues.scala-lang.org/browse/SI-2876
https://lampsvn.epfl.ch/trac/scala/changeset/20490
That was for views. The issue in 2876 doesn't look so bad from this
vantage, but as I recall there was a more serious compiler bug which
was never resolved which made the whole process too tedious.
It's probably doable, but in my experience one tends to discover new
or (worse) old and unfixed compiler bugs when attempting these things,
so you need to be prepared for battle.