Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

`ConstantResolver#context_constants_cache` grows quadratically

オープン
  • 何か問題がありますか？
#3,225 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
57/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
ruby
領域
performance

調査の方向性

The issue identifies RBS::Resolver::ConstantResolver#context_constants_cache and load_context_constants as the source of the duplicated hashes; first read that resolver and its tests. Compare cached constants with the proposed layered lookup across the Ruby and RBS cases named in the report, then run the relevant resolver tests and steep check on the reported fixtures. Done means lookups match the current behavior while cache memory scales with shared layers rather than contexts times constants.

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
Ruby
スター
2.2k
フォーク
258
平均マージ
1日 4時間
マージ済み PR（30日）
52

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

ruby/rbs のほかの issue

ruby/rbs の issue をすべて見る

似ている issue

Ruby の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。