はじめに
こんにちは、株式会社 Techouse で新卒 1 年目のエンジニアをしている kinoshita です。
本記事では、RubyKaigi 2026 の Day2 に行われた Jeremy Evans さんのセッション「Implementing Core Set」をご紹介します。おなじみの Set クラスがコアクラスへ書き直されたと聞いて気になり、本セッションを聴きに行きました。セッションでは多くのことが語られましたが、本記事では 「単なる Hash のラッパー」から卒業し、コアクラスへと進化した Set の背景・実装に込められた意図・副次的に得られた利点をまとめていきます。
なお、本記事で言う「Core Set」とは、これまで Ruby 実装の標準ライブラリだった Set クラスをコア（C 実装）へ昇格させたものを指します。
Set の中身は Hash だった
Ruby には Set クラスがあり、Ruby 1.8.0 から標準ライブラリとして提供されてきました。Ruby 3.2 以降は組み込み（built-in）化されており、require 'set' を書かなくても利用できます。
s = Set.new([1, 2, 3]) s.add(2) # => Set[1, 2, 3]（既にあるので変化なし） s.add(4) # => Set[1, 2, 3, 4]（新規要素を追加）
このように普段使いできる Set ですが、セッションでは次のように説明されていました。
Each element of the set is a key in the hash, and all of the hash values are true.
つまり、Set の内部実装は 「要素を Hash のキー、値は常に true」 という形で実現されています。
具体的には、Set クラスは内部に Hash インスタンスを 1 つ抱えていて、要素を追加するたびにその要素をキー・値を true として Hash に登録します。たとえば Set.new([1, 2, 3]) の内部状態は、Hash で書けば { 1 => true, 2 => true, 3 => true } に近いイメージです。
イメージしやすいように 擬似コード で表すと、次のような形で表現できます。※実際の lib/set.rb とは異なります。
def initialize(enum = nil) @hash = {} # 内部に Hash インスタンスを 1 つ抱える enum&.each { |e| add(e) } end def add(o) @hash[o] = true # 要素をキー、値を true として登録 self end
要素の有無を問い合わせるのは Hash のキー検索になるので、Hash の高速な検索の恩恵をそのまま受けられる、という設計です。
この設計は 1.8.0 から Ruby 3.4 まで、ほとんど変わらず使われてきました。しかし、時間と共に 2 つの問題が見えてきました。
問題 1：エントリごとに 1/3 のメモリが未使用のまま確保されていた
Set として使うと、Hash に true だけがたくさん並ぶことになります。このような実装では、すべてのキーが意味のないまま true を保有し続けることになり、大量の要素を持つ Set の場合、要素数ぶんだけ true を保存する無駄なメモリを確保し続けてしまいます。
具体的に見ていきます。Ruby の Hash は内部的には st_table という C のハッシュテーブル実装で動いています。Hash に格納されている 1 つのエントリ（キーと値の組）はそれぞれ st_table_entry という構造体で表現されます。
struct st_table_entry { st_hash_t hash; // キーのハッシュ値（探索の高速化用キャッシュ） st_data_t key; // キー st_data_t record; // 値（Set 用途では常に true） };
ここで st_data_t は Ruby の値を 1 つ収めるための汎用型（実体は unsigned long 相当）で、整数やポインタ、true などを同じ枠で扱えるようになっています。
C の構造体は、各フィールドのサイズが定義時点で固定されています。record に何が入るかに関わらず、エントリごとに st_data_t 1 つぶんの領域が確保されます。Set 用途で record が true 固定であっても、その領域そのものは確保されてしまいます。つまりエントリ 1 つにつき、構造体のおよそ 1/3 のメモリを「同じ値（true）で埋まり続けるだけの領域」として無駄に保有していた、ということになります。
問題 2：add? がスレッドセーフでない
もう 1 つの問題はスレッドセーフ性でした。標準ライブラリの Set#add? の実装はこうなっています。
def add?(o) add(o) unless include?(o) end
add? は「新規追加なら self を、既に存在していたら nil を返す」メソッドです。実装は素直で、include? で存在を確認し、存在しなければ add を呼ぶ。読みやすく、ロジックとしては正しく見えます。
しかし、複数のスレッドから同じ要素を同時に add? すると期待どおりに動作しません。add? の中身は 「include? で確認してから、add で追加する」 という独立した 2 回のメソッド呼び出しで、その間に他のスレッドが割り込めるためです。本来は「最初に追加できた 1 スレッドだけが self を返し、残りは nil を返す」のが期待される動作ですが、両者がともに self を返してしまうケースが起きます。
時系列で追うと、次のような順番で起きています（以下の @hash は冒頭の擬似コードに登場した、Set が内部で抱える Hash インスタンスを指します）。
# 初期状態
@hash = {}
# (1) Thread A と Thread B が同時に include?(x) を実行
Thread A: include?(x) # => false
Thread B: include?(x) # => false ← 両スレッドが x が Set に存在しないことを確認
# (2) Thread A が add(x) を実行
Thread A: add(x) # @hash[x] = true
# @hash == { x => true }
Thread A: return self # ✓ 新規追加なので self
# (3) Thread B も add(x) を実行
Thread B: add(x) # @hash[x] = true（無条件で上書き）
Thread B: return self # ✗ 本来は nil（B は新規追加していない）
この問題は Set 側だけでは修正できず、Hash 側に「存在しなければ追加する」というアトミックな API を入れる必要がありました。過去にもそうした提案は何度かあったものの、Ruby 本体には取り込まれてこなかった、と Jeremy さんはセッションでおっしゃっていました。
加えて、「ハッシュ計算が 2 回走る（include? と add の両方で）」というパフォーマンス上の小さい問題も抱えていました。
解決アプローチ：Hash から不要な要素を削った C クラスを新設する
タイトルにすでに表れているように、Ruby 4.0 で取られたアプローチは「Hash の C 実装を活かしつつ、Set のために不要な部分を削ぎ落とした新しい C クラスを作る」というものでした。「Hash に手を入れて Set のために API を増やす」のではなく、Hash と独立した実装を C レベルで持つことで、Set 用に好きな API を自由に設計できる状態にした、ということです。
具体的には次の 2 段構えで、先ほどの 2 つの問題に対応しています。
- 問題 1 への対応 — Set 専用のハッシュテーブル
set_tableを新設し、recordを削ってメモリ消費を抑える - 問題 2 への対応 —
add?を 1 回の C 関数呼び出しに集約し、スレッドセーフ性を確保する（あわせてパフォーマンスも改善）
それぞれ順に見ていきます。
問題 1 への対応：Set 専用のハッシュテーブルを新設する
Ruby 4.0 ではまず、Hash 用の st_table を 丸ごとコピー して、Set 用の set_table を新しく作りました。
1) entry から record を削る
最初の変更は、エントリ構造体から record フィールドを削除することです。
/* Before（Hash 用） */ struct st_table_entry { st_hash_t hash; st_data_t key; st_data_t record; }; /* After（Set 用、新設） */ struct set_table_entry { st_hash_t hash; st_data_t key; };
これだけで、エントリ 1 つあたりのサイズが 1/3 減ります。問題 1 の解消はここから始まります。
2) 関数も set_* プレフィックスに置き換えてコピーする
エントリだけでなく、テーブル本体の構造体（st_table → set_table）もコピーして作り直されています。テーブルを操作する関数群（st_init_table → set_init_table など）も同様です。多くは引数の型と関数名を置き換えるだけのシンプルな変換でした。一方で「record を扱うコードを丸ごと削る」必要がある関数もあり、手間がかかったものもあったと話されていました。セッションでは、テーブル関連の変換作業は全体の工数のおよそ 3 割だったそうです。結果として st_table と set_table という似た構造の C コードが 2 系統並ぶことになり、その分のメンテナンスコストを抱える形にはなっています。
問題 2 への対応：add? を 1 回の C 関数に集約する
続いて Set#add? の新しい C 実装を見ていきます。Ruby から add? を呼ぶと set_i_add_p が呼ばれます。
static VALUE set_i_add_p(VALUE set, VALUE item) { rb_check_frozen(set); if (set_iterating_p(set)) { if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) { no_new_item(); } return Qnil; } else { return set_insert_wb(set, item) ? Qnil : set; } }
if 節は反復中の Set に対する新規追加を防ぐためのガードで、本記事の主眼ではないため割愛します。注目したいのは else ブロック内の return set_insert_wb(set, item) ? Qnil : set; の 1 行です。先ほど挙げた問題 2（スレッドセーフ性）の解消と、あわせてパフォーマンス改善が、ここに凝縮されています。
スレッドセーフ性
return set_insert_wb(set, item) ? Qnil : set;
set_insert_wb は内部で「新規追加なら 0、要素が既にあれば 0 以外（非 0）を返す」関数です（set_insert のソースコメントに明記）。結果として「既存なら Qnil、新規追加なら set（= self）」を返す形になっており、「存在確認と追加」が 1 回の呼び出し にまとまっています。
これが C で書かれていることが効いています。CRuby には GVL（Global VM Lock。Ruby コードの同時実行を防ぐ大域ロック）があり、C 関数はデフォルトでこの GVL を保持したまま実行されます。set_i_add_p は内部で GVL を手放さないため、実行中に他の Ruby スレッドが割り込んで Ruby コードを動かすことはありません。結果として「存在確認 → 追加」がアトミックに実行されます。標準ライブラリ版の add? は Ruby メソッドの呼び出しを 2 回（include? と add）行っていたため、その間に他のスレッドが割り込めてしまっていました。「呼び出し回数を 2 から 1 にした」だけで、スレッドセーフの問題が解消されています。
パフォーマンス
ハッシュテーブルへのアクセスが 1 回になると、ハッシュ値の計算も 1 回で済みます。標準ライブラリ版は include? でハッシュを計算してバケットを探索し、add でも同じ処理を繰り返していました。ここのオーバーヘッドが消えるので、add? は標準ライブラリ版より速くなる、という副次効果もあります。
副次的に得られた利点：Ruby インタプリタ自身も恩恵を受けている
ここまで「ユーザーが使う Set クラスの改善」の話をしてきましたが、実は今回の変更で恩恵を受けているのは私たちが普段 Ruby を使うときだけに留まりません。
Ruby インタプリタ自身も、内部で「全部の値が true の Hash」を使っている箇所がいくつかありました。Core Set 導入後、Jean Boussier（@byroot）さんがそれらを set_table で置き換えるパッチを送り、スライドでは具体例として次の 2 箇所が紹介されていました。
- 定数キャッシュ —
MyClass::FOOのような定数参照を高速化するためのキャッシュ。「この定数名はキャッシュ済み」というフラグだけ覚えていれば良く、値は不要 - 未使用ブロック警告 — 「ブロックを取らないメソッドにブロックが渡された」という警告で、同じ場所を 2 回警告しないため、警告済みの位置を覚えておく必要がある。位置だけで値は不要
共通点は 「キーの集合だけ覚えたい、値はいらない」 という用途です。set_table ができるまでは、これらの用途でも Hash（つまり st_table）を使い、record フィールドを未使用のまま確保し続けていました。
感想
Set のコアクラス化を読み解いて特に印象的だったのは、「メモリ削減」というメリットを追求する過程で、長年「Hash の上に被せた Set」という便宜的な構造が解きほぐされていった点でした。Hash と Set はそれぞれの責務に沿った必要十分な実装として、独立したクラスへ整理し直されています。結果的に st_lookup ↔ set_table_lookup、st_insert ↔ set_insert などほぼ同じ実装の関数が約 40 組並ぶ形になり、メンテナンスのコストはほぼ 2 倍に膨らむと考えられます。それでも、性能改善や責務に沿った整理といったメリットを得るためなら、冗長性やメンテナンスコストは厭わない——そういう判断が Ruby 本体のような場所でも普通に行われていると知り、印象に残りました。
今回は私にとって初めての RubyKaigi 参加でした。事前に新卒のメンバーで『Ruby のしくみ』を読み込んで臨み、本セッションでも st_table 周辺の話は既視感がありイメージしながら聴くことができました。一方で、英語のセッションを含め、その場で十分に咀嚼しきれなかったものが大多数で不完全燃焼なまま終わってしまったのが正直な感想です。来年までに Ruby への理解と英語力の両方をもう一段深めて、より多くをその場で持ち帰れる状態でまた RubyKaigi に挑戦したいと考えています。最後になりますが、発表者の Jeremy Evans さんに感謝を申し上げます。
関連リソース
- セッションスライド: code.jeremyevans.net/presentations/rubykaigi2026/
- 公式セッションページ: rubykaigi.org/2026/presentations/jeremyevans0.html
- Ruby 本体ソース:
set.c（Set クラスの Ruby API 実装）／set_table本体の派生実装はst.cの末尾に同居している
Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。
