Rubyの（小さな）ハッシュを高速化する

私がこれらのブログ記事を書くのが本当に嫌いだということは、告白しなければならないことです。カンファレンスでの講演ほどではありませんが、私にとっては歯を抜くような活動のリストの上位にあります。結果に誇りを持っていないわけではありません。絶対に誇りを持っています。しかし、それらを書くプロセスは私にとって非常に苦痛です。特に最初の文はそうですが、記事が進むにつれて少し楽になります。それでも、私は自分自身にそれを強います。なぜなら、それは問題について考えるのに役立ち、私の頭の中で知識を「コンパイル」するからです。間違ったことや不正確なことを投稿することを恐れるあまり、長年持っていた仮定を再確認したり、実装方法についてさらに詳しく掘り下げたりする傾向があります。そして非常に頻繁に、投稿を公開した直後に、以前は見落としていた新しいアイデアを思いつきます。この記事は、Rubyのハッシュを縮小するという以前の記事を公開した直後に思いついたアイデアの1つについてです。まだ読んでいない場合は、ぜひ読んでください。この投稿はそれの直接の続きです。ARテーブルはハッシュテーブルではない以前の記事の主なテイクアウトの1つは、8個のエントリまで、RubyのHashクラスは、その名前が示唆するように、実際にはハッシュテーブルではないということです。代わりに、それは文字通りペアの配列です。そのデータ構造を見てみましょう：#define RHASH_AR_TABLE_MAX_SIZE SIZEOF_VALUE typedef unsigned char ar_hint_t; typedef struct ar_table_pair_struct { VALUE key; VALUE val; } ar_table_pair; typedef struct ar_table_struct { union { ar_hint_t ary[RHASH_AR_TABLE_MAX_SIZE]; VALUE word; } ar_hint; /* 64bit CPU: 8B * 2 * 8 = 128B */ ar_table_pair pairs[RHASH_AR_TABLE_MAX_SIZE]; } ar_table; Cは、初心者には少し難解かもしれませんが、説明させてください。VALUEはRubyオブジェクトの参照、基本的にポインタであり、8バイトです。1 ar_hintは8バイト長で、8バイトの配列または単一の8バイト（64ビット）整数として解釈できます。pairsは、キーと値のペアを含む配列です。前の記事で述べたように、ヒントは基本的に単一バイトのハッシュコードです。Rubyでは、ハッシュコードは8バイト長であり、st_table（実際のハッシュテーブル実装）によってバックアップされる場合、ハッシュコード全体が格納され比較されます。しかし、メモリを節約するために、ar_tableはハッシュコードの下位バイトのみを格納します。根本的に、それは何も変更しませんが、ハッシュの衝突の可能性を高めるだけですが、8個以上のキーを持つことがないことを知っている場合は、許容できるトレードオフです。Rubyでar_tableを実装するとした場合、{a: 1, b: 2, c: 3}の構造は次のようになるかもしれません：class ARTable def initialize @ar_hint = [0x34, 0x65, 0x72] @pairs = [:a, 1, :b, 2, :c, 3] end end では、前の記事を執筆中に詳しく調べたが、それ以前は深く考えたことのなかったar_tableルックアップルーチンのコアを見てみましょう：// 見つかった場合はビンインデックスを返し、見つからなかった場合はRHASH_AR_TABLE_MAX_BOUNDを返します、// または、#eql?またはThreadがハッシュをst_tableに変換した場合はRHASH_AR_TABLE_CONVERTED_TO_ST_TABLEを返します。static unsigned ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key) { for (unsigned i = 0; i < RHASH_AR_TABLE_BOUND(hash); i++) { const ar_hint_t *hints = RHASH_AR_TABLE(hash)->ar_hint.ary; if (hints[i] == hint) { ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i); int eq = ar_equal(key, pair->key); if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) { return RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE; } if (eq) { return i; } } } return RHASH_AR_TABLE_MAX_BOUND; } 見てわかるように、これは基本的に線形、つまりO(n)の検索です。検索するキーのヒントを受け取り、テーブルリストで一致を線形に検索します。一致が見つかった場合、衝突を考慮する必要があるため、Object#eql?（ar_equal）を呼び出し、falseを返した場合は、配列の終わりに達するまで検索を続けます。このO(n)パフォーマンスは、実験的に検証できます：require 'benchmark/ips' ar = {a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8}.freeze Benchmark.ips do |x| x.report("ar-hit-0") { ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a] } x.report("ar-hit-1") { ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b] } x.report("ar-hit-2") { ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c] } x.report("ar-hit-3") { ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d] } x.report("ar-hit-4") { ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e] } x.report("ar-hit-5") { ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f] } x.report("ar-hit-6") { ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g] } x.report("ar-hit-7") { ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h] } x.report("ar-miss ") { ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X] } x.compare!(order: :baseline) end ruby 4.1.0dev (2026-08-11T14:41:10Z c-api-shareable-co.. ab6b8ceaac) +YJIT +PRISM [arm64-darwin25] ar-hit-0 14.188M (± 0.8%) i/s (70.48 ns/i) - 71.928M in 5.069797s ar-hit-1 13.247M (± 0.3%) i/s (75.49 ns/i) - 67.139M in 5.068423s ar-hit-2 11.890M (± 0.4%) i/s (84.11 ns/i) - 60.027M in 5.048655s ar-hit-3 11.119M (± 1.7%) i/s (89.94 ns/i) - 56.290M in 5.062484s ar-hit-4 10.456M (± 1.5%) i/s (95.64 ns/i) - 53.056M in 5.074381s ar-hit-5 10.018M (± 0.4%) i/s (99.82 ns/i) - 50.464M in 5.037463s ar-hit-6 9.380M (± 2.9%) i/s (106.61 ns/i) - 47.215M in 5.033578s ar-hit-7 8.983M (± 0.6%) i/s (111.32 ns/i) - 45.158M in 5.026746s ar-miss 9.163M (± 1.9%) i/s (109.14 ns/i) - 46.161M in 5.037831s Comparison: ar-hit-0: 14187571.6 i/s ar-hit-1: 13246581.8 i/s - 1.07x slower ar-hit-2: 11889678.7 i/s - 1.19x slower ar-hit-3: 11118989.8 i/s - 1.28x slower ar-hit-4: 10455642.8 i/s - 1.36x slower ar-hit-5: 10017678.5 i/s - 1.42x slower ar-hit-6: 9379948.0 i/s - 1.51x slower ar-miss : 9162845.7 i/s - 1.55x slower ar-hit-7: 8983492.7 i/s - 1.58x slower 予想通り、8番目のキーをルックアップするのは、最初のキーをルックアップするよりも明らかに遅いです。Ruby側で測定すると、仮想マシンのディスパッチなどの固定コストのオーバーヘッドがあるため、測定された差はわずか約1.5倍ですが、それでも重要です。ここでも、最大8個のエントリしか扱わないことを考えると、O(n)アルゴリズムで問題ありません。この特定のケースでは、線形検索のパフォーマンスは、ハッシュがst_tableでバックアップされている場合とそれほど大きくは変わりません：require 'benchmark/ips' ar = {a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8}.freeze # 容量が8を超えるハッシュを作成すると、`st_table`が得られます st = Hash.new(capacity: 9).merge(ar).freeze Benchmark.ips do |x| x.report("ar-hit-7") { ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h] } x.report("st-hit-7") { st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h] } x.compare!(order: :baseline) end ruby 4.1.0dev (2026-08-11T14:41:10Z c-api-shareable-co.. ab6b8ceaac) +YJIT +PRISM [arm64-darwin25] ar-hit-7 8.967M (± 1.9%) i/s (111.52 ns/i) - 45.030M in 5.021777s st-hit-7 10.574M (± 0.1%) i/s (94.57 ns/i) - 53.527M in 5.061952s Comparison: ar-hit-7: 8966929.4 i/s st-hit-7: 10574312.0 i/s - 1.18x faster したがって、ar_tableとst_tableを使用するのは、典型的なスペース対時間のトレードオフです。しかし、ほとんどの人がハッシュテーブルについて考えるとき、O(1)アクセスを考えます。そのため、少し間違っているように感じます。しかし、ar_tableのルックアップもO(1)にすることはできないでしょうか？SWAR検索ar_find_entry_hintのコアは、8個の整数配列で特定の整数を検索するループです。しかし、別の角度から見ると、それは8バイトの配列、つまり文字列内の特定のバイト、別名文字を検索しています。文字列内の文字を効率的に検索することは、json gemで多く行ってきたことであり、このブログで以前にも触れたことです。バイトごとに文字列を検索するのは非常に無駄です。なぜなら、各バイトを反復処理するコストは、そのバイトを比較するコストをはるかに上回る傾向があるからです。そして、このケースでは、8バイト、つまり正確にサイズを見ています。