Go Conference 2024 で登壇しました！

こんにちは、SWEの小島です。 2024年6月8日(土)に開催されたGo Conference 2024 で「Mapのパフォーマンス向上のために検討されているSwissTableを理解する」というタイトルで登壇してきました！

Go Conference 2024 について

Go Conference は年に1回開催されるGo言語に関するカンファレンスで2024年は久しぶりのオフラインでの開催となりました。自分がGo Conferenceに参加し始めたのはGo Conference 2021 Springからでその時には既にオンライン開催だったので、オフラインでのGo Conferenceには始めての参加になりました。

登壇内容について

speakerdeck.com

発表では、Goの既存のMap実装について簡単に触れ、その後SwissTableの概要を説明し、GoのMap実装にSwissTableを導入するための提案について紹介しました。

発表後に面白かったと声をかけていただいたり、Xでも面白かったとポストしていただいた方がいたりSwissTableだけでなく既存のMap実装についても理解が深まったという感想をいただいてて、発表した甲斐があったなと思いました。見つけることができた自分の発表について触れてくれているポストすべてにいいねつけて回るぐらい嬉しかったです。感想をポストしてくださった方ありがとうございます。

実はproposalを出したタイミングでは既存のMap実装については触れずにSwissTableだけに絞って説明する予定だったのですが、既存のMap実装についても説明した方がSwissTableを導入すること内部実装がどう変わるのか理解しやすいと思い、発表では既存のMap実装についても触れることにしました。

そのため時間の関係で発表中に説明しきれなかった箇所がいくつかあるのでここで紹介させてください。

既存のMap実装にoverflow bucketが閾値を超えた場合の再配置について

既存のMap実装ではbucketが一杯になった場合にoverflow bucketを追加しますが、overflow bucketの数が閾値を超えた場合にはbucketの再配置が行われます。

発表ではこの条件は「削除操作が多くないと発生しない」と説明するだけになってしまいました。この条件の時はbucketは作り直し再配置を実施するのですが、その時bucketの数は2倍にしないまま再配置を実施します。自分はこの処理を行っているコードを初めて読んだ時はなんでbucekt数を2倍にしないのに再配置するだけで問題ないのか理解できず、この処理がある理由がわからず混乱したことを覚えてます。

なぜbucket数を2倍にしないまま再配置を実施するだけで問題ないのかというと、既存のMap実装では格納されているアイテムを削除する場合、アイテムが格納されているスロットを空に戻すのではなく、削除済みフラグを立てると言う処理をしています。これは下記の図のようにスロットを空に戻した場合にそのスロットよりも後にあるスロットに格納されているアイテムを操作しようとした場合に削除により空に戻ったスロットがあった場合にそこで探索が止まってしまうのを防ぐための仕組みです。

このアイテムを削除する場合に削除フラグを立てるという操作を行うとbucketの中にアイテムは格納されていないが、使用することもできないスロットが生まれるため削除操作をしない場合と比べて少ないアイテム数でoverflow bucketが必要になります。そのため、削除操作が多いと「使用している箇所がbucket数に応じた閾値を超えた場合」の条件を満たす前に「overflow bucketの数が閾値を超えている」を満たすようになります。そして、その場合bucket数は変更しないで再配置を実施するだけで削除により使えなくなっていたスロットにアイテムを配置できるためoverflow bucketの数が減少し、mapの拡張の条件を満たさない状態に戻ることができるということでした。

SwissTableのH2 hashを用いたフィルタ処理について

ここの処理はSwissTableの特徴の1つなので本来なら発表中に触れたかったのですが、時間の都合で省略せざるを得なかったのでここで補足させてください。

cockroachdb/swissの実装ではSIMD実装はまだされていないため、c++のabseilのSwissTableの実装を元に説明します。 abseilではフィルタの処理は下記のように実装されています。

  // Returns a bitmask representing the positions of slots that match hash.
  BitMask<uint16_t, kWidth> Match(h2_t hash) const {
    auto match = _mm_set1_epi8(static_cast<char>(hash));
    BitMask<uint16_t, kWidth> result = BitMask<uint16_t, kWidth>(0);
    result = BitMask<uint16_t, kWidth>(
        static_cast<uint16_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(match, ctrl))));
    return result;
  }

ref: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h#L687-L694

_mm_set1_epi8・_mm_cmpeq_epi8・_mm_movemask_epi8がSIMD命令の操作をしている箇所になります。

処理としては

H2をmetadataのバイト分作成する(_mm_set1_epi8)
バイト単位で一致しているか比較 (_mm_cmpeq_epi8)
各バイトの最上位ビットを取り出す (_mm_movemask_epi8)

の順で処理をしており図にすると下記のようにバイト単位で処理していることがわかりやすいかと思います。

ではSIMD実装をしていないcockroachdb/swissの実装はどのようになっているのかというと、ビット演算を用いてほぼ同等の処理を行うように実装されています。

const (
    bitsetLSB     = 0x0101010101010101
    bitsetMSB     = 0x8080808080808080
)

// matchH2 returns the set of slots which are full and for which the 7-bit hash
// matches the given value. May return false positives.
func (g *ctrlGroup) matchH2(h uintptr) bitset {
    // NB: This generic matching routine produces false positive matches when
    // h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For
    // example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we
    // subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be
    // considered matches of h. The false positive matches are not a problem,
    // just a rare inefficiency. Note that they only occur if there is a real
    // match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key
    // comparisons ensure that there is no correctness issue.
    v := uint64(*g) ^ (bitsetLSB * uint64(h))
    return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)
}

refs

実装だけみると複雑に見えますが1つ1つ分解していくと下記の図のようになっておりH2とバイト単位でマッチした箇所の先頭ビットのみを1にするために演算を繰り返しているのがわかると思います。またコメントに記載されているとおりH2が2N乗で隣が2N+1の場合にv-bitsetLSBの演算において繰り下がりが発生するため、本来ならマッチしていないスロットについてもマッチしていると判定されてしまうことがあります。(図の右下の例)

H2 hashを用いたフィルタ処理でマッチしたバイト列を使ったgroup内の探索

こちら発表ではマッチした箇所を順に見るとだけ説明しましたが、実際にはH2 hashを用いたフィルタ処理が完了した時点ではマッチしたスロットの先頭bitが1になっている8バイトのバイト列があるだけで、何番目のスロットがマッチしたのかの表すindexのスライスがあるといった状態ではないのでバイト列からマッチしたスロットのindexを順番に取得する必要があります。

実装としては図のようになっています。

これをgoのコードとして実装している箇所は下記になります。

// bitset represents a set of slots within a group.
//
// The underlying representation uses one byte per slot, where each byte is
// either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it
// convenient to calculate for an entire group at once (e.g. see matchEmpty).
type bitset uint64

// first assumes that only the MSB of each control byte can be set (e.g. bitset
// is the result of matchEmpty or similar) and returns the relative index of the
// first control byte in the group that has the MSB set.
//
// Returns 8 if the bitset is 0.
// Returns groupSize if the bitset is empty.
func (b bitset) first() uint32 {
    return uint32(bits.TrailingZeros64(uint64(b))) >> 3
}

// removeFirst removes the first set bit (that is, resets the least significant set bit to 0).
func (b bitset) removeFirst() bitset {
    return b & (b - 1)
}

ref: https://github.com/cockroachdb/swiss/blob/main/map.go#L1433-L1466

図の1番の処理に対応するのがfunc (b bitset) first() uint32で2番の処理の対応するのがfunc (b bitset) removeFirst() bitsetになります。

参加した感想

開催してくださった運営のみなさま・発表を聞いてくださった方々・現地でお話させてくださったみなさま・スポンサー企業様ありがとうございました。久しぶりのオフラインでの開催となったGo Conference 2024参加・登壇することができとても楽しかったです。

自分の発表の前は緊張で集中して発表きけてなかった & 発表後は疲れ切っていたので後半の発表はあまり頭に入っていないのですが、個人的には GMOペパボ株式会社の小山さんが発表していたCleanup handling in Goが印象に残っています。サーバのグレースフルシャットダウンだったりテストの後処理だったりといった処理の後処理をどう実装するかを紹介して、終了処理についての理解を深めていき、最後にそれらを比較しつつ理想的な終了処理に求められる仕様を整理してそれを満たすライブラリを作ったので紹介という綺麗な流れの発表で、自分もいつかはこういった内容で発表してみたいと思いました。ちなみに紹介されていたライブラリであるdonegroup、テスト除くと1ファイル300行ぐらいで済んでいたので実装読んでみようと思っています。

エブリー / アンドパッド / LayerX / STORES の Go Conference 2024 スポンサー各社と Go Bash を開催します！

アンドパッドはGo Conference 2024 ではスポンサー抽選の結果ブースを持つことはできませんでしたが、協賛するエブリー / LayerX / STORES の各社様と一緒して、 Go Bash というイベントを 6/18 (火) 19 時 から開催 *1 します！

connpass.com

Beer ならぬ Go を肴にワイワイするイベントで、スポンサー各社の Go Conference 2024 に登壇・参加した Gopher が主体となりトークや感想戦を繰り広げます！ Go Conference 2024 で感じた Go への余熱を発散できるイベントになるので、ぜひご参加くださいませ！

そして、会場は LayerX さんの新オフィス（東銀座）で開催され、なんと LayerX さんのご厚意で、Go Conference 2024 では実現できなかったアンドパッドのスポンサーブース（簡易版）も出展できることになりました！新しいノベルティも用意して、皆さんのお越しをお待ちしております！