Miniboxing: JVM Generics without the Overhead

Miniboxing presentation at PNWScala '14. Cool conference!! Website: http://pnwscala.org/2014/index.html

The recording is available on youtube:
https://www.youtube.com/watch?v=RnIupOJv_oM

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

Transcript

1. scala-miniboxing.org 14th of November 2014 PNWScala 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 What is miniboxing? Why use it? Conclusion How to use it? 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(java.lang.Integer.valueOf(5)) scalac / javac
11. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(java.lang.Integer.valueOf(5)) scalac / javac Object representation
12. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(java.lang.Integer.valueOf(5)) scalac / javac inflates heap requirements Object representation
13. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(java.lang.Integer.valueOf(5)) scalac / javac produces garbage inflates heap requirements Object representation
14. scala-miniboxing.org Erased Generics Erased Generics identity(5) identity(java.lang.Integer.valueOf(5)) 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(java.lang.Integer.valueOf(5)) 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 // no boxing!
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 Specialization Specialization the insight the insight One day in 2012 Miguel Garcia walked into my office and said: “From a low-level perspective, there are only values and pointers. Maybe you can use that!”
33. scala-miniboxing.org Specialization Specialization the insight the insight One day in 2012 Miguel Garcia walked into my office and said: “From a low-level perspective, there are only values and pointers. Maybe you can use that!” ... LONG DOUBLE INT FLOAT SHORT
34. scala-miniboxing.org Specialization Specialization the insight the insight One day in 2012 Miguel Garcia walked into my office and said: “From a low-level perspective, there are only values and pointers. Maybe you can use that!” ... LONG DOUBLE INT FLOAT SHORT a long integer
35. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t
36. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t miniboxing
37. scala-miniboxing.org Miniboxing Miniboxing def identity[T](t: T): T = t def identity(t: Object): Object = t miniboxing
38. 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
39. 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
40. 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
41. scala-miniboxing.org Miniboxing Miniboxing identity(3)
42. scala-miniboxing.org Miniboxing Miniboxing identity(3) miniboxing
43. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing
44. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing The miniboxed variant of identity
45. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing The miniboxed variant of identity inflates heap requirements
46. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing The miniboxed variant of identity inflates heap requirements produces garbage
47. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing The miniboxed variant of identity inflates heap requirements produces garbage indirect (slow) access to the value
48. scala-miniboxing.org Miniboxing Miniboxing identity(3) identity_M(..., int2minibox(3)) miniboxing The miniboxed variant of identity inflates heap requirements produces garbage breaks locality guarantees indirect (slow) access to the value
49. scala-miniboxing.org What is miniboxing? Why use it? Conclusion How to use it? Benchmarks
50. scala-miniboxing.org http://stephenjudkins.github.io/pureimage-presentation/#/
51. scala-miniboxing.org Stephen, are you around? http://stephenjudkins.github.io/pureimage-presentation/#/
52. scala-miniboxing.org http://stephenjudkins.github.io/pureimage-presentation/#/32
53. scala-miniboxing.org PureImage PureImage • has very nice abstractions – generalizes over input, output format – generalizes over pixel format – provides collection-like mapping over images • liked it a lot
54. scala-miniboxing.org PureImage PureImage • took the usual path to using miniboxing – code up a mock-up – become familiar with the problem – try out miniboxing on a small scale – then extend to the whole program [not yet]
55. scala-miniboxing.org PureImage Mock-up PureImage Mock-up
56. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Image[Repr: Pixel] { def width: Int def height: Int def apply(x: Int, y: Int): Repr def map[Repr2: Pixel](f: Image[Repr] => Generator[Repr2]): Image[Repr2] }
57. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Image[Repr: Pixel] { def width: Int def height: Int def apply(x: Int, y: Int): Repr def map[Repr2: Pixel](f: Image[Repr] => Generator[Repr2]): Image[Repr2] } What's a generator?
58. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Generator[Repr: Pixel] { def width: Int def height: Int def generate(x: Int, y: Int): Repr }
59. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Generator[Repr: Pixel] { def width: Int def height: Int def generate(x: Int, y: Int): Repr } Why generic? What is pixel?
60. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors
61. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels
62. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels
63. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels Transformed image 8-bit RGBA channels ...
64. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels Image on disk Indexed colors Transformed image 8-bit RGBA channels ...
65. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels Image on disk Indexed colors Transformed image 8-bit RGBA channels ... discretization after each filter => artifacts
66. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels Image on disk Indexed colors Transformed image 8-bit RGBA channels ... discretization after each filter => artifacts double precision RGBA double precision RGBA
67. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels Image on disk Indexed colors Transformed image 8-bit RGBA channels ... discretization after each filter => artifacts double precision RGBA double precision RGBA discretization only when saving the file => better quality
68. scala-miniboxing.org PureImage Mock-up PureImage Mock-up Image on disk Indexed colors Loaded image 8-bit RGBA channels Transformed image 8-bit RGBA channels Image on disk Indexed colors Transformed image 8-bit RGBA channels ... discretization after each filter => artifacts double precision RGBA double precision RGBA discretization only when saving the file => better quality Pixel representation
69. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Pixel[Repr: Manifest] { def r(t: Repr): Double // red def g(t: Repr): Double // green def b(t: Repr): Double // blue def a(t: Repr): Double // alpha def pack(r: Double, g: Double, b: Double, a: Double): Repr ... }
70. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Pixel[Repr: Manifest] { def r(t: Repr): Double // red def g(t: Repr): Double // green def b(t: Repr): Double // blue def a(t: Repr): Double // alpha def pack(r: Double, g: Double, b: Double, a: Double): Repr ... } All transformations work on double precision FP numbers
71. scala-miniboxing.org PureImage Mock-up PureImage Mock-up abstract class Pixel[Repr: Manifest] { def r(t: Repr): Double // red def g(t: Repr): Double // green def b(t: Repr): Double // blue def a(t: Repr): Double // alpha def pack(r: Double, g: Double, b: Double, a: Double): Repr ... } All transformations work on double precision FP numbers But the data can be encoded differently
72. scala-miniboxing.org PureImage Mock-up PureImage Mock-up object RGBA extends Pixel[Int] { ... } object RGBAExtended extends Pixel[Long] { ... }
73. scala-miniboxing.org PureImage Mock-up PureImage Mock-up object RGBA extends Pixel[Int] { ... } object RGBAExtended extends Pixel[Long] { ... } Encoding all channels
74. scala-miniboxing.org PureImage Mock-up PureImage Mock-up object RGBA extends Pixel[Int] { ... } object RGBAExtended extends Pixel[Long] { ... } Encoding all channels case class DiscreteChannels[T](r: T, g: T, b: T, a: T) object FullPixel extends FourChannelPixel[Double] object HalfPixel extends FourChannelPixel[Float]
75. scala-miniboxing.org PureImage Mock-up PureImage Mock-up object RGBA extends Pixel[Int] { ... } object RGBAExtended extends Pixel[Long] { ... } Encoding all channels case class DiscreteChannels[T](r: T, g: T, b: T, a: T) object FullPixel extends FourChannelPixel[Double] object HalfPixel extends FourChannelPixel[Float] Storing channels individually
76. scala-miniboxing.org PureImage Mock-up PureImage Mock-up DEMO
77. scala-miniboxing.org What is miniboxing? Why use it? Conclusion How to use it? Benchmarks
78. scala-miniboxing.org Sbt Configuration Guidance How to use it? Website
79. scala-miniboxing.org Sbt Configuration Guidance How to use it? Website
80. scala-miniboxing.org build.sbt build.sbt resolvers += Resolver.sonatypeRepo("snapshots") libraryDependencies += "org.scala-miniboxing.plugins" %% "miniboxing-runtime" % "0.4-SNAPSHOT" addCompilerPlugin("org.scala-miniboxing.plugins" %% "miniboxing-plugin" % "0.4-SNAPSHOT")
81. scala-miniboxing.org build.sbt build.sbt resolvers += Resolver.sonatypeRepo("snapshots") libraryDependencies += "org.scala-miniboxing.plugins" %% "miniboxing-runtime" % "0.4-SNAPSHOT" addCompilerPlugin("org.scala-miniboxing.plugins" %% "miniboxing-plugin" % "0.4-SNAPSHOT") Release 0.4 in the works now
82. scala-miniboxing.org build.sbt build.sbt scalacOptions ++= "-P:minibox:hijack" :: // transform @specialized into @miniboxed "-P:minibox:mark-all" :: // mark all type parameters as @miniboxed "-P:minibox:log" :: // explain how classes are transformed "-P:minibox:warn" :: // warn for suboptimal code "-P:minibox:warn-all" :: // warn for suboptimal code across projects Nil
83. scala-miniboxing.org build.sbt build.sbt scalacOptions ++= "-P:minibox:hijack" :: // transform @specialized into @miniboxed "-P:minibox:mark-all" :: // mark all type parameters as @miniboxed "-P:minibox:log" :: // explain how classes are transformed "-P:minibox:warn" :: // warn for suboptimal code "-P:minibox:warn-all" :: // warn for suboptimal code across projects Nil Huh? What's the difference?
84. scala-miniboxing.org warn vs warn-all warn vs warn-all scala> 3 :: Nil // under -P:minibox:warn res0: List[Int] = List(3)
85. scala-miniboxing.org warn vs warn-all warn vs warn-all scala> 3 :: Nil // under -P:minibox:warn res0: List[Int] = List(3) scala> 3 :: Nil // under -P:minibox:warn-all <console>:8: warning: The method List.:: would benefit from miniboxing type parameter B, since it is instantiated by a primitive type. 3 :: Nil ^ res0: List[Int] = List(3)
86. scala-miniboxing.org warn vs warn-all warn vs warn-all scala> 3 :: Nil // under -P:minibox:warn res0: List[Int] = List(3) scala> 3 :: Nil // under -P:minibox:warn-all <console>:8: warning: The method List.:: would benefit from miniboxing type parameter B, since it is instantiated by a primitive type. 3 :: Nil ^ res0: List[Int] = List(3)
87. scala-miniboxing.org warn vs warn-all warn vs warn-all scala> 3 :: Nil // under -P:minibox:warn res0: List[Int] = List(3) scala> 3 :: Nil // under -P:minibox:warn-all <console>:8: warning: The method List.:: would benefit from miniboxing type parameter B, since it is instantiated by a primitive type. 3 :: Nil ^ res0: List[Int] = List(3) Warning for the scala library :)
88. scala-miniboxing.org warn vs warn-all warn vs warn-all scala> 3 :: Nil // under -P:minibox:warn res0: List[Int] = List(3) scala> 3 :: Nil // under -P:minibox:warn-all <console>:8: warning: The method List.:: would benefit from miniboxing type parameter B, since it is instantiated by a primitive type. 3 :: Nil ^ res0: List[Int] = List(3) Warning for the scala library :) Across projects, not limited to the program being compiled.
89. scala-miniboxing.org Sbt Configuration Guidance How to use it? Website
90. scala-miniboxing.org
91. scala-miniboxing.org Alex Prokopec, axel22.github.io
92. scala-miniboxing.org Alex Prokopec, axel22.github.io designer of the parallel collections
93. scala-miniboxing.org Alex Prokopec, axel22.github.io designer of the parallel collections • performance (on the JVM) is magic
94. scala-miniboxing.org Alex Prokopec, axel22.github.io designer of the parallel collections • performance (on the JVM) is magic • specialization (in scalac) is black magic
95. scala-miniboxing.org Alex Prokopec, axel22.github.io designer of the parallel collections • performance (on the JVM) is magic • specialization (in scalac) is black magic – “know the conditions of specialization” – point n: “Use Traits” – point n+1: “Don't use Traits” – … and other 10 pieces of advice ... – is your code running at max performance? • who knows?
96. scala-miniboxing.org Alex Prokopec, axel22.github.io designer of the parallel collections • performance (on the JVM) is magic • specialization (in scalac) is black magic – “know the conditions of specialization” – point n: “Use Traits” – point n+1: “Don't use Traits” – … and other 10 pieces of advice ... – is your code running at max performance? • who knows? Can we do something about this?
97. scala-miniboxing.org Guidance Guidance -P:minibox:warn
98. scala-miniboxing.org Guidance Guidance scala> def identity[@miniboxed T](t: T) = t foo: [T](t: T)T
99. scala-miniboxing.org Guidance Guidance scala> def identity[@miniboxed T](t: T) = t foo: [T](t: T)T let's see how miniboxed identity can be used...
100. scala-miniboxing.org Guidance Guidance
101. scala-miniboxing.org Guidance Guidance scala> identity(3) res1: Int = 3
102. scala-miniboxing.org Guidance Guidance scala> identity(3) res1: Int = 3 scala> identity("3") res2: String = 3
103. scala-miniboxing.org Guidance Guidance scala> identity(3) res1: Int = 3 scala> identity("3") res2: String = 3 scala> identity[Any](3) <console>:9: warning: Using the type argument "Any" for the miniboxed type parameter T of method identity is not specific enough, as it could mean either a primitive or a reference type. Although method foo is miniboxed, it won't benefit from specialization: identity[Any](3) ^ res3: Any = 3
104. scala-miniboxing.org Guidance Guidance scala> identity(3) res1: Int = 3 scala> identity("3") res2: String = 3 scala> identity[Any](3) <console>:9: warning: Using the type argument "Any" for the miniboxed type parameter T of method identity is not specific enough, as it could mean either a primitive or a reference type. Although method foo is miniboxed, it won't benefit from specialization: identity[Any](3) ^ res3: Any = 3 what if identity wasn't miniboxed?
105. scala-miniboxing.org Guidance Guidance
106. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T
107. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T scala> def bar[T](t: T) = foo(t) bar: [T](t: T)T
108. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T scala> def bar[T](t: T) = foo(t) bar: [T](t: T)T scala> bar(3) <console>:10: warning: The method bar would benefit from miniboxing type parameter T, since it is instantiated by a primitive type. bar(3) ^ res1: Int = 3
109. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T bar is generic, let's add @miniboxed scala> def bar[T](t: T) = foo(t) bar: [T](t: T)T scala> bar(3) <console>:10: warning: The method bar would benefit from miniboxing type parameter T, since it is instantiated by a primitive type. bar(3) ^ res1: Int = 3
110. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T
111. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T scala> def bar[@miniboxed T](t: T) = foo(t) <console>:8: warning: The method foo would benefit from miniboxing type parameter T, since it is instantiated by miniboxed type parameter T of method bar. def bar[@miniboxed T](t: T) = foo(t) ^ bar: [T](t: T)T
112. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T scala> def bar[@miniboxed T](t: T) = foo(t) <console>:8: warning: The method foo would benefit from miniboxing type parameter T, since it is instantiated by miniboxed type parameter T of method bar. def bar[@miniboxed T](t: T) = foo(t) ^ bar: [T](t: T)T scala> bar(3) res1: Int = 3
113. scala-miniboxing.org Guidance Guidance scala> def foo[T](t: T) = t foo: [T](t: T)T Why? Because the miniboxed bar should call miniboxed foo, but foo is not miniboxed... scala> def bar[@miniboxed T](t: T) = foo(t) <console>:8: warning: The method foo would benefit from miniboxing type parameter T, since it is instantiated by miniboxed type parameter T of method bar. def bar[@miniboxed T](t: T) = foo(t) ^ bar: [T](t: T)T scala> bar(3) res1: Int = 3
114. scala-miniboxing.org Guidance Guidance scala> def foo[@miniboxed T](t: T) = t foo: [T](t: T)T
115. scala-miniboxing.org Guidance Guidance scala> def foo[@miniboxed T](t: T) = t foo: [T](t: T)T scala> def bar[@miniboxed T](t: T) = foo(t) bar: [T](t: T)T
116. scala-miniboxing.org Guidance Guidance scala> def foo[@miniboxed T](t: T) = t foo: [T](t: T)T scala> def bar[@miniboxed T](t: T) = foo(t) bar: [T](t: T)T scala> bar(3) res1: Int = 3
117. scala-miniboxing.org Guidance Guidance scala> def foo[@miniboxed T](t: T) = t foo: [T](t: T)T scala> def bar[@miniboxed T](t: T) = foo(t) bar: [T](t: T)T scala> bar(3) res1: Int = 3 no warning, everything is specialized
118. scala-miniboxing.org Guidance Guidance • “optimized trace” – one miniboxed method calling another • data uses miniboxing encoding – three patterns • initiator – starts an optimized trace • propagator – propagates it • inhibitor – goes back to boxed :(
119. scala-miniboxing.org Guidance Guidance • “optimized trace” – one miniboxed method calling another • data uses miniboxing encoding – three patterns • initiator – starts an optimized trace • propagator – propagates it • inhibitor – goes back to boxed :( Full tutorial on the website
120. scala-miniboxing.org Sbt Configuration Guidance How to use it? Website
121. scala-miniboxing.org
122. scala-miniboxing.org scala-miniboxing.org
123. scala-miniboxing.org scala-miniboxing.org
124. scala-miniboxing.org scala-miniboxing.org tutorials
125. scala-miniboxing.org scala-miniboxing.org tutorials sbt config
126. scala-miniboxing.org scala-miniboxing.org tutorials sbt config examples
127. scala-miniboxing.org scala-miniboxing.org tutorials sbt config examples support
128. scala-miniboxing.org What is miniboxing? Why use it? Conclusion How to use it? Benchmarks
129. scala-miniboxing.org Linked List
130. scala-miniboxing.org Benchmarks Benchmarks on the linked list on the linked list • work with Aymeric Genet (github: @MelodyLucid) • mock-up of Scala linked list – Function1 / Function2 / Tuple2 – Traversable / TraversableLike – Iterator / Iterable / IterableLike – LinearSeqOptimized – Builder / CanBuildFrom
131. scala-miniboxing.org Benchmarks Benchmarks on the linked list on the linked list • work with Aymeric Genet (github: @MelodyLucid) • mock-up of Scala linked list – Function1 / Function2 / Tuple2 – Traversable / TraversableLike – Iterator / Iterable / IterableLike – LinearSeqOptimized – Builder / CanBuildFrom
132. scala-miniboxing.org Benchmarks Benchmarks on the linked list on the linked list • benchmark: Least Squares Method
133. scala-miniboxing.org Benchmarks Benchmarks on the linked list on the linked list • benchmark: Least Squares Method
134. scala-miniboxing.org Benchmarks Benchmarks on the linked list (infinite heap) on the linked list (infinite heap)
135. scala-miniboxing.org Benchmarks Benchmarks on the linked list (infinite heap) on the linked list (infinite heap) 1.7x faster with infinite heap
136. scala-miniboxing.org Benchmarks Benchmarks on the linked list (limited heap) on the linked list (limited heap)
137. scala-miniboxing.org Benchmarks Benchmarks on the linked list (limited heap) on the linked list (limited heap) 3x faster with limited heap
138. scala-miniboxing.org non/spire
139. scala-miniboxing.org Benchmarks Benchmarks on the Spire library (Complex) on the Spire library (Complex) miniboxed specialized generic
140. scala-miniboxing.org Benchmarks Benchmarks on the Spire library (RexBench) on the Spire library (RexBench) miniboxed specialized generic
141. scala-miniboxing.org bytecode
142. scala-miniboxing.org Benchmarks Benchmarks on the linked list (bytecode) on the linked list (bytecode) generic miniboxed specialized
143. scala-miniboxing.org Benchmarks Benchmarks on the Spire library (bytecode) on the Spire library (bytecode) generic miniboxed specialized
144. scala-miniboxing.org What is miniboxing? Why use it? Conclusion How to use it? Benchmarks
145. 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 • Dmitry Petrashko, for the many cool discussions we had • Ilya Klyuchnikov and Pablo Guerrero - fixes and commits • 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!)
146. scala-miniboxing.org Clipart from www.clipartpanda.com
147. scala-miniboxing.org Miniboxed Encoding • ScalaDays 2014 Talk https://www.parleys.com/play/53a7d 2d0e4b0543940d9e567 • OOPSLA '13 Paper http://infoscience.epfl.ch/ record/188060 Clipart from www.clipartpanda.com
148. scala-miniboxing.org Miniboxed Encoding • ScalaDays 2014 Talk https://www.parleys.com/play/53a7d 2d0e4b0543940d9e567 • OOPSLA '13 Paper http://infoscience.epfl.ch/ record/188060 • OOPSLA Talk https://speakerdeck.com/vladureche/ late-data-layout-ooplsa-talk (or the Scala Bay talk) • OOPSLA '14 Paper http://infoscience.epfl.ch/ • record/200963 Code Transformation Related to value classes and multi-stage programming scala-ldl.org Clipart from www.clipartpanda.com
149. scala-miniboxing.org Miniboxed Encoding • ScalaDays 2014 Talk https://www.parleys.com/play/53a7d 2d0e4b0543940d9e567 • OOPSLA '13 Paper http://infoscience.epfl.ch/ record/188060 Other Considerations • Function Encoding (Bucharest FP) https://github.com/ miniboxing/miniboxing- plugin/blob/wip/docs/ 2014-08-miniboxing-bjug.pdf • The Quirks of Miniboxing (PDXScala) https://www.youtube.com/watch? v=g5yFlQySQ5k • OOPSLA Talk https://speakerdeck.com/vladureche/ late-data-layout-ooplsa-talk (or the Scala Bay talk) • OOPSLA '14 Paper http://infoscience.epfl.ch/ • record/200963 Code Transformation Related to value classes and multi-stage programming scala-ldl.org Clipart from www.clipartpanda.com
150. scala-miniboxing.org Clipart from www.clipartpanda.com Miniboxed Encoding • ScalaDays 2014 Talk https://www.parleys.com/play/53a7d 2d0e4b0543940d9e567 • OOPSLA '13 Paper http://infoscience.epfl.ch/ record/188060 Other Considerations • Function Encoding (Bucharest FP) https://github.com/ miniboxing/miniboxing- plugin/blob/wip/docs/ 2014-08-miniboxing-bjug.pdf • The Quirks of Miniboxing (PDXScala) https://www.youtube.com/watch? v=g5yFlQySQ5k • OOPSLA Talk https://speakerdeck.com/vladureche/ late-data-layout-ooplsa-talk (or the Scala Bay talk) • OOPSLA '14 Paper http://infoscience.epfl.ch/ • record/200963 Code Transformation Related to value classes and multi-stage programming scala-ldl.org scala-miniboxing.org
151. scala-miniboxing.org scala-miniboxing.org
152. scala-miniboxing.org ScalaTeam @ EPFL lamp.epfl.ch
153. scala-miniboxing.org ScalaTeam @ EPFL • YinYang frontend multi-stage execution – based on macro transformations – Vojin Jovanovic, Sandro Stucki https://github.com/vjovanov/yin-yang
154. scala-miniboxing.org ScalaTeam @ EPFL • Scala.js backend – compiles Scala to JavaScript – Sébastien Doeraene, Tobias Schlatter http://www.scala-js.org/ www
155. scala-miniboxing.org ScalaTeam @ EPFL • Lightweight Modular Staging – program optimization – Tiark Rompf + pretty much everyone http://scala-lms.github.io/ www
156. 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
157. 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
158. scala-miniboxing.org ScalaTeam @ EPFL • Staged Parser-combinators – fast parser combinators through staging – Manohar Jonnalagedda + others https://github.com/manojo/experiments
159. scala-miniboxing.org ScalaTeam @ EPFL • dotty compiler – compiler for Scala but with the DOT type system – Martin Odersky, Dmitry Petrashko + many others https://github.com/lampepfl/dotty
160. scala-miniboxing.org ScalaTeam @ EPFL • scala.meta metaprogramming support – Improved reflection, macros, and many more – Eugene Burmako, Denys Shabalin + others http://scalameta.org/ www
161. 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
162. scala-miniboxing.org ScalaTeam @ EPFL • miniboxing specialization – LDL transformation – Vlad Ureche, Aymeric Genêt + others http://scala-miniboxing.org/ www
163. scala-miniboxing.org ScalaTeam @ EPFL • ScalaBlitz optimization framework – macro-based collection optimization – Dmitry Petrashko, Aleksandar Prokopec http://scala-blitz.github.io/ www
164. scala-miniboxing.org ScalaTeam @ EPFL • LMS-Kappa protein simulator – using multi-stage programming for performance – Sandro Stucki https://github.com/sstucki/lms-kappa
165. scala-miniboxing.org ScalaTeam @ EPFL • Odds probabilistic programming framework – using scala-virtualized and macros – Sandro Stucki https://github.com/sstucki/odds
166. 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
167. scala-miniboxing.org ScalaTeam @ EPFL • ScalaMeter benchmarking framework – google caliper for scala – Aleksandar Prokopec http://scalameter.github.io/ www
168. 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
169. scala-miniboxing.org ScalaTeam @ EPFL lamp.epfl.ch