Goにおける高速な不変マップ

以下の問題を考えてみましょう。大量の文字列セットがあり、数百万個に及ぶ可能性があります。これらの文字列を8バイトの整数（uint64）にマッピングする必要があります。これらの整数は与えられています。

Goで作業している場合、標準的な解決策はマップを作成することです。構築は簡単で、次のようなループのようになります。

m := make(map[string]uint64, N)
for i, k := range keys {
    m[k] = values[i]
}

欠点の1つは、マップがエントリあたり50バイト以上を使用する可能性があることです。

重要なシナリオでは、次のような条件があるかもしれません。マップが大規模（100万エントリ以上）で、動的に変更する必要がなく（不変）、クエリされるすべてのキーがセットに含まれている場合です。このような条件では、メモリ使用量をキーのサイズにほぼ抑えることができ、エントリあたり約8バイトになります。高速な手法の1つがbinary fuse filtersです。

私はこれをconstmapというGoライブラリとして実装しました。このライブラリは、binary fuse filtersを使用して文字列からuint64値への不変マップを提供します。このデータ構造は、構築時に固定のキーのセットがあり、その後高速でメモリ効率の良いルックアップが必要な場合に理想的です。マップを一度構築してディスクに保存することもできるため、必要になるたびにマップを構築するコストを支払う必要がありません。

使い方は同様に簡単です。

package main

import (
    "fmt"
    "log"

    "github.com/lemire/constmap"
)

func main() {
    keys := []string{"apple", "banana", "cherry"}
    values := []uint64{100, 200, 300}

    cm, err := constmap.New(keys, values)
    if err != nil {
        log.Fatal(err)
    }

    fmt.Println(cm.Map("banana")) // 200
}

構築時間は高くなります（コンパクトなデータ構造では当然ですが）、ただしルックアップは速度向けに最適化されています。私はApple M4 Maxプロセッサでベンチマークを実行し、constmapのルックアップとGoの組み込みmap[string]uint64を比較しました。テストでは100万個のキーを使用します。

ConstMapは、ルックアップにおいてGoの標準マップの約3倍高速です！また、メモリ使用量を6分の1に削減しました。

ConstMapは常に高速とは限りませんが、常に大幅にメモリ使用量が少なくなるはずです。マップがCPUキャッシュに収まらない場合でも、ConstMapがキャッシュに収まれば大幅に高速になります。

ソースコード 実装はGitHubで入手できます：github.com/lemire/constmap。

Published by

Post navigation