Bug #22465: Method lookup cache invalidation loop from Kernel#extend

• Status: Open
• Assignee: -
• Target version: -
• Backport: 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN

[alanwu (Alan Wu)]

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

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

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

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

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:

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:

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

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.

[alanwu (Alan Wu)]

• Subject changed from Method lookup cache invalidation loop from BasicObject#extend to Method lookup cache invalidation loop from Kernel#extend

[alanwu (Alan Wu)]

• Description updated (diff)