Data-centric Metaprogramming @ ICOOOLPS 2015

scala-ildl.org Data-centric Metaprogramming in Object-Oriented Languages 6th of July 2015
ICOOLPS Invited Talk Prague, Czech Republic

scala-ildl.org STOP Please ask if things are not clear!

scala-ildl.org STOP Please ask if things are not clear! Really!
I mean it!

scala-ildl.org Vlad URECHE PhD student in the Scala Team @
EPFL Working on program transformations focusing on data representation. Miniboxing guy. @ @VladUreche @VladUreche [email protected]

scala-ildl.org Data-centric Metaprogramming in Object-Oriented Languages

scala-ildl.org Data-centric Metaprogramming in Object-Oriented Languages Joint work with •
Martin Odersky • Aggelos Biboudis • Yannis Smaragdakis

scala-ildl.org infoscience.epfl.ch/record/207050

scala-ildl.org github.com/miniboxing/ildl-plugin

scala-ildl.org Data-centric Metaprogramming in Object-Oriented Languages

scala-ildl.org Motivation Transformation Applications Challenges Conclusion Related Work

scala-ildl.org Object Composition Object Composition class Vector[T] { … }

The Vector collection in the Scala library

scala-ildl.org Object Composition Object Composition class Employee(...) ID NAME SALARY
class Vector[T] { … } The Vector collection in the Scala library

Auto-generated, corresponds to a table row class Vector[T] { … } The Vector collection in the Scala library

class Employee(...) ID NAME SALARY

Vector[Employee] ID NAME SALARY ID NAME SALARY class Vector[T] { … }

Vector[Employee] ID NAME SALARY ID NAME SALARY class Vector[T] { … } Traversal requires dereferencing a pointer for each employee.

scala-ildl.org A Better Representation A Better Representation Vector[Employee] ID NAME
SALARY ID NAME SALARY

scala-ildl.org A Better Representation A Better Representation NAME ... NAME
EmployeeVector ID ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY

EmployeeVector ID ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY iteration is 5x faster

EmployeeVector ID ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY iteration is 5x faster C++ would produce a better representation here, but there are still cases where the C++ representation could be improved over.

scala-ildl.org A Better Representation A Better Representation • In isolation
Vector[T] and Employee are optimal

Vector[T] and Employee are optimal • Together, Vector[Employee] can be optimized

Vector[T] and Employee are optimal • Together, Vector[Employee] can be optimized Challenge: No means of communicating this to the compiler

Vector[T] and Employee are optimal • Together, Vector[Employee] can be optimized Challenge: No means of communicating this to the compiler You may disagree. We'll have a related work section later.

scala-ildl.org

scala-ildl.org • Transforming the code by hand – Makes maintenance
difficult – Changes are not contained

scala-ildl.org • Transforming the code by hand – Makes maintenance
difficult – Changes are not contained Can we automate this?

scala-ildl.org Transformation Transformation Definition Application

scala-ildl.org Transformation Transformation Definition Application • can't be automated •
based on experience • based on speculation • one-time effort

based on experience • based on speculation • one-time effort programmer

based on experience • based on speculation • one-time effort • repetitive and simple • affects code readability • is verbose • is error-prone programmer

scala-ildl.org Transformation Transformation programmer Definition Application • can't be automated
• based on experience • based on speculation • one-time effort • repetitive and simple • affects code readability • is verbose • is error-prone compiler (automated)

scala-ildl.org Data-centric Metaprogramming Data-centric Metaprogramming object VectorOfEmployeeOpt extends Transformation {
... }

... } An object that describes a Transformation.

... } An object that describes a Transformation. A marker trait for transformations.

... }

... } What does the compiler need to know?

... } What does the compiler need to know? The target of the transformation and its representation.

type Target = Vector[Employee] type Result = EmployeeVector ... }

type Target = Vector[Employee] type Result = EmployeeVector ... } The transformation is type-driven we indicate → the type of the target and of the representation.

type Target = Vector[Employee] type Result = EmployeeVector ... } The transformation is type-driven we indicate → the type of the target and of the representation. The improved representation is defined in the host language.

type Target = Vector[Employee] type Result = EmployeeVector ... }

type Target = Vector[Employee] type Result = EmployeeVector ... } How to transform Vector[Employee] into an EmployeeVector?

type Target = Vector[Employee] type Result = EmployeeVector def toResult(t: Target): Result = ... def toTarget(t: Result): Target = ... ... }

type Target = Vector[Employee] type Result = EmployeeVector def toResult(t: Target): Result = ... def toTarget(t: Result): Target = ... ... } Conversions to/from Vector[Employee] that consume/produce a EmployeeVector?

type Target = Vector[Employee] type Result = EmployeeVector def toResult(t: Target): Result = ... def toTarget(t: Result): Target = ... ... }

type Target = Vector[Employee] type Result = EmployeeVector def toResult(t: Target): Result = ... def toTarget(t: Result): Target = ... ... } So far so good, but how to execute Vector[Employee] operations on EmployeeVector?

type Target = Vector[Employee] type Result = EmployeeVector def toResult(t: Target): Result = ... def toTarget(t: Result): Target = ... def bypass_length: Int = ... def bypass_apply(i: Int): Employee = ... def bypass_update(i: Int, v: Employee) = ... def bypass_toString: String = … ... }

scala-ildl.org Data-centric Metaprogramming Data-centric Metaprogramming programmer Definition Application • can't
be automated • based on experience • based on speculation • one-time effort • repetitive and simple • affects code readability • is verbose • is error-prone compiler (automated)

scala-ildl.org

scala-ildl.org Motivation Transformation Applications Challenges Conclusion Related Work Open-world Best
Represenation? Composition

scala-ildl.org Open World Assumption Open World Assumption class Vector[T] {
… } class Employee(...) ID NAME SALARY

scala-ildl.org Open World Assumption Open World Assumption class Employee(...) ID
NAME SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY class Vector[T] { … }

NAME SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY class Vector[T] { … } NAME ... NAME EmployeeVector ID ID ... ... SALARY SALARY

NAME SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY class Vector[T] { … } NAME ... NAME EmployeeVector ID ID ... ... SALARY SALARY class NewEmployee(...) extends Employee(...) ID NAME SALARY DEPT

NAME SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY class Vector[T] { … } NAME ... NAME EmployeeVector ID ID ... ... SALARY SALARY class NewEmployee(...) extends Employee(...) ID NAME SALARY DEPT Oooops...

scala-ildl.org Open World Assumption Open World Assumption • Globally anything
can happen

can happen • Locally the programmer has full control: – Knows the values that will be used – Can reject non-conforming values

can happen • Locally the programmer has full control: – Knows the values that will be used – Can reject non-conforming values How to use this information?

can happen • Locally the programmer has full control: – Knows the values that will be used – Can reject non-conforming values How to use this information? Scopes

scala-ildl.org Scopes Scopes def indexSalary(employees: Vector[Employee], by: Float): Vector[Employee] =
for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary )

for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) Method operating on Scala collections (familiar to programmers)

for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary )

scala-ildl.org Scopes Scopes transform(VectorOfEmployeeOpt) { def indexSalary(employees: Vector[Employee], by: Float):
Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) }

Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) } Now the method operates on the EmployeeVector representation.

Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) } Now the method operates on the EmployeeVector representation. Programmers can freely choose which parts of their code to transform.

scala-ildl.org Scopes Scopes • Can wrap statements, methods even entire
classes – Inlined immediately after the parser – Visible outside the "scope"

scala-ildl.org Scopes Scopes • Can wrap statements, methods even entire
classes – Inlined immediately after the parser – Visible outside the "scope" • Locally closed world – Incoming/outgoing values go through conversions – Programmer can reject unexpected values

scala-ildl.org Research Challenges Research Challenges • No way to say
"@only Employee" in the type system – Currently producing a runtime error – Ideally we should generate a compile-time error

scala-ildl.org Research Challenges Research Challenges • No way to say
"@only Employee" in the type system – Currently producing a runtime error – Ideally we should generate a compile-time error • No way to undo variance (e.g. List[+T]) – We have to convert back to List[Employee] – Still correct, but inefficient • Could we restrict this in the type system? • Or prevent the transformation? val v: List[Any] = listOfEmployees

scala-ildl.org Best Representation Best Representation Vector[Employee] ID NAME SALARY ID
NAME SALARY

scala-ildl.org Best ...? Best ...? NAME ... NAME EmployeeVector ID
ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY

ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY EmployeeJSON { id: 123, name: “John Doe” salary: 100 }

ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY EmployeeJSON { id: 123, name: “John Doe” salary: 100 } CompactVector <compressed binary blob>

ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY EmployeeJSON { id: 123, name: “John Doe” salary: 100 } CompactVector <compressed binary blob> Scopes!

Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) }

Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) } Method operating on column-based storage

scala-ildl.org Scopes Scopes transform(VectorOfEmployeeJSON) { def indexSalary(employees: Vector[Employee], by: Float):
Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) } Method operating on JSON data

scala-ildl.org Scopes Scopes transform(VectorOfEmployeeBinary) { def indexSalary(employees: Vector[Employee], by: Float):
Vector[Employee] = for (employee ← employees) yield employee.copy( salary = (1 + by) * employee.salary ) } Method operating on binary data

scala-ildl.org Scope Composition Scope Composition • Code can be –
Left untransformed (using the original repr.) – Transformed using different representations

scala-ildl.org Scope Composition Scope Composition calling • Original code •
Transformed code • Original code • Transformed code • Same transformation • Different transformation • Code can be – Left untransformed (using the original repr.) – Transformed using different representations

scala-ildl.org Scope Composition – Case 1 Scope Composition – Case
1 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... }

1 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } val employees = loadEmployees(...) indexSalary(employees) No transformation scope applied here.

1 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } val employees = loadEmployees(...) indexSalary(employees) No transformation scope applied here. Different representation: • vector: EmployeeVector • employees: Vector[Employee]

1 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } val employees = loadEmployees(...) indexSalary(employees) No transformation scope applied here. Different representation: • vector: EmployeeVector • employees: Vector[Employee] The compiler adds conversions

1 • Values using different representations – Are automatically converted – Even in different files – Even across separate compilation

1 • Values using different representations – Are automatically converted – Even in different files – Even across separate compilation • This may not always be what you want – aliasing mutable objects – expensive coercions

1 • Values using different representations – Are automatically converted – Even in different files – Even across separate compilation • This may not always be what you want – aliasing mutable objects – expensive coercions • The compiler can warn about this

1 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } val employees = loadEmployees(...) indexSalary(employees)

1 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } val employees = loadEmployees(...) indexSalary(employees) warning: When calling method indexSalary, the argument 'employees' needs to be converted to the 'EmployeeVector' representation, which may incur an overhead: indexSalary(employees) ˆ

2 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... }

scala-ildl.org // in another file, compiled separately: Scope Composition –
Case 2 Scope Composition – Case 2 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } transform(VectorOfEmployeeOpt) { val employees = loadEmployees(...) indexSalary(employees) }

scala-ildl.org // in another file, compiled separately: Scope Composition –
Case 2 Scope Composition – Case 2 transform(VectorOfEmployeeOpt) { def indexSalary(vector: Vector[Employee]) = ... } Scopes compose across separate compilation transform(VectorOfEmployeeOpt) { val employees = loadEmployees(...) indexSalary(employees) }

2 • Values transformed identically – Are passed without conversions – Even in different files – Even across separate compilation

Transformed code • Original code • Transformed code • Same transformation • Different transformation • Code can be – Left untransformed (using the original repr.) – Transformed using different representations double conversions

scala-ildl.org Scope Composition Scope Composition calling overriding • Original code
• Transformed code • Original code • Transformed code • Same transformation • Different transformation • Code can be – Left untransformed (using the original repr.) – Transformed using different representations

• Transformed code • Original code • Transformed code • Same transformation • Different transformation • Code can be – Left untransformed (using the original repr.) – Transformed using different representations The transformation has to preserve the object model.

• Transformed code • Original code • Transformed code • Same transformation • Different transformation • Code can be – Left untransformed (using the original repr.) – Transformed using different representations The transformation has to preserve the object model. All these cases are handled automatically by the ildl transformation!

scala-ildl.org Research Challenges Research Challenges • Chaining transformations – A
B → + B C → = A C →

B → + B C → = A C → • Interaction with Generics – We can transform List[(Int, Int)] to List[Long] – We can transform List[T] for any T

B → + B C → = A C → • Interaction with Generics – We can transform List[(Int, Int)] to List[Long] – We can transform List[T] for any T – But only transforming (Int, Int) to Long • Doesn't transform List[(Int, Int)] to List[Long] • We have to do it separately

scala-ildl.org Array of Stuct Array of Stuct (Column-oriented) (Column-oriented) NAME
... NAME EmployeeVector ID ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY

scala-ildl.org Array of Stuct Array of Stuct (Column-oriented) (Column-oriented) NAME
... NAME EmployeeVector ID ID ... ... SALARY SALARY Vector[Employee] ID NAME SALARY ID NAME SALARY 5x faster

scala-ildl.org Specialization Specialization and stack allocation and stack allocation 3
5 (3,5) Tuples in Scala are generic so they need to use pointers and objects

scala-ildl.org Specialization Specialization and stack allocation and stack allocation 3
5 3 5 (3,5) (3,5) Tuples in Scala are generic so they need to use pointers and objects + stack allocation

scala-ildl.org + stack allocation Specialization Specialization and stack allocation and
stack allocation 14x faster reduced memory footprint 3 5 3 5 (3,5) (3,5) Tuples in Scala are generic so they need to use pointers and objects

scala-ildl.org Deforestation Deforestation List(1,2,3).map(_ + 1).map(_ * 2).sum

scala-ildl.org Deforestation Deforestation List(1,2,3).map(_ + 1).map(_ * 2).sum List(2,3,4)

scala-ildl.org Deforestation Deforestation List(1,2,3).map(_ + 1).map(_ * 2).sum List(2,3,4) List(4,6,8)

18

18 transform(ListDeforestation) { List(1,2,3).map(_ + 1).map(_ * 2).sum }

18 transform(ListDeforestation) { List(1,2,3).map(_ + 1).map(_ * 2).sum } accumulate function

18 transform(ListDeforestation) { List(1,2,3).map(_ + 1).map(_ * 2).sum } accumulate function accumulate function

18 transform(ListDeforestation) { List(1,2,3).map(_ + 1).map(_ * 2).sum } accumulate function accumulate function compute: 18

18 transform(ListDeforestation) { List(1,2,3).map(_ + 1).map(_ * 2).sum } accumulate function accumulate function compute: 18 6x faster

scala-ildl.org Research Challenge Research Challenge • Scopes make speculations constraints
→ • Programmers need to make sure the code conforms – Deforestation requires pure functions – Otherwise it reorders effects → broken semantics • We need a static language – For specifying the constraints – For verifying these on the actual scope

scala-ildl.org Multi-Stage Programming Multi-Stage Programming • Multi-Stage Programming – “Abstraction
without regret” - Tiark Rompf – DSLs small enough to be staged → • 10000x speed improvements

without regret” - Tiark Rompf – DSLs small enough to be staged → • 10000x speed improvements – Scala many features not supported by LMS: → • Separate compilation/modularization • Dynamic dispatch • Aliasing • Reflection

without regret” - Tiark Rompf – DSLs small enough to be staged → • 10000x speed improvements – Scala many features not supported by LMS: → • Separate compilation/modularization • Dynamic dispatch • Aliasing • Reflection If we add support, we lose the ability to optimize code :(

scala-ildl.org Low-level Optimizers Low-level Optimizers • JIT optimizers with virtual
machine support – Access to the low-level code – Can assume a (local) closed world – Can speculate based on profiles – On the critical path – limited analysis

machine support – Access to the low-level code – Can assume a (local) closed world – Can speculate based on profiles – On the critical path – limited analysis – Biggest opportunities are high-level - O(n2) O(n) → • Incoming code is low-level • Rarely possible to recover opportunities

machine support – Access to the low-level code – Can assume a (local) closed world – Can speculate based on profiles – On the critical path – limited analysis – Biggest opportunities are high-level - O(n2) O(n) → • Incoming code is low-level • Rarely possible to recover opportunities Typical solution: Metaprogramming

scala-ildl.org Metaprogramming Metaprogramming • Not your grandpa's C preprocessor def
optimize(tree: AST): AST = { ... }

scala-ildl.org Metaprogramming Metaprogramming • Not your grandpa's C preprocessor •
Full-fledged program transformers – :) Lots of power def optimize(tree: AST): AST = { ... }

Full-fledged program transformers – :) Lots of power – :( Lots of responsibility def optimize(tree: AST): AST = { ... }

Full-fledged program transformers – :) Lots of power – :( Lots of responsibility • Compiler invariants • Object-oriented model • Modularity def optimize(tree: AST): AST = { ... }

Full-fledged program transformers – :) Lots of power – :( Lots of responsibility • Compiler invariants • Object-oriented model • Modularity def optimize(tree: AST): AST = { ... } Can we make metaprogramming “high-level”?

scala-ildl.org Conclusion Conclusion • Object-oriented composition inefcient representation → •
Solution: data-centric metaprogramming – Splitting the responsibility: • Defining the Transformation programmer → • Applying the Transformation compiler → – Scopes • Adapt the data representation to the operation • Allow speculating properties of the scope • We've just begun to scratch the surface – Many interesting research questions lie ahead

scala-ildl.org

scala-ildl.org Thank you!

Data-centric Metaprogramming @ ICOOOLPS 2015

Data-centric Metaprogramming @ ICOOOLPS 2015

Transcript