I've been writing ring buffers wrong all these years (2016)

そこで私は、1 要素のリングバッファを実装しようとしていました。
ご存知の通り、これは非常に合理的なデータ構造です。

書くのは思ったよりも面倒でした――その理由について後ほど触れます。考えてみると、ずっと「間違った」方法でリングバッファを書いていたことに気づきました。そしてもっと良いやり方があるという結論に至りました。

---

配列 + 2 つのインデックス

リングバッファを使ってキューを実装する一般的な方法は二通りあります。

1. 配列をバックエンドとして使用し、配列へのポインタとして read と write の 2 つのインデックスを保持します。
   ヘッドから値を取り出す ときは

   read

   を使って配列にアクセスし、その後

   read

   をインクリメントします。
   テールへ値を追加する ときは

   write

   を使って配列に書き込み、次に

   write

   をインクリメントします。

両方のインデックスは常に

0 … (capacity‑1)

の範囲に収まります。これはインデックスが増えた後でマスクして行います。

uint32 read;
uint32 write;

mask(val)  { return val & (array.capacity - 1); }
inc(index) { return mask(index + 1); }

push(val)  { assert(!full()); array[write] = val; write = inc(write); }
shift()    { assert(!empty()); ret = array[read]; read = inc(read); return ret; }

empty()    { return read == write; }
full()     { return inc(write) == read; }
size()     { return mask(write - read); }

欠点

この表現は配列の 1 要素を無駄にします。
例えば配列が 4 要素なら、キューは最大で 3 要素しか保持できません。なぜかというと、空バッファでは

read == write

が成り立ちますが、満杯のバッファ（容量 N）でも同じ状態になってしまいます。そのため「満杯」を判定するには 1 スロットを未使用にしておく 必要があります。

大きなバッファでは無駄は目立ちませんが、1 要素しかない配列だと 100 % のオーバーヘッドになり、ペイロードゼロです！

---

配列 + インデックス + 長さ

もう一つの方法は インデックス と 長さ（length）を保持します。
要素を取り出すときは

read

を使い、

read

をインクリメントしながら

length

を減算します。追加するときは

mask(read + length)

に書き込み、

length

を増やします。

uint32 read;
uint32 length;

mask(val)  { return val & (array.capacity - 1); }
inc(index) { return mask(index + 1); }

push(val)  { assert(!full()); array[mask(read + length++)] = val; }
shift()    { assert(!empty()); --length; ret = array[read]; read = inc(read); return ret; }

empty()    { return length == 0; }
full()     { return length == array.capacity; }
size()     { return length; }

これなら全容量を使えますが、私はあまり好きではありません。
同時に読者と書き手がいる場合、両方のスレッドが

length

を更新するためキャッシュ効率が落ち、原子操作が必要になります。

---

配列 + 2 つの 未マスク インデックス

「両方の表現のメリットを得て、第三の状態変数を持たない方法」はあります――それは インクリメント時にマスクしない で、配列へアクセスするときだけマスクすることです。符号なし整数のオーバーフローが自然にゼロに戻るようにします。

uint32 read;
uint32 write;

mask(val)  { return val & (array.capacity - 1); }

push(val)  { assert(!full()); array[mask(write++)] = val; }
shift()    { assert(!empty()); return array[mask(read++)]; }

empty()    { return read == write; }
full()     { return size() == array.capacity; }
size()     { return write - read; }

無駄になっていたスロットが回収されます。インデックスの更新コードはシンプルで、状態判定も直感的です。

制限事項

• 言語が符号なし整数のオーバーフローをラップアラウンドで扱うこと。

• capacity

  は 2 のべき乗（モジュロ演算でも必要）。
• 最大容量はインデックス型の範囲の半分まで（例：32 ビット符号なしなら (2^{31}-1)）。

これらは通常問題になりません。

---

なぜ人々は「劣る」バージョンを使い続けているのでしょうか？

• 慣習：教科書的手法が教えられ、再考せずに継承されます。
• 安全性への懸念：符号なしオーバーフローはバグだと恐れる人もおり、意図しないオーバーフローを避けるため明示的にマスクします。
• 非 2 のべき乗サイズ：容量が必ずしも 2 のべき乗でないケースでは、マスク版があればどんなサイズでも動作します。
• 歴史的慣性：未マスク手法は（例：Andrew Morton, 2004）既に知られていましたが、多くの実装は古いパターンを続けています。

---

結論

容量が 2 のべき乗で、符号なし整数オーバーフローを利用できる場合は 未マスクインデックス を使う方が簡潔かつ効率的です。
「マスク後に増分」バージョンが残っているのは主に慣習とオーバーフローバグへの不安によるもので、必ずしも優れた設計だからではありません。