Goにおける文字列からfloat配列へのマッピング：どれだけ高速にできるか？

現代のソフトウェアでよく見られるパターンは、文字列キーを浮動小数点数の小さな配列にマッピングすることです。単語埋め込み、特徴ベクトル、物理定数のルックアップテーブル：いずれも同じテーマのバリエーションです。Goでは、これを記述する明白な方法はmap[string][]float32です。しかし、実際にどれだけ高速なのでしょうか、そしてより良い方法があるのでしょうか？

私はconstmapというGoライブラリの開発に取り組んできました。これはbinary fuse filterの構成を使用して、文字列からuint64値への不変マップを構築します。ルックアップは1回のハッシュ、3回の配列読み取り、2回のXORで完了します。比較、チェイン、プロービングは必要ありません。テーブル全体はキーあたり約9バイトで収まるため、Goのマップが収まらない場合でもキャッシュに収まることがよくあります。

Goには高速なマップがありますが、パフォーマンスで簡単に打ち負かすことはできません。しかし、より小さなデータ構造を構築してキャッシュミスを減らせば、確実に高速化できます。

デフォルトでは、constmapはuint64を返します。しかし、値が8つのfloat32数値の配列である場合はどうでしょうか？少なくとも2つの選択肢があります：

1. 配列を別個のスライス[][]float32に保持する。constmapはインデックスを返します。
2. float配列へのポインタをconstmapのuint64内に直接格納する。

2番目のオプションでは、整数フィールドを通じてポインタを密輸するため、unsafeパッケージが必要です。いくつかの制限があります。

• データ構造をディスクにデシリアライズすることはできませんし、すべきではありません。
• float配列への参照を保持し続ける必要があります。そうしないと、ガベージコレクタがそれを回収し、ダングリングポインタが残る可能性があります。Goは使用されなくなったメモリを回収できるため、これは思ったより難しい問題です。また、整数をポインタ値に変換するunsafe呼び出しを通じては見えません。幸いなことに、すべてのfloat配列を配列に配置し、戦略的な場所でruntime.KeepAlive(mybigarray)を呼び出すだけで済みます。これにより、Goがmybigarrayを回収するのを防げます。runtime.KeepAliveの呼び出しは無料ではありませんが、かなり安価なので、多くの呼び出しを使用できる可能性があります。ベンチマーク

私は100,000のキーに対して3つのルックアップを構築しました。各キーは8要素の[]float32にマッピングされます。ベンチマークを少し公平にするため、常に配列の最初の要素にアクセスします。ランダムなクエリの大きなセット（クエリは文字列）を使用します。

map[string][]float32、配列と結合された標準のconstmap（constmapがインデックスを含む）、および[]float32の位置へのポインタを実質的に含むconstmapを比較します。

Apple M4 MaxでGoの標準ベンチマークハーネスで実行：

インデックス付きのconstmapは、すでにGoマップの2倍高速です。インデックスを生のポインタに置き換えることで、[][]float32スライスヘッダー経由の間接参照をスキップし、さらに2ns短縮します。私のケースでは約20%の高速化です。

この結果はそれ自体興味深いものです：constmapのルックアップは十分に高速であるため、次のメモリロード、スライスヘッダーの読み取りが作業の測定可能な割合になります。

ベンチマークとコードはgithub.com/lemire/constmapにあります。次のコマンドで実行します：

go test -bench 'FloatArray' -benchtime=1s

公開者

記事ナビゲーション