循環バッファ入門：仕組み・実装・並列処理とパフォーマンス最適化
エバープレイ編集部循環バッファとは：概要と基本概念
循環バッファ（リングバッファ、ring buffer、circular buffer）は、固定長の配列領域を先頭と末尾がつながった「円環」のように扱い、データを逐次読み書きするためのデータ構造です。主にプロデューサー／コンシューマー（生産者／消費者）モデルで使用され、ストリーム処理やリアルタイム処理、デバイスドライバ、音声・映像バッファ、ネットワークパケットの一時保管などで広く使われます。
基本実装と動作
典型的な実装は固定長配列と2つのインデックス（head/tail または write/read ポインタ）を持ちます。片方はデータの書き込み位置、もう片方は読み出し位置を示します。インデックスは配列長で割った余り（モジュロ演算）でラップアラウンドします。
- 空（empty）判定：head == tail（別途カウントを持たない場合は注意）
- 満杯（full）判定：通常は (tail + 1) % capacity == head として「1スロットを空ける」手法を用いるか、要素数カウンタを保持して比較する
- 要素数を保持する方法は full/empty を明確に区別できるが、原子性や同期が必要
代表的な疑似コード
最も単純な SPSC（Single Producer Single Consumer）版の擬似実装：
enqueue(x):
next = (tail + 1) % N
if next == head:
return false // full
buffer[tail] = x
tail = next
return true
dequeue():
if head == tail:
return EMPTY
x = buffer[head]
head = (head + 1) % N
return x
容量と「1スロット残し」トリック
配列長 N を指定した場合、上記の「next == head」で full 判定を行う実装では実際に格納可能な要素数は N-1 になります。これを嫌う場合は要素数カウンタを追加して head と tail が一致しても区別できるようにする方法がありますが、並列環境ではカウンタの原子更新や同期が必要になります。
パフォーマンス最適化
- 容量を 2 の累乗にしてビットマスク（index & (capacity-1)）でラップすることでモジュロ演算を高速化できます。
- 一括読み書き（バッチ処理）を行い、1 要素ごとの指数的オーバーヘッドを減らす。
- キャッシュラインを考慮した配置（head/tail を別キャッシュラインに置く）で偽共有（false sharing）を避ける。
- メモリの二重マッピング（mmap を使って同じ物理メモリを仮想空間に連続して2回マップ）により、ラップ処理の分岐をなくして単一の連続領域として扱うテクニックが知られています（高性能 I/O で利用される）。
並行処理（Concurrency）に関する考慮
循環バッファは並列アクセスの設計次第で非常に高速に動作しますが、実装を誤るとデータ破壊や競合が発生します。
- SPSC（1 つの producer と 1 つの consumer）では head と tail をそれぞれ一方のスレッドだけが更新する設計にすると、ほとんど同期を必要とせずにロックフリーで実装できます。ただし読み取り側は書き込み側の更新を適切なメモリバリアで観測する必要があります。
- MPSC（複数 producer、単一 consumer）や MPMC（複数 producer／複数 consumer）は単純な head/tail だけでは成立せず、原子操作／CAS（compare-and-swap）やロックが必要になります。Vyukov のようなロックフリーな有界 MPMC キューの実装は複雑ですが高性能です。
- OS レベルやカーネルの実装（Linux の kfifo や RTOS のストリームバッファ）は、用途に応じてロックあり／ロックなし、コピー回数の削減、割り込み安全性などを組み合わせています。
利用例と用途
- 音声/映像のストリーミングバッファ（遅延管理、ジャッタ吸収）
- シリアル通信やネットワークパケットの受信／送信バッファ
- デバイスドライバやカーネル内部の FIFO（ログやイベントキュー）
- マルチスレッドのプロデューサー／コンシューマー間データ受け渡し（低レイテンシが求められる場面）
- ログの循環保存（古いエントリを上書きする固定長ログ）
落とし穴と運用上の注意点
- オーバーラン：プロデューサがコンシューマより速いとデータが上書きされる。上書き可／不可のポリシーを明確にする（上書きして最新のみ保持する設計もある）。
- 同期の誤り：並行実装でメモリバリアや原子性を無視すると破損や読み飛ばしが起こる。
- スロット数の誤り：N と実際に使える容量（N-1 か要素カウンタで N）を混同しない。
- 可変サイズ要素の扱い：要素サイズが可変の場合、バッファに長さ＋データを格納する方法か、ポインタを格納する方法を選ぶ。ポインタ方式は所有権管理とメモリ破壊に注意。
実装と既存ライブラリ／実装例
- Linux カーネルの kfifo：汎用的でパフォーマンス指向の実装（カーネル文書参照）。
- FreeRTOS のストリームバッファ／メッセージバッファ：組み込み系の RTOS 向けに設計された API。
- Vyukov の有界 MPMC キューや 1024cores のロックフリーアルゴリズム群：高性能並列キューの参考。
- ユーザ空間では Boost.Lockfree（C++）、Ring Buffer 実装の多数ライブラリが存在。
まとめ
循環バッファは単純な構造ながら、低レイテンシでメモリ効率の高いキュー実装として非常に有用です。用途や並列性の要件に応じて、容量の取り方（N vs N-1）、同期手法（ロック、原子操作、メモリバリア）、パフォーマンス最適化（バッチ処理、ビットマスク、二重マッピング）を慎重に選ぶ必要があります。特に並列環境では正しいメモリモデル理解とテストが重要です。
参考文献
- 循環バッファ - Wikipedia（日本語）
- Circular buffer - Wikipedia (English)
- kfifo — Linux kernel documentation
- FreeRTOS: Stream buffers and message buffers
- Circular Queue — GeeksforGeeks (実装例)
- Bounded MPMC queue — 1024cores (Vyukov)
- LWN.net: The mmap trick for ring buffers
投稿者プロフィール
