Speeding up Instance Variables in Ruby 3.3

Slides from my RubyKaigi presentation about speeding up instance variables in Ruby 3.3

Transcript

1. RubyKaigi 2024 Speeding Up Instance Variables in Ruby 3.3
2. Aaron Patterson @tenderlove
4. Ruby Implementation Details
5. Data Structures
6. Red Black Trees
7. Instance Variables
8. Object Shapes
9. What Makes IVs Slow
10. Speeding up IVs
11. Data Structures
12. Red-Black 🌲
13. Red-Black Tree is a Binary Tree
14. Self Balancing
15. Red Black Tree Left is < parent, Right is > parent 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil Insert 5 Insert 3 Insert 2 Insert 4 Insert 7 Insert 8 Insert 9
16. Red Black Tree: Rule 1 All nodes are Red or Black 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil
17. Red Black Tree: Rule 2 All Leaf Nodes are Black 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil
18. Red Black Tree: Rule 3 Red Nodes Cannot Have Red Children 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil
19. Red Black Tree: Rule 4 Every path from a given node to a leaf passes through the same number of black nodes 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil
20. Red Black Tree: Rule 4 Every path from a given node to a leaf passes through the same number of black nodes 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil
21. Red Black Tree: Bonus Rule The root node is always black. 3 2 nil nil 7 5 4 nil nil nil 8 nil 9 nil nil
22. Let’s Implement It!
23. Okasaki Style Functional Red Black Tree https://www.cs.tufts.edu/comp/150FP/archive/chris-okasaki/redblack99.pdf
24. Chris Okasaki Everybody learns about balanced search trees in their introductory computer science classes, but even the stouthearted tremble at the thought of implementing such a beast. […] we present an algorithm for insertion in to red-black trees that any competent programmer should be able to implement in fifteen minutes or less
25. Competent Programmer?
26. Blog in 15 min
27. Leaf Nodes module RBTree class Leaf def color = :black def leaf? = true def deconstruct [:black, nil, nil, nil] end def insert val RBTree.insert self, val end end LEAF = Leaf.new def self.new; LEAF; end end tree = RBTree.new Always black Used by pattern matching Helper “insert” method Leaf is a singleton Creating a new tree just returns leaf
28. Regular Node module RBTree class Node attr_reader :color, :key, :left, :right def initialize color, key, left, right @color = color @key = key @left = left @right = right end def leaf? = false def deconstruct [color, key, left, right] end def insert val RBTree.insert self, val end end end Used by pattern matching
29. Inserting a Key module RBTree def self.insert tree, key root = insert_aux(tree, key) case root in [:red, key, left, right] Node.new(:black, key, left, right) else root end end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # FIXME! end end end tree = RBTree.new tree = tree.insert(5) pp tree
30. Inserting a Key module RBTree def self.insert tree, key root = insert_aux(tree, key) case root in [:red, key, left, right] Node.new(:black, key, left, right) else root end end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # FIXME! end end end tree = RBTree.new tree = tree.insert(5) pp tree
31. Inserting a Key module RBTree def self.insert tree, key root = insert_aux(tree, key) case root in [:red, key, left, right] Node.new(:black, key, left, right) else root end end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # FIXME! end end end tree = RBTree.new tree = tree.insert(5) pp tree Deconstruct and reassemble with pattern matching
32. Inserting a Key module RBTree def self.insert tree, key root = insert_aux(tree, key) case root in [:red, key, left, right] Node.new(:black, key, left, right) else root end end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # FIXME! end end end tree = RBTree.new tree = tree.insert(5) pp tree
33. Inserting a Key module RBTree def self.insert tree, key root = insert_aux(tree, key) case root in [:red, key, left, right] Node.new(:black, key, left, right) else root end end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # FIXME! end end end tree = RBTree.new tree = tree.insert(5) pp tree LEAF LEAF LEAF 5 LEAF LEAF 5 LEAF
34. Inserting a Second Key module RBTree private_class_method def self.balance color, key, left, right return Node.new(color, key, left, right) end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # If the new key is smaller, we need to put it on the left if key < tree.key new_left = insert_aux(tree.left, key) balance(tree.color, tree.key, new_left, tree.right) elsif key > tree.key # ... else tree end end end end tree = RBTree.new tree = tree.insert(5) tree = tree.insert(3) LEAF LEAF 5 LEAF LEAF 3 5 LEAF
35. Inserting a Second Key module RBTree private_class_method def self.balance color, key, left, right return Node.new(color, key, left, right) end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # If the new key is smaller, we need to put it on the left if key < tree.key new_left = insert_aux(tree.left, key) balance(tree.color, tree.key, new_left, tree.right) elsif key > tree.key # ... else tree end end end end tree = RBTree.new tree = tree.insert(5) tree = tree.insert(3) LEAF LEAF 5 LEAF LEAF 3 5 LEAF LEAF LEAF 5
36. module RBTree private_class_method def self.balance color, key, left, right return Node.new(color, key, left, right) end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # If the new key is smaller, we need to put it on the left if key < tree.key new_left = insert_aux(tree.left, key) balance(tree.color, tree.key, new_left, tree.right) elsif key > tree.key # ... else tree end end end end tree = RBTree.new tree = tree.insert(5) tree = tree.insert(3) tree = tree.insert(2) Inserting a Third Key LEAF LEAF 3 5 LEAF 2 < ? LEAF LEAF 2
37. Inserting a Third Key module RBTree private_class_method def self.balance color, key, left, right return Node.new(color, key, left, right) end private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # If the new key is smaller, we need to put it on the left if key < tree.key new_left = insert_aux(tree.left, key) balance(tree.color, tree.key, new_left, tree.right) elsif key > tree.key # ... else tree end end end end tree = RBTree.new tree = tree.insert(5) tree = tree.insert(3) tree = tree.insert(2) LEAF 3 5 LEAF LEAF LEAF 2 Rule 2: Red Nodes Cannot Have Red Children
38. Rebalancing Detect violations LEAF 3 5 LEAF LEAF LEAF 2
39. Rebalancing Rotating the tree LEAF 3 5 LEAF LEAF LEAF 2 Must be a leaf OR less than 5 and greater than 3
40. Rebalancing Rotating the tree LEAF 3 5 LEAF LEAF LEAF 2 LEAF 5 2
41. General Form Z Y X A B C D
42. Z Y General Form X A B C D X
43. Detect Violations with Pattern Matching Pattern matching detects violations and deconstructs nodes private_class_method def self.balance color, key, left, right # x, y, z are keys # a, b, c, d are nodes case [color, key, left, right] in [:black, z, [:red, y, [:red, x, a, b], c], d] else return Node.new(color, key, left, right) end Node.new(:red, y, Node.new(:black, x, a, b), Node.new(:black, z, c, d)) end Top Node Black? Left Child Red? Left Child Red? Rotate Tree Make a new node
44. Only 4 Patterns
45. Four different violation patterns Z Y X A B C D X A Y B C D Z X A B C D Z Y Z X A B C Y D Y X C A B D Z
46. Rotation Patterns Node Placement and Color Head Left Left Left Head Left Left Right Head Right Right Right Head Right Right Left
47. Detect Violations with Pattern Matching Handle all four cases private_class_method def self.balance color, key, left, right # x, y, z are keys # a, b, c, d are nodes case [color, key, left, right] # HEAD LEFT LEFT-LEFT in [:black, z, [:red, y, [:red, x, a, b], c], d] # HEAD LEFT LEFT-RIGHT in [:black, z, [:red, x, a, [:red, y, b, c]], d] # HEAD RIGHT RIGHT-RIGHT in [:black, x, a, [:red, y, b, [:red, z, c, d]]] # HEAD RIGHT RIGHT-LEFT in [:black, x, a, [:red, z, [:red, y, b, c], d]] else return Node.new(color, key, left, right) end Node.new(:red, y, Node.new(:black, x, a, b), Node.new(:black, z, c, d)) end
48. Finish Up insert_aux We need to handle both smaller and larger numbers private_class_method def self.insert_aux tree, key if tree.leaf? Node.new :red, key, LEAF, LEAF else # If the new key is smaller, we need to put it on the left if key < tree.key new_left = insert_aux(tree.left, key) balance(tree.color, tree.key, new_left, tree.right) # If the new key is larger, we need to put it on the right elsif key > tree.key new_right = insert_aux(tree.right, key) balance(tree.color, tree.key, tree.left, new_right) else tree end end end If the tree is empty, make a new node If the number is smaller, put it on the left If the number is larger, put it on the right
49. That’s It! module RBTree class Leaf def color = :black def leaf? = true def deconstruct [:black, nil, nil, nil] end def insert val RBTree.insert self, val end end class Node attr_reader :color, :key, :left, :right def initialize color, key, left, right @color = color @key = key @left = left @right = right end def leaf? = false def deconstruct [color, key, left, right] end def insert val RBTree.insert self, val end end LEAF = Leaf.new def self.new; LEAF; end def self.insert tree, key root = insert_aux(tree, key) case root Get the code!
50. Using the Red Black Tree tree = RBTree.new tree = tree.insert(5) tree = tree.insert(3) tree = tree.insert(2) p tree.key?(5) # => true p tree.key?(10) # => false
51. Each Insert Returns a New Tree
52. Only rebalanced nodes are copied
53. Red Black Tree Advantages Versions Share Memory Fast Inserts O(log n) Fast Lookups O(log n)
54. We can’t delete anything 😅
55. Object Shapes and Instance Variables
56. Object Shapes: Mapping Instance Variables to Indexes
57. How Object Shapes Work
58. Object Shapes: The Bad Parts
59. Instance Variable Storage Instance variables are stored in an array on the object class Node def initialize color, key, left, right @color = color @key = key @left = left @right = right end def color @color end end n = Node.new(:red, 5, nil, nil) n.color Node Instance name index value @color 0 :red @key 1 5 @left 2 nil @right 3 nil
60. Tree Data Structure
61. “Shape Tree”
62. Shape Tree Structure Each node has an ID, each edge represents an instance variable 0 1 2 3 Tree Root: all objects start here @color @key @left 4 @right class Node def initialize a, b, c, d @color = a @key = b @left = d @right = c end end
63. class Node2 def initialize a, b, c, d @color = a @key = b @right = c @left = d end end Shape Tree Structure Each node has an ID, each edge represents an instance variable 0 1 2 3 5 @color @key @right @left 4 6 @right @left class Node def initialize a, b, c, d @color = a @key = b @left = d @right = c end end
64. Many objects can share the same shape
65. Shape Tree: IV Name / Order
66. Setting an Instance Variable Tree depth determines array index class Node def initialize color, key, left, right # Start at tree root # @color = color @key = key @left = left @right = right end end n = Node.new(:red, 5, nil, nil) Node Instance 1 2 3 @color @key @left 4 @right 0 0 0 :red 1 5 2 nil 3 nil 1 2 3 4 Shape Tree @key? @left? @right? Shape ID
67. Instance Variable Index: Tree Depth
68. Before Setting: Check if an IV is defined
69. Bad News: Checking IV’s is O(n)
70. Good News: Inline Caches
71. Inline Caches Cache Key is Shape ID class Node def initialize color, key, left, right # Start at tree root # @color = color @key = key @left = left @right = right end end n = Node.new(:red, 5, nil, nil) Node Instance 1 2 3 @color @key @left 4 @right 0 0 0 :red 1 5 2 nil 3 nil 1 2 3 4 Shape Tree Shape ID shape: 0, next id: 1, iv index: 0 shape: 1, next id: 2, iv index: 1 shape: 2, next id: 3, iv index: 2 shape: 3, next id: 4, iv index: 3 Cache Key Next Shape IV Index
72. Inline Caches: Second Run Cache Key is Shape ID class Node def initialize color, key, left, right # Start at tree root # @color = color @key = key @left = left @right = right end end n = Node.new(:red, 5, nil, nil) n = Node.new(:red, 5, nil, nil) Node Instance 1 2 3 @color @key @left 4 @right 0 0 0 :red 1 5 2 nil 3 nil 1 2 3 4 Shape Tree Shape ID shape: 0, next id: 1, iv index: 0 shape: 1, next id: 2, iv index: 1 shape: 2, next id: 3, iv index: 2 shape: 3, next id: 4, iv index: 3 Cache Key Cache Key
73. Cache Hit: O(1)
74. Cache Miss: O(n)
75. Speeding up Cache Misses
76. When do cache misses occur?
77. Subclasses (on read) Subclasses can add IVs, causing the shape to be di ff erent class NodeWithManyIVs def initialize @a0 = 0 @a1 = 1 @a2 = 2 end def read; @a0; end end class Subclass < NodeWithManyIVs def initialize super @foo = 123 end end obj = NodeWithManyIVs.new # shape N sub = Subclass.new # shape N + 1 obj.read # cache MISS in read obj.read # cache HIT in read sub.read # cache MISS in read sub.read # cache HIT in read
78. Subclasses (on write) Subclasses can add IVs, causing the shape to be di ff erent class ManyIVs def initialize # Shape 0 or 1, # depending on subclass @a0 = 0 @a1 = 1 @a2 = 2 end end class Subclass def initialize # always starts at shape 0 @foo = 123 # makes a new shape super end end ManyIVs.new # All IVs MISS on set Subclass.new # All IVs MISS on set ManyIVs.new # All IVs MISS on set Subclass.new # All IVs MISS on set
79. Lazy IV Initialization Instance variable name and order is what matters class LazyIvs def initialize @a = 1 end def b @b ||= 1 end def c @c ||= 1 end def a @a end end LazyIvs.new.a # Shape 1 LazyIvs.new.tap { x.b }.a # Shape 2 LazyIvs.new.tap { x.c }.a # Shape 3 LazyIvs.new.tap { x.c; x.b }.a # Shape 4 LazyIvs.new.tap { x.b; x.c }.a # Shape 5 Creates a new shape Creates a new shape
80. Fairly Rare
81. How can we speed this up?
82. 1 2 3 @color @key @left 4 @right 0 Shape Tree {right, left, key, color} {left, key, color} {key, color} {color} @color? Ancestor Index
83. Functional Red Black Tree!
84. “You can’t delete from that tree”
85. Shapes are never deleted
86. Ruby 3.3 1 2 3 @color @key @left 4 @right 0 Shape Tree {right, left, key, color} {left, key, color} {key, color} {color} Ancestor Index (Red Black Tree)
87. Benchmark IV Read Performance N = ARGV[0].to_i class ManyIVs class_eval "def initialize;" + N.times.map { "@a#{_1} = #{_1}" }.join("\n") + "end" def read; @a0; end end class Subclass < ManyIVs def initialize super @foo = 123 end end def always_miss a = ManyIVs.new b = Subclass.new Benchmark.measure { 200000.times { a.read; b.read } }.real end def always_hit a = ManyIVs.new b = ManyIVs.new Benchmark.measure { 200000.times { a.read; b.read } }.real end puts "#{N},#{always_hit},#{always_miss}" Set N instance variables Compare always hitting with never hitting
88. Ruby 3.2.2: Instance Variable Read Speed (Lower is Better) Time to Read IV 0.0000 0.0200 0.0400 0.0600 0.0800 Number of Instance Variables 1 4 7 10 13 16 19 22 25 28 31 Always Cache Hit Always Cache Miss
89. Ruby 3.3.0: Instance Variable Read Speed (Lower is Better) Time to Read IV 0.0000 0.0075 0.0150 0.0225 0.0300 Number of Instance Variables 1 4 7 10 13 16 19 22 25 28 31 Always Hit Always Miss
90. Benchmark IV Write Performance require "benchmark" N = ARGV[0].to_i class ManyIVs class_eval "def initialize;" + N.times.map { "@a#{_1} = #{_1}" }.join("\n") + "end" def write; @a0 = 0; end end class Subclass < ManyIVs def initialize @foo = 123 super end end def always_miss a = ManyIVs.new b = Subclass.new Benchmark.measure { 500000.times { a.write; b.write } }.real end def always_hit a = ManyIVs.new b = ManyIVs.new Benchmark.measure { 500000.times { a.write; b.write } }.real end puts "#{N},#{always_hit},#{always_miss}" Change read to write
91. Writing one IV on Ruby 3.2 Time to write one IV 0.0000 0.0200 0.0400 0.0600 0.0800 Number of Instance Variables on Object 1 4 7 10 13 16 19 22 25 28 31 Always Cache Hit Always Cache Miss
92. Writing one IV on Ruby 3.3 Time to write one IV 0.0000 0.0120 0.0240 0.0360 0.0480 Number of Instance Variables on Object 1 4 7 10 13 16 19 22 25 28 31 Always Cache Hit Always Cache Miss
93. Memoization Set a variable only if it’s not de fi ned class ManyIVs def memoized if defined?(@some_iv) @some_iv else @some_iv = something_expensive end end end
94. Benchmark Undefined IV require "benchmark" N = ARGV[0].to_i class ManyIVs class_eval "def initialize;" + N.times.map { "@a#{_1} = #{_1}" }.join("\n") + "end" def defined; defined?(@not_defined); end end class Subclass < ManyIVs def initialize super @foo = 123 end end def always_miss a = ManyIVs.new b = Subclass.new Benchmark.measure { 500000.times { a.defined; b.defined } }.real end def always_hit a = ManyIVs.new b = ManyIVs.new Benchmark.measure { 500000.times { a.defined; b.defined } }.real end puts "#{N},#{always_hit},#{always_miss}" look for an IV that’s never de fi ned
95. Check for Unde fi ned IV: Ruby 3.2 Time to Check for Unde fi ned IV 0.0000 0.0200 0.0400 0.0600 0.0800 Number of IVs on Object 1 4 7 10 13 16 19 22 25 28 31 Always Cache Hit Always Cache Miss No Cache on Ruby 3.2 😅
96. Check for Unde fi ned IV: Ruby 3.3 Time to Check for Unde fi ned IV 0.0000 0.0225 0.0450 0.0675 0.0900 Number of IVs on Object 1 4 7 10 13 16 19 22 25 28 31 Always Cache Hit Always Cache Miss Not Using red black tree😅
97. Check for Unde fi ned IV: Ruby 3.4 Time to Check for Unde fi ned IV 0.0000 0.0085 0.0170 0.0255 0.0340 Number of IVs on Object 1 4 7 10 13 16 19 22 25 28 31 Always Cache Hit Always Cache Miss
98. Conclusion
99. O(n) O(log n) 🙅 🙆
100. Data structures are fun! Even if you never use them
101. Ruby 3.3 is Fast!
102. ͋Γ͕ͱ͏͍͟͝·ͨ͠ʂ