リングバッファ
リングバッファ (英: ring buffer)、サーキュラーバッファ (英: circular buffer)、または環状バッファ（かんじょうバッファ）とは、リング状に配置されたバッファである（図を参照）。一時的にデータを貯めておくバッファ領域のうち、終端と先端が論理的に連結され、循環的に利用されるようになっている。最も古い内容を最新の内容で上書きし、常に一定の数の過去までのデータを蓄えるような用途に用いられる[1]。
仕組み
[編集]バッファは一般的にメモリ空間効率の高い配列を使って実装されるが、配列を物理的にリング状に配置することはできないので、インデックス（添え字、添え数）をバッファサイズで割って剰余を取る正規化をし、一定の範囲に限定することで、直線状のバッファの両端を論理的に繋げる。正規化により、インデックスがバッファの最後を超えると最初に戻り、また負数が適切に処理されていれば、バッファの最初より前になると最後に進む。
正規化の内容は剰余演算だが、たいていのプロセッサの命令セットアーキテクチャでは整数の剰余演算は除算同様に遅いため、実際には、バッファサイズNを2の冪に切り上げ、N-1とのビットごとの論理積を求めることが多い（ソースコード上では剰余のままであっても、現在[いつ?]のコンパイラの多くは、2の冪での剰余を自動的にビットごとの論理積に最適化する）。ただしバッファサイズを切り上げると余分なメモリが必要になるため、メモリ使用量の制約が強いときはバッファサイズを半端なままにしておき、一般的な方法で剰余を求めたり、バッファの端に達したかどうかで条件分岐[注釈 1]したりする。とはいえ、よほど大量にインデックス計算を繰り返すようなことがない限り、オーバーヘッドは微々たるものである。
ただしこれらは、配列のインデックスが「0オリジン」（配列の最初の要素のインデックスが0）の場合の話である。「1オリジン」など、配列の最初の要素のインデックスが0ではない場合[注釈 2]は、0オリジンのインデックスに換算して正規化する必要がある。
リングバッファのインデックスは、数論的には剰余類をなす。
類似の機構
[編集]エンドレステープは、アナログ記録ではあるが、物理的にリングを実現したリングバッファと考えることもできる。
用途
[編集]現在[いつ?]では、動画や音楽再生のバッファリングとしてよく使用される。この場合、書き込みを行う位置と、読み込みを行う位置の衝突が発生する場合がある。 ストリーミング等でバッファの蓄積が再生より遅くなった場合、再生のバッファ待ちが発生する。
