Bug #22465
Updated by alanwu (Alan Wu) about 13 hours ago
(More precisely, the invalidation happens with any method override in the range between `singleton_class.ancestors.first` and the first non-singleton class.)
I'll use YJIT for the example because it has counters in the default build for observing method lookup cache (CME) invalidations, but CME invalidations also impact the interpreter.
```ruby
# --yjit-call-threshold=1
def lookup(hash)
hash.fetch(0, default: nil) # This call site only ever sees Hash
end
lookup({})
# ... but using Kernel#extend BasicObject#extend on an unrelated
# Hash instance it never sees invalidates the CME
# for the site in `lookup`.
unless ENV['DONT_EXTEND']
my_special_hash = {}
my_special_hash.extend(Module.new { def fetch(*) = :unused })
# Note that `def my_special_hash.fetch = nil` doesn't suffer
# from the same issue because the singleton class would be leaf.
end
p RubyVM::YJIT.runtime_stats(:invalidate_method_lookup)
# => 1, or 0 when DONT_EXTEND=1.
```
## Background
The script hits the so called "unrelated invalidation" scenario from #16614 ("New method cache mechanism for Guild"), shown in invalidate_with_subclasses.png. It's also called the "tree invalidation" path in the implementation: any override in a sub-tree walks up to the root of the tree and invalidates the CME for the entire inheritance tree.
Here's my own rendition of a tree invalidation scenario, with a diagram:
```ruby
class Animal
def speak = "poetically, everything can speak"
end
class Mammal < Animal; end
class Cat < Mammal; end
class Dog < Mammal; end
class Raven < Animal; end
def print_speech(object) = printf("a %5s: #{object.speak}\n", object.class)
print_speech(Cat.new)
print_speech(Raven.new)
class Mammal; def speak = "mammals speak differently"; end
print_speech(Raven.new) # IC miss inside
print_speech(Cat.new)
__END__
a Cat: poetically, everything can speak
a Raven: poetically, everything can speak
a Raven: poetically, everything can speak
a Cat: mammals speak differently
```
<details>
```mermaid
flowchart BT
Animal["Animal<br/>owns speak"]
Dog
Raven
Cat
Mammal["Mammal<br/>def speak ← newly added"] --> Animal
Cat --> Mammal
Dog --> Mammal
Raven --> Animal
classDef collateral fill:#ff8a8a,color:#000,stroke:#b33
classDef must fill:#ffd27a,color:#000,stroke:#b80
class Dog,Cat,Mammal must
class Animal,Raven collateral
subgraph legend
direction TB
req["necessary invalidation"]
col["unrelated/collateral invalidation"]
class req must
class col collateral
end
```
</details>
## Invalidation loop disproportionately slow under JITs
This tree invalidation behavior happens every time on override through `extend`. In the interpreter, that means unrelated call sites take an inline cache miss on-demand. With YJIT and ZJIT, there's a large upfront cost on invalidation for patching all code that depend on the CME. After that, there is a heavy on-demand re-compile pause each time control reaches any of the invalidated call sites. Once re-compiled, this process repeats next time there is an override through `extend`.
In a large application written by many teams of people, `extend` in one component ends up having an outsized global effect, especially when it overrides some methods on core classes such as `Hash`. It can also be hard to diagnose the issue back to `extend`, as much of the code never sees the singleton class.
Here's a demo that simulates the worst case scenario from this issue for YJIT:
```ruby
UNRELATED_PARTIES = 10_000
H = { 0 => 1 }
call_sites = UNRELATED_PARTIES.times.map { RubyVM::InstructionSequence.compile('H.fetch(0)') }
# The first wave of invalidations doesn't stop future ones
2.times do
call_sites.each(&:eval)
my_special_hash = {}
# If the `extend` is in some specific route of a web app,
# request traffic drives when the slowness hits.
my_special_hash.extend(Module.new { def fetch(*) = :unused })
p RubyVM::YJIT.runtime_stats(:invalidate_method_lookup)
end
__END__
$ command time ruby test.rb
nil
nil
0.06 real 0.04 user 0.01 sys
$ command time ruby --yjit-call-threshold=1 test.rb
10000
20000
2.21 real 0.74 user 1.46 sys
```
## Solutions
Going back to the first example, this is the ancestry tree on `extend`:
<details>
```mermaid
flowchart BT
Hash
AnonMod["AnonMod<br/>def fetch ← newly added"] --> Hash
Singleton["(singleton class of my_special_hash)"] --> AnonMod
classDef collateral fill:#ff8a8a,color:#000,stroke:#b33
classDef must fill:#ffd27a,color:#000,stroke:#b80
class Singleton,AnonMod must
class Hash collateral
subgraph legend
direction TB
req["necessary invalidation"]
col["unrelated/collateral invalidation"]
class req must
class col collateral
end
```
</details>
Tree invalidation handles branches in the inheritance tree, but the portion relevant to `extend` is always a straight line; e.g. `Class.new({}.singleton_class)` is a TypeError. We can use this property to limit unrelated invalidations.
1. A somewhat general fix involves walking towards the singleton class from the override point. If no CME for the method is found during the walk, then no invalidation is necessary. This adds a VM lock section proportional to the number of modules mixed into the singleton class.
2. A carve-out for `extend` calls that create a new singleton class. There's no CME cached on a freshly created singleton class and iclass, so no invalidation is necessary. This may end up a speed benefit for the `extend` call itself, at the cost of generality compared to (1): e.g. simulating `obj.extend(X)` with `class << obj; include(X); end` can still cause unrelated invalidations.
Note that when there is a CME cached on any item in the singleton class chain, we have no choice but to invalidate the CME and accept the unrelated invalidations; finding all uses of that CME (e.g. interpreter CC, JIT code) is infeasible without significantly reworking the cache system. So, all the solutions focus on when it's possible to invalidate nothing.
I've been working on implementing (1), but I'm now leaning towards (2) because it's easier to see correctness and hopefully a smaller patch.