From: "alanwu (Alan Wu) via ruby-core" <ruby-core@...>
Date: 2026-10-22T22:29:22+00:00
Subject: [ruby-core:127217] [Ruby Bug#22465] Method lookup cache invalidation loop from BasicObject#extend

Issue #22465 has been reported by alanwu (Alan Wu).

----------------------------------------
Bug #22465: Method lookup cache invalidation loop from BasicObject#extend
https://bugs.ruby-lang.org/issues/22465

* Author: alanwu (Alan Wu)
* Status: Open
* Backport: 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN
----------------------------------------
(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 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
```

![](tree-invalidation.png)

<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`:

![](extend-invalidation.png)

<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.


---Files--------------------------------
extend-invalidation.png (64.3 KB)
tree-invalidation.png (72.8 KB)


-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/