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 ```  <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. ---Files-------------------------------- extend-invalidation.png (64.3 KB) tree-invalidation.png (72.8 KB) -- https://bugs.ruby-lang.org/