Share
Embed
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
Transcript
102 slides
-
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
Rebalancing Rotating the tree LEAF 3 5 LEAF LEAF LEAF
2 Must be a leaf OR less than 5 and greater than 3 -
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 -
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 -
Rotation Patterns Node Placement and Color Head Left Left Left
Head Left Left Right Head Right Right Right Head Right Right Left -
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 -
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 -
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! -
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 -
Red Black Tree Advantages Versions Share Memory Fast Inserts O(log
n) Fast Lookups O(log n) -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
1 2 3 @color @key @left 4 @right 0 Shape
Tree {right, left, key, color} {left, key, color} {key, color} {color} @color? Ancestor Index -
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) -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 😅 -
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😅 -
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