AutoSpecialization in Dotty

Dmitry Petrashko

About me:

  • https://github.com/darkdimius/
  • doing PhD at EPFL
  • previously worked on ScalaBlitz (up to 24x faster collections)
  • since March 2014 building on Dotty under supervision of Martin.
  • since March 2015 working on Dotty Linker and supervising students working on Dotty.

Dotty contributor stats:

alias blame-lines="git ls-tree -r -z --name-only HEAD -- | egrep -z -Z -E '\.(scala)$'\
| xargs -0 -n1 git blame --line-porcelain | grep "^author "| sort | uniq -c | sort -nr"
authorcommitsadditionsdeletionsblame lines
Martin Odersky2,280
146,133
85,391
66,698
Dmitry Petrashko628
158,249
50,201
83,713
Samuel Gruetter19
62,324
12,510
36,615
Others144
5,315
2,108
4,161
JavaScala

public double average(int[] data) {
 int sum = 0;
 for(int i = 0; i < data.length; i++) {
   sum += data[i];
 }
 return sum * 1.0d / data.length
}
 

def average(x: Array[Int]) = {
  x.reduce(_ + _) * 1.0 / x.size
}
20 msec 650 msec

Why?


public double average(int[] data) {
 int sum = 0;
 for(int i = 0; i < data.length; i++) {
   sum += data[i];
 }
 return sum * 1.0d / data.length
}

Java cycle body:

  • Range check;
  • Addition;
  • Index Increment.

Why?


def reduce(op: Function2[Obj, Obj, Obj]): Obj = {
  var first = true
  var acc: Obj = null
  this.foreach{ e =>
    if (first) {
      acc = e
      first = false
    } else acc = op.apply(acc, e)
  }
  acc
}

def foreach(f: Funtion1[Obj, Obj]) {
  var i = 0
  val len = length
  while (i < len) {
    f.apply(this(i));
    i += 1
  }
}

Scala cycle body:

  • Range check;
  • boxing of element
  • dynamic dispatch(foreach arg)
  • predicate check(first?)
  • dynamic dispatch(reduce arg)
  • Addition;
  • boxing inside addition.
  • Index Increment.

Thank you!

See my other talks

Q&A

@DarkDimius