Repository navigation
ConstantResolver#context_constants_cache grows quadratically #3225
Description
load_context_constants builds one Hash per context, and each starts with a full copy of ::Object's children plus table.toplevel. Both the number of contexts and the number of toplevel constants grow with the app, so the cache grows with their product.
Reproduction
A synthetic app with N toplevel modules, 5 classes each, checked with steep check -j 1 (rbs 4.2.0, Steep 2.1.0, Ruby 4.0.6):
# gen.rb DIR MODULES CLASSES_PER_MODULE
dir, m, k = ARGV[0], Integer(ARGV[1]), Integer(ARGV[2])
require "fileutils"
FileUtils.mkdir_p(["#{dir}/lib", "#{dir}/sig"])
File.write("#{dir}/Steepfile", %(target :lib do\n signature "sig"\n check "lib"\nend\n))
m.times do |i|
rb = +"module Mod#{i}\n"
rbs = +"module Mod#{i}\n"
k.times do |j|
rb << " class C#{j}\n def run = String\n end\n"
rbs << " class C#{j}\n def run: () -> singleton(String)\n end\n"
end
File.write("#{dir}/lib/mod#{i}.rb", rb + "end\n")
File.write("#{dir}/sig/mod#{i}.rbs", rbs + "end\n")
end| modules | contexts | total entries | cache size |
|---|---|---|---|
| 400 | 2,001 | 1.04M | 58 MB |
| 800 | 4,001 | 3.68M | 115 MB |
| 1,600 | 8,001 | 13.8M | 460 MB |
Cache size is the sum of ObjectSpace.memsize_of over the cached hashes.
At 1,600 modules, only 0.3% of the entries differ from the shared ::Object + toplevel prefix.
Proposal
Cache the merged layers by reference instead of copying them: the context itself, the lexical scopes' table.children(...), the ancestors' entries that differ from the prefix (once per module), and the prefix (once per resolver). merge! never deletes, so looking the layers up in reverse merge order gives the same answer. constants(context) builds a Hash on demand.
Prototype
module LayeredContextConstants
Layers = Struct.new(:itself, :lexical, :delta, :seed) do
def lookup(name)
return itself[name] if itself.key?(name)
lexical.each { |h| return h[name] if h.key?(name) }
return delta[name] if delta.key?(name)
seed ? seed[name] : nil
end
def to_h
h = {}
h.merge!(seed) if seed
h.merge!(delta)
lexical.reverse_each { |l| h.merge!(l) }
h.merge!(itself)
end
end
EMPTY = {}.freeze
def resolve(name, context:)
cs = layers(context) or raise "Broken context is given"
cs.lookup(name)
end
def constants(context)
layers(context)&.to_h
end
private
def layers(context)
context_constants_cache.fetch(context) { load_context_layers(context) }
end
def load_context_layers(context)
delta, seed = ancestor_layer(context&.[](1) || BuiltinNames::Object.name)
lexical = []
c = context
while c
parent, last = c
if last
consts = table.children(builder.env.normalize_module_name(last)) or return
lexical << consts
end
c = parent
end
itself = {}
constants_itself(context, constants: itself)
context_constants_cache[context] = Layers.new(itself.empty? ? EMPTY : itself, lexical.freeze, delta, seed)
end
def ancestor_layer(name)
@ancestor_layers ||= {}
entry = builder.env.module_class_entry(name, normalized: true) or raise
@ancestor_layers.fetch(entry.name) do
full = {}
constants_from_ancestors(name, constants: full)
seeded = entry.is_a?(Environment::ClassEntry) || entry.is_a?(Environment::ModuleEntry)
seed = seeded ? ancestor_seed : nil
delta = seed ? full.reject { |k, v| seed[k].equal?(v) } : full
@ancestor_layers[entry.name] = [delta.empty? ? EMPTY : delta, seed]
end
end
def ancestor_seed
@ancestor_seed ||= {}.merge!(table.children(BuiltinNames::Object.name) || raise).merge!(table.toplevel)
end
end
RBS::Resolver::ConstantResolver.prepend(LayeredContextConstants)Results
Every cached context returned the same constants as the original code on ruby/rbs, soutaro/steep, kaigionrails/conference-app and the synthetic app, and steep check output was unchanged.
Memory of the type check worker, measured the same way before and after, at exit (average of 2 runs). Live heap is ObjectSpace.memsize_of_all after GC.start. Peak footprint is "Physical footprint (peak)" from vmmap --summary.
| modules | live heap before | live heap after | peak footprint before | peak footprint after |
|---|---|---|---|---|
| 400 | 174 MB | 117 MB (−33%) | 253 MiB | 205 MiB (−19%) |
| 800 | 326 MB | 212 MB (−35%) | 470 MiB | 364 MiB (−23%) |
| 1,600 | 858 MB | 401 MB (−53%) | 982 MiB | 550 MiB (−44%) |
The drop in live heap matches the cache size above (57, 114 and 457 MB).
Time of steep check -j 1, hyperfine, 5 runs each, without any instrumentation:
| modules | before | after |
|---|---|---|
| 400 | 3.12 s ± 0.13 | 3.27 s ± 0.04 |
| 800 | 6.30 s ± 0.14 | 6.25 s ± 0.05 |
| 1,600 | 15.64 s ± 0.47 | 15.02 s ± 0.05 |
The differences are within noise.
Note: context_constants_cache would hold Layers instead of Hash.
Activity