AutoSpecialization in Dotty
Dmitry Petrashko
About me:
- https://github.com/darkdimius/
- PhD in EPFL
- previously worked on ScalaBlitz
- Now working on Dotty & Linker.
- supervising:
- Guillaume Martres: value classes and arrays of value classes
- Alex Sikiaridis: specialization
- Allan Renucci: idempotent method optimization, auto-collections
The language’s scalability is the result of a careful integration of object-oriented and functional language concepts.
But nothing comes for free.
Example: Boxing
class WrappedArray[A] extends IndexedSeq
class IndexedSeq[A] {
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)13x slowdown due to boxing
But doesn't @specialize solve this problem?
Problems with specialization: subtyping
class WrappedArray[@specialized A] extends IndexedSeq
class IndexedSeq[@specialized A] {
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[@specialized B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[@specialized B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)Problems with specialization: partial specialization
def sumLogged[@specialized B >: A, C <: Logger[A]]
(implicit num: Numeric[B], log: C)But doesn't miniboxing solve those problems?
Problems with specialization and miniboxing
trait Function3[-T1, -T2, -T3 +R]
How many specializations are needed?
Specialization: 10000 classes
Miniboxing: 81 classes
Are they actually needed?
in your program?
Most likely no!
What is we could generate only specializations that your program needs?
How do we know which ones?
TASTY
- Tells how all methods are actually implemented
- Included for all classes emitted by dotc
- source code for dependencies
Call-graph analysis
Detect program entry points, mark them as reachable
For every reachable method:
- mark all methods called from it as reachable
- track how type params flow to other methods
- track which trait combinations were instantiated
Paper: Ali K., Rapoport M., Lhoták O., Dolby J., Tip F. Constructing Call Graphs of Scala Programs, ECOOP 2014
Call-graph analysis, example
// in IndexedSeq
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)
// in App.scala
def main(args: Array[String]) = println(args.map(.toInt).sum)Call-graph analysis, example
- marked
mainas entry point mapis called frommainwith tparams [String]sumis called frommainwith tparams [Int]foldLeftis called fromsumwith tparams [Int]foldlis called fromfoldLeftwith tparams [Int]Function.applyis called fromfoldlwith tparams [Int, Int, Int]
What can linker do?
- smart specialization
- smart dead code elimination. squeryl: 400 methods vs 1500 methods reachable by proguard
- convert classes to value classes
- infer more precise types
- eliminate virtual dispatch
- replace vars by vals
- remove duplicate vals
Smart dead code elimination
methods| original | linker | proguard | |
| squeryl | 3000 | 400 | 1500 |
| kiama | 15000 | 7200 | 13000 |
| dotty | 35000 | 18000 | 32000 |
Converting classes to value classes
Class needs to follow the restrictions:
- Does not reach a callsite that calls AnyRef methods
- Does not have side effects in constructor
- Is effectively final
Closing the world
But what if some other program has a class that inherits from class that was marked as a value class?
- No problem, it has our TASTY and will tune us for it's own use-case.
- Binary compatibility not guaranteed
- source- and TASTY-compatibility provided instead
Eliminating virtual dispatch: inlining
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)
Array(1,2,3).sum
яEliminating virtual dispatch: inlining
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)
Array(1,2,3).sum
Array(1,2,3).foldLeft(IntIsIntegral.zero)(IntIsIntegral.plus)
яEliminating virtual dispatch: inlining
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)
Array(1,2,3).sum
Array(1,2,3).foldLeft(IntIsIntegral.zero)(IntIsIntegral.plus)
Array(1,2,3).foldl(0, len, IntIsIntegral.zero, IntIsIntegral.plus)
яEliminating virtual dispatch: inlining
- does not handle recursive methods
- increases size of program if method is frequently used
- can hurt performance if methods become huge
- is already performed by JVM or JS backend
Eliminating virtual dispatch: clonning
def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)
def foldLeft[B](z: B)(op: (B, A) => B): B =
foldl(0, len, z, op)
private def foldl[B](start: Int, end: Int,
z: B, op: (B, A) => B): B =
if (start == end) z
else foldl(start + 1, end, op(z, this(start)), op)
def sum1(implicit num: IntIsIntegral.type): Int =
foldLeft1(num.zero)(num.plus)
def foldLeft1(z: IntIsIntegral.zero.type)
(op: IntIsIntegral.plus.type): Int =
foldl1(0, len, z, op)Eliminating virtual dispatch: clonning
- handles recursive methods
- small increase in size
- no huge methods
- is actually just specialization for singleton types
Demonstration
Measurements
| original | proguard | linker | |
| methods | 1036 | 823 | 196 |
| bytecode size | 500KB | 330KB | 180KB |
| JVM code cache size(1000 runs) | 1700KB | 1500KB | 1000KB |
| objects allocated | 136K | 120K | 39K |
Future ideas
- De-lazify lazy vals
- use offheap memory(scala-offheap)
- deduplicate methods
Why would one use scala-offheap?
for(i <- 1 to 10) {
(1 to i).map(_ + 1).mkString
}
for(i <- 1 to 10) region {
(1 to i).map(_ + 1).mkString
}12 times faster with region
Thank you.
See my other talks.
0
AutoSpecialization in Dotty
Dmitry Petrashko