Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Speeding up Instance Variables in Ruby 3.3

Speeding up Instance Variables in Ruby 3.3

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

Aaron Patterson

June 03, 2024
Tweet

More Decks by Aaron Patterson

Other Decks in Programming

Transcript

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. Rebalancing Rotating the tree LEAF 3 5 LEAF LEAF LEAF

    2 Must be a leaf OR less than 5 and greater than 3
  21. 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
  22. 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
  23. Rotation Patterns Node Placement and Color Head Left Left Left

    Head Left Left Right Head Right Right Right Head Right Right Left
  24. 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
  25. 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
  26. 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!
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 1 2 3 @color @key @left 4 @right 0 Shape

    Tree {right, left, key, color} {left, key, color} {key, color} {color} @color? Ancestor Index
  38. 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)
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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 😅
  48. 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😅
  49. 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