rethinking specialization
Erik Osheim
I. Background
I've been looking closely at specialization bugs recently, trying to
figure out how to make the feature less buggy, and more able to handle
real-world situations that users might throw at it. (As a library
author trying to use specialization I feel like I have a reasonably
good idea of some important use cases.)
This has involved reading Iulian's thesis, working on fixing bugs, and
discussing it with others. I don't claim to understand every detail of
the specialize phase implementation, but I feel like I have a pretty
good handle on how specialization does (or doesn't) work, the current
state of it, and some of the (seemingly) intractable problems with it.
I'm writing this because recently I've been kicking around a different
class specialization design in my head, and I just want to get it out
into the wider world so that other people can either show me why it's
naive and wrong, or to pave the way to a formal SIP around improving
specialization (or just a go-ahead signal from martin &co).
First, I will try to discuss some of the (seemingly intractable)
problems with specialization. In addition to these, there are lots of
other bugs we're currently facing, but with work I think a lot of these
can be fixed. I want to focus on the problems I see with the overall
design.
II. Example of Specialization
Consider this code:
import scala.{specialized => spec}
class Foo[@spec(Int) A](a:A, b:A) {
def bar(c:A) = new Foo(a, c)
def baz = b
def qux = a == b
}
Specializing Foo does a lot of things. Here's a rough outline of how
class specialization plays out in this case:
1. It decides which of Foo's methods should be specialized on A, Foo's
type parameter. In this case it will choose bar and baz.
2. For each of those methods, and for each primitive type we want to
specialize on (just Int in this case) it creates a "specialized
variant", e.g. Foo.bar$mcI$sp, which replaces A with Int. This
method will call into the original method (e.g. forwarding to bar),
boxing and unboxing to satisfy its own interface. This is sometimes
called a "specialized overload".
3. For each type we want to specialize on, a specialized subclass of
Foo is created. In this case, just Foo$mcI$spa is created,
corresponding to Foo[Int].
4. For each of the fields in Foo (e.g. a and b) Foo$mcI$sp is given
specialized versions of them (e.g. a$mcI$sp and b$mcI$sp).
5. All of the "specialized methods" in Foo from step #1 (both the
original method and the corresponding specialized variant) are
overridden in Foo$mcI$sp.
6. The specialized subclass' override of the specialized variant (i.e.
Foo$mcI$sp.bar$mcI$sp) is implemented by copying the tree of the
original method (i.e. Foo.bar) and then rewritten by replacing all
fields/methods/classes with specialized versions where appropriate.
So, in bar's implementation, "new Foo" is rewritten to be
"new Foo$mcI$sp".
7. The subclass' override of the original method (Foo$mcI$sp.bar)
is forwarded to the specialized variant (Foo$mcI$sp.bar$mcI$sp)
doing boxing/unboxing as required by its interface.
The result (in summarized form) is:
// this is the "original" unspecialized class, where generic use of
// A is implemented as Object on the JVM. When A = Int, interfaces
// needing Object will require the Int to be boxed.
class Foo {
protected[this] val a: Object = _;
protected[this] val b: Object = _;
def bar(c: Object): Foo = new Foo(Foo.this.a, c);
def bar$mcI$sp(c: Int): Foo = Foo.this.bar(Int.box(c));
def baz(): Object = Foo.this.b;
def baz$mcI$sp(): Int = Int.unbox(Foo.this.baz());
def qux(): Boolean = Foo.this.a.==(Foo.this.b);
def this(a: Object, b: Object): Foo = {
Foo.this.a = a;
Foo.this.b = b;
Foo.super.this();
()
}
}
// this is the specialized subclass. anything not overridden here is
// inherited from Foo. this means that Foo$mcI$sp has 4 fields (a, b,
// a$mcI$sp, and b$mcI$sp) whereas Foo only has two (a and b).
class Foo$mcI$sp extends Foo {
protected[this] val a$mcI$sp: Int = _;
protected[this] val b$mcI$sp: Int = _;
override def bar(c: Int): Foo = Foo$mcI$sp.this.bar$mcI$sp(c);
override def bar(c: Object): Foo = Foo$mcI$sp.this.bar(Int.unbox(c));
override def bar$mcI$sp(c: Int): Foo = new Foo$mcI$sp(Foo$mcI$sp.this.a$mcI$sp, c);
override def baz(): Int = Foo$mcI$sp.this.baz$mcI$sp();
override def baz(): Object = Int.box(Foo$mcI$sp.this.baz());
override def baz$mcI$sp(): Int = Foo$mcI$sp.this.b$mcI$sp;
def this(a$mcI$sp: Int, b$mcI$sp: Int): Foo$mcI$sp = {
Foo$mcI$sp.this.a$mcI$sp = a$mcI$sp;
Foo$mcI$sp.this.b$mcI$sp = b$mcI$sp;
Foo$mcI$sp.super.this(Int.box(a$mcI$sp), Int.box(b$mcI$sp));
()
}
}
III. Analysis of Existing Strategy
This strategy is designed to allow generic and specialized code to be
intermixed: since all the specialized subclasses extend Foo, code that
treats a specialized class/instance as generic will continue working
(because the specialized instances supports the same interface as the
generic version). This strategy also reduces the amount of bytecode
duplicated, since only overrides some of Foo's methods, rather than all
of them.
In practice, the fact that users provide one class (Foo) which
effectively becomes an inheritance hierarchy (i.e. Foo$mcI$sp extending
Foo) is a huge headache. It prevents specialized classes from
effectively using private (since specialized subclasses would not be
able to forward to or override a private member of Foo). Modifiers like
final and @inline often don't work correctly for Foo: even though the
user has no intention of extending Foo, the specialization machinery
needs to be able to do just that.
There are problems with double-initializing final vals (once in
Foo$mcI$sp's constructor as null, and again when it calls into Foo's
constructor). There's the fact that the specialized subclasses often
have twice as many fields as the original class. There's the fact that
extending a specialized class doesn't work correctly, meaning that
rather than a (mostly transparent) optimizing annotation,
specialization is a mandate to remove abstract classes in favor of
traits.
In my opinion, almost all of the major issues in specialization stem
from the fact that specialized subclasses end up having one class' guts
smeared between two classes in a way that is hard for the end user to
predict or control.
IV. Proposed Changes
The major shift I propose is moving from a world where Foo is both a
generic class, and also the parent of specialized subclasses, to a
world where Foo becomes just an interface (a trait with only
public/protected members and without implementations). AnyRef already
moves us closer to this goal, but this change brings us all the way.
This means that all instances of Foo need to be rewritten, either to a
specialized form (e.g. Foo$mcI$sp) or to the AnyRef specialization
(e.g. Foo$mcL$sp[A]). These classes all extend Foo, but do not share
any implementation code: they would each contain a full copy of Foo's
members (including private members), their own constructors, etc.
The downside of this is that you really do have x2-10 as much bytecode
as you did when Foo was just a single class. It also means that you
can't write code that just uses Foo (because Foo is no longer a
concrete class), instead your compiler *always* has to translate Foo to
Foo$mcL$sp, even if you are compiling with specialization turned off.
This also means that people using things like reflection will always
see the "specialized names" of classes.
But the upsides are great! For one, you don't need to rewrite any of
the access controls, annotations, or other modifiers like final. Since
we just renamed a class into another class (and performed some
transformations on types/names) we can be pretty sure that the
semantics of the class intialization, inlining, visibility, etc are
what the original author intended. We also don't end up with extra
fields that we don't plan to use.
Also it may not be more bytecode in some cases. Let's say we generate 5
specializations of a class (with 3 specialized methods). The current
startegy involves creating 5 specialized overloads of the 3 methods,
then creating 5 subclasses overriding all the methods. That is, you end
up with 6 classes each with 18 methods (although many of the methods
just do boxing/unboxing and forward somewhere else). My strategy ends
up with 6 classes each with 3 methods (each method containing the full
implementation).
My sense is that the transformation I'm talking about is a lot easier
in practice than the one we are currently trying to support.
Unfortunately it is not backwards-compatible with the existing
strategy, although it could probably use the same naming scheme if we
want. I would rather not try to support both schemes.
V. Example
For completeness, I will sketch out how the previous class would be
transformed under my scheme:
trait Foo[A] {
def a: A
def b: A
def bar(c: A): Foo[A]
def baz: A
def qux: Boolean
}
class Foo$mcL$sp[A](a:A, b:A) extends Foo[A] {
def bar(c: A): Foo$mcL$sp[A] = new Foo$mcL$sp(a, c)
def baz: A = b
def qux: Boolean = a == b
}
class Foo$mcI$sp(a:Int, b:Int) extends Foo[Int] {
def bar(c: Int): Foo$mcI$sp = new Foo$mcI$sp(a, c)
def baz: Int = b
def qux: Boolean = a == b
}
As you can see, Foo$mcL$sp[A] and Foo$mcI$sp are both (relatively)
obvious transformations of the original Foo class, and any code which
would work with Foo[A] should work with these (either with Foo$mcI$sp
when A is known to be Int, or Foo$mcL$sp otherwise). The big difference
is that calling code would need to transform:
val foo1:Foo[Int] = new Foo[Int](13, 45)
val foo2:Foo[B] = new Foo[B](b1, b2)
into
val foo1:Foo$mcI$sp = new Foo$mcI$sp(13, 45)
val foo2:Foo$mcL$sp[B] = new Foo$mcL$sp[B](b1, b2)
VI. Final Thoughts
Again, this doesn't seem (to me) to be that much more difficult than
what is currently being done and I don't see obvious problems with
partial compilation. In fact, I think the question about how to handle
specialized classes is significantly *less* complicated, since in these
cases you don't need to munge the method names (or worry about the
difference between calling Foo.bar$mcI$sp and Foo$mcI$sp.bar$mcI$sp).
I haven't mentioned "method specialization" because I think the
existing approach is basically fine and seems to work pretty well.
There may be bugs with it, but I don't think these are structural. So,
even in my proposal users could specialized particular methods
basically as they do now (by creating a copy of their tree, renaming
it, and substituting type params and other classes/methods as
appropriate for that specialized version).
What do you all think? Is this a terrible idea? A great one? Are there
things I have completely overlooked? Am I wrong, and the existing
strategy is fine (modulo a few design changes)? I look forward to your
feedback.
-- Erik
Geoff Reedy
> The downside of this is that you really do have x2-10 as much bytecode
> as you did when Foo was just a single class. It also means that you
> can't write code that just uses Foo (because Foo is no longer a
> concrete class), instead your compiler *always* has to translate Foo to
> Foo$mcL$sp, even if you are compiling with specialization turned off.
> This also means that people using things like reflection will always
> see the "specialized names" of classes.
Could this be mitigated by keeping Foo as an actual class with only a
single member containing the true implementation class. You could even
have overloaded constructors when a specialized type param is used as a
constructor argument. In this way even non-specialized compiled code
could get some of the benefits since internally the actual compuation
would be done by a specialized class (in this example the un/boxing
currently required for the quux method could be eliminated). Of course
there is the additional overhead of the delegation that would have to be
carefully measured.
-- Geoff
Erik Osheim
> Could this be mitigated by keeping Foo as an actual class with only a
> single member containing the true implementation class. You could even
> have overloaded constructors when a specialized type param is used as a
> constructor argument. In this way even non-specialized compiled code
> could get some of the benefits since internally the actual compuation
> would be done by a specialized class (in this example the un/boxing
> currently required for the quux method could be eliminated). Of course
> there is the additional overhead of the delegation that would have to be
> carefully measured.
So I guess the plan here is rather than having the compiler rewrite new
Foo into new Foo$mcL$sp you want Foo to be a synthetic class that does
that transformation itself? It works I suppose, although I don't like
all the implied boxing that would probably happen. Consider the effect
of Some(3) assuming Some[A] is specialized on Int... we end up "double
boxing" the integer into something like Some(Some$mcI$sp(3)).
That might end up defeating a lot of the benefit of specialization for
small objects (although obviously I haven't measured it myself). I
guess I am just saying that it's not just delegation cost, but also
boxing overhead (which is hard to optimize away) which we have to
consider.
-- Erik
Erik Osheim
mentioned) would be that it would create an obvious path to
user-defined specializations. For instance, you could imagine:
class Foo[@spec(Int, Double) A](a:A) { ... }
@manualSpec(Foo, Int) class IntFoo(a:Int) { ... }
It's hard to keep enough of the current specialization details in one's
head enough to effectively implement a specialized subclass of Foo by
hand (as I found out writing the original email). But in my opinion my
proposal makes it much easier (more intuitive) to imagine how a
specialized version of Foo should look.
Of course, you can simulate user-driven specializations using type
classes so it's not essential that we must support them. I just think
it's a nice side benefit that the proposal is simple enough that users
could be expected to get this right.
-- Erik
Matthew Pocock
Thanks for looking at this. I like the idea of moving the anyref case to be treated the same as for primitives. One enhancement I would like to see is the ability to get more control over what portion of the cross product of multiple type parameters get expanded. For example, (a:A @spec, b:B @spec(matches=A)) would generate specialised versions only in the cases where A and B are the same type.
Rex Kerr
I've come to similar conclusions as you regarding the problem with specialization as it now exists.
I'm not entirely sure that your solution scales properly, however.
Let's take the most hideous beast in the current Scala library, Function2, which is specialized on
arg1: Int, Long, Double
arg2: Int, Long, Double
return: Unit, Boolean, Int, Float, Long, Double
This has fully 55 different versions in the current scheme (54 specialized and 1 generic), and generates around 1.2M of bytecode, of which ~25k is the core class itself with ~5k more per variant (of which the majority is from curried and tupled).
Exception Function2 is actually a trait. So it has both the interface (with 55 copies of every method) and the corresponding class (with the same number of copies).
Your proposal would do what to this, exactly, and interact with generic code how, exactly?
I think you have 55 different versions of the class but with only their own apply/tupled/curried.
But now suppose I wanted to write
def ff[@specialized(Int) A, @specialized(Double) B](f1: (A,A) => B, f2: (B,B) => A, a4: (A,A,A,A)) =
f2( f1(a4._1, a4._2), f1(a4._3, a4._4) )
how would this work? It claims to be specialized, but only on a subset of the types that the functions are, so what does the default version use? I haven't quite been able to grasp the consequences deeply enough to see if what you're proposing is a big win, a big loss, or something else in these situations. It is these high-degree-of-specialization cases that are the most expensive (and most confusing).
The cases for which ff was not specialized and Function2 was would get translated into the AnyRef version, using the normal two-methods-for-primitives scheme that lets you have a generic with a primitive type parameter?
--Rex
iulian dragos
In my opinion, almost all of the major issues in specialization stem
from the fact that specialized subclasses end up having one class' guts
smeared between two classes in a way that is hard for the end user to
predict or control.
IV. Proposed Changes
The major shift I propose is moving from a world where Foo is both a
generic class, and also the parent of specialized subclasses, to a
world where Foo becomes just an interface (a trait with only
public/protected members and without implementations). AnyRef already
moves us closer to this goal, but this change brings us all the way.
This means that all instances of Foo need to be rewritten, either to a
specialized form (e.g. Foo$mcI$sp) or to the AnyRef specialization
(e.g. Foo$mcL$sp[A]). These classes all extend Foo, but do not share
any implementation code: they would each contain a full copy of Foo's
members (including private members), their own constructors, etc.
[..]
But the upsides are great! For one, you don't need to rewrite any of
the access controls, annotations, or other modifiers like final. Since
we just renamed a class into another class (and performed some
transformations on types/names) we can be pretty sure that the
semantics of the class intialization, inlining, visibility, etc are
what the original author intended. We also don't end up with extra
fields that we don't plan to use.
V. Example
For completeness, I will sketch out how the previous class would be
transformed under my scheme:
trait Foo[A] {
def a: A
def b: A
def bar(c: A): Foo[A]
def baz: A
def qux: Boolean
}
class Foo$mcL$sp[A](a:A, b:A) extends Foo[A] {
def bar(c: A): Foo$mcL$sp[A] = new Foo$mcL$sp(a, c)
def baz: A = b
def qux: Boolean = a == b
}
class Foo$mcI$sp(a:Int, b:Int) extends Foo[Int] {
def bar(c: Int): Foo$mcI$sp = new Foo$mcI$sp(a, c)
def baz: Int = b
def qux: Boolean = a == b
}
As you can see, Foo$mcL$sp[A] and Foo$mcI$sp are both (relatively)
obvious transformations of the original Foo class, and any code which
would work with Foo[A] should work with these (either with Foo$mcI$sp
when A is known to be Int, or Foo$mcL$sp otherwise). The big difference
is that calling code would need to transform:
val foo1:Foo[Int] = new Foo[Int](13, 45)
val foo2:Foo[B] = new Foo[B](b1, b2)
into
val foo1:Foo$mcI$sp = new Foo$mcI$sp(13, 45)
val foo2:Foo$mcL$sp[B] = new Foo$mcL$sp[B](b1, b2)
VI. Final Thoughts
Again, this doesn't seem (to me) to be that much more difficult than
what is currently being done and I don't see obvious problems with
partial compilation. In fact, I think the question about how to handle
specialized classes is significantly *less* complicated, since in these
cases you don't need to munge the method names (or worry about the
difference between calling Foo.bar$mcI$sp and Foo$mcI$sp.bar$mcI$sp).
I haven't mentioned "method specialization" because I think the
existing approach is basically fine and seems to work pretty well.
There may be bugs with it, but I don't think these are structural. So,
even in my proposal users could specialized particular methods
basically as they do now (by creating a copy of their tree, renaming
it, and substituting type params and other classes/methods as
appropriate for that specialized version).
What do you all think? Is this a terrible idea? A great one? Are there
things I have completely overlooked? Am I wrong, and the existing
strategy is fine (modulo a few design changes)? I look forward to your
feedback.
-- Erik
« Je déteste la montagne, ça cache le paysage »
Alphonse Allais
Erik Osheim
Thanks for taking the time to read my email and come up with an
example. I think it's a lot easier to reason about how this "new
specialization" would be behave in this case and hopefully I can
convince you of it.
On Tue, Feb 21, 2012 at 12:06:16PM -0500, Rex Kerr wrote:
> But now suppose I wanted to write
>
> def ff[@specialized(Int) A, @specialized(Double) B](f1: (A,A) => B, f2:
> (B,B) => A, a4: (A,A,A,A)) =
> f2( f1(a4._1, a4._2), f1(a4._3, a4._4) )
>
> how would this work? It claims to be specialized, but only on a subset of
> the types that the functions are, so what does the default version use? I
> haven't quite been able to grasp the consequences deeply enough to see if
> what you're proposing is a big win, a big loss, or something else in these
> situations. It is these high-degree-of-specialization cases that are the
> most expensive (and most confusing).
The default version in my proposal resembles AnyRef specialization
under the current specialization scheme. So in your case, you'd end up
with with four implementations of ff. Using a simplified naming scheme
(I = Int, D = Double, L = Object/AnyRef) they would be:
def ff_ID(f1:Function2_IID, f2:Function2_DDI, a4:(Int,Int,Int,Int)):Int
def ff_IL[B](f1:Function2_IIL[B], f2:Function2_LLI[B,B], a4:(Int,Int,Int,Int)):Int
def ff_LD[A](f1:Function2_LLD[A,A], f2:Function2_DDL[A], a4:(A,A,A,A)):A
def ff_LL[A,B](f1:Function2_LLL[A,A,B], f2:Function2_LLL[B,B,A], a4:(A,A,A,A)):A
Does this make sense? The big difference between my proposal and the
current scheme is that in my proposal there is always exactly one class
(e.g. Function2_LLD) which has *all* the methods you want, rather than
having a Function2_LLD which inherits a bunch of its methods from
Function2.
I feel like the translation I performed is pretty mechanical and should
be pretty easy to generalize. Let me know if you foresee problems.
Thanks,
-- Erik
Erik Osheim
> +1 for having just one set of fields. This is definitely doable, and on our
> to-do list (Vlad has recently stepped up as the maintainer of
> specialization, and this was one of the first items we discussed).
Awesome! What is your plan exactly? As long as Foo is a concrete class
with fields, and Foo$mcI$sp inherits from it, I don't see an obvious
way around this (although you certainly have spent a lot more time
thinking about it than I have).
> Does your approach depend on the ability to distinguish between primitive
> types and reference types at the point of instantiation? Because if it
> does, I don't see how to make it work in cases where that information is
> unavailable. Say we have
No, my plan basically uses the "generic" version if it is not certain
that the type is primitive. This means that users will need to
"specialize through" the entire call chain to pass this information
along, much like they do now.
So in your example:
> class Foo[@specialized T](x: T) {
> def bar(y: T)
> }
>
> def makeFoo[T](x: T): Foo[T] = {
> new Foo[T] // T could be instantiated to a primitive type, but there is
> no way to tell
> }
>
> makeFoo[Int](10).bar(11)
trait Foo[T](x:T) {
def bar(y:T)
}
class Foo$mcL$sp[T](t:T) extends Foo[T] {
def bar(y:T) = <original generic implementation>
}
class Foo$mcI$sp(t:Int) extends Foo[Int] {
def bar(y:Int) = <specialized implementation>
}
...
The compiler would rewrite all generic use of Foo[T](tt) to be
Foo$mcL$sp[T](tt), except when T is known to be an Int, at which point it
would use Foo$mcI$sp(tt).
This is the big change... that none of the classes inherit
implementation from each other, but only an interface which they share.
You can always use the generic version with a primitive type, you'll
just see boxing in those cases (just like if instantiate a specialized
class from a generic method, you'll always end up using the original,
generic version).
> > But the upsides are great! For one, you don't need to rewrite any of
> > the access controls, annotations, or other modifiers like final. Since
> > we just renamed a class into another class (and performed some
> > transformations on types/names) we can be pretty sure that the
> > semantics of the class intialization, inlining, visibility, etc are
> > what the original author intended. We also don't end up with extra
> > fields that we don't plan to use.
> >
>
> It's hard to see if that's the case, maybe an example which has these
> problems would help.
OK, for example:
class Widget[@spec(Int) A, @spec(Int) B](a:A, b:B) {
private[this] def blend(a:A, i:Int):Double = ...
final def frob(x:A):A = ...
def cobble(y:B, z:B):A = ...
}
Right now there is a whole lot of rewriting that has to happen, sine
Foo's specialized subclasses can't extend "blend" if it's final, and
can't override "frob" (which it needs to do to provide specialized
versions).
The transformation would be:
trait Widget[A, B] {
def frob(x:A):A
def cobble(y:B, z:B):A
}
// notice that this is just a "copy" of the original Widget class
class Widget_LL[A, B](a:A, b:B) extends Widget[A, B] {
private[this] def blend(a:A, i:Int):Double = ...
final def frob(x:A):A = ...
def cobble(y:B, z:B):A = ...
}
class Widget_IL[B](a:Int, b:B) extends Widget[Int, B] {
private[this] def blend(a:Int, i:Int):Double = ...
final def frob(x:Int):Int = ...
def cobble(y:B, z:B):Int = ...
}
class Widget_LI[A, Int](a:A, b:Int) extends Widget[A, Int] {
private[this] def blend(a:A, i:Int):Double = ...
final def frob(x:A):A = ...
def cobble(y:Int, z:Int):A = ...
}
class Widget_II(a:Int, b:Int) {
private[this] def blend(a:Int, i:Int):Double = ...
final def frob(x:Int):Int = ...
def cobble(y:Int, z:Int):Int = ...
}
So... as you can see it's a pretty mechanical translation. I have to do
a bit of work to generate the interface trait correctly (i.e. leave out
the private method "blend", and make sure to remove final from the
"frob" prototype) but I can pretty much just copy the original Widget
class' body into the specialized types and then do some type
substitution for the relevant type parameters.
And it ensures that no one is inheriting anyone else's fields.
I'll translate the above into post-erasure output below.
> Do you always transform a class to a trait? Also, you don't add specialized
> variants (a$mcI$sp, etc)? It would be helpful to see the intended output
> after erasure as well.
interface Widget {
def frob(x:Object):Object
def cobble(y:Object, z:Object):Object
}
class Widget_LL(a:Object, b:Object) extends Widget {
private[this] def blend(a:Object, i:Int):Double = ...
final def frob(x:Object):Object = ...
def cobble(y:Object, z:Object):Object = ...
}
class Widget_IL[Object](a:Int, b:Object) extends Widget {
private[this] def blend(a:Int, i:Int):Double = ...
private[this] def blend(a:Object, i:Int):Double = <unbox "a" then call prev>
final def frob(x:Int):Int = ...
final def frob(x:Object):Int = <unbox x then call prev>
def cobble(y:Object, z:Object):Int = ...
def cobble(y:Object, z:Object):Object = <call prev, then box result>
}
class Widget_LI[Object, Int](a:Object, b:Int) extends Widget {
private[this] def blend(a:Object, i:Int):Double = ...
final def frob(x:Object):Object = ...
def cobble(y:Int, z:Int):Object = ...
def cobble(y:Object, z:Object):Object = <unbox y,z then call prev>
}
class Widget_II(a:Int, b:Int) {
private[this] def blend(a:Int, i:Int):Double = ...
private[this] def blend(a:Object, i:Int):Double = <unbox "a" then call prev>
final def frob(x:Int):Int = ...
final def frob(x:Object):Int = <unbox x then call prev>
def cobble(y:Int, z:Int):Int = ...
def cobble(y:Object, z:Object):Object = <unbox y,z then call prev, then box result>
}
> > class Foo$mcL$sp[A](a:A, b:A) extends Foo[A] {
> >
>
> I was expecting 'A' to be bound by AnyRef, is it intentional?
My plan is to bind A to Any instead of AnyRef, because the "generic
version" should be usable with boxed primitives as well as AnyRef
types.
> It's important to see also the code as a use site. I am afraid that without
> the specialized variants, there will always be boxing. Here's a sketch of
> what happens:
>
> val foo: Foo[Int] // assume I have a specialized instance of Foo
> (Foo$mcI$sp), created somewhere else
>
> foo.bar(10) // I expect no boxing here
In my plan, if you don't know that you have an instance of Foo$mcI$sp
then you will get boxing. This is true in the current plan and will
always be true, won't it? As far as I know the big difference is just
that we won't need to call into other class' (supposedly private)
methods or override their (supposedly final) methods in order to work
properly.
> Now let's forget for a moment about specialization, and think what the
> compiler does when it compiles this code.
>
> - the type of foo is Foo[Int]
> - after erasure, all occurrences of T in Foo are replaced by the upper
> bound, meaning Object
> - foo.bar is adapted by boxing the int in order to call the erased method,
> 'bar'
Yes exactly.
> Vlad may have more ideas about what can be reworked in specialization, and
> I think it's great that there is interest to improve it -- for sure it
> needs another good push to fulfill its potential.
Thanks. And sorry if I'm still misunderstanding... I am just trying to
come to grips with what is happening currently and what could be
better. I may have overstated my case a little bit, but I do think that
moving toward always generating an interface with multiple implementing
classes will make many of these bugs easier.
-- Erik
Erik Osheim
have been thinking about this plan transforms Scala code into other
valid Scala code, so I may have failed to get the exact erasure
mechanics right.
You'll notice that here we only have one version of each method:
On Tue, Feb 21, 2012 at 02:57:14PM -0500, Erik Osheim wrote:
> class Widget_IL[B](a:Int, b:B) extends Widget[Int, B] {
> private[this] def blend(a:Int, i:Int):Double = ...
> final def frob(x:Int):Int = ...
> def cobble(y:B, z:B):Int = ...
> }
That's because in Scala-land I think this is enough to satisfy
Widget[A,B]'s interface (at least, from what I can tell). Of course,
when you do erasure I think you may end up with something like this:
> class Widget_IL[Object](a:Int, b:Object) extends Widget {
> private[this] def blend(a:Int, i:Int):Double = ...
> private[this] def blend(a:Object, i:Int):Double = <unbox "a" then call prev>
>
> final def frob(x:Int):Int = ...
> final def frob(x:Object):Int = <unbox x then call prev>
>
> def cobble(y:Object, z:Object):Int = ...
> def cobble(y:Object, z:Object):Object = <call prev, then box result>
> }
Here I have provided the methods that satisfy the Widget interface as
well as the overloaded specialized versions. I am pretty sure this is
possible even if I am a bit vague on exactly when this happens.
-- Erik
Erik Osheim
> Let's take the most hideous beast in the current Scala library, Function2,
> which is specialized on
> arg1: Int, Long, Double
> arg2: Int, Long, Double
> return: Unit, Boolean, Int, Float, Long, Double
> This has fully 55 different versions in the current scheme (54 specialized
> and 1 generic), and generates around 1.2M of bytecode, of which ~25k is the
> core class itself with ~5k more per variant (of which the majority is from
> curried and tupled).
I guess the implicit thing I forgot to mention is that my plan
basically means that anytime you specialize you *have* to include
AnyRef, since the generic version is essentially the AnyRef
specialization on all parameters.
So I would rely on having additional specializations available beyond
the 54 that you mention.
Hope that clears things up a bit.
-- Erik
iulian dragos
On Tue, Feb 21, 2012 at 08:25:13PM +0100, iulian dragos wrote:Awesome! What is your plan exactly? As long as Foo is a concrete class
> +1 for having just one set of fields. This is definitely doable, and on our
> to-do list (Vlad has recently stepped up as the maintainer of
> specialization, and this was one of the first items we discussed).
with fields, and Foo$mcI$sp inherits from it, I don't see an obvious
way around this (although you certainly have spent a lot more time
thinking about it than I have).
No, my plan basically uses the "generic" version if it is not certain
> Does your approach depend on the ability to distinguish between primitive
> types and reference types at the point of instantiation? Because if it
> does, I don't see how to make it work in cases where that information is
> unavailable. Say we have
that the type is primitive. This means that users will need to
"specialize through" the entire call chain to pass this information
along, much like they do now.
The compiler would rewrite all generic use of Foo[T](tt) to be
Foo$mcL$sp[T](tt), except when T is known to be an Int, at which point it
would use Foo$mcI$sp(tt).
So... as you can see it's a pretty mechanical translation. I have to do
a bit of work to generate the interface trait correctly (i.e. leave out
the private method "blend", and make sure to remove final from the
"frob" prototype) but I can pretty much just copy the original Widget
class' body into the specialized types and then do some type
substitution for the relevant type parameters.
And it ensures that no one is inheriting anyone else's fields.
I'll translate the above into post-erasure output below.
interface Widget {
> Do you always transform a class to a trait? Also, you don't add specialized
> variants (a$mcI$sp, etc)? It would be helpful to see the intended output
> after erasure as well.
def frob(x:Object):Object
def cobble(y:Object, z:Object):Object
}
> It's important to see also the code as a use site. I am afraid that withoutIn my plan, if you don't know that you have an instance of Foo$mcI$sp
> the specialized variants, there will always be boxing. Here's a sketch of
> what happens:
>
> val foo: Foo[Int] // assume I have a specialized instance of Foo
> (Foo$mcI$sp), created somewhere else
>
> foo.bar(10) // I expect no boxing here
then you will get boxing. This is true in the current plan and will
always be true, won't it?
As far as I know the big difference is just
that we won't need to call into other class' (supposedly private)
methods or override their (supposedly final) methods in order to work
properly.
Thanks. And sorry if I'm still misunderstanding... I am just trying to
come to grips with what is happening currently and what could be
better.
Erik Osheim
> The class fields can be abstract (meaning only getters/setters in the base
> class), and the concrete subclasses will implement them, very similar to
> your proposal.
OK, so this means that AnyRef specialization would always be on then,
and the base class would be abstract? This goes a long way toward what
I'm hoping for.
> > The compiler would rewrite all generic use of Foo[T](tt) to be
> > Foo$mcL$sp[T](tt), except when T is known to be an Int, at which point it
> > would use Foo$mcI$sp(tt).
> >
>
> ..but when does it have this knowledge? Basically, only at the point of
> instantiation (because any instance of Foo[Int] has to be assumed to be a
> generic one). If Foo was instantiated "somewhere else", you don't have this
> knowledge.
Ah, I see what you're saying now. If all uses of specialized methods
were themselves automatically specialized then you could relax this
requirement (which would be a very big change), but otherwise you're
right, someone could pass a Foo_L[Int] to your method expecting Foo_I
and then bam!
If we *could* specialize uses of Foo[Int] into Foo_L[Int] and Foo_I
then this problem goes away, but that means specialization details are
leaking out into callers, which is certainly outside of the current
spec or the one I proposed.
> Unfortunately, you can't transform it always to a trait, since classes may
> have constructor parameters. For instance, Tuples are an important use case.
I thought that you could make any exposed parameters abstract and
simply copy the constructor to the actual concrete classes. Maybe
there's a reason this doesn't work?
> The difference is that currently you can disconnect the knowledge at the
> call site and the knowledge at the instantiation site. The thing that
> allows this is specialized variants: at the call-site, if I know I'm
> dealing with a Foo[Int], I rewrite the call towards bar_I. Depending on the
> actual instance of Foo, it may go through without boxing, or it will be
> boxed and passed to the generic one (this is performed by the specialized
> variant bar_I: the default implementation boxes, the specialized one 'just
> works').
>
> In your proposal there is only one method, bar(Object) in the interface. At
> the call-site, even if I know I am dealing with a Foo[Int], I need to know
> *also* the runtime value of Foo, to downcast it to Foo$mcI$sp, and call
> bar(Int) (remember, there is no bar(Int) in the interface). So currently, I
> don't see any case in which boxing is actually eliminated!
>
> The big gains in your proposal would come from getting rid of specialized
> variants: they take additional space, and they need to be kept in sync
> (overriding one of them needs the compiler to override the others as well
> -- place for subtle bugs). But I don't yet see how that can be achieved.
Yeah, I clearly need to think about this.
It's really too bad, because in cases where you call specialized code
from unspecialized code you mostly lose the benefits anyway (even
though accessors can in theory avoid boxing, you're using a call path
which wants everything to be an Object, so you usually end up boxing
anyway).
I think that is why I have been thinking about this wrong, because the
"right" way to use specialization is to call directly into a
specialized generic class/method with a concrete type. But of course
without letting specialization details leak into a caller (or some
other kind of "auto-specialization") you can't really support this.
Thanks for talking me through this.
> > As far as I know the big difference is just
> > that we won't need to call into other class' (supposedly private)
> > methods or override their (supposedly final) methods in order to work
> > properly.
> >
>
> I see that as orthogonal to the variants, so we could keep specialized
> variants but move downwards private members and fields. But 'final' methods
> stil need to be overridden if they need specialization (and are public).
Right. I guess if you are prepared to make the "parent class" abstract
(in terms of its fields, final methods and things like that) and then
let the subclasses actually implement that stuff, it goes a long way
toward what I'm hoping for.
One other benefit which you didn't mention is that my proposal means
that you get to specialize *all* the methods, rather than just those
which mention the specialized type parameter (e.g. A). This ends up
being really important when dealing with inner classes/methods, and
other places where it's not natural to mention the type parameter again
(e.g. Quantity[A]#toInt or something).
Thanks,
-- Erik
iulian dragos
> Unfortunately, you can't transform it always to a trait, since classes may> have constructor parameters. For instance, Tuples are an important use case.I thought that you could make any exposed parameters abstract and
simply copy the constructor to the actual concrete classes. Maybe
there's a reason this doesn't work?
Vlad Ureche
On Wed, Feb 22, 2012 at 2:43 PM, Erik Osheim <er...@plastic-idolatry.com> wrote:> Unfortunately, you can't transform it always to a trait, since classes may> have constructor parameters. For instance, Tuples are an important use case.I thought that you could make any exposed parameters abstract and
simply copy the constructor to the actual concrete classes. Maybe
there's a reason this doesn't work?
class Foo[@spec(Int) T] (t: T) { ... }
would be transformed into
trait Foo[T] { ... }
class Foo_I(t: Int) extends Foo[Int] { ... }
class Foo_L(t: AnyRef) extends Foo[AnyRef] { ... } // generic variant
and an instantiation would be transformed from:
val foo: Foo[Int] = new Foo(3)
into:
val foo: Foo[Int] = new Foo_I(3)
Is this the case? Luckily the typer will see class Foo by the time it types the code and after the specialization phase, the instantiations will be correct. We probably have to be careful about retyping things from the specialization phase, as that might find the program in a not-completely transformed/correct state.
One more thing, should we start writing a SIP so we clarify things on our minds? What do you think Erik?
Vlad
Vlad Ureche
The default version in my proposal resembles AnyRef specialization
under the current specialization scheme. So in your case, you'd end up
with with four implementations of ff. Using a simplified naming scheme
(I = Int, D = Double, L = Object/AnyRef) they would be:
def ff_ID(f1:Function2_IID, f2:Function2_DDI, a4:(Int,Int,Int,Int)):Int
def ff_IL[B](f1:Function2_IIL[B], f2:Function2_LLI[B,B], a4:(Int,Int,Int,Int)):Int
def ff_LD[A](f1:Function2_LLD[A,A], f2:Function2_DDL[A], a4:(A,A,A,A)):A
def ff_LL[A,B](f1:Function2_LLL[A,A,B], f2:Function2_LLL[B,B,A], a4:(A,A,A,A)):A
def ff[@specialized(Int, AnyRef) A, @specialized(Long, AnyRef) B]
while for the (Int, Long) specialization this should only be:
def ff_ID ...
def ff_LL ... // the fully generic version, added by the specializer automatically as AnyRef for all members
This would allow programmers to have more control over the specializations that get generated, instead of getting AnyRef added by default to their patterns.
Does it sound reasonable?
Vlad
Erik Osheim
> I think the above versions should be generated for
> def ff[@specialized(Int, AnyRef) A, @specialized(Long, AnyRef) B]
>
> while for the (Int, Long) specialization this should only be:
> def ff_ID ...
> def ff_LL ... // the fully generic version, added by the specializer
> automatically as AnyRef for all members
>
> This would allow programmers to have more control over the specializations
> that get generated, instead of getting AnyRef added by default to their
> patterns.
> Does it sound reasonable?
Sure, I think that would be fine.
-- Erik
Erik Osheim
> If I understand correctly, that would mean the following:
> class Foo[@spec(Int) T] (t: T) { ... }
> would be transformed into
> trait Foo[T] { ... }
> class Foo_I(t: Int) extends Foo[Int] { ... }
> class Foo_L(t: AnyRef) extends Foo[AnyRef] { ... } // generic variant
>
> and an instantiation would be transformed from:
> val foo: Foo[Int] = new Foo(3)
> into:
> val foo: Foo[Int] = new Foo_I(3)
>
> Is this the case? Luckily the typer will see class Foo by the time it types
> the code and after the specialization phase, the instantiations will be
> correct. We probably have to be careful about retyping things from the
> specialization phase, as that might find the program in a not-completely
> transformed/correct state.
Yes, that's how I was imagining it also.
> One more thing, should we start writing a SIP so we clarify things on our
> minds? What do you think Erik?
Yeah, if this is something that other people besides me are excited
about then I'd be interested in trying to write a SIP to be a bit more
explicit about how it would work. I am not a fantastic writer but I
could probably provide a first draft.
I probably will not be able to really focus on writing a SIP until
April, although in the meantime I'm happy to talk about it informally,
or help edit someone else's draft.
-- Erik
Vlad Ureche
Yeah, if this is something that other people besides me are excited
about then I'd be interested in trying to write a SIP to be a bit more
explicit about how it would work. I am not a fantastic writer but I
could probably provide a first draft.
Cheers,
Vlad