Rubyの(小さな)ハッシュを高速化する
Speeding Up (Small) Ruby Hashes (byroot.github.io)
要約
この記事は、RubyのHashクラスが要素数8個以下の場合、実際にはハッシュテーブルではなくペアの配列として実装されていることを解説しています。この配列ベースの実装(ar_table)は、要素数が増えると線形探索(O(n))になるため、パフォーマンスが低下します。しかし、SWAR(SIMD Within A Register)のような技術を用いることで、この線形探索を高速化し、O(1)に近いパフォーマンスを実現する可能性が示唆されています。
全文翻訳
Rubyの(小さな)ハッシュの高速化
告白しなければならないのは、私はブログ記事を書くのが本当に嫌いだということです。カンファレンスでの発表ほどではありませんが、私にとっては歯を抜くような活動のリストの上位にあります。結果に誇りを持っていないわけではありません。もちろん誇りを持っています。しかし、書くプロセスは私にとって非常に苦痛です。特に最初の文はそうですが、記事が進むにつれて少しずつ楽になります。
それでも、私は自分自身を駆り立ててそれを実行します。なぜなら、それは問題について考える助けになり、頭の中の知識を「コンパイル」するのに役立つからです。間違ったことや不正確なことを投稿することを非常に恐れているため、長年抱いてきた仮定を再確認したり、実装の詳細を掘り下げたりする傾向があります。
そして非常に頻繁に、記事を公開した直後に、以前は見落としていた新しいアイデアを思いつきます。この記事は、Rubyのハッシュを縮小するという前の記事を公開した直後に思いついたアイデアの一つについてです。まだ読んでいない場合は、ぜひ読んでください。この記事はそれの直接の続きです。
ARテーブルはハッシュテーブルではない
前の記事の主な結論の1つは、RubyのHashクラスは、その名前が示唆するように、8エントリまでは真のハッシュテーブルではないということです。代わりに、それは文字通りのペアの配列です。そのデータ構造を見てみましょう。
#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はキーと値のペアを含む配列です。
前の記事で述べたように、hintは本質的に単一バイトのハッシュコードです。Rubyでは、ハッシュコードは8バイト長であり、st_table(実際のハッシュテーブル実装)でバックされている場合、ハッシュコード全体が格納され比較されます。
しかし、メモリを節約するために、ar_tableはハッシュコードの下位バイトのみを格納します。根本的には、これは何も変更しませんが、ハッシュの衝突の可能性を高めるだけです。しかし、8つ以上のキーを持つことがないことがわかっている場合は、これは許容できるトレードオフです。
もしar_tableをRubyで実装するとしたら、{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? またはスレッドがハッシュを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)検索です。検索したいキーのhintを受け取り、テーブルリスト内で線形に検索します。
一致が見つかった場合、衝突に対処する必要があるため、Object#eql?(ar_equal)を呼び出します。それが偽を返した場合、配列の終わりに達するまで検索を続けます。
この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.5xですが、それでも無視できません。
繰り返しになりますが、最大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バイトを見ており、これはCPUレジスタのサイズと正確に一致するため、SWAR(SIMD Within A Register)に最適です。
以前、SIMD(および偶然にもSWAR)とは何かについての簡単な説明を投稿しましたので、ここでは繰り返しません。
しかし、アイデアの核心は、ar_hintを8つの1バイト長の数値のリストとして解釈するのではなく、単一の8バイト数値として解釈できるということです。そして、オーバーフローしないように注意する限り、これらのすべてのバイトに対して一度に同じ操作を実行できます。
これは一般的なトリックであり、Wikipediaの記事ではNULLバイトを8バイト数値内で見つける方法が直接示されています。
#include <stdio.h>
#include <stdint.h>
static void has_null_byte(uint64_t word)
{
uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
uint64_t x8 = x7 | word;
uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
if (~matches) {
printf("0x%llx has a NULL byte\n", word);
}
else {
printf("0x%0llx does not have a NULL byte\n", word);
}
}
int main(int argc, char **argv)
{
has_null_byte(0x1020304050607080);
has_null_byte(0x1020304000607080);
return 0;
}
0x1020304050607080 does not have a NULL byte
0x1020304000607080 has a NULL byte
上記の例は魔法のように聞こえるかもしれませんが、分解してみましょう。
最初のステップはword & 0x7f7f7f7f7f7f7f7f、つまりバイトにスコープするとbyte & 0x7f(127)、バイナリ形式ではbyte & 0b01111111です。つまり、各バイトの最上位ビットを削除します。これは、次の操作がオーバーフローするのを防ぐために必要です。
次に、各バイトに同じ0x7f値を加算します。アイデアは、0x7fが0b01111111であるため、バイトに0以外の値が含まれている場合、加算キャリーによって最上位ビットが1に設定されるということです。
e.g.
0b00000000 + 0b01111111 = 0b011111110b00000001 + 0b01111111 = 0b100000000b00000010 + 0b01111111 = 0b10000001- …
したがって、下位7ビットのいずれかがセットされていたすべてのバイトは、8番目のビットもセットされるようになります。しかし、最初のビットごとのANDで最上位ビットが破棄された0x80 / 0b10000000を特別に処理する必要があります。
その最上位ビットを復元するために、元の値(x7 | word)でビットごとのORを実行します。したがって、元のバイトが0x80だった場合、そのライフサイクルは次のようになります。
0x80 | 0b10000000 // start
0x00 | 0b00000000 // & 0x7f
0x7f | 0b01111111 // + 0x7f
0x8f | 0b11111111 // | 0x80 aka 0b10000000
その時点で、ゼロだったバイト以外のすべてのバイトは最上位ビットがセットされています。したがって、バイトのいずれかがゼロだったかどうかという質問に答えるために、最上位ビットのみを保持し(x8 | 0x7f7f7f7f7f7f7f7f)、その後すべてを反転(NOT、~matches)できます。
結果として、0x00バイトは0x80 / 0b10000000になり、他のすべてのバイトは0x00になります。つまり、8バイトのいずれも最初からゼロでなかった場合、結果の数値は0になります。これがブール条件です。
さらに良いことに、最上位ビット以外のすべてのビットが常に0であることを知っているので、少なくとも1つのバイトがNULLだったかどうかという質問に答えるだけでなく、ビットインデックスからバイトインデックスを導き出すことさえできます。
ゼロのカウント
ビットマップは一般的であるため、CPUにはffs(Find First Set)、ctz(Count Trailing Zeros)、またはntz(Number of Trailing Zeros)のような専用の命令がある傾向があります。
しかし、ここではエンディアンネスに注意する必要があります。
数値0x1020304050607080を考慮すると、バイト配列として解釈した場合、次のようになると考えるかもしれません。
char ary[8] = { 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x80 };
これは、左から右への言語を使用する人間にとっては、ある程度自然です。結局のところ、それが私たちが数値を書く方法です。
しかし実際には、それはビッグエンディアンアーキテクチャでのみ真実であり、今日では非常にまれです。
ほとんどの最新のコンピュータはリトルエンディアンであり、基本的に数値を右から左に格納および読み取ることを意味します。したがって、上記の配列は実際には次のようになります。
char ary[8] = { 0x80, 0x70, 0x60, 0x50, 0x40, 0x30, 0x20, 0x10 };
したがって、必要なインデックスは最下位バイトから始まる必要があります。
そのため、CPUエンディアンネスに応じて異なる関数を使用する必要があります。ほとんどのアーキテクチャでは、最下位バイトからカウントを開始したいので、ntz(Trailing Zerosの数)を使用したいです。一方、Rubyがサポートする数少ないビッグエンディアンアーキテクチャでは、nlz(Leading Zerosの数)をカウントしたいです。
また、これらはビットをカウントしているため、結果を8で割る必要があります。実際にはCHAR_BITで割る必要があります。これはほとんどの場合8ですが、理論的には何でも許可されます。
32ビットアーキテクチャもサポートする必要があることを考慮すると、次のようなマクロになります。
#if SIZEOF_VALUE == 8
#ifdef WORDS_BIGENDIAN
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (nlz_int64(x) / CHAR_BIT)
#else
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (ntz_int64(x) / CHAR_BIT)
#endif
#else
#ifdef WORDS_BIGENDIAN
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (nlz_int32(x) / CHAR_BIT)
#else
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (ntz_int32(x) / CHAR_BIT)
#endif
#endif
これはRuby自体の他の多くのdefineに依存していますが、それほど興味深いものではないので掘り下げません。
言及する価値があるのは、一般的に整数除算は比較的遅い操作ですが2、この場合、定数8で割ることがほぼ確実にわかっているので、自己尊重のあるCコンパイラならすべて右シフト操作に最適化します:x / 8 == x >> 3。そして右シフトは非常に高速です。
したがって、NULLバイトがあるかどうかを判断できるだけでなく、その位置も導き出すことができます。
static void first_null_byte(uint64_t word)
{
uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
uint64_t x8 = x7 | word;
uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
uint64_t indexes = ~matches;
if (indexes) {
printf("0x%llx has a NULL byte at index %u\n", word, __builtin_ctzll(indexes) / CHAR_BIT);
}
else {
printf("0x%0llx does not have a NULL byte\n", word);
}
}
int main(int argc, char **argv)
{
first_null_byte(0x1020304050607080);
first_null_byte(0x1020304000607080);
return 0;
}
0x1020304050607080 does not have a NULL byte
0x1020304000607080 has a NULL byte at index 3
しかし、さらに良いことに、indexes変数は、その名前が示すように、最初のNULLバイトの位置だけでなく、すべてのNULLバイトの位置も含まれています。次の位置にアクセスするには、最下位ビットをクリアするだけで済みます。これを実行する一般的なトリックは次のとおりです。
x & (x - 1)
これは、-1がバイナリで最下位ビットをゼロに変換する一方で、別の下位ビットを上げる可能性があるため機能します。したがって、その結果をANDビットマスクとして使用すると、次のようになります。
>> puts 42.to_s(2)
101010
=> nil
>> puts (42 - 1).to_s(2)
101001
=> nil
>> puts (42 & (42 - 1)).to_s(2)
101000
static void find_null_bytes(uint64_t word)
{
uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
uint64_t x8 = x7 | word;
uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
uint64_t indexes = ~matches;
printf("0x%0llx ------------------------\n", word);
if (!indexes) {
printf("does not have a NULL byte\n");
return;
}
while (indexes) {
printf("NULL byte at index %u\n", __builtin_ctzll(indexes) / CHAR_BIT);
indexes &= indexes - 1;
}
}
int main(int argc, char **argv)
{
find_null_bytes(0x1020304050607080);
find_null_bytes(0x1000304000607000);
return 0;
}
0x1020304050607080 ------------------------
does not have a NULL byte
0x1000304000607000 ------------------------
NULL byte at index 0
NULL byte at index 3
NULL byte at index 6
マスクの作成
この時点で、ステップを飛ばしたと思っているかもしれません。配列内でNULLバイトを高速に見つけることができるのは素晴らしいですが、ar_tableのヒントは任意の値であり、0ではありません。
したがって、この小さな関数が役立つようにするには、まず、関心のある一致するバイトをゼロに、他のバイトを非ゼロに変換する必要があります。
論理ゲートに慣れているなら、XORを認識したかもしれません。必要なのは、すべてのヒントバイトを検索したい値、たとえば0x42とXORすることです。
>> 0x42 ^ 0x42
=> 0
>> 0x11 ^ 0x42
=> 83
>> 0x00 ^ 0x42
=> 66
しかし、XORするバイトが8つあるため、まず0x4242424242424242マスクを作成する必要があります。これは、乗算で簡単に実行できます。
>> puts (0x0101010101010101 * 0x42).to_s(16)
4242424242424242
再び、すべてをまとめると、次のようになります。
static void find_bytes(uint8_t needle, uint64_t haystack)
{
uint64_t search_mask = 0x0101010101010101 * needle;
uint64_t word = haystack ^ search_mask;
uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
uint64_t x8 = x7 | word;
uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
uint64_t indexes = ~matches;
printf("0x%x in 0x%0llx ------------------------\n", needle, haystack);
if (!indexes) {
printf("miss\n");
return;
}
while (indexes) {
printf("hit at index %u\n", __builtin_ctzll(indexes) / CHAR_BIT);
indexes &= indexes - 1;
}
}
int main(int argc, char **argv)
{
find_bytes(0x42, 0x1020304050607080);
find_bytes(0x42, 0x1042304200607000);
return 0;
}
0x42 in 0x1020304050607080 ------------------------
miss
0x42 in 0x1042304200607000 ------------------------
hit at index 4
hit at index 6
Rubyへの統合
作業アルゴリズムができたので、それをRubyに統合する必要がありました。
私の最初の試みは次のようになりました。
static unsigned
ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key)
{
VALUE matches = ar_search_hint(hint, RHASH_AR_TABLE(hash)->ar_hint.word);
unsigned i;
while ((i = ar_search_position(matches)) < RHASH_AR_TABLE_BOUND(hash)) {
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;
}
matches &= matches - 1;
}
return RHASH_AR_TABLE_MAX_BOUND;
}
基本的に、上記のfind_bytes関数がforループを置き換えます。残念ながら、それは機能しませんでした。さらに悪いことに、Rubyはまずminirubyと呼ばれる最小限のRubyバージョンをコンパイルし、それを使用してビルドスクリプトを実行するため、Hashの実装を壊してしまったため、一部のビルドスクリプトが失敗しました。
私が見落としていたのは、前述したように、ar_equalが任意のオブジェクトに対してHash#eql?を呼び出すことです。オブジェクトは独自のeql?メソッドを定義できるため、任意のコードを呼び出すことになり、現在検索中のHashをミューテートするなど、奇妙なことを行う可能性があります。
したがって、ここでの間違いは、ar_equalを呼び出すたびにmatchesの結果を信頼できなくなることです。ar_hintが変更されたかどうかを確認するか、完全に再計算することで、再検証する必要があります。
そのため、forの条件はi < RHASH_AR_TABLE_BOUND(hash)となっています。ループの境界をローカル変数に格納する方がパフォーマンスが良いと自然に考えるかもしれませんが、イテレーション中にテーブルの境界が変更される可能性があるため、それはできません。
しかし、結局、複雑すぎる価値はないと思いました。ar_tableは非常に小さいため、衝突について心配する必要はほとんどありません。衝突が発生した場合でも、線形検索のコストはそれほど悪くありません。
そこで、最初のマッチにスキップするように変更しました。
// 見つかった場合はビンインデックスを返し、見つからなかった場合はRHASH_AR_TABLE_MAX_BOUNDを返し、
// #eql? またはスレッドがハッシュを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 = ar_hint_first_match(hint, RHASH_AR_TABLE(hash)->ar_hint.word); 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;
}
そして、ベンチマークの結果はかなり良好でした。
| |compare-ruby|built-ruby|
|:-----------|-----------:|---------:|
|hit_first | 14.783M| 13.635M|
| | 1.08x| -|
|hit_fourth | 13.139M| 13.877M|
| | -| 1.06x|
|hit_last | 11.343M| 13.801M|
| | -| 1.22x|
|miss | 11.096M| 16.892M|
| | -| 1.52x|
ここで私が気に入ったのは、最初のキーにヒットした場合でも、パフォーマンスが同一になったことです。ミスの場合も非常に顕著に高速になりました。
しかし、最初のキーにヒットした場合のパフォーマンスの低下には少し悩まされました。前の記事で述べたように、非常に小さなハッシュは一般的であるため、約8%遅いというのはひどいものではありませんが、避けたいところです。
そして、いつものように、私はハッピーパスの最適化に焦点を当てました。コードを見ると、最初のイテレーションでは、if (hints[i] == hint) {という条件は完全に冗長です。hints[i] == hintであることをすでに確立しているので、不要なオーバーヘッドであるだけでなく、条件にあることが分岐予測器を混乱させます。
そこで、最初のマッチを専門化することにしました。
static unsigned
ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key)
{
unsigned first_match = ar_hint_first_match(hint, RHASH_AR_TABLE(hash)->ar_hint.word);
if (LIKELY(first_match >= RHASH_AR_TABLE_BOUND(hash))) {
return RHASH_AR_TABLE_MAX_BOUND;
}
RUBY_ASSERT(RHASH_AR_TABLE(hash)->ar_hint.ary[first_match] == hint);
int eq = ar_equal(key, RHASH_AR_TABLE_REF(hash, first_match)->key);
if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) {
return RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE;
}
if (LIKELY(eq)) {
return first_match;
}
else {
for (unsigned i = first_match + 1; i < RHASH_AR_TABLE_BOUND(hash); i++) {
const ar_hint_t *hints = RHASH_AR_TABLE(hash)->ar_hint.ary;
if (UNLIKELY(hints[i] == hint)) {
eq = ar_equal(key, RHASH_AR_TABLE_REF(hash, i)->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;
}
コードは著しく増えましたが、分岐予測器にとって非常に友好的になり、ルックアップが高速化されました。最初のキーであってもです。
| |compare-ruby|built-ruby|
|:-----------|-----------:|---------:|
|hit_first | 13.891M| 15.085M|
| | -| 1.09x|
|hit_third | 13.322M| 15.065M|
| | -| 1.13x|
|hit_fourth | 12.759M| 14.410M|
| | -| 1.13x|
|hit_last | 11.545M| 15.275M|
| | -| 1.32x|
|miss | 10.872M| 16.286M|
| | -| 1.50x|
私のパッチを適用して最初のベンチマークを実行すると、Niceで定数時間パフォーマンスが見られます。
ruby 4.1.0dev (2026-08-13T12:08:01Z ar-find-entry-swar-2 a62abe3f4c) +YJIT +PRISM [arm64-darwin25]
ar-hit-0 13.973M (± 0.3%) i/s (71.57 ns/i) - 70.048M in 5.013198s
ar-hit-1 14.029M (± 0.1%) i/s (71.28 ns/i) - 70.743M in 5.042555s
ar-hit-2 14.013M (± 0.3%) i/s (71.36 ns/i) - 70.121M in 5.003860s
ar-hit-3 13.981M (± 0.1%) i/s (71.53 ns/i) - 70.910M in 5.071933s
ar-hit-4 14.011M (± 0.5%) i/s (71.37 ns/i) - 71.328M in 5.090874s
ar-hit-5 14.081M (± 0.2%) i/s (71.02 ns/i) - 70.663M in 5.018430s
ar-hit-6 14.010M (± 0.6%) i/s (71.38 ns/i) - 70.308M in 5.018301s
ar-hit-7 13.998M (± 0.3%) i/s (71.44 ns/i) - 70.268M in 5.019812s
ar-miss 16.053M (± 1.0%) i/s (62.30 ns/i) - 80.447M in 5.011457s
Comparison:
ar-hit-0: 13972808.8 i/s
ar-miss : 16052554.8 i/s - 1.15x faster
ar-hit-5: 14080711.5 i/s - 1.01x faster
ar-hit-1: 14029245.1 i/s - same-ish: difference falls within error
ar-hit-2: 14013320.9 i/s - same-ish: difference falls within error
ar-hit-4: 14011018.5 i/s - same-ish: difference falls within error
ar-hit-6: 14010319.4 i/s - same-ish: difference falls within error
ar-hit-7: 13998111.9 i/s - same-ish: difference falls within error
ar-hit-3: 13980914.6 i/s - same-ish: difference falls within error
そして、おまけとして、ar_tableは常にst_tableよりも高速になりました。
ruby 4.1.0dev (2026-08-13T12:08:01Z ar-find-entry-swar-2 a62abe3f4c) +YJIT +PRISM [arm64-darwin25]
ar-hit-7 13.975M (± 0.2%) i/s (71.55 ns/i) - 69.920M in 5.003078s
st-hit-7 10.884M (± 0.5%) i/s (91.88 ns/i) - 54.857M in 5.040316s
Comparison:
ar-hit-7: 13975351.4 i/s
st-hit-7: 10883687.8 i/s - 1.28x slower
まだ私のパッチをマージしていませんが、この時点でマージしない理由はほとんど見当たらないので、きれいに片付ける必要があります。
-
いつものように、話を簡単にするために、投稿全体で64ビットアーキテクチャを想定します。↩
-
Turing Completeをプレイしたことがあるなら、それを感じることができるかもしれません。↩