← 2025-12-30 の一覧へ戻るホーム
高性能C++ハッシュテーブル：SIMDメタデータグループスキャンを用いた実装

2025/12/24 9:27

高性能C++ハッシュテーブル：SIMDメタデータグループスキャンを用いた実装

RSS: https://news.ycombinator.com/rss

元のHacker News記事へ ↗
要約▶

Japanese Translation:

GroupedSIMDElasticは、軽量でヘッダーオンリーのC++17ハッシュテーブルです。500 k要素を超える大規模テーブルに対して、現在最先端とされる

ankerl::unordered_dense
よりも優れた性能を発揮します。この性能は、各スロットあたり1バイトのメタデータ（ビット7が占有済みフラグ、ビット0–6に7ビットハッシュフラグメント）を格納し、16個の連続したスロットを「クワドラティックジャンプパターン」（
h + 16×n²
）で探索することで実現します。SIMDスキャンはキー比較前に約127/128件の非一致を除外し、1 M要素時に最大で約1.5倍速い検索（61.5 ms対104 ms）が可能です。一方、挿入性能はやや遅くなるものの（70.1 ms対50.8 ms）、それでも同等か僅かに劣ります。APIには
insert
、
find
、
contains
、
operator[]
が含まれ、
size()
、
capacity()
、
load_factor()
、
max_probe_used()
などの統計情報も提供します。

実装はSSE2のみを必要とし、外部依存はなくMITライセンスで配布されています。Google の Swiss Tables および 2025年2月に発表された「Elastic Hashing」論文（Yao の均一探索仮説を否定したもの）からインスピレーションを得ています。実験結果では、散在型 SIMD ガザリはグループ化探索より約5倍遅いことも示されています。

現在の制限点としては、挿入オーバーヘッドが高い、削除機能がない、固定容量（リサイズ不可）、ARM NEON サポートが欠如していることがあります。将来的にはこれらの機能追加とプラットフォーム対応拡張を予定しています。ソースファイルは 

grouped_simd_elastic.hpp
、ベンチマークおよびドキュメント用に 
hybrid_elastic.hpp
（基準実装）、
benchmark_final_sota.cpp
、
INSIGHTS.md
、
EXPERIMENT_RESULTS.md
です。

本文

グループ化された SIMD ハッシュテーブル – スケールでの最先端ハッシング

Dimitris Mitsos & AgentsKB.com によって作成

概要

高性能な C++ ハッシュテーブルで、テーブルサイズが約 500 k 要素を超え、ワークロードが検索中心の場合に、最先端（Robin Hood）実装 ankerl::unordered_dense を上回ります。主なアイデアは グループ化プロービング：16 個の連続したスロットを 1 回の SIMD ロードで走査し、その後次のグループへジャンプします。

結果

サイズankerl (ms)GroupedSIMD (ms)勝者
100 k2.763.36ankerl
500 k29.234.0ankerl
1 M72.371.9GroupedSIMD
2 M157.4156.3GroupedSIMD

1 M 要素（80 % 負荷）での操作別内訳

操作ankerl (ms)GroupedSIMD (ms)スピードアップ
Insert50.870.10.72×
Lookup Hit10461.51.69×
Lookup Miss5.44.51.21×

使用推奨：テーブルサイズ > 500k、検索中心のワークロード。
挿入オーバーヘッド（0.72×）は、検索が支配的であれば許容範囲です。

使い方

#include "grouped_simd_elastic.hpp"

// 1M 要素用に容量を確保
GroupedSIMDElastic<uint64_t, uint64_t> table(1200000);

// 挿入
table.insert(key, value);

// 検索
uint64_t* result = table.find(key);
if (result) {
    // 見つかった: *result が値
}

// 存在確認
if (table.contains(key)) { /* … */ }

// 代入演算子
table[key] = value;

動作原理

SIMD とハッシュテーブルの問題点

二次探査は散らばったメモリアクセスを行います：

h, h+1, h+4, h+9, h+16, h+25…

SIMD を使うには 16 個のランダムな位置を集める必要があり、スカラーコードより遅くなります。

解決策：グループ化プロービング

16 個の連続したスロット を 1 グループとしてまとめ、その後次のグループへジャンプします：

Group 0: [h+0 … h+15]   ← SIMD スキャン（1 ロード）
Group 1: [h+16…h+31]    ← SIMD スキャン（1 ロード）
Group 2: [h+32…h+47]    ← SIMD スキャン（1 ロード）

各グループ内で SSE2 は 16 バイトのメタデータを約 3 命令で走査します：

__m128i meta   = _mm_loadu_si128((__m128i*)&metadata_[base]);
__m128i matches= _mm_cmpeq_epi8(meta, target);
uint32_t mask  = _mm_movemask_epi8(matches);

これは Google の Swiss Tables が採用した洞察と同じです。

メタデータ形式

各スロットは 1 バイトのメタデータタグ を持ちます：

ビット意味
7占有フラグ (1 = 占有)
0–67 ビットハッシュフラグメント

これにより、キー比較前に 127/128 の非一致を除外できます。

API リファレンス

template <typename K, typename V,
          typename Hash = std::hash<K>>
class GroupedSIMDElastic {
public:
    explicit GroupedSIMDElastic(size_t capacity, double delta = 0.15);

    bool insert(const K& key, const V& value);
    V* find(const K& key);
    const V* find(const K& key) const;
    bool contains(const K& key) const;

    V& operator[](const K& key);   // 未登録ならデフォルト挿入

    size_t size() const;
    size_t capacity() const;
    double load_factor() const;
    size_t max_probe_used() const;
};

要件

  • C++17 以降
  • SSE2 対応（すべての x86‑64 CPU に標準）
  • ヘッダーオンリー、外部依存なし

ベンチマーク

# コンパイル
g++ -O3 -march=native -msse2 -std=c++17 \
    -o benchmark benchmark_final_sota.cpp

# 実行
./benchmark

研究の軌跡

実装は 2025 年 2 月に公開された Elastic Hashing 論文を探索する過程で進化しました。この論文は、ヤオが提唱した 40 年前からの「均一探査」仮説を覆しました。

バリアント結果学び
非貪欲プロービング1M で 5% 速いO(1) 平均遅延が機能
SIMD（散乱）0.18× (5× 遅い)Gather オーバーヘッドが殺す
メモリプリフェッチ0.41× (2.5× 遅い)ハードウェアプリフェッチャーが勝つ
Robin Hoodミスで 2×速いプローブ分散が重要
グループ化 SIMD検索で 1.5×速い隣接アクセスが SIMD を可能に

鍵となる洞察：SIMD は連続メモリアクセスを必要とします。二次探査はアクセスを散らすため、SIMD が機能しません。グループ化プロービング（Swiss Tables のアプローチ）がこれを解決します。

制限とトレードオフ

トレードオフ影響備考
挿入オーバーヘッドankerl と比べ 0.72×非貪欲候補収集
小規模テーブル500k 未満で劣る約 500k–1M 要素で交差点
削除なし実装未完了今後予定
リサイズなし固定容量事前にサイズ決定
SSE2 のみx86‑64 限定ARM NEON バージョンは無し

技術的詳細：なぜ二次グループジャンプか？

グループはクラスタリングを避けるために二次ジャンプを採用します：

Group 0: h + 16×0² = h
Group 1: h + 16×1² = h+16
Group 2: h + 16×2² = h+64
Group 3: h + 16×3² = h+144

線形ジャンプ（h, h+16, h+32…）は、プローブシーケンスの重複により挿入失敗率が 42% になるためです。二次ジャンプでグループをテーブル全体に分散させることで、すべてのスロットへ到達可能になります。

ファイル一覧

  • grouped_simd_elastic.hpp
    – 本実装（配布対象）
  • hybrid_elastic.hpp
    – 非 SIMD ベースライン
  • benchmark_final_sota.cpp
    – ankerl とのベンチマーク
  • INSIGHTS.md
    – 完全研究ログ
  • EXPERIMENT_RESULTS.md
    – 全実験データ

ライセンス

MIT

謝辞

  • Swiss Tables（Google）– グループ化プロービングの洞察
  • ankerl::unordered_dense – SOTA ベンチマークベースライン
  • Elastic Hashing 論文 – 理論的基盤

同じ日のほかのニュース

一覧に戻る →

2025/12/30 6:46

USPS（米国郵便公社）が切手印日付システムの変更を発表しました。

## Japanese Translation: > **概要：** > USPSは最終規則（FR Doc. 2025‑20740）を発行し、国内郵便マニュアルに「セクション 608.11 —『切手印と郵便保有』」を追加しました。この規則では、切手印の定義が正式に示され、該当する印記がリストアップされています。切手印は印付け日でUSPSがその物件を保有していることを確認しますが、必ずしもアイテムの最初の受理日と同一ではありません。USPSは通常業務で全ての郵便に切手印を貼らないため、切手印が欠落していても、その物件が未処理だったとは限りません。機械による自動切手印は、施設内で最初に行われた自動処理操作の日付（「date of the first automated processing operation」）を表示し、投函日ではなく、地域輸送最適化（RTO）や路線ベースのサービス基準により受理日より遅くなることがあります。切手印は小売ユニットからの輸送後やカレンダー日がまたがる場合に付けられることが多いため、郵送日を示す信頼できる指標ではありません。同一日の切手印を確保するには、小売窓口で手動（ローカル）切手印を依頼できます。小売窓口で料金を支払うと「Postage Validation Imprint（PVI）」が付与され、受理日が記録されます。また、郵便証明書、登録メール、または認定メールは提示日を裏付ける領収書として機能します。この規則の影響は税務申告において重要です。IRC §7502 は、文書が期限までに物理的に届けられなかった場合に、提出の適時性を判断する際に切手印の日付を使用しています。

2025/12/30 1:07

**Zig における静的割り当て** Zig のコンパイル時メモリ管理を使えば、実行時ではなくコンパイル時にストレージを確保できます。データ構造のサイズが事前に分かっている場合やヒープ割り当てを避けたいときに便利です。 ### 重要概念 - **コンパイル時定数** `const` や `comptime` の値を使い、コンパイラがコンパイル中に評価できるサイズを記述します。 - **固定長配列** リテラルサイズで配列を宣言します。 ```zig const buf = [_]u8{0} ** 128; // 128 バイト、すべてゼロ初期化 ``` - **静的フィールドを持つ構造体** 固定長配列やその他コンパイル時に決まる型を含む構造体を定義します。 ### 例 ```zig const std = @import("std"); // 静的サイズのバッファを持つ構造体 pub const Message = struct { id: u32, payload: [256]u8, // 256 バイト、コンパイル時に確保 }; // 静的割り当てを使う関数 fn process(msg: *Message) void { // ヒープ割り当ては不要；msg はスタック上またはグローバルに存在 std.debug.print("ID: {d}\n", .{msg.id}); } pub fn main() !void { var msg = Message{ .id = 42, .payload = [_]u8{0} ** 256, // すべてのバイトをゼロで初期化 }; process(&msg); } ``` ### 利点 - **決定的なメモリ使用量** – サイズはコンパイル時に分かる - **実行時割り当てオーバーヘッドがゼロ** – ヒープアロケータ呼び出しなし - **安全性** – コンパイラが境界と寿命を検証できる ### 使うべき場面 - 固定長バッファ（例：ネットワークパケット、ファイルヘッダー） - 短時間しか存続しない小規模補助データ構造 - 性能や決定的な動作が重要な状況 --- コンパイル時定数・固定配列・構造体定義を活用することで、Zig は最小限のボイラープレートで最大の安全性を保ちつつメモリを静的に割り当てることができます。

## Japanese Translation: > **概要：** > このプロジェクトは、Zigで書かれた軽量Redis互換のキー/バリューサーバー「kv」を構築し、最小限のコマンドセットで本番環境に適した設計を目指しています。コアデザインでは起動時にすべてのメモリを確保することで、実行中にダイナミックヒープを使用せず、レイテンシスパイクやユース・アフター・フリー（use‑after‑free）バグを回避します。接続は`io_uring`で非同期に処理され、システムは3つのプール（Connection、受信バッファプール、送信バッファプール）を事前確保し、デフォルトでは約1000件までの同時接続数をサポートします。各接続は設定パラメータから派生した固定サイズの受信/送信バッファを使用します。 > コマンド解析はRedisのRESPプロトコルのサブセットに従い、Zigの`std.heap.FixedBufferAllocator`を用いてゼロコピーで解析し、各リクエスト後にアロケータをリセットします。バッファサイズは`list_length_max`と`val_size_max`に依存します。 > ストレージは未管理型の`StringHashMapUnmanaged(Value)`を使用し、初期化時に`ensureTotalCapacity`で容量を確保します。キーと値は共有`ByteArrayPool`に格納され、マップはポインタのみを保持します。削除操作では墓石（tombstone）が残り、墓石数が増えると再ハッシュが必要になる場合があります。 > 設定構造体(`Config`)は `connections_max`、`key_count`、`key_size_max`、`val_size_max`、`list_length_max` などのフィールドを公開し、派生アロケーションで接続ごとのバッファサイズを決定します。デフォルト設定（総計約748 MB、2048エントリ）では `val_size_max` または `list_length_max` を倍増すると、割り当て量が約2.8 GBに上昇する可能性があります。 > 今後の作業としては、カスタム静的コンテキストマップ実装の改善、より良いメモリ利用を実現する代替アロケータの探索、境界検査（fuzz）テストの追加による限界確認、および墓石再ハッシュ処理への対応が挙げられます。

2025/12/27 20:30

**フレームグラフ 対 ツリーマップ 対 サンバースト（2017）**

## Japanese Translation: **概要：** Flame グラフ（SVG）はディスク使用量を高レベルで明確に示します。たとえば、Linux 4.9‑rc5 では `drivers` ディレクトリが全容量の50％以上を占め、`drivers/net` サブディレクトリは約15％です。Tree マップ（macOS の GrandPerspective、Linux の Baobab）は非常に大きなファイルを素早く検出できますが、高レベルのラベルが欠けています；Baobab のツリー表示では各ディレクトリの横にミニバーグラフが表示されます。Sunburst（Baobab の極座標図）は視覚的に印象的ですが、角度で大きさを判断するため長さや面積よりも誤解しやすいです。他のツール―`ncdu` の ASCII バーと `du -hs * | sort -hr` ―はテキストベースで迅速なサマリーを提供しますが、同時に一階層のみ表示されます。 提案されたユーティリティは、これら三つの可視化（Flame グラフ（デフォルト）、Tree マップ、Sunburst）すべてを組み合わせるものです。Flame グラフは読みやすさ・印刷性・最小スペース使用量が優れているため、多数のサンプルファイルシステムでテストした後にデフォルトとして採用されます。このアプローチは、ディスク使用量を簡潔かつ印刷可能なスナップショットとして提供し、ユーザーや開発者がスペースを占有する項目をより効率的に検出できるよう支援します。アイデアは ACMQ の「The Flame Graph」記事と「A Tour through the Visualization Zoo」に引用された既存の研究に基づいています。 **反映された主なポイント：** flame グラフの高レベルビュー、Tree マップの大きなファイルを素早く検出できるがラベルが欠けている点、Sunburst の視覚的魅力とサイズ認識の問題、他ツールの制限、および提案ツールの三つのビュー（デフォルトは flame グラフ）と引用元への参照。