Miniboxing presentation at ScalaDays 2014

Miniboxing presentation at ScalaDays 2014: http://scaladays.org/berlin2014/index.html

The recording is available on Parleys: https://www.parleys.com/tutorial/miniboxing-specialization-diet

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

Transcript

1. scala-miniboxing.org Miniboxing Miniboxing Fast Generics on the JVM ScalaDays, 18th of June 2014 Vlad Ureche gh/twitter:@VladUreche
2. 2 scala-miniboxing.org class C[T](t: T) class C[T](t: T)
3. 3 scala-miniboxing.org class C[T](t: T) class C[T](t: T) scalac / javac
4. 4 scala-miniboxing.org class C(t: Object) class C(t: Object) class C[T](t: T) class C[T](t: T) scalac / javac
5. 5 scala-miniboxing.org class C(t: Object) class C(t: Object) class C[T](t: T) class C[T](t: T) The process is called erasure, and it replaces type paramerers by their upper bound scalac / javac
6. 6 scala-miniboxing.org class C(t: Object) class C(t: Object) Requires boxed primitive types (java.lang.Integer, ...) class C[T](t: T) class C[T](t: T) The process is called erasure, and it replaces type paramerers by their upper bound scalac / javac
7. 7 scala-miniboxing.org class C(t: Object) class C(t: Object) Requires boxed primitive types (java.lang.Integer, ...) class C[T](t: T) class C[T](t: T) The process is called erasure, and it replaces type paramerers by their upper bound scalac / javac You don't see it: scala.Int can be either int or j.l.Integer. Scalac does the work for you!
8. 8 scala-miniboxing.org class C(t: Object) class C(t: Object) Requires boxed primitive types (java.lang.Integer, ...) class C[T](t: T) class C[T](t: T) The process is called erasure, and it replaces type paramerers by their upper bound scalac / javac Yet boxing degrades performance - heap allocations / GC cycles ... - indirect reads, broken locality You don't see it: scala.Int can be either int or j.l.Integer. Scalac does the work for you!
9. 9 scala-miniboxing.org class C[T](t: T) class C[T](t: T) @specialized @specialized
10. 10 scala-miniboxing.org class C[T](t: T) class C[T](t: T) @miniboxed @miniboxed
11. 11 scala-miniboxing.org What is ? What is ?
12. 12 scala-miniboxing.org @miniboxed =
13. 13 scala-miniboxing.org @specialized @specialized @miniboxed =
14. 14 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations
15. 15 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat
16. 16 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat opens the way to @miniboxed Scala collections
17. 17 scala-miniboxing.org @specialized @specialized
18. 18 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T)
19. 19 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T]
20. 20 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T]
21. 21 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4)
22. 22 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4) spec new C$mcI$sp(4)
23. 23 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4) spec new C$mcI$sp(4) Adapted to integers (t$mcI$sp: int)
24. 24 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4) spec new C$mcI$sp(4) Adapted to integers (t$mcI$sp: int) new C(“abc”)
25. 25 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4) spec new C$mcI$sp(4) Adapted to integers (t$mcI$sp: int) new C(“abc”) spec new C[String](“abc”)
26. 26 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4) spec new C$mcI$sp(4) * similar transformation for methods Adapted to integers (t$mcI$sp: int) new C(“abc”) spec new C[String](“abc”)
27. 27 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others C[T] new C[Int](4) spec new C$mcI$sp(4) * similar transformation for methods Adapted to integers (t$mcI$sp: int) new C(“abc”) spec new C[String](“abc”) Can speed up certain code patterns by up to 20x
28. 28 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat
29. 29 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat • duplicate fields • broken inheriance
30. 30 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T)
31. 31 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T]
32. 32 scala-miniboxing.org class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others
33. 33 scala-miniboxing.org new C(“abc”) spec new C[String](“abc”) class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others
34. 34 scala-miniboxing.org new C(“abc”) spec new C[String](“abc”) class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others t: Object
35. 35 scala-miniboxing.org new C[Int](4) spec new C$mcI$sp(4) new C(“abc”) spec new C[String](“abc”) class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others t: Object
36. 36 scala-miniboxing.org new C[Int](4) spec new C$mcI$sp(4) new C(“abc”) spec new C[String](“abc”) t$mcI$sp: int class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others t: Object
37. 37 scala-miniboxing.org t$mcI$sp: int class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others t: Object
38. 38 scala-miniboxing.org t$mcI$sp: int class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others Carries two fields: • t: Object • t$mcI$sp: int t: Object
39. 39 scala-miniboxing.org t$mcI$sp: int class C[ class C[@specialized @specialized T](t: T) T](t: T) C[T] C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others Carries two fields: • t: Object • t$mcI$sp: int That's bad: duplicate fields SI-3585 t: Object
40. 40 scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) extends C[T] extends C[T]
41. 41 scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) extends C[T] extends C[T] C[T] D[T]
42. 42 scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] C[T] D[T]
43. 43 scala-miniboxing.org def foo(t2: T) class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] C[T] D[T]
44. 44 scala-miniboxing.org def foo(t2: T) class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] C[T] D[T] def foo$mcI$sp(t2: int)
45. 45 scala-miniboxing.org def foo(t2: T) class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] D$mcI$sp D$mcJ$sp D$mcD$sp … and 6 others C[T] D[T] def foo$mcI$sp(t2: int)
46. 46 scala-miniboxing.org def foo(t2: T) class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] D$mcI$sp D$mcJ$sp D$mcD$sp … and 6 others C[T] D[T] def foo$mcI$sp(t2: int) call foo$mcI$sp(t2: int)
47. 47 scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] D$mcI$sp D$mcJ$sp D$mcD$sp … and 6 others C[T] D[T]
48. 48 scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] D$mcI$sp D$mcJ$sp D$mcD$sp … and 6 others C[T] D[T] JVM: Single inheritance!
49. 49 scala-miniboxing.org class D[ class D[@specialized @specialized T](t: T) T](t: T) C$mcI$sp C$mcJ$sp C$mcD$sp … and 6 others extends C[T] extends C[T] D$mcI$sp D$mcJ$sp D$mcD$sp … and 6 others C[T] D[T] JVM: Single inheritance! Specialized class inhertance doesn't work: SI-8405
50. 50 scala-miniboxing.org @miniboxing @miniboxing
51. 51 scala-miniboxing.org C[T] class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T)
52. 52 scala-miniboxing.org C_J[T] C_L[T] C[T] class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T)
53. 53 scala-miniboxing.org C_J[T] C_L[T] C[T] class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) A single field t
54. 54 scala-miniboxing.org C_J[T] C_L[T] C[T] class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) A single field t With specialized getters and setters declared in the interface
55. 55 scala-miniboxing.org C_J[T] C_L[T] C[T] class C[ class C[@miniboxed @miniboxed T](t: T) T](t: T) A single field t With specialized getters and setters declared in the interface Fixed: duplicate fields SI-3585
56. 56 scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T]
57. 57 scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_J[T] C_L[T] C[T]
58. 58 scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_J[T] C_L[T] C[T] D_J[T] D_L[T] D[T]
59. 59 scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_J[T] C_L[T] C[T] D_J[T] D_L[T] D[T] Fixed: class inhertance SI-8405
60. 60 scala-miniboxing.org class D[ class D[@miniboxed @miniboxed T](t: T) T](t: T) extends C[T] extends C[T] C_J[T] C_L[T] C[T] D_J[T] D_L[T] D[T] But why so few classes? Fixed: class inhertance SI-8405
61. 61 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat
62. 62 scala-miniboxing.org Where's the Where's the trait Function2[-T1, -T2, +R] bytecode bloat? bytecode bloat?
63. 63 scala-miniboxing.org Where's the Where's the trait Function2[-T1, -T2, +R] bytecode bloat? bytecode bloat? Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object
64. 64 scala-miniboxing.org Where's the Where's the trait Function2[-T1, -T2, +R] • fully specializing Function2 → 103 traits bytecode bloat? bytecode bloat? Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object
65. 65 scala-miniboxing.org Where's the Where's the trait Function2[-T1, -T2, +R] • fully specializing Function2 → 103 traits • upfront bytecode (not on-demand) bytecode bloat? bytecode bloat? Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object
66. 66 scala-miniboxing.org Where's the Where's the trait Function2[-T1, -T2, +R] • fully specializing Function2 → 103 traits • upfront bytecode (not on-demand) • too much for the Scala library bytecode bloat? bytecode bloat? Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object
67. 67 scala-miniboxing.org Where's the Where's the trait Function2[-T1, -T2, +R] • fully specializing Function2 → 103 traits • upfront bytecode (not on-demand) • too much for the Scala library bytecode bloat? bytecode bloat? Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object Unit, Boolean, Byte, Char, Short, Int, Long, Float, Double, Object Still want to distribute it via maven, not via torrents
68. 68 scala-miniboxing.org But... But... we can do better we can do better
69. 69 scala-miniboxing.org But... But... we can do better we can do better 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!”
70. 70 scala-miniboxing.org But... But... we can do better we can do better 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
71. 71 scala-miniboxing.org But... But... we can do better we can do better 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
72. 72 scala-miniboxing.org And then the And then the
73. 73 scala-miniboxing.org And then the And then the idea was born idea was born
74. 74 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE)
75. 75 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) Stores the original type
76. 76 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) Stores the original type Stores the encoded value (as a long integer)
77. 77 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) BOOL 0x1 true =
78. 78 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) BOOL 0x1 true = INT 0x2A 42 =
79. 79 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) BOOL 0x1 true = INT 0x2A 42 = FLOAT bit representation 5.0f =
80. 80 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) • somewhat similar to a boxed object
81. 81 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) • somewhat similar to a boxed object • but not in the heap memory
82. 82 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) • somewhat similar to a boxed object • but not in the heap memory • direct access to the value
83. 83 scala-miniboxing.org And then the And then the idea was born idea was born it started from the tagged union TAG DATA (VALUE) • somewhat similar to a boxed object • but not in the heap memory • direct access to the value Same benefits as for unboxed values
84. 84 scala-miniboxing.org And then the And then the idea was born idea was born we can reduce the number of variants C[T]
85. 85 scala-miniboxing.org And then the And then the idea was born idea was born we can reduce the number of variants C_J[T] C[T]
86. 86 scala-miniboxing.org And then the And then the idea was born idea was born we can reduce the number of variants C_J[T] C[T] C_L[T]
87. 87 scala-miniboxing.org And then the And then the idea was born idea was born we can reduce the number of variants C_J[T] C[T] C_L[T] “From a low-level perspective, there are only values and pointers.”
88. 88 scala-miniboxing.org And then the And then the idea was born idea was born we can reduce the number of variants C_J[T] C[T] C_L[T] “From a low-level perspective, there are only values and pointers.” Let's take an example
89. 89 scala-miniboxing.org Let's take Let's take an example an example def choice[@miniboxed T](t1: T, t2: T): T = if (util.Random.nextBoolean()) t1 else t2
90. 90 scala-miniboxing.org Let's take Let's take an example an example def choice[@miniboxed T](t1: T, t2: T): T = if (util.Random.nextBoolean()) t1 else t2
91. 91 scala-miniboxing.org Let's take Let's take an example an example def choice[@miniboxed T](t1: T, t2: T): T = if (util.Random.nextBoolean()) t1 else t2 We'll have a version for primitive types
92. 92 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: ..., t2: ...): ... = if (util.Random.nextBoolean()) t1 else t2
93. 93 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: ..., t2: ...): ... = if (util.Random.nextBoolean()) t1 else t2 But what's the signature?
94. 94 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: (Tag,Value), t2: (Tag,Value)):(Tag,Value)= if (util.Random.nextBoolean()) t1 else t2
95. 95 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: (Tag,Value), t2: (Tag,Value)):(Tag,Value)= if (util.Random.nextBoolean()) t1 else t2 This is naive tagged union
96. 96 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: (Tag,Value), t2: (Tag,Value)):(Tag,Value)= if (util.Random.nextBoolean()) t1 else t2 That's wasteful: we carry the tag for T twice This is naive tagged union
97. 97 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: (Tag,Value), t2: (Tag,Value)):(Tag,Value)= if (util.Random.nextBoolean()) t1 else t2 That's wasteful: we carry the tag for T twice And we even return it, despite the caller having passed it This is naive tagged union
98. 98 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](t1: (Tag,Value), t2: (Tag,Value)):(Tag,Value)= if (util.Random.nextBoolean()) t1 else t2 That's wasteful: we carry the tag for T twice And we even return it, despite the caller having passed it This is naive tagged union Insight: we're in a statically typed language, use that!
99. 99 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](T_Tag: Tag, t1: Value, t2: Value):Value= if (util.Random.nextBoolean()) t1 else t2
100. 100 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](T_Tag: Tag, t1: Value, t2: Value):Value= if (util.Random.nextBoolean()) t1 else t2 T_Tag corresponds to the type parameter
101. 101 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](T_Tag: Tag, t1: Value, t2: Value):Value= if (util.Random.nextBoolean()) t1 else t2 T_Tag corresponds to the type parameter Sort of a class tag
102. 102 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](T_Tag: Tag, t1: Value, t2: Value):Value= if (util.Random.nextBoolean()) t1 else t2 T_Tag corresponds to the type parameter Sort of a class tag Encoded as Long
103. 103 scala-miniboxing.org Let's take Let's take an example an example def choice_J[T](T_Tag: Byte, t1: Long, t2: Long): Long= if (util.Random.nextBoolean()) t1 else t2
104. 104 scala-miniboxing.org So, back to the So, back to the bytecode issue bytecode issue trait Function2[-T1, -T2, +R] • with specialization this produces 103 traits
105. 105 scala-miniboxing.org So, back to the So, back to the bytecode issue bytecode issue trait Function2[-T1, -T2, +R] • with specialization this produces 103 traits • with miniboxing only 23 (100x less bytecode)
106. 106 scala-miniboxing.org So, back to the So, back to the bytecode issue bytecode issue trait Function2[-T1, -T2, +R] • with specialization this produces 103 traits • with miniboxing only 23 (100x less bytecode) • so we expect it will be usable on the library
107. 107 scala-miniboxing.org So, back to the So, back to the bytecode issue bytecode issue trait Function2[-T1, -T2, +R] • with specialization this produces 103 traits • with miniboxing only 23 (100x less bytecode) • so we expect it will be usable on the library But before we wrap this up
108. 108 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat
109. 109 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat before the benchmarks: some internals
110. 110 scala-miniboxing.org this is where it gets complicated
111. 111 scala-miniboxing.org this is where it gets complicated time for the hardhats
112. 112 scala-miniboxing.org Let's revisit Let's revisit the example the example def choice[@ miniboxed T](t1: T, t2: T): T = if (nextBoolean() && t1.hashCode != 13) t1 else t2
113. 113 scala-miniboxing.org Let's revisit Let's revisit the example the example def choice_J[T](T_Tag: Tag, t1: Long, t2: Long): Long = if (nextBoolean() && t1.hashCode != 13) t1 else t2
114. 114 scala-miniboxing.org Let's revisit Let's revisit the example the example def choice_J[T](T_Tag: Tag, t1: Long, t2: Long): Long = if (nextBoolean() && t1.hashCode != 13) t1 else t2
115. 115 scala-miniboxing.org Let's revisit Let's revisit the example the example t1.hashCode
116. 116 scala-miniboxing.org Let's revisit Let's revisit the example the example t1.hashCode • how to translate this?
117. 117 scala-miniboxing.org Let's revisit Let's revisit the example the example t1.hashCode • how to translate this? • when t1 is miniboxed?
118. 118 scala-miniboxing.org Let's revisit Let's revisit the example the example scala> true.hashCode res0: Int = 1231 scala> false.hashCode res1: Int = 1237
119. 119 scala-miniboxing.org Let's revisit Let's revisit the example the example scala> true.hashCode res0: Int = 1231 scala> false.hashCode res1: Int = 1237 So calling hashCode on the Long won't work
120. 120 scala-miniboxing.org Let's revisit Let's revisit the example the example minibox2box[T](T_Tag, t).hashCode
121. 121 scala-miniboxing.org Let's revisit Let's revisit the example the example minibox2box[T](T_Tag, t).hashCode • conversions: minibox2box, box2minibox
122. 122 scala-miniboxing.org Let's revisit Let's revisit the example the example minibox2box[T](T_Tag, t).hashCode • conversions: minibox2box, box2minibox • hash code
123. 123 scala-miniboxing.org Let's revisit Let's revisit the example the example minibox2box[T](T_Tag, t).hashCode • conversions: minibox2box, box2minibox • hash code – box the value back
124. 124 scala-miniboxing.org Let's revisit Let's revisit the example the example minibox2box[T](T_Tag, t).hashCode • conversions: minibox2box, box2minibox • hash code – box the value back – execute the hashCode method
125. 125 scala-miniboxing.org Performance-wise Performance-wise
126. 126 scala-miniboxing.org Performance-wise Performance-wise this is okay this is okay
127. 127 scala-miniboxing.org Performance-wise Performance-wise this is okay this is okay • conversions
128. 128 scala-miniboxing.org Performance-wise Performance-wise this is okay this is okay • conversions – between minboxed and unboxed integer types • free on x64
129. 129 scala-miniboxing.org Performance-wise Performance-wise this is okay this is okay • conversions – between minboxed and unboxed integer types • free on x64 – between miniboxed and floating point types • low overhead (not free*) * improved translation (thanks Rex!)
130. 130 scala-miniboxing.org Performance-wise Performance-wise this is okay this is okay • conversions – between minboxed and unboxed integer types • free on x64 – between miniboxed and floating point types • low overhead (not free*) – between miniboxed and boxed values • avoided by @miniboxed! * improved translation (thanks Rex!)
131. 131 scala-miniboxing.org the last example before the benchmarks
132. 132 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list[@miniboxed T](t1: T, t2: T): List[T] = List[T](t1, t2)
133. 133 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list[@miniboxed T](t1: T, t2: T): List[T] = List[T](t1, t2) List.apply[T](t1, t2)
134. 134 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list[@miniboxed T](t1: T, t2: T): List[T] = List.apply[T](t1, t2)
135. 135 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list[@miniboxed T](t1: T, t2: T): List[T] = List.apply[T](t1, t2) def list_J[T](T_Tag: Byte, t1: Long, t2: Long): ... = List[T].apply(t1, t2)
136. 136 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list[@miniboxed T](t1: T, t2: T): List[T] = List.apply[T](t1, t2) def list_J[T](T_Tag: Byte, t1: Long, t2: Long): ... = List[T].apply(t1, t2) How to transform List[T]?
137. 137 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks List[T] what is List[T] when T is miniboxed?
138. 138 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks List[T] what is List[T] when T is miniboxed? – for specialization: [T Int] List[T] => List[Int] ←
139. 139 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks List[T] what is List[T] when T is miniboxed? – for specialization: [T Int] List[T] => List[Int] ← – for miniboxing: still List[T]
140. 140 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks List[T] what is List[T] when T is miniboxed? – for specialization: [T Int] List[T] => List[Int] ← – for miniboxing: still List[T] List_J[T] List_L[T] List[T]
141. 141 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks List[T] what is List[T] when T is miniboxed? – for specialization: [T Int] List[T] => List[Int] ← – for miniboxing: still List[T] List_J[T] List_L[T] List[T] But List[T] is an interface, we can still have an adapted implementation class (List_J)
142. 142 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply[T](t1, t2)
143. 143 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply[T](t1, t2)
144. 144 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply[T](t1, t2) expected: T found: Long
145. 145 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply[T](minibox2box[T](T_Tag,t1), minibox2box[T](T_Tag,t2))
146. 146 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply[T](minibox2box[T](T_Tag,t1), minibox2box[T](T_Tag,t2))
147. 147 scala-miniboxing.org The last example The last example before the benchmarks before the benchmarks def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply[T](minibox2box[T](T_Tag,t1), minibox2box[T](T_Tag,t2)) def list_J[T](T_Tag: Byte, t1: Long, t2: Long): List[T] = List.apply_J[T](T_Tag, t1, t2)
148. 148 scala-miniboxing.org It turns out there's It turns out there's more here more here
149. 149 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism
150. 150 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism • and Eugene (xeno-by) gave it a shot
151. 151 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism • and Eugene (xeno-by) gave it a shot – in a week he implemented
152. 152 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism • and Eugene (xeno-by) gave it a shot – in a week he implemented – a value class plugin
153. 153 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism • and Eugene (xeno-by) gave it a shot – in a week he implemented – a value class plugin – with multi-param value classes
154. 154 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism • and Eugene (xeno-by) gave it a shot – in a week he implemented – a value class plugin – with multi-param value classes https://github.com/miniboxing/value-plugin
155. 155 scala-miniboxing.org It turns out there's It turns out there's more here more here • essentially a very general mechanism • and Eugene (xeno-by) gave it a shot – in a week he implemented – a value class plugin – with multi-param value classes https://github.com/miniboxing/value-plugin
156. 156 scala-miniboxing.org Benchmarks
157. 157 scala-miniboxing.org Linked List
158. 158 scala-miniboxing.org Benchmarks Benchmarks on the Scala library on the Scala library • work with Aymeric Genet (github: @MelodyLucid) • mock-up of Scala linked list – Function1 / Function2 / Tuple2 – Traversable / TraversableLike – Iterator / Iterable / IterableLike – LinearSeqOptimized – Builder / CanBuildFrom
159. 159 scala-miniboxing.org Benchmarks Benchmarks on the Scala library on the Scala library • work with Aymeric Genet (github: @MelodyLucid) • mock-up of Scala linked list – Function1 / Function2 / Tuple2 – Traversable / TraversableLike – Iterator / Iterable / IterableLike – LinearSeqOptimized – Builder / CanBuildFrom
160. 160 scala-miniboxing.org Benchmarks Benchmarks on the Scala library on the Scala library • benchmark: Least Squares Method
161. 161 scala-miniboxing.org Benchmarks Benchmarks on the Scala library on the Scala library • benchmark: Least Squares Method
162. 162 scala-miniboxing.org Benchmarks Benchmarks on the Scala library (inf. heap) on the Scala library (inf. heap)
163. 163 scala-miniboxing.org Benchmarks Benchmarks on the Scala library (inf. heap) on the Scala library (inf. heap) 1.7x faster
164. 164 scala-miniboxing.org Benchmarks Benchmarks on the Scala library (with GC) on the Scala library (with GC) 3x faster
165. 165 scala-miniboxing.org Benchmarks Benchmarks on the Scala library (bytecode) on the Scala library (bytecode) generic miniboxed specialized
166. 166 scala-miniboxing.org non/spire
167. 167 scala-miniboxing.org Benchmarks Benchmarks on the Spire library (Complex) on the Spire library (Complex) miniboxed specialized generic
168. 168 scala-miniboxing.org Benchmarks Benchmarks on the Spire library (RexBench) on the Spire library (RexBench) miniboxed specialized generic
169. 169 scala-miniboxing.org Benchmarks Benchmarks on the Spire library (bytecode) on the Spire library (bytecode) generic miniboxed specialized
170. 170 scala-miniboxing.org Benchmarks Benchmarks on the Spire library (bytecode) on the Spire library (bytecode) generic miniboxed specialized Spire is optimized for specialization
171. 171 scala-miniboxing.org Credits Credits • 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 • 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
172. 172 scala-miniboxing.org @specialized @specialized @miniboxed = - the limitations - bytecode bloat
173. scala-miniboxing.org visit visit scala-miniboxing.org scala-miniboxing.org! ! for Scala collections!