race condition in structural type polycache

Hi Paul,

There is incorrect use of soft references in synthetic method:

=============================================
public static Method reflMethod$Method1(Class class1) {
    if((MethodCache)reflPoly$Cache1.get() == null)
        reflPoly$Cache1 = new SoftReference(new EmptyMethodCache());
    Method method1 = ((MethodCache)reflPoly$Cache1.get()).find(class1);
    if(method1 == null) {
        method1 = ScalaRunTime$.MODULE$.ensureAccessible(class1.getMethod("clear", reflParams$Cache1));
        reflPoly$Cache1 = new SoftReference(((MethodCache)reflPoly$Cache1.get()).add(class1, method1));
    }
    return method1;
}
=============================================

Between any of the three calls to reflPoly$Cache1.get() soft reference can be cleared by GC.

The correct code so should be:

=============================================
public static Method reflMethod$Method1(Class class1) {
    MethodCache cache = (MethodCache)reflPoly$Cache1.get();
    if(cache == null) {
        cache = new EmptyMethodCache();
    }
    Method method1 = cache.find(class1);
    if(method1 == null) {
        method1 = ScalaRunTime$.MODULE$.ensureAccessible(class1.getMethod("clear", reflParams$Cache1));
        reflPoly$Cache1 = new SoftReference(cache.add(class1, method1));
    }
    return method1;
}
=============================================

BTW, can I ask a silly question:
What are the reasons structural types are implemented is such a performance-ineffective way (using Java reflection, caches and soft references)?
It may provoke annoying surprises in performance-sensitive code, and I fear that people might beware of using structural types at all.

On Mon, Dec 5, 2011 at 5:15 AM, Pavel Pavlov wrote:
> BTW, can I ask a silly question:
> What are the reasons structural types are implemented is such a
> performance-ineffective way (using Java reflection, caches and soft
> references)?

Reflection is unavoidable in the general case. I mean, how else do
you propose to implement this:

def f(x: { def bippy(): Int }) = x.bippy()

You can call that method with anything with a bippy(), even classes
that didn't exist when the method was compiled. It is true there are
specific cases where reflection could be avoided, but isn't, which
falls under the broad rubric of possible future optimizations.

The method cache of course is for performance.

Soft references are in there because the cache was killing sbt permgen
by making whole classloaders uncollectable.

https://issues.scala-lang.org/browse/SI-2365

> It may provoke annoying surprises in performance-sensitive code, and I fear
> that people might beware of using structural types at all.

You're supposed to be wary of using structural types at all. They
should be the last resort.

> Reflection is unavoidable in the general case. I mean, how else do
> you propose to implement this:
>
> def f(x: { def bippy(): Int }) = x.bippy()

Eventually, interface injection. Until then, what about caller-side
wrappers, e.g.:

interface Type1 {
def bippy(): Int
}

val a = somethingBipLike()
f(new Type1() {
def bippy() = a.bippy();
);

Granted, this breaks object identity, but so do implict wrappers.

Perhaps this is a terribly naive approach, but I've been curious
why Scala didn't use a caller-side approach to structural types,
and since the topic came up thought I'd ask.

- Stephen

On Mon, Dec 5, 2011 at 11:46 AM, Stephen Haberman
wrote:
> Granted, this breaks object identity, but so do implict wrappers.
>
> Perhaps this is a terribly naive approach, but I've been curious
> why Scala didn't use a caller-side approach to structural types,
> and since the topic came up thought I'd ask.

http://www.mendeley.com/download/public/3088371/3853183682/eba925073c26c...

"Compiling Structural Types on the JVM - A Comparison of Reflective
and Generative Techniques from Scala’s Perspective"

Thanks for the link.

> Generative techniques create Java interfaces to stand in for structural types on the JVM.
> The complexity of such techniques lies in that all classes that are to be used as structural
> types anywhere in the program must implement the right interfaces. When this is done
> at compile time, it prevents separate compilation. When that is done at runtime,
> it requires to adapt dynamically objects to interfaces, which is expensive and complex.

> Gil and Maman's Whiteoak [1] is an extension to Java with structural types that are compiled
> using a generative technique. Whiteoak does not modify classes to implement interfaces
> at compile time; instead, it uses ASM, a bytecode generation framework,
> to create wrapper classes at runtime.

They (in Whiteoak) create wrapper classes at runtime!
And besides they have all the fuss with caching.
No wonder that they have such results:
> However, a start-up cost of about 200s is incurred before the first structural call is executed.
> They also report that the worst case scenario is about 7 times slower than the best case.
Not to mention the fact that their approach is really hard to implement correctly.

I believe that Stephen's approach (which I also had in mind) is to let the compiler generate all the wrapper classes.
Problems with object identity etc. can be relatively easy solved.
Moreover, this approach can futher be improved to avoid creation of extra (wrapper) objects.

On Mon, Dec 5, 2011 at 2:22 PM, Pavel Pavlov wrote:
> I believe that Stephen's approach (which I also had in mind) is to let the
> compiler generate all the wrapper classes.

I assume separate compilation becomes your new problem here, although
offhand I don't know in what way.

> Problems with object identity etc. can be relatively easy solved.

You might have to elaborate on that one. How? The more call site
rewriting you do the deeper into sketchville you go. There's a large
minefield amidst separate compilation which is hard to appreciate
until you try to implement something like this. Your wrappers will
have to be polymorphic, they'll have to compose...

scala> type Foo = { def bippy(): Int }
defined type alias Foo

scala> type Bar = { def dingus(): Int }
defined type alias Bar

scala> def f(x: Foo with Bar) = x.bippy() + x.dingus()
f: (x: Foo with Bar)Int

Not saying it couldn't be done, but you can't punt on object identity
and you have to hang onto separate compilation.

> Moreover, this approach can futher be improved to avoid creation of extra
> (wrapper) objects.

By inlining direct method calls at individual call sites? (This sounds
good regardless.) By "specializing" a method on the classes known to
be used as a given structural type? Don't be coy, you've had all kinds
of good (or at least plausibly good) ideas, don't deprive me of
details.

>> Moreover, this approach can futher be improved to avoid creation of extra
>> (wrapper) objects.
>
> By inlining direct method calls at individual call sites? (This sounds
> good regardless.) By "specializing" a method on the classes known to
> be used as a given structural type? Don't be coy, you've had all kinds
> of good (or at least plausibly good) ideas, don't deprive me of
> details.

This got me to thinking of a possible desugaring of structural types to context bounds.

type ST = { def bippy(): Int }

also creates

trait ST$impl[T] { def bippy($this: T): Int }

and

def f(x: ST) = x.bippy()

turns into

def f[T: ST$impl](x: T) = implicitly[ST$impl[T]].bippy(x)

and given

class Whee { def bippy(): Int = 42 }

then

println(f(new Whee))

does something like

implicit object ST$impl$Whee extends ST$impl[Whee] {
def bippy($this: Whee): Int = $this.bippy()
}
println(f(new Whee))

with some sort of hash consing on the xxx$impl traits and the xxx$impl$yyy objects of course to keep the number of classes down.

On Mon, Dec 5, 2011 at 9:39 PM, Geoff Reedy wrote:
> This got me to thinking of a possible desugaring of structural types to context bounds.

You know what else you'd scoop up in that net...

"Parameter type in structural refinement may not refer to an abstract
type defined outside that refinement"

scala> class C[T] { type ST = { def bippy(x: T): Int } }
:7: error: Parameter type in structural refinement may not
refer to an abstract type defined outside that refinement
class C[T] { type ST = { def bippy(x: T): Int } }
^

But if the compiler made us a structural type manifest (and structural
type manifests are what we're really talking about I think: it's the
same issue as with array manifests, that you want to be able to write
generically in scala even though the jvm demands you be specific in
bytecode, so you say hey scalac, why don't you just whip me up one of
them every time I get all structural) then you encode everything in
the manifest and the limitations fall away. I think.

On Mon, Dec 05, 2011 at 11:44:03PM -0800, Paul Phillips said
> But if the compiler made us a structural type manifest (and structural
> type manifests are what we're really talking about I think: it's the
> same issue as with array manifests, that you want to be able to write
> generically in scala even though the jvm demands you be specific in
> bytecode, so you say hey scalac, why don't you just whip me up one of
> them every time I get all structural) then you encode everything in
> the manifest and the limitations fall away. I think.

It looks like it:

class C[T] {
// was type ST = { def bippy(x: T): Int }
trait ST$impl[Z] { def bippy($this: Z, x: T): Int }
// was def f(s: ST, q: T) = s.bippy(q)
def f[S: ST$impl](s: S, q: T) = implicitly[ST$impl[S]].bippy(s, q)
}

class Foo {
def bippy(q: Int): Int = 2*q
}

class Bar {
def bippy(q: Double): Int = q.toInt
}

object Test {
def main(args: Array[String]) {
val ci = new C[Int]
val foo = new Foo
implicit object ci$ST$impl$Foo extends ci.ST$impl[Foo] {
def bippy($this: Foo, x: Int): Int = $this.bippy(x)
}
println(ci.f(foo, 3))
val cd = new C[Double]
val bar = new Bar
implicit object cd$ST$impl$Bar extends cd.ST$impl[Bar] {
def bippy($this: Bar, x: Double): Int = $this.bippy(x)
}
println(cd.f(bar, math.Pi))
}
}

The crucial difference from array manifests is we have to make new
classes, potentially one for each call site. We're already quite
prolific in the classes we create, how much more can we afford? Also,
it'd be interesting to benchmark this approach versus reflection see how
much it helps.

Another possibility is that with this strategy to avoid class bloat when
performance is not critical there can still be a fall back reflective
implementation for the xxx$impl.

On Wed, Dec 7, 2011 at 9:20 AM, Geoff Reedy wrote:
> The crucial difference from array manifests is we have to make new
> classes, potentially one for each call site.

Only one per class which poses as the structural type, right? I mean
that's technically potentially one per call site as long as you use a
different class every time you call it, but the realistic ceiling on
distinct classes with a bippy(Int)Int method is pretty low.

Compare with by-name arguments, where you get an additional class at
every call site, full stop. getOrElse alone created something like
400 classes in the compiler (which I only know because I pursued and
realized their elimination via inlining under -optimise.)

You'd still have to use structural types judiciously, but that goes
without saying. I don't think the new classes would make that
situation measurably worse.

> We're already quite
> prolific in the classes we create, how much more can we afford? Also,
> it'd be interesting to benchmark this approach versus reflection see how
> much it helps.

Yeah, I'm often (or always) surprised by what I find when I actually
measure things. But the primary benefit here to my eye isn't the
obvious performance gain of the method invocations. It's doing less
via reflection, which makes everything else work better (think of
things like proguard losing the ability to eliminate things,
environments where reflection is restricted or prohibited, bugs in
java reflection or our utilization of it which manifest at runtime
which we could bypass entirely, ...)

Hi Paul,

I'm agree on all your points here.
(I'm still writing my message about structural types implementation & optimization, just haven't enough spare time to finish it)

Regards,
Pavel.

четверг, 8 декабря 2011 г. 0:31:27 UTC+7 пользователь Paul Phillips написал:

On Wed, Dec 7, 2011 at 9:20 AM, Geoff Reedy <ge [dot] [dot] [dot] [at] programmer-monk [dot] net> wrote:
> The crucial difference from array manifests is we have to make new
> classes, potentially one for each call site.

Only one per class which poses as the structural type, right? I mean
that's technically potentially one per call site as long as you use a
different class every time you call it, but the realistic ceiling on
distinct classes with a bippy(Int)Int method is pretty low.

Compare with by-name arguments, where you get an additional class at
every call site, full stop.  getOrElse alone created something like
400 classes in the compiler (which I only know because I pursued and
realized their elimination via inlining under -optimise.)

You'd still have to use structural types judiciously, but that goes
without saying.  I don't think the new classes would make that
situation measurably worse.

> We're already quite
> prolific in the classes we create, how much more can we afford? Also,
> it'd be interesting to benchmark this approach versus reflection see how
> much it helps.

Yeah, I'm often (or always) surprised by what I find when I actually
measure things.  But the primary benefit here to my eye isn't the
obvious performance gain of the method invocations.  It's doing less
via reflection, which makes everything else work better (think of
things like proguard losing the ability to eliminate things,
environments where reflection is restricted or prohibited, bugs in
java reflection or our utilization of it which manifest at runtime
which we could bypass entirely, ...)

On Dec 7, 2011, at 10:31 AM, Paul Phillips wrote:
> Yeah, I'm often (or always) surprised by what I find when I actually
> measure things.

FWIW I cooked up this benchmark for caliper:

import com.google.caliper.SimpleBenchmark

class Whee { def bippy(): Int = 42 }

class Benchmark extends SimpleBenchmark {

type ST = { def bippy(): Int }
def plainf(x: ST) = x.bippy()

trait ST$impl[T] { def bippy($this: T): Int }
implicit object ST$impl$Whee extends ST$impl[Whee] {
def bippy($this: Whee) = $this.bippy()
}
def contextf[T: ST$impl](x: T) = implicitly[ST$impl[T]].bippy(x)

val w = new Whee

def timePlain(reps: Int) = {
var i = reps;
var r = 0;
while (i > 0) {
r += plainf(w)
i = i-1
}
r
}

def timeContext(reps: Int) = {
var i = reps;
var r = 0;
while (i > 0) {
r += contextf(w)
i = i-1
}
r
}
}

and get

0% Scenario{vm=java, trial=0, benchmark=Plain, memoryInit=-Xms1024M, memoryMax=-Xmx1024M} 18.46 ns; ?=0.15 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=Context, memoryInit=-Xms1024M, memoryMax=-Xmx1024M} 2.15 ns; ?=0.00 ns @ 3 trials

benchmark ns linear runtime
Plain 18.46 ==============================
Context 2.15 ===

quite a difference, though I'm no expert in benchmark design so I may not have done it right.

> But the primary benefit here to my eye isn't the
> obvious performance gain of the method invocations. It's doing less
> via reflection, which makes everything else work better (think of
> things like proguard losing the ability to eliminate things,
> environments where reflection is restricted or prohibited, bugs in
> java reflection or our utilization of it which manifest at runtime
> which we could bypass entirely, ...)

Yeah, I definitely see this point. That would be a fair chunk of implementation complexity that could be dispensed with.

looks promising!
with manifests becoming wrappers for the full scala.reflect types (i'll be working on that soon), this should become easier to implement
Geoff, do you feel like taking a stab at prototyping/SIP'ing this? I'll be happy to provide pointers/support!
cheersadriaan

On Thu, Dec 8, 2011 at 5:51 AM, Geoff Reedy <geoff [at] programmer-monk [dot] net> wrote:

On Dec 7, 2011, at 10:31 AM, Paul Phillips wrote:
> Yeah, I'm often (or always) surprised by what I find when I actually
> measure things.

FWIW I cooked up this benchmark for caliper:

import com.google.caliper.SimpleBenchmark

class Whee { def bippy(): Int = 42 }

class Benchmark extends SimpleBenchmark {

 type ST = { def bippy(): Int }
 def plainf(x: ST) = x.bippy()

 trait ST$impl[T] { def bippy($this: T): Int }
 implicit object ST$impl$Whee extends ST$impl[Whee] {
   def bippy($this: Whee) = $this.bippy()
 }
 def contextf[T: ST$impl](x: T) = implicitly[ST$impl[T]].bippy(x)

 val w = new Whee

 def timePlain(reps: Int) = {
   var i = reps;
   var r = 0;
   while (i > 0) {
     r += plainf(w)
     i = i-1
   }
   r
 }

 def timeContext(reps: Int) = {
   var i = reps;
   var r = 0;
   while (i > 0) {
     r += contextf(w)
     i = i-1
   }
   r
 }
}

and get

 0% Scenario{vm=java, trial=0, benchmark=Plain, memoryInit=-Xms1024M, memoryMax=-Xmx1024M} 18.46 ns; ?=0.15 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=Context, memoryInit=-Xms1024M, memoryMax=-Xmx1024M} 2.15 ns; ?=0.00 ns @ 3 trials

benchmark    ns linear runtime
   Plain 18.46 ==============================
 Context  2.15 ===

quite a difference, though I'm no expert in benchmark design so I may not have done it right.

> But the primary benefit here to my eye isn't the
> obvious performance gain of the method invocations.  It's doing less
> via reflection, which makes everything else work better (think of
> things like proguard losing the ability to eliminate things,
> environments where reflection is restricted or prohibited, bugs in
> java reflection or our utilization of it which manifest at runtime
> which we could bypass entirely, ...)

Yeah, I definitely see this point. That would be a fair chunk of implementation complexity that could be dispensed with.

Hi Paul,


вторник, 6 декабря 2011 г. 6:19:17 UTC+7 пользователь Paul Phillips написал:

On Mon, Dec 5, 2011 at 2:22 PM, Pavel Pavlov <pavel [dot] e [dot] [dot] [dot] [at] gmail [dot] com> wrote:

> Problems with object identity etc. can be relatively easy solved.

You might have to elaborate on that one.  How?

> Moreover, this approach can futher be improved to avoid creation of extra

> (wrapper) objects.

By inlining direct method calls at individual call sites? (This sounds
good regardless.) By "specializing" a method on the classes known to
be used as a given structural type? Don't be coy, you've had all kinds
of good (or at least plausibly good) ideas, don't deprive me of
details.

Ok, let's start from beginning.

The "generative approach" (as presented in that paper), in both its variants (compile-time rewriting of all affected classes or runtime generation of classes) looks like total madness for me. Y'know why.
Reflective approach is really the last resort. It helps when nobody else can help.

The only way to get an acceptable performance on JVM is to mimic its basic constructs, which are: classes/interfaces and invokevirtual/invokeinterface calls.

I can see only two options here:
1) Use wrapper objects (a-la rich wrappers, Stephen's approach).
2) Use method dictionaries (a-la typeclasses, Geoff's approach).

Both approaches have their weak and strong points, but first one can be implemented on top of second one. So I will talk about typeclass approach first.

Your example "def f(x: { def bippy(): Int }) = x.bippy()" isn't anything difficult, as compiler is able to apply any of these two approaches there as it knows the actual type of the object and can generate all the necessary synthetic classes (Geoff and Stephen already wrote how it can be done).
The worst operation is cast to structural type, explicit or implicit (for erased generics), as compiler cannot say anything about actual object's type so there we'll need to use reflective approach anyway (but some optimizations are still possible).

I won't consider explicit downcasts here as now in Scala they do not work anyway (is it a bug or not?):
========================================
scala>   type Clearable = { def clear(): Unit }
defined type alias Clearable

scala> def cast1(x: AnyRef): Clearable = x.asInstanceOf[Clearable]
cast1: (x: AnyRef)Clearable

scala> def cast2(x: AnyRef): Clearable = x match { case x: Clearable => x }
warning: there were 1 unchecked warnings; re-run with -unchecked for details
cast2: (x: AnyRef)Clearable

scala> val x = new Object
x: java.lang.Object = java.lang.Object@dad4b8

scala> cast1(x).clear()
java.lang.NoSuchMethodException: java.lang.Object.clear()
        at java.lang.Class.getMethod(Class.java:1605)
        at .reflMethod$Method1(<console>:11)
        at .<init>(<console>:11)
        at .<clinit>(<console>:11)
        at .<init>(<console>:11)
        at .<clinit>(<console>)
        at $print(<console>)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:704)
        at scala.tools.nsc.interpreter.IMain$Request$$anonfun$14.apply(IMain.scala:920)
        at scala.tools.nsc.interpreter.Line$$anonfun$1.apply$mcV$sp(Line.scala:43)
        at scala.tools.nsc.io.package$$anon$2.run(package.scala:25)
        at java.lang.Thread.run(Thread.java:619)


scala> cast2(x).clear()
java.lang.NoSuchMethodException: java.lang.Object.clear()
        at java.lang.Class.getMethod(Class.java:1605)
        at .reflMethod$Method1(<console>:11)
        at .<init>(<console>:11)
        at .<clinit>(<console>:11)
        at .<init>(<console>:11)
        at .<clinit>(<console>)
        at $print(<console>)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:704)
        at scala.tools.nsc.interpreter.IMain$Request$$anonfun$14.apply(IMain.scala:920)
        at scala.tools.nsc.interpreter.Line$$anonfun$1.apply$mcV$sp(Line.scala:43)
        at scala.tools.nsc.io.package$$anon$2.run(package.scala:25)
        at java.lang.Thread.run(Thread.java:619)


scala>
========================================

Typeclass approach does not create wrapper objects for each structural value. So it does not alter object's identity and does not create additional performance costs at JVM level. However this is also the main drawback of this approach.
As we do not attach the 'structural typeclass' to the object reference (which type is erased to Object at JVM level), we need to carry the pair (objectRef, typeclass) at runtime everywhere where the structural type is used.
So we have to rewrite signatures of all methods which receive structural type arguments (adding Geoff's context bounds), which is not always possible or desirable.
Worse yet, we have something to do with method's return values and variables.
For example:
========================================
type ST = { def bippy(x: Int): Int }
class Foo { def bippy(q: Int): Int = 2*q }
def id[T](x: T): T = x

def test(x: ST) { println(x.bippy) } // ok, translates in Geoff's way
test(new Foo) //ok

val xs: Array[ST] = Array(new Foo)
test(xs(0)) // where's my context bound???
test(id(new Foo)) // where's my context bound???
========================================

Object wrapper approach handles such situations without problems.

As object wrappers can be built on top of typeclasses (they can be just (objectRef, typeClass) tuples), I believe the best implementation strategy is to use both approaches together.
So the last example will be translated into:
========================================
abstract class ST$tclass[T] { def bippy($this: T, x: Int): Int }
object Foo$ST$tclass extends ST$tclass[Foo] { def bippy($this: Foo, x: Int) = $this.bippy(x) }
type Wrapped[T] = (T, ST$class[T])
def wrap[T](ref: T, tclass: ST$class[T]) = (ref, tclass)

def test(x: ST, tclass: ST$class[T]) { println(tclass.bippy(x)) }
test(new Foo, Foo$ST$tclass)

val xs: Array[Wrapped[ST]] = Array(wrap(new Foo, Foo$ST$tclass))
{ val (r, tc) = xs(0); test(r, tc) }
{ val (r, tc) = id(wrap(new Foo, Foo$ST$tclass)); test(r, tc) }
========================================

To preserve the object identity we must aviod wrapping when assigning values of structural types to the variables of non-structural types:
  val x: AnyRef = xs(0); xs(0).toString
must be translated to:
  val x: AnyRef = xs(0)._1; xs(0)._1.toString

Harder case occurs when we use covariant generics:
  val foo = new Foo
  val z: List[ST] = List(foo) // ok, let's store wrapped STs in the list
  val zz: List[AnyRef] = z
  assert(z.head == zz.head) //oops!
So we should not to wrap foo there. Ok, we don't wrap. Now let's try to use the list:
  test(z.head) // where's my tclass???

Thus even in the absence of explicit casts to/matches of structural types, there are still situations for which compiler does not know statically which typeclass/context bound to choose.

It can be fixed for now by adding cache to Foo$tclass:
========================================
abstract class ST$tclass[T] {
  def bippy($this: T, x: Int): Int
  static def getCached[U](ref: U): ST$class[U] = ...
  static def addToCache[U](jvmClass: java.lang.Class[U], tclass: ST$tclass[U]) { ... }
}
object Foo$ST$tclass extends ST$tclass[Foo] {
  def bippy($this: Foo, x: Int) = $this.bippy(x)
  static {
    ST$tclass.addToCache(classOf[Foo], this)
  }
}
========================================

Another tough situation is upcast from one structural type to another. It cannot be fixed with such a cache. However, it still can be implemented without failing to Java reflection.

четверг, 8 декабря 2011 г. 22:35:58 UTC+7 пользователь Pavel Pavlov написал:

Typeclass approach does not create wrapper objects for each structural value. So it does not alter object's identity and does not create additional performance costs at JVM level.
...
As object wrappers can be built on top of typeclasses (they can be just (objectRef, typeClass) tuples), I believe the best implementation strategy is to use both approaches together.

We can use the same ideas to optimize a way more performance-critical use case - implicit/rich wrappers.

To do this, let's introduce inline classes (I use SIP-13 here as well):
  @inline implicit final class RichInt(val self: Int) {
    def min(that: Int): Int = if (self < that) self else that
  }

Then let's add some translation rules:
1) All methods of @inline class are @inline by default
2) Compiler generates static "typeclass-like" impl. methods, adding inlined class state to their signatures:
  final class RichInt(val self: Int) {
    @inline static def $min($self: Int, that: Int): Int = if ($self < that) $self else that
    @inline def min(that: Int): Int = $min(self, that)
  }

3) Compiler eliminates instance creations of @inline classes where possible:
  val x = 1 min 2
translates to:
  val x = (new RichInt(1)).min(2)
then to:
  val x = RichInt.$min(1, 2)

This way we can reduce the cost of rich wrappers and pimp-my-library pattern to virtually zero.

To bypass instance creation we need to pass all the class state to static impl. methods.
For RichInt as for the most of rich wrappers it's single value.

Going further we can generalize this scheme to classes which state consist of several values/fields:

  @inline class Range(val start: Int, val end: Int, val step: Int) {
    final def foreach[U](f: Int => U) {
      if (length > 0) {
        val last = this.last
        var i = start
        while (i != last) { f(i); i += step }
        f(i)
      }
    }
    final def last: Int = ...
  }

translates to:

  class Range(val start: Int, val end: Int, val step: Int) {
    @inline static def $foreach[U]($start: Int, $end: Int, $step: Int, f: Int => U) {
      if (length > 0) {
        val last = $last($start, $end, $step)
        var i = $start
        while (i != last) { f(i); i += $step }
        f(i)
      }
    }
    @inline static def $last($start: Int, $end: Int, $step: Int): Int = ...
    @inline final def foreach[U](f: Int => U) { $foreach(start, end, step, f) }
    @inline final def last: Int = $last(start, end, step)
  }


Using these techniques the code like "for(i <- 0 until N) { x(i) = y(i) }" can be translated to its while-loop equivalent, with all the ancillary objects completely removed.

Any thoughts? Comments?

On Thu, Dec 08, 2011 at 07:56:58PM -0800, Pavel Pavlov wrote:
> Using these techniques the code like "for(i <- 0 until N) { x(i) = y(i) }"
> can be translated to its while-loop equivalent, with all the ancillary
> objects completely removed.
>
> Any thoughts? Comments?

I'm neutral on exactly how the syntax should look, but a lot of us are
excited about the possibility of getting the Scala compiler to do the
translation you're talking about:

new NumericOps[Int](x)(ev).+(y) -> ev.plus(x, y)

Josh Suereth had a proposal to do this for awhile. I am hoping
something like this makes it into Scala. Failing that, I would even be
OK with some kind of annotation + compiler plugin that did the
optimization.

You can check out my OptimizedNumeric plugin [1] to see one example of
doing this. I'm (slowly) working on a generalized version that would
use annotations to determine which implicit wrappers to optimize out.
While it would be nice to have this in the language, I think this would
still be really useful (especially if the plugin shipped with Scala, a
la the continuations plugin).

If any of you all are interested in collaborating on such a plugin
please get in touch (@d6 on twitter, d_m on IRC, or by email).