Go puzpuzpuz/xsync を ChatGPT とともに見る

mercari.go #24 を開催しました #mercarigo | メルカリエンジニアリング　を読んで、CPUキャッシュラインを考慮した高効率な sync パッケージの存在を知ったので少し調べてみた。

スライドはこちら Concurrent Data Structures and CPU Cache with Go - Google スライド

CacheLine とは

CPUキャッシュがGoのコードに与える影響（翻訳）｜TechRacho by BPS株式会社を見るのが良い

さて、プロセッサの世界には「参照の局所性（locality of reference）」と呼ばれる重要な概念があります。プロセッサがメモリ上の特定の場所にアクセスするとき、以下のように予測を立てます。

近い将来、メモリ上の同じ場所にアクセスする可能性が非常に高いこれは「時間的局所性（temporal locality）の法則」です近い将来、メモリ上のその場所からごく近い場所にアクセスする可能性が非常に高いこれは「空間的局所性（spatial locality）の法則」です

CPUにキャッシュが存在する理由のひとつが、この時間的局所性です。では空間的局所性を高めるにはどうすればよいでしょうか？答えは、メモリ上の1つの場所を単品でCPUキャッシュにコピーするのではなく、「cache line」という単位でCPUキャッシュにコピーすることです（cache lineとは、メモリ上での連続セグメントのことです）。

〜

プロセッサは、変数ひとつをL1キャッシュにコピーするのではなく、64バイトの連続セグメントをL1キャッシュにコピーします。たとえば、Go言語のスライスのint64要素を1個だけコピーするのではなく、その要素以外に7つのint64要素もまとめてコピーします。

CPUキャッシュがGoのコードに与える影響（翻訳）｜TechRacho by BPS株式会社を見るのが良い

cache line の範囲内に複数の用途の変数が存在している場合、スレッドやプロセスごとに別々の変数を使っていたとしても同じ cache line が別の CPU に保存されることがあります。CPUはこのようなキャッシュについて調整してくれるのですが、この作業はパフォーマンスを損なうことがあります。

この問題を false sharing といいます。

`puzpuzpuz/xsync` の実装

go の標準パッケージの sync は cacheline を考慮していないようで、代わりに puzpuzpuz/xsync: Concurrent data structures for Go というパッケージが存在しています。

map 関数について ChatGPT にどのように cacheline を考慮した設計をしているのかを聞いてみました。

以下 ChatGPT の回答です。

このコードでは、キャッシュラインを考慮するために、主に以下のような実装が行われています。

バケットのサイズ: コメントによると、各バケットは64バイト（一般的なCPUキャッシュラインのサイズ）に収まるように設計されています。これは、entriesPerMapBucket 定数が3に設定されていることからわかります。これにより、64ビットマシン上で各バケットがちょうど1つのキャッシュラインに収まるようになります。
```
 // number of entries per bucket; 3 entries lead to size of 64B
 // (one cache line) on 64-bit machines
 entriesPerMapBucket = 3
```

バケット内の各エントリは、キーと値のポインタ（unsafe.Pointer）、およびハッシュ値の一部を格納します。64ビットアーキテクチャでは、unsafe.Pointer は8バイトを占めます。バケット内の各エントリは次のように構成されています：

type bucket struct {
    next   unsafe.Pointer // *bucketPadded
    keys   [entriesPerMapBucket]unsafe.Pointer
    values [entriesPerMapBucket]unsafe.Pointer
    // topHashMutex is a 2-in-1 value.
    //
    // It contains packed top 20 bits (20 MSBs) of hash codes for keys
    // stored in the bucket:
    // | key 0's top hash | key 1's top hash | key 2's top hash | bitmap for keys | mutex |
    // |      20 bits     |      20 bits     |      20 bits     |     3 bits      | 1 bit |
    //
    // The least significant bit is used for the mutex (TTAS spinlock).
    topHashMutex uint64
}

キーのポインタ: 8バイト値のポインタ: 8バイトハッシュ値の一部（このコードでは直接的なサイズは示されていませんが、通常は数ビット） entriesPerMapBucket が3である場合、バケット内のエントリは合計で以下のようになります：

キーのポインタ x 3 = 24バイト値のポインタ x 3 = 24バイトハッシュ値の一部（全エントリにわたる）ここで、キーと値のポインタだけで48バイトを占めています。残りの部分（ハッシュ値の一部やその他の管理用のデータ）が16バイト以内に収まるように設計されていれば、全体のバケットサイズが64バイトのキャッシュラインに収まることになります。

このように、entriesPerMapBucket を3に設定することで、バケット全体が一つのキャッシュラインに収まり、CPUキャッシュの効率が向上することを意図しています。キャッシュラインに収まることで、CPUが必要なデータをより迅速にアクセスでき、パフォーマンスが向上します。

パディングを使用した構造体: bucketPadded と counterStripe 構造体は、キャッシュラインの境界に合わせてパディングされています。これにより、いわゆる「false sharing」を防ぐことができます。False sharingは、異なるデータが同じキャッシュラインに配置されることで、不必要なキャッシュの無効化や競合が発生する現象です。
```
 type counterStripe struct {
     c int64
     //lint:ignore U1000 prevents false sharing
     pad [cacheLineSize - 8]byte
 }

 type bucketPadded struct {
     //lint:ignore U1000 ensure each bucket takes two cache lines on both 32 and 64-bit archs
     pad [cacheLineSize - unsafe.Sizeof(bucket{})]byte
     bucket
 }
```

ここで、cacheLineSize はプラットフォーム固有のキャッシュラインのサイズを表します。このパディングにより、各 bucketPadded と counterStripe が独立したキャッシュラインに配置され、他のデータ構造とのキャッシュラインの共有を防ぎます。

これらの設計により、このパッケージはキャッシュの効率を最大化し、マルチスレッド環境でのパフォーマンスを向上させています。キャッシュラインを考慮することで、CPUとメモリ間のデータ転送を最適化し、アクセス時間を短縮することが可能になります。

（追加で質問）

実データではなくポインタを保存している場合って、実データ自体は全然ちがうところにありますよね？それはキャッシュライン考慮しなくてよいんですか？

ChatGPT ご質問の内容について、さらに詳しく説明します。

確かに、ポインタを使用してデータを保存する場合、実際のデータはメモリの別の場所に存在します。この場合、キャッシュラインの最適化は、ポインタ自体が格納されているデータ構造に対して行われます。つまり、この最適化は、ポインタが格納されているバケットや配列のアクセス効率を向上させることを目的としています。

実際のデータ（ポインタが指すオブジェクト）に関しては、それらがどのようにメモリ上に配置されているかによります。理想的には、これらのデータもキャッシュフレンドリーな方法で配置されると良いのですが、実際にはデータのサイズやアクセスパターンによって異なります。

キャッシュラインを考慮する主な理由は、CPUがデータをキャッシュする際に、一度に特定のサイズ（多くの現代のCPUでは64バイト）のブロックを読み込むためです。したがって、データ構造がこのキャッシュラインのサイズに合わせて設計されている場合、CPUは必要なデータをより少ないアクセスで取得でき、パフォーマンスが向上します。

要約すると、キャッシュラインの最適化は、ポインタが格納されているデータ構造に対して行われるものであり、ポインタが指す実データの配置については、別途考慮する必要があります。実データがメモリ上でどのように配置されているかは、そのデータのアクセスパターンやサイズに依存します。