Share
Embed
Late Data Layout - OOPLSA Talk
Late Data Layout talk at the OOPLSA research conference (Object-Oriented Programming, Systems, Languages & Applications). Website: http://2014.splashcon.org/event/oopsla2014-unifying-data-representation-transformations
Project website: http://scala-ldl.org
Vlad Ureche
October 23, 2014
Transcript
146 slides
-
scala-ldl.org Late Data Layout: Unifying Data Representation Transformations Vlad Ureche
Eugene Burmako Martin Odersky École polytechnique fédérale de Lausanne, Switzerland {first.last}@epfl.ch 23rd of October 2014 OOPSLA '14 Portland, OR -
scala-ldl.org Late Data Layout: Unifying Data Representation Transformations • compiler
transformations • separate compilation • global scope -
scala-ldl.org Late Data Layout: Unifying Data Representation Transformations • unboxing,
value classes • how data is represented -
scala-ldl.org Late Data Layout: Unifying Data Representation Transformations • what
is there to unify? • why bother? -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types int • value
• no garbage collection • locality -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer in Java, programmers are responsible for the choice of representation int • value • no garbage collection • locality -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer in Java, programmers are responsible for the choice of representation What about Scala? int • value • no garbage collection • locality -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality scala.Int -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality scalac scala.Int -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality scalac Choice of representation 1 scala.Int -
scala-ldl.org Unboxing Primitive Types Unboxing Primitive Types • indirect access
• object allocation • and thus garbage collection • no locality guarantees • compatible with erased generics java.lang.Integer int • value • no garbage collection • locality scalac Choice of representation 1 2 Coercions between representations scala.Int -
scala-ldl.org Value Classes Value Classes value class struct (by-val) •
preferred encoding • fields are inlined • no heap allocations -
scala-ldl.org Value Classes Value Classes value class struct (by-val) •
preferred encoding • fields are inlined • no heap allocations • fallback encoding • compatible with • subtyping • erased generics object (by-ref) -
scala-ldl.org Value Classes Value Classes value class struct (by-val) •
preferred encoding • fields are inlined • no heap allocations • fallback encoding • compatible with • subtyping • erased generics object (by-ref) scalac Choice of representation 1 2 Coercions between representations -
scala-ldl.org Miniboxing Miniboxing long integer • preferred encoding • for
all primitive types T (primitive) -
scala-ldl.org Miniboxing Miniboxing long integer • preferred encoding • for
all primitive types • fallback encoding • compatible with • virtual dispatch • subtyping • erased generics T (erased to Object) T (primitive) -
scala-ldl.org Miniboxing Miniboxing long integer • preferred encoding • for
all primitive types • fallback encoding • compatible with • virtual dispatch • subtyping • erased generics T (erased to Object) T (primitive) scalac Choice of representation 1 2 Coercions between representations -
scala-ldl.org Unboxing Primitive Types Value Classes Representation Transformations Miniboxing motivated
by erased generics Staging (Multi-Stage Programming) -
scala-ldl.org Staging Staging Program Result 1+1+3 5 1-stage execution Program
Program Result 2+3 1+1+3 5 2-stage execution -
scala-ldl.org Staging Staging value direct value (5) • is a
computed value • from an expression evaluated in the current stage -
scala-ldl.org Staging Staging value direct value (5) • is a
computed value • from an expression evaluated in the current stage • executed in the next stage • stores the expression that produces the value lifted expression (2+3) -
scala-ldl.org scalac Staging Staging value direct value (5) • is
a computed value • from an expression evaluated in the current stage • executed in the next stage • stores the expression that produces the value lifted expression (2+3) Choice of representation – domain-specific 1 2 Coercions between representations -
scala-ldl.org How to transform a program? We'll use primitive unboxing
as the running example, to keep things simple -
scala-ldl.org Syntax-based Syntax-based • we need coercions between representations •
simple set of syntax-based rules – example -
scala-ldl.org Syntax-based Syntax-based val x: Int = ... val y:
Int = x val x: int = unbox(...) val y: Int = box(x) -
scala-ldl.org Syntax-based Syntax-based val x: Int = ... val y:
Int = x val x: int = unbox(...) val y: Int = box(x) Coerce the definition right-hand side -
scala-ldl.org Syntax-based Syntax-based val x: Int = ... val y:
Int = x val x: int = unbox(...) val y: Int = box(x) Coerce all occurences of the transformed value -
scala-ldl.org Syntax-based Syntax-based val x: Int = ... val y:
Int = x val x: int = unbox(...) val y: Int = box(x) -
scala-ldl.org Syntax-based Syntax-based val x: Int = ... val y:
Int = x val x: int = unbox(...) val y: Int = box(x) val x: int = unbox(...) val y: int = unbox(box(x)) -
scala-ldl.org Syntax-based Syntax-based val x: Int = ... val y:
Int = x val x: int = unbox(...) val y: Int = box(x) val x: int = unbox(...) val y: int = unbox(box(x)) suboptimal -
scala-ldl.org Peephole Optimization Peephole Optimization val y: int = unbox(box(x))
val y: int = x peephole -
scala-ldl.org Syntax-based Syntax-based def choice(t1: Int, t2: Int): Int =
if (Random.nextBoolean()) t1 else t2 -
scala-ldl.org Syntax-based Syntax-based def choice(t1: Int, t2: Int): Int =
if (Random.nextBoolean()) t1 else t2 Transform one by one -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: Int): Int =
if (Random.nextBoolean()) box(t1) else t2 -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): Int =
if (Random.nextBoolean()) box(t1) else box(t2) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): Int =
if (Random.nextBoolean()) box(t1) else box(t2) Anything missing? -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): Int =
if (Random.nextBoolean()) box(t1) else box(t2) Anything missing? Yes, unboxing the returned value -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): Int =
if (Random.nextBoolean()) box(t1) else box(t2) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): Int =
if (Random.nextBoolean()) box(t1) else box(t2) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
if (Random.nextBoolean()) box(t1) else box(t2) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
unbox( if (Random.nextBoolean()) box(t1) else box(t2) ) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
unbox( if (Random.nextBoolean()) box(t1) else box(t2) ) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
unbox( if (Random.nextBoolean()) box(t1) else box(t2) ) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
unbox( if (Random.nextBoolean()) box(t1) else box(t2) ) new peephole rule -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
unbox( if (Random.nextBoolean()) box(t1) else box(t2) ) new peephole rule sink outside coercions into the if branches -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
if (Random.nextBoolean()) unbox(box(t1)) else unbox(box(t2)) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
if (Random.nextBoolean()) unbox(box(t1)) else unbox(box(t2)) -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
if (Random.nextBoolean()) t1 else t2 -
scala-ldl.org Syntax-based Syntax-based def choice(t1: int, t2: int): int =
if (Random.nextBoolean()) t1 else t2 complicated -
scala-ldl.org Syntax-based Syntax-based • peephole transformation does not scale –
needs multiple rewrite rules for each node – needs stateful rewrite rules – leads to an explosion of rules x states Details in the paper -
scala-ldl.org Coercions are fixed in the tree and moving them
around is difficult. -
scala-ldl.org Coercions are fixed in the tree and moving them
around is difficult. We need a more fluid abstraction. -
scala-ldl.org Coercions are fixed in the tree and moving them
around is difficult. We need a more fluid abstraction. Types -
scala-ldl.org LDL Transformation LDL Transformation • propagates representation information –
into the type system • based on annotated types • e.g. an @unboxed annotation added to integers The Inject Phase The Inject Phase -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: Int, t2: Int):
Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit depending on the transformation, other operations can be performed as well (e.g. miniboxing duplicates methods) -
scala-ldl.org LDL Transformation LDL Transformation • introduces coercions – re-type-checks
the tree – exposes representation mismatches • as annotation mismatches (Int vs @unboxed Int) • leading to coercions The Coerce Phase The Coerce Phase -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit the return type of choice is @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit the return type of choice is @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int the return type of choice is @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int expected type (part of local type inference) the return type of choice is @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : Boolean -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : Boolean matches: expected: Boolean found: Boolean -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int matches: expected: @unboxed Int found: @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit matches: ... : @unboxed Int -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit LDL optimally transforms the tree the first time -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit LDL optimally transforms the tree the first time No peephole transformation -
scala-ldl.org LDL Transformation LDL Transformation • converts annotations to representations
– @unboxed Int → int – Int java.lang.Integer → • coercion markers are also transformed – box(...) → new Integer(...) – unbox(...) → ....intValue The Commit Phase The Commit Phase -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: @unboxed Int, t2:
@unboxed Int): @unboxed Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: int, t2: int):
int = if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org LDL Transformation LDL Transformation def choice(t1: int, t2: int):
int = if (Random.nextBoolean()) t1 else t2 inject coerce commit that's it! -
scala-ldl.org Selectivity Consistency Optimality (not formally proven yet) Properties Late
Data Layout transformation -
scala-ldl.org Selectivity Selectivity inject coerce commit • annotated types –
selectively pick the representation for each value -
scala-ldl.org Selectivity Selectivity inject coerce commit • annotated types –
selectively pick the representation for each value • selectivity is used for – bridge methods (some args boxed, others unboxed) – value classes (JVM: no multi-value returns) – staging (representation: domain-specific knowledge) • List[Int] vs List[@staged Int] vs @staged List[Int] -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: Int): Int =
if (Random.nextBoolean()) t1 else t2 inject coerce commit -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: Int): Int =
if (Random.nextBoolean()) t1 else t2 inject coerce commit what if we did not annotate t1? -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit what if we did not annotate t1? -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int mismatch: expected: @unboxed Int found: Int -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) t1 else t2 inject coerce commit : @unboxed Int mismatch: expected: @unboxed Int found: Int coercion -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) unbox(t1) else t2 inject coerce commit -
scala-ldl.org Selectivity Selectivity def choice(t1: Int, t2: @unboxed Int): @unboxed
Int = if (Random.nextBoolean()) unbox(t1) else t2 inject coerce commit -
scala-ldl.org Selectivity Selectivity def choice(t1: java.lang.Integer, t2: int): int =
if (Random.nextBoolean()) t1.intValue else t2 inject coerce commit -
scala-ldl.org Selectivity Consistency Optimality (not formally proven yet) Properties Late
Data Layout transformation -
scala-ldl.org Consistency Consistency inject coerce commit • representations become part
of types • re-type-checking the program – proves type correctness – proves representation consistency -
scala-ldl.org Selectivity Consistency Optimality (not formally proven yet) Properties Late
Data Layout transformation -
scala-ldl.org Optimality Optimality def choice(t1: java.lang.Integer, t2: int): int =
if (Random.nextBoolean()) t1.intValue else t2 inject coerce commit -
scala-ldl.org Optimality Optimality def choice(t1: java.lang.Integer, t2: int): int =
if (Random.nextBoolean()) t1.intValue else t2 execution inject coerce commit -
scala-ldl.org Optimality Optimality def choice(t1: java.lang.Integer, t2: int): int =
if (Random.nextBoolean()) t1.intValue else t2 1 coercion execution inject coerce commit -
scala-ldl.org Optimality Optimality def choice(t1: java.lang.Integer, t2: int): int =
if (Random.nextBoolean()) t1.intValue else t2 1 coercion no coercions execution inject coerce commit -
scala-ldl.org Optimality Optimality • on any execution trace through the
program – the number of coercions executed is minimum – assuming the program terminates inject coerce commit -
scala-ldl.org Optimality Optimality • on any execution trace through the
program – the number of coercions executed is minimum – assuming the program terminates • modulo – annotations introduced by the inject phase • unbox both parameters → no coercions at all inject coerce commit -
scala-ldl.org Optimality Optimality • on any execution trace through the
program – the number of coercions executed is minimum – assuming the program terminates • modulo – annotations introduced by the inject phase • unbox both parameters → no coercions at all – post-transformations done by the commit phase • box(...) → new Integer(new Integer(...).intValue) inject coerce commit -
scala-ldl.org Optimality Optimality • peephole optimization – propagates coercions •
type system – propagates types inject coerce commit -
scala-ldl.org Optimality Optimality • peephole optimization – propagates coercions •
type system – propagates types – but types are fluid whereas coercions are not details in the paper inject coerce commit -
scala-ldl.org Selectivity Consistency Optimality (not formally proven yet) Properties Late
Data Layout transformation -
scala-ldl.org LDL is used in LDL is used in •
Scala compiler plugins – miniboxing (specialization) – value-class plugin – staging plugin -
scala-ldl.org Benchmarks Benchmarks … … in the paper in the
paper • implementation effort – Late Data Layout mechanism • developed as part of miniboxing • reused by the other compiler plugins – value class plugin → 2 developer-weeks – staging plugin → 1 developer-week -
scala-ldl.org Benchmarks Benchmarks … … in the paper in the
paper • performance – baseline vs transformed code • numbers – up to 2x speedup when transforming value classes – up to 22x speedup when using miniboxing – up to 59x speedup when staging -
scala-ldl.org Conclusion Conclusion Insights Insights • use annotated types –
to selectively mark values with the representation • use expected type propagation – to provide optimal transformation • use the type system – to provide representation consistency -
scala-ldl.org Credits and Thank you-s • Cristian Talau - developed
the initial prototype, as a semester project • Eugene Burmako - the value class plugin based on the LDL transformation • Aymeric Genet - developing collection-like benchmarks for the miniboxing plugin • Martin Odersky, for his patient guidance • Eugene Burmako, for trusting the idea enough to develop the value-plugin based on the LDL transformation • Iulian Dragos, for his work on specialization and many explanations • Miguel Garcia, for his original insights that spawned the miniboxing idea • Michel Schinz, for his wonderful comments and enlightening ACC course • Andrew Myers and Roland Ducournau for the discussions we had and the feedback provided • Heather Miller for the eye-opening discussions we had • Vojin Jovanovic, Sandro Stucki, Manohar Jonalagedda and the whole LAMP laboratory in EPFL for the extraordinary atmosphere • Adriaan Moors, for the miniboxing name which stuck :)) • Thierry Coppey, Vera Salvisberg and George Nithin, who patiently listened to many presentations and provided valuable feedback • Grzegorz Kossakowski, for the many brainstorming sessions on specialization • Erik Osheim, Tom Switzer and Rex Kerr for their guidance on the Scala community side • OOPSLA paper and artifact reviewers, who reshaped the paper with their feedback • Sandro, Vojin, Nada, Heather, Manohar - reviews and discussions on the LDL paper • Hubert Plociniczak for the type notation in the LDL paper • Denys Shabalin, Dmitry Petrashko for their patient reviews of the LDL paper • Xiaoya Xiang and Philip Stutz for trusting miniboxing enough to try it out Special thanks to the Scala Community for their support! (@StuHood, @vpatryshev and everyone else!) -
scala-ldl.org concept repr. 1 … repr. n repr. 2 How
would you use this? -
scala-ldl.org Thank you! concept repr. 1 … repr. n repr.
2 How would you use this?