원형버퍼
원형버퍼 구현방식에 대해 알아봅니다
영어로는 ring buffer 또는 circular buffer.
원형버퍼를 구현하는 방식에는 크게 두가지가 있습니다. 읽기와 쓰기를 위한 각각 별도의 인덱스를 갖는 경우와 하나의 인덱스와 카운트 변수를 갖는 경우입니다.
두 개의 인덱스
구현이 간단하지만, empty 와 full 을 구분하기 위해 slot 하나를 낭비하게 됩니다.
mod(n) { return n % cap; }
init() { r = w = 0; }
write(val) { buf[r] = val, r = mod(r + 1); }
read() { res = buf[w], w = mod(w + 1); return res; }
empty() { return r == w; }
full() { return mod(r + 1) == w; }
N 이 2 의 거듭제곱이라면, mod 의 나머지 연산은 mask(n) { n & (cap - 1); }
로 최적화 할 수 있습니다.
하나의 인덱스와 카운트 변수
slot 하나를 낭비하는 위 방법과는 달리 버퍼 내 모든 공간을 활용하지만,
write, read 두 함수 모두에서 카운트 변수를 변경합니다. 따라서 캐싱 효율을
떨어뜨릴 수 있고, 동시성 처리를 위한 추가적인 작업이 필요합니다.
물론, 다수의 reader 나 다수의 writer 가 있는 경우에는 어떤 방식의 구현이든 동시성 처리가 필요합니다.
init() { index = count = 0; }
write(val) { buf[mod(w + count++)] = val; }
read() { return count--, buf[mod(index++)]; }
empty() { return count == 0; }
full() { return count == cap; }
증가하기만 하는 두 개의 인덱스
첫번째 방식에서 인덱스가 버퍼 크기를 벗어나지 않도록 모듈로 연산을 사용한 반면, 아래는 unsigned integer overflow 를 활용해 인덱스를 증가시키기만 하는 방식입니다. 첫번째 구현방식과는 달리 낭비하는 slot 없이 버퍼 내 모든 공간을 활용합니다.
init() { r = w = 0; }
write(val) { buf[mod(r++)] = val; }
read() { return buf[mod(w++)]; }
empty() { return r == w; }
full() { return (r - w) == cap; }
주의할 점은:
- 오버플로우의 경우 인덱스가 0 부터 wraparound 되기 때문에 버퍼 크기는 2 의 제곱승만 사용할 수 있습니다
- C 에서 signed 데이터 타입의 오버플로우는 undefined 이기 때문에 인덱스는 반드시 unsigned 여야 합니다
- 인덱스에 32 비트 자료형을 사용할 경우, 최대 버퍼 사이즈는 \(2^{31}-1\) 가 됩니다