Miniboxing presentation at OOPSLA 2013

Miniboxing presentation at OOPSLA 2013. Website: http://splashcon.org/2013/program/oopsla-research-papers

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

1. scala-miniboxing.org Miniboxing Miniboxing Load-time Specialization on the JVM OOPSLA, 29th of October 2013 Vlad Ureche Cristian Talau Martin Odersky
2. 2 scala-miniboxing.org We all like generics We all like generics
3. 3 scala-miniboxing.org We all like generics We all like generics a trivial example a trivial example
4. 4 scala-miniboxing.org We all like generics We all like generics def identity[T](t: T): T = t a trivial example a trivial example
5. 5 scala-miniboxing.org We all like generics We all like generics def identity[T](t: T): T = t • will take any type and • will return that same type a trivial example a trivial example
6. 6 scala-miniboxing.org We all like generics We all like generics def identity[T](t: T): T = t • will take any type and • will return that same type a trivial example a trivial example
7. 7 scala-miniboxing.org We all like generics We all like generics def identity[T](t: T): T = t a trivial example a trivial example but under erasure: def identity(t: Any): Any = t
8. 8 scala-miniboxing.org We all like generics We all like generics def identity[T](t: T): T = t a trivial example a trivial example but under erasure: def identity(t: Any): Any = t Any is the top of the Scala type system
9. 9 scala-miniboxing.org We all like generics We all like generics x = identity(3) a trivial example a trivial example
10. 10 scala-miniboxing.org We all like generics We all like generics x = identity(3) under erasure: a trivial example a trivial example x = unbox(identity(box(3)))
11. 11 scala-miniboxing.org We all like generics We all like generics but under but under erasure erasure
12. 12 scala-miniboxing.org We all like generics We all like generics generics execute similarly to dynamic languages but under but under erasure erasure
13. 13 scala-miniboxing.org We all like generics We all like generics generics execute similarly to dynamic languages – generic values lose their type information but under but under erasure erasure
14. 14 scala-miniboxing.org We all like generics We all like generics generics execute similarly to dynamic languages – generic values lose their type information – primitives need boxing but under but under erasure erasure
15. 15 scala-miniboxing.org We all like generics We all like generics generics execute similarly to dynamic languages – generic values lose their type information – primitives need boxing – performance is affected but under but under erasure erasure
16. 16 scala-miniboxing.org We all like generics We all like generics generics execute similarly to dynamic languages – generic values lose their type information – primitives need boxing – performance is affected but under but under erasure erasure Dynamic language VMs use specialization to improve performance*
17. 17 scala-miniboxing.org We all like generics We all like generics generics execute similarly to dynamic languages – generic values lose their type information – primitives need boxing – performance is affected but under but under erasure erasure Dynamic language VMs use specialization to improve performance* *but the HotSpot JVM doesn't
18. 18 scala-miniboxing.org WE ARE HERE Generics Specialization Miniboxing Performance Evaluation
19. 19 scala-miniboxing.org Scala has a solution Scala has a solution
20. 20 scala-miniboxing.org Scala has a solution Scala has a solution it's called specialization it's called specialization* * * Iulian Dragos – PhD thesis, EPFL, 2010
21. 21 scala-miniboxing.org Scala has a solution Scala has a solution Compile-time (static) transformation – duplicates the original code – adapts it for each primitive type – rewrites programs to use the adapted code it's called specialization it's called specialization* * * Iulian Dragos – PhD thesis, EPFL, 2010
22. 22 scala-miniboxing.org Scala has a solution Scala has a solution Compile-time (static) transformation – duplicates the original code – adapts it for each primitive type – rewrites programs to use the adapted code it's called specialization it's called specialization* * Adapted code doesn't need to box * Iulian Dragos – PhD thesis, EPFL, 2010
23. 23 scala-miniboxing.org Scala has a solution Scala has a solution Compile-time (static) transformation – duplicates the original code – adapts it for each primitive type – rewrites programs to use the adapted code it's called specialization it's called specialization* * Adapted code doesn't need to box Performance is regained. * Iulian Dragos – PhD thesis, EPFL, 2010
24. 24 scala-miniboxing.org Specialization Specialization let's revisit `def identity` let's revisit `def identity`
25. 25 scala-miniboxing.org Specialization Specialization let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t
26. 26 scala-miniboxing.org Specialization Specialization let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_V(t: Unit): Unit = t def identity_Z(t: Boolean): Boolean = t def identity_B(t: Byte): Byte = t def identity_C(t: Char): Char = t def identity_S(t: Short): Short = t def identity_I(t: Int): Int = t def identity_J(t: Long): Long = t def identity_F(t: Float): Float = t def identity_D(t: Double): Double = t
27. 27 scala-miniboxing.org Specialization Specialization let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_V(t: Unit): Unit = t def identity_Z(t: Boolean): Boolean = t def identity_B(t: Byte): Byte = t def identity_C(t: Char): Char = t def identity_S(t: Short): Short = t def identity_I(t: Int): Int = t def identity_J(t: Long): Long = t def identity_F(t: Float): Float = t def identity_D(t: Double): Double = t Generates 10 times the original code
28. 28 scala-miniboxing.org Specialization Specialization … … it gets even worse it gets even worse
29. 29 scala-miniboxing.org Specialization Specialization … … it gets even worse it gets even worse def pack[T1, T2](t1: T1, t2: T2) = ...
30. 30 scala-miniboxing.org def pack_VV(t1: Unit, t2: Unit) def pack_VZ(t1: Unit, t2: Boolean) def pack_VB(t1: Unit, t2: Byte) def pack_VC(t1: Unit, t2: Char) def pack_VS(t1: Unit, t2: Short) def pack_VI(t1: Unit, t2: Int) def pack_VJ(t1: Unit, t2: Long) def pack_VF(t1: Unit, t2: Float) def pack_VD(t1: Unit, t2: Double) Specialization Specialization … … it gets even worse it gets even worse def pack[T1, T2](t1: T1, t2: T2) = ...
31. 31 scala-miniboxing.org def pack_VV(t1: Unit, t2: Unit) def pack_VZ(t1: Unit, t2: Boolean) def pack_VB(t1: Unit, t2: Byte) def pack_VC(t1: Unit, t2: Char) def pack_VS(t1: Unit, t2: Short) def pack_VI(t1: Unit, t2: Int) def pack_VJ(t1: Unit, t2: Long) def pack_VF(t1: Unit, t2: Float) def pack_VD(t1: Unit, t2: Double) Specialization Specialization … … it gets even worse it gets even worse def pack[T1, T2](t1: T1, t2: T2) = ... 10^n, where n is the number of type params
32. 32 scala-miniboxing.org def pack_VV(t1: Unit, t2: Unit) def pack_VZ(t1: Unit, t2: Boolean) def pack_VB(t1: Unit, t2: Byte) def pack_VC(t1: Unit, t2: Char) def pack_VS(t1: Unit, t2: Short) def pack_VI(t1: Unit, t2: Int) def pack_VJ(t1: Unit, t2: Long) def pack_VF(t1: Unit, t2: Float) def pack_VD(t1: Unit, t2: Double) Specialization Specialization … … it gets even worse it gets even worse def pack[T1, T2](t1: T1, t2: T2) = ... 10^n, where n is the number of type params And this is common: Maps, Tuples, Functions
33. 33 scala-miniboxing.org def pack_VV(t1: Unit, t2: Unit) def pack_VZ(t1: Unit, t2: Boolean) def pack_VB(t1: Unit, t2: Byte) def pack_VC(t1: Unit, t2: Char) def pack_VS(t1: Unit, t2: Short) def pack_VI(t1: Unit, t2: Int) def pack_VJ(t1: Unit, t2: Long) def pack_VF(t1: Unit, t2: Float) def pack_VD(t1: Unit, t2: Double) Specialization Specialization … … it gets even worse it gets even worse def pack[T1, T2](t1: T1, t2: T2) = ... 10^n, where n is the number of type params And this is common: Maps, Tuples, Functions
34. 34 scala-miniboxing.org WE ARE HERE Generics Specialization Miniboxing Performance Evaluation
35. 35 scala-miniboxing.org Miniboxing Miniboxing
36. 36 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants
37. 37 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE)
38. 38 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE) Stores the original type
39. 39 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE) Stores the original type Stores the encoded value in a long integer
40. 40 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE)
41. 41 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE) BOOL 0x0 false =
42. 42 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE) BOOL 0x0 false = BOOL 0x1 true =
43. 43 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE) BOOL 0x0 false = BOOL 0x1 true = INT 0x2A 42 =
44. 44 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE)
45. 45 scala-miniboxing.org Miniboxing Miniboxing reduces the variants reduces the variants by using something like a tagged union TAG DATA (VALUE) and using the static type information – tags are attached to code, not to values
46. 46 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t
47. 47 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_M(T_tag: Byte, t: Long): Long
48. 48 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_M(T_tag: Byte, t: Long): Long TAG
49. 49 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_M(T_tag: Byte, t: Long): Long TAG DATA (VALUE)
50. 50 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_M(T_tag: Byte, t: Long): Long TAG DATA (VALUE) T_tag corresponds to the type parameter, instead of the values being passed around.
51. 51 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t def identity_M(T_tag: Byte, t: Long): Long TAG DATA (VALUE) T_tag corresponds to the type parameter, instead of the values being passed around. Tag hoisting
52. 52 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t Two variants per type parameter (reference + minibox) def identity_M(T_tag: Byte, t: Long): Long
53. 53 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t Two variants per type parameter (reference + minibox) `def pack` will have 4 variants def identity_M(T_tag: Byte, t: Long): Long
54. 54 scala-miniboxing.org Miniboxing Miniboxing let's revisit `def identity` let's revisit `def identity` def identity[T](t: T): T = t Two variants per type parameter (reference + minibox) `def pack` will have 4 variants Tag hoisting is instrumental in obtaining good performance def identity_M(T_tag: Byte, t: Long): Long
55. 55 scala-miniboxing.org WE ARE HERE Generics Specialization Miniboxing Performance Evaluation
56. 56 scala-miniboxing.org Performance Performance Miniboxing Tagged union = needs one more ingredient needs one more ingredient
57. 57 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient
58. 58 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ???
59. 59 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ??? Why do we need a secret ingredient?
60. 60 scala-miniboxing.org Switching on tags Switching on tags kills performance kills performance
61. 61 scala-miniboxing.org def toString(T_tag: Byte, value: Long): String = T_tag match { case UNIT => ... case BOOL => ... ... } Switching on tags Switching on tags kills performance kills performance
62. 62 scala-miniboxing.org def toString(T_tag: Byte, value: Long): String = T_tag match { case UNIT => ... case BOOL => ... ... } Even more so for consecutive switches Switching on tags Switching on tags kills performance kills performance
63. 63 scala-miniboxing.org T_tag match { case X => op1 } T_tag match { case X => op2 } Switching on tags Switching on tags kills performance kills performance
64. 64 scala-miniboxing.org T_tag match { case X => op1 } T_tag match { case X => op2 } Switching on tags Switching on tags kills performance kills performance Redundant switch
65. 65 scala-miniboxing.org T_tag match { case X => op1 } T_tag match { case X => op2 } Switching on tags Switching on tags kills performance kills performance Redundant switch
66. 66 scala-miniboxing.org T_tag match { case X => op1; op2 } T_tag match { case X => } Switching on tags Switching on tags kills performance kills performance Redundant switch
67. 67 scala-miniboxing.org T_tag match { case X => op1; op2 } T_tag match { case X => } Switching on tags Switching on tags kills performance kills performance Redundant switch
68. 68 scala-miniboxing.org T_tag match { case X => op1; op2 } T_tag match { case X => } Switching on tags Switching on tags kills performance kills performance Redundant switch Fused together
69. 69 scala-miniboxing.org T_tag match { case X => op1; op2 } T_tag match { case X => } Switching on tags Switching on tags kills performance kills performance This is critical for array operations Redundant switch Fused together
70. 70 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } Switching Switching
71. 71 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_tag match { case INT => ... ... } Switching Switching
72. 72 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } Switching Switching
73. 73 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } Switching Switching
74. 74 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } T_tag match { case INT => ... ... } Fuse the operations together? Switching Switching
75. 75 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_tag match { case INT => val tmp1 = ... val tmp2 = ... array(.) = ... array(.) = ... ... } Switching Switching
76. 76 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_tag match { case INT => val tmp1 = ... val tmp2 = ... array(.) = ... array(.) = ... ... } Hoist the switch out of the loop? Switching Switching
77. 77 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } Switching Switching T_tag match { case INT => var index = 0 while (...) { ... index += 1 } }
78. 78 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(opposite) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } Is that enough? Method may be called from a loop Switching Switching T_tag match { case INT => var index = 0 while (...) { ... index += 1 } }
79. 79 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ???
80. 80 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ??? Can't be switching
81. 81 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ??? Can't be switching Must be something else
82. 82 scala-miniboxing.org • Dispatch object – Encodes array interactions Dispatching Dispatching
83. 83 scala-miniboxing.org • Dispatch object – Encodes array interactions class Dispatcher[T] { def array_get(...): Long def array_set(...): Unit } Dispatching Dispatching
84. 84 scala-miniboxing.org • Dispatch object – Encodes array interactions class Dispatcher[T] { def array_get(...): Long def array_set(...): Unit } Dispatching Dispatching def identity_M(T_dispatcher: Dispatcher[T], t: Long): Long
85. 85 scala-miniboxing.org • Dispatch object – Encodes array interactions class Dispatcher[T] { def array_get(...): Long def array_set(...): Unit } Dispatching Dispatching def identity_M(T_dispatcher: Dispatcher[T], t: Long): Long instead of tag
86. 86 scala-miniboxing.org • Dispatch object – Encodes array interactions Dispatching Dispatching object IntDispatcher extends Dispatcher[Int] { def array_get(...): Long = ... def array_set(...): Unit = ... }
87. 87 scala-miniboxing.org • Dispatch object – Encodes array interactions Dispatching Dispatching object IntDispatcher extends Dispatcher[Int] { def array_get(...): Long = ... def array_set(...): Unit = ... } object LongDispatcher ... object CharDispatcher ...
88. 88 scala-miniboxing.org • Dispatch object – Encodes array interactions Passing a dispatcher = hoisted already Dispatching Dispatching object IntDispatcher extends Dispatcher[Int] { def array_get(...): Long = ... def array_set(...): Unit = ... } object LongDispatcher ... object CharDispatcher ...
89. 89 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(other) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } Dispatching Dispatching
90. 90 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(other) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_dispatcher.array_get Dispatching Dispatching
91. 91 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(other) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_dispatcher.array_get T_dispatcher.array_get Dispatching Dispatching
92. 92 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(other) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_dispatcher.array_get T_dispatcher.array_get T_dispatcher.array_set T_dispatcher.array_set Dispatching Dispatching
93. 93 scala-miniboxing.org ArrayBuffer.reverse() def reverse(): Unit { var index = 0 while (index * 2 < length) { val opposite = length-index-1 val tmp1: T = array(index) val tmp2: T = array(other) array(index) = tmp2 array(opposite) = tmp1 index += 1 } } T_dispatcher.array_get T_dispatcher.array_get T_dispatcher.array_set T_dispatcher.array_set Dispatching Dispatching With inlining, we get good performance
94. 94 scala-miniboxing.org ArrayBuffer.reverse() T_dispatcher.array_get Dispatching Dispatching
95. 95 scala-miniboxing.org ArrayBuffer.reverse() T_dispatcher.array_get Dispatching Dispatching IntDispatcher Monomorphic, okay
96. 96 scala-miniboxing.org ArrayBuffer.reverse() T_dispatcher.array_get Dispatching Dispatching LongDispatcher Polymorphic, okay IntDispatcher Monomorphic, okay
97. 97 scala-miniboxing.org DoubleDispatcher Megamorphic* no more inlining → * for the HotSpot JVM ArrayBuffer.reverse() T_dispatcher.array_get Dispatching Dispatching LongDispatcher Polymorphic, okay IntDispatcher Monomorphic, okay
98. 98 scala-miniboxing.org DoubleDispatcher Megamorphic* no more inlining → * for the HotSpot JVM ArrayBuffer.reverse() T_dispatcher.array_get Dispatching Dispatching LongDispatcher Polymorphic, okay IntDispatcher Monomorphic, okay No more inlining bad performance →
99. 99 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ???
100. 100 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + ??? Object oriented dispatch isn't that
101. 101 scala-miniboxing.org The secret ingredient The secret ingredient
102. 102 scala-miniboxing.org • Switch-based dispatching T_tag match { case INT => ... ... } The secret ingredient The secret ingredient
103. 103 scala-miniboxing.org • Switch-based dispatching • When instantiating the class – T_tag is known T_tag match { case INT => ... ... } The secret ingredient The secret ingredient
104. 104 scala-miniboxing.org • Switch-based dispatching • When instantiating the class – T_tag is known – T_tag is a constant T_tag match { case INT => ... ... } The secret ingredient The secret ingredient
105. 105 scala-miniboxing.org • Switch-based dispatching • When instantiating the class – T_tag is known – T_tag is a constant T_tag match { case INT => ... ... } Encode T_tag in the class name? The secret ingredient The secret ingredient
106. 106 scala-miniboxing.org • Switch-based dispatching • When instantiating the class – T_tag is known – T_tag is a constant T_tag match { case INT => ... ... } Encode T_tag in the class name? The secret ingredient The secret ingredient Staticly? Code explosion!
107. 107 scala-miniboxing.org T_tag match { case INT => ... case CHAR => ... case UNIT => ... ... } Load-time specialization Load-time specialization • Load-time transformation
108. 108 scala-miniboxing.org • Load-time transformation – set T_tag statically T_tag match { case INT => ... case CHAR => ... case UNIT => ... ... } Load-time specialization Load-time specialization INT
109. 109 scala-miniboxing.org • Load-time transformation – set T_tag statically – perform constant folding T_tag match { case INT => ... case CHAR => ... case UNIT => ... ... } Load-time specialization Load-time specialization ... INT
110. 110 scala-miniboxing.org • Load-time transformation – set T_tag statically – perform constant folding – perform dead code elimination Load-time specialization Load-time specialization ...
111. 111 scala-miniboxing.org • Load-time transformation – set T_tag statically – perform constant folding – perform dead code elimination Load-time specialization Load-time specialization ... Only the useful code
112. 112 scala-miniboxing.org • Load-time transformation – set T_tag statically – perform constant folding – perform dead code elimination Load-time specialization Load-time specialization ... Only the useful code No dispatching
113. 113 scala-miniboxing.org • Load-time transformation – set T_tag statically – perform constant folding – perform dead code elimination Is this the secret ingredient? Yes! Load-time specialization Load-time specialization ... Only the useful code No dispatching
114. 114 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + Load-time specialization
115. 115 scala-miniboxing.org Performance Performance Tag hoisting + Miniboxing Tagged union = needs one more ingredient needs one more ingredient + Load-time specialization Attaching tags to code enables load-time specialization
116. 116 scala-miniboxing.org WE ARE HERE Generics Specialization Miniboxing Performance Evaluation
117. 117 scala-miniboxing.org (less is better) Evaluation - Performance Evaluation - Performance Best Performance Worst Performance
118. 118 scala-miniboxing.org (less is better) Evaluation - Performance Evaluation - Performance Best Performance Worst Performance
119. 119 scala-miniboxing.org (less is better) Evaluation - Performance Evaluation - Performance Best Performance Worst Performance Predictable performance
120. 120 scala-miniboxing.org (less is better) Evaluation - Performance Evaluation - Performance Best Performance Worst Performance Predictable performance 5x less bytecode
121. 121 scala-miniboxing.org (less is better) Evaluation - Performance Evaluation - Performance Best Performance Worst Performance Predictable performance 5x less bytecode Similar results on other benchmarks
122. 122 scala-miniboxing.org Spire – numeric abstractions library (12KLOC) Evaluation - Code size Evaluation - Code size (less is better)
123. 123 scala-miniboxing.org Spire – numeric abstractions library (12KLOC) 2.8x bytecode reduction (4.7x for Vector in std. lib) Evaluation - Code size Evaluation - Code size (less is better)
124. 124 scala-miniboxing.org Contributions Contributions Miniboxing
125. 125 scala-miniboxing.org Contributions Contributions Miniboxing Tagged union =
126. 126 scala-miniboxing.org Contributions Contributions Tag hoisting + Miniboxing Tagged union =
127. 127 scala-miniboxing.org Contributions Contributions Tag hoisting + Miniboxing Tagged union = Load-time specialization +
128. scala-miniboxing.org • improves performance • reduces bytecode size Conclusions Conclusions visit visit scala-miniboxing.org scala-miniboxing.org! !