Miniboxing presentation @PDXScala meetup

Miniboxing presentation @PDXScala meetup

On youtube (partial recording):
https://www.youtube.com/watch?v=g5yFlQySQ5k

Project website: http://scala-miniboxing.org

Transcript

1. scala-miniboxing.org 21st of October 2014 PDXScala Meetup Portland, OR scala-miniboxing.org
2. scala-miniboxing.org Vlad URECHE PhD student in the Scala Team @ EPFL Miniboxing guy. Also worked on Scala specialization, the backend and scaladoc. @ @VladUreche @VladUreche vlad.ureche@epfl.ch
3. scala-miniboxing.org scala-miniboxing.org
4. scala-miniboxing.org Miniboxing Theory Conclusion Practice Benchmarks
5. scala-miniboxing.org Erased Generics Erased Generics def identity[T](t: T): T = t
6. scala-miniboxing.org Erased Generics Erased Generics def identity[T](t: T): T = t scalac / javac
7. scala-miniboxing.org Erased Generics Erased Generics def identity[T](t: T): T = t def identity(t: Object): Object = t scalac / javac
8. scala-miniboxing.org Erased Generics Erased Generics identity(5)
9. scala-miniboxing.org Erased Generics Erased Generics identity(5) scalac / javac
10. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(j.l.Integer.valueOf(5)).intValue scalac / javac
11. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(j.l.Integer.valueOf(5)).intValue scalac / javac Object representation
12. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(j.l.Integer.valueOf(5)).intValue scalac / javac inflates heap requirements Object representation
13. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(j.l.Integer.valueOf(5)).intValue scalac / javac produces garbage inflates heap requirements Object representation
14. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(j.l.Integer.valueOf(5)).intValue scalac / javac produces garbage inflates heap requirements indirect (slow) access to the value Object representation
15. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(j.l.Integer.valueOf(5)).intValue scalac / javac produces garbage breaks locality guarantees inflates heap requirements indirect (slow) access to the value Object representation
16. scala-miniboxing.org Specialization Specialization def identity[T](t: T): T = t
17. scala-miniboxing.org Specialization Specialization def identity[T](t: T): T = t specialization
18. scala-miniboxing.org Specialization Specialization def identity[T](t: T): T = t def identity(t: Object): Object = t specialization
19. scala-miniboxing.org Specialization Specialization def identity[T](t: T): T = t def identity(t: Object): Object = t specialization def identity_Z(t: bool): bool = t
20. scala-miniboxing.org Specialization Specialization def identity[T](t: T): T = t def identity(t: Object): Object = t specialization def identity_Z(t: bool): bool = t def identity_C(t: char): char = t
21. scala-miniboxing.org Specialization Specialization def identity[T](t: T): T = t def identity(t: Object): Object = t specialization def identity_Z(t: bool): bool = t def identity_C(t: char): char = t … (7 other variants)
22. scala-miniboxing.org Specialization Specialization identity(5)
23. scala-miniboxing.org Specialization Specialization identity(5) specialization
24. scala-miniboxing.org Specialization Specialization identity(5) identity_I(5) specialization
25. scala-miniboxing.org Specialization Specialization identity(5) identity_I(5) specialization The variant of identity specialized for int
26. scala-miniboxing.org Specialization Specialization identity(5) identity_I(5) specialization The variant of identity specialized for int // no boxing!
27. scala-miniboxing.org Specialization Specialization def tupled[T1, T2](t1: T1, t2: T2) ...
28. scala-miniboxing.org Specialization Specialization def tupled[T1, T2](t1: T1, t2: T2) ... specialization
29. scala-miniboxing.org Specialization Specialization def tupled[T1, T2](t1: T1, t2: T2) ... // 100 methods (102) specialization
30. scala-miniboxing.org Specialization Specialization def tupled[T1, T2](t1: T1, t2: T2) ... // 100 methods (102) specialization
31. scala-miniboxing.org Specialization Specialization def tupled[T1, T2](t1: T1, t2: T2) ... // 100 methods (102) specialization Can we do better?
32. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t
33. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t miniboxing
34. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t def identity(t: Object): Object = t miniboxing
35. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t def identity(t: Object): Object = t miniboxing def identity_M(..., t: long): long = t
36. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t def identity(t: Object): Object = t miniboxing def identity_M(..., t: long): long = t long encodes all primitive types
37. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t def identity(t: Object): Object = t miniboxing def identity_M(..., t: long): long = t Only 2n variants long encodes all primitive types
38. scala-miniboxing.org Miniboxing Miniboxing identity(3)
39. scala-miniboxing.org Miniboxing Miniboxing identity(3) miniboxing
40. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing
41. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing The miniboxed variant of identity
42. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing Encoding the integer into a long integer The miniboxed variant of identity
43. scala-miniboxing.org Miniboxing Theory Conclusion Practice Benchmarks
44. scala-miniboxing.org Class Transformation Late Data Layout The Theory of Miniboxing ...
45. scala-miniboxing.org Class Transformation Late Data Layout The Theory of Miniboxing ...
46. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T)
47. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T]
48. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C[T]
49. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C[T]
50. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C[T] C$mcD$sp … and 7 others
51. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C[T] C$mcD$sp … and 7 others What is the field t In this class?
52. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C[T] C$mcD$sp … and 7 others What is the field t In this class? Actually there are two fields: a generic one from C and a specialized one
53. scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C[T] C$mcD$sp … and 7 others What is the field t In this class? Actually there are two fields: a generic one from C and a specialized one That's bad: we waste memory SI-3585
54. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T)
55. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C[T]
56. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C[T]
57. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C_L[T] C[T]
58. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C_L[T] C[T] C_M[T]
59. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C_L[T] C[T] A single field C_M[T]
60. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C_L[T] C[T] A single field C_M[T] Erased (t: Object)
61. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C_L[T] C[T] A single field C_M[T] Erased (t: Object) Miniboxed (t: long)
62. scala-miniboxing.org class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) C_L[T] C[T] A single field With specialized getters and setters declared in the interface C_M[T] Erased (t: Object) Miniboxed (t: long)
63. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) extends C[T] extends C[T]
64. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] extends C[T] extends C[T]
65. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] extends C[T] extends C[T] D[T]
66. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcI$sp C$mcI$sp … and 7 others extends C[T] extends C[T] D[T]
67. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcI$sp C$mcI$sp … and 7 others extends C[T] extends C[T] D$mcI$sp D$mcI$sp D$mcI$sp … and 7 others D[T]
68. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcI$sp C$mcI$sp … and 7 others extends C[T] extends C[T] D$mcI$sp D$mcI$sp D$mcI$sp … and 7 others D[T]
69. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcI$sp C$mcI$sp … and 7 others extends C[T] extends C[T] D$mcI$sp D$mcI$sp D$mcI$sp … and 7 others D[T] NoSuchThingError: Multiple Inheritance on the JVM
70. scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcI$sp C$mcI$sp … and 7 others Class inhertance doesn't work SI-8405 extends C[T] extends C[T] D$mcI$sp D$mcI$sp D$mcI$sp … and 7 others D[T] NoSuchThingError: Multiple Inheritance on the JVM
71. scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T]
72. scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_L[T] C_M[T] C[T]
73. scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_L[T] C_M[T] C[T] D_L[T] D_M[T] D[T]
74. scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_L[T] C_M[T] C[T] D_L[T] D_M[T] D[T] Inheritance OK
75. scala-miniboxing.org Class Transformation Late Data Layout The Theory of Miniboxing ...
76. scala-miniboxing.org Late Data Layout Late Data Layout • theory of the transformation – how T becomes long • generalizes miniboxing – value classes – staging support – function representation – etc • scala-ldl.org
77. scala-miniboxing.org Class Transformation Late Data Layout The Theory of Miniboxing ...
78. scala-miniboxing.org Miniboxing Theory Conclusion Practice Benchmarks
79. scala-miniboxing.org Documentation Quirks Miniboxing in Practice Live Demo
80. scala-miniboxing.org Documentation Quirks Miniboxing in Practice Live Demo
81. scala-miniboxing.org
82. scala-miniboxing.org scala-miniboxing.org
83. scala-miniboxing.org scala-miniboxing.org
84. scala-miniboxing.org scala-miniboxing.org tutorials
85. scala-miniboxing.org scala-miniboxing.org tutorials sbt config
86. scala-miniboxing.org scala-miniboxing.org tutorials sbt config examples
87. scala-miniboxing.org scala-miniboxing.org tutorials sbt config examples support
88. scala-miniboxing.org Documentation Quirks Miniboxing in Practice Live Demo
89. scala-miniboxing.org
90. scala-miniboxing.org Alex Prokopec, axel22.github.io
91. scala-miniboxing.org Alex Prokopec, axel22.github.io
92. scala-miniboxing.org Know the conditions for method specialization - method specialization Know the conditions for method specialization - class specialization Initialize specialized values outside constructor body Resolve access problems using the package-private modifier Use traits where possible Avoid traits where possible Make your classes as flat as possible Avoid super calls Be wary of vars Think about the primitive types you really care about Avoid using specialization and implicit classes Alex Prokopec, axel22.github.io
93. scala-miniboxing.org Know the conditions for method specialization - method specialization Know the conditions for method specialization - class specialization Initialize specialized values outside constructor body Resolve access problems using the package-private modifier Use traits where possible Avoid traits where possible Make your classes as flat as possible Avoid super calls Be wary of vars Think about the primitive types you really care about Avoid using specialization and implicit classes Alex Prokopec, axel22.github.io
94. scala-miniboxing.org Know the conditions for method specialization - method specialization Know the conditions for method specialization - class specialization Initialize specialized values outside constructor body Resolve access problems using the package-private modifier Use traits where possible Avoid traits where possible Make your classes as flat as possible Avoid super calls Be wary of vars Think about the primitive types you really care about Avoid using specialization and implicit classes Alex Prokopec, axel22.github.io
95. scala-miniboxing.org Know the conditions for method specialization - method specialization Know the conditions for method specialization - class specialization Initialize specialized values outside constructor body Resolve access problems using the package-private modifier Use traits where possible Avoid traits where possible Make your classes as flat as possible Avoid super calls Be wary of vars Think about the primitive types you really care about Avoid using specialization and implicit classes Alex Prokopec, axel22.github.io = fixed by the 0.4 release
96. scala-miniboxing.org Alex Prokopec, axel22.github.io Quirk
97. scala-miniboxing.org Alex Prokopec, axel22.github.io Quirk = limitation
98. scala-miniboxing.org Alex Prokopec, axel22.github.io Quirk = limitation + silent failure
99. scala-miniboxing.org Alex Prokopec, axel22.github.io Quirk = limitation + silent failure let's make the limitations transparent
100. scala-miniboxing.org Documentation Quirks Miniboxing in Practice Live Demo
101. scala-miniboxing.org Miniboxing Theory Conclusion Practice Benchmarks
102. scala-miniboxing.org Microbenchmarks Collections Benchmarks Spire
103. scala-miniboxing.org Miniboxing Benchmarks Miniboxing Benchmarks on array buffers on array buffers
104. scala-miniboxing.org Miniboxing Benchmarks Miniboxing Benchmarks on linked lists on linked lists
105. scala-miniboxing.org Miniboxing Benchmarks Miniboxing Benchmarks on linked lists on linked lists 3x faster On a non-contiguous data structure
106. scala-miniboxing.org Miniboxing Benchmarks Miniboxing Benchmarks on the Spire library (RexBench) on the Spire library (RexBench) miniboxed specialized generic
107. scala-miniboxing.org Miniboxing Theory Conclusion Practice Benchmarks
108. scala-miniboxing.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 Special thanks to the Scala Community for their support! (@StuHood, @vpatryshev and everyone else!)
109. scala-miniboxing.org scala-miniboxing.org
110. scala-miniboxing.org ScalaTeam @ EPFL
111. scala-miniboxing.org ScalaTeam @ EPFL • YinYang frontend multi-stage execution – based on macro transformations – Vojin Jovanovic/Sandro Stucki https://github.com/vjovanov/yin-yang
112. scala-miniboxing.org ScalaTeam @ EPFL • Scala.js backend – compiles Scala to JavaScript – Sébastien Doeraene/Tobias Schlatter http://www.scala-js.org/ www
113. scala-miniboxing.org ScalaTeam @ EPFL • Lightweight Modular Staging – program optimization – Tiark Rompf + pretty much everyone http://scala-lms.github.io/ www
114. scala-miniboxing.org ScalaTeam @ EPFL • Dependent Object Types calculus – core type system of the dotty compiler – Nada Amin/Tiark Rompf https://github.com/TiarkRompf/minidot https://github.com/lampepfl/dotty
115. scala-miniboxing.org ScalaTeam @ EPFL • Pickling framework and Spores – support for distributed programming – Heather Miller/Philipp Haller + others https://github.com/scala/pickling https://github.com/heathermiller/spores
116. scala-miniboxing.org ScalaTeam @ EPFL • Staged Parser-combinators – fast parser combinators through staging – Manohar Jonnalagedda + others https://github.com/manojo/experiments
117. scala-miniboxing.org ScalaTeam @ EPFL • dotty compiler – compiler for Scala but with the DOT type system – Martin Odersky/Dmitry Petrashko/Tobias Schlatter https://github.com/lampepfl/dotty
118. scala-miniboxing.org ScalaTeam @ EPFL • scala.meta metaprogramming support – Improved reflection, macros, and many more – Eugene Burmako/Denys Shabalin + others http://scalameta.org/ www
119. scala-miniboxing.org ScalaTeam @ EPFL • scaladyno plugin – giving Scala a dynamic language look and feel – Cédric Bastin/Vlad Ureche https://github.com/scaladyno/scaladyno-plugin
120. scala-miniboxing.org ScalaTeam @ EPFL • miniboxing specialization – LDL transformation – Vlad Ureche/Aymeric Genêt + others http://scala-miniboxing.org/ www
121. scala-miniboxing.org ScalaTeam @ EPFL • ScalaBlitz optimization framework – macro-based collection optimization – Dmitry Petrashko/Aleksandar Prokopec http://scala-blitz.github.io/ www
122. scala-miniboxing.org ScalaTeam @ EPFL • LMS-Kappa protein simulator – using multi-stage programming for performance – Sandro Stucki https://github.com/sstucki/lms-kappa
123. scala-miniboxing.org ScalaTeam @ EPFL • Odds probabilistic programming framework – using scala-virtualized and macros – Sandro Stucki https://github.com/sstucki/odds
124. scala-miniboxing.org ScalaTeam @ EPFL • Type debugger for Scala – debugging aid for Scala type errors – Hubert Plociniczak http://lampwww.epfl.ch/~plocinic/ type-debugger-tutorial/ www
125. scala-miniboxing.org ScalaTeam @ EPFL • ScalaMeter benchmarking framework – google caliper for scala – Aleksandar Prokopec http://scalameter.github.io/ www
126. scala-miniboxing.org ScalaTeam @ EPFL • Vector implementation using RRB trees – improved performance for Scala collections – Nicolas Stucki https://github.com/nicolasstucki/scala-rrb-vector www
127. scala-miniboxing.org ScalaTeam @ EPFL • the new scalac backend – good performance gains – Miguel Garcia • on the job market right now http://magarciaepfl.github.io/scala/ www @ miguel.garcia@tuhh.de