Speeding up Instance Variables in Ruby 3.3

Transcript

1. RubyKaigi 2024 Speeding Up Instance Variables in Ruby 3.3

2. Aaron Patterson @tenderlove

3. None

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. ͋Γ͕ͱ͏͍͟͝·ͨ͠ʂ