링 버퍼는 순환 버퍼(circular buffer)라고도 불린다.
배열 기반 큐의 문제점은 큐의 뒤쪽에 새로운 아이템을 추가하는 것은 빠르지만(O(1)), 큐의 앞쪽에서 아이템을 제거하는 것은 느리다는 점이다(O(n)). 아이템을 제거할 때 남은 배열 요소를 메모리에서 이동시켜야 하기 때문에 느리다.
큐를 더 효율적으로 구현하려면 링 버퍼 또는 순환 버퍼를 사용할 수 있다. 이는 개념적으로 배열의 끝에서 다시 시작 부분으로 돌아가도록 설계된 배열로, 아이템을 제거할 필요가 없다. 모든 연산이 **O(1)**로 수행된다.
원리는 다음과 같다. 고정된 크기의 배열이 있다고 가정하자. 예를 들어 5개의 아이템을 저장할 수 있는 배열이다:
[ , , , , ]
r
w
처음에는 배열이 비어 있고 읽기(r)와 쓰기(w) 포인터가 시작 부분에 위치한다.
이 배열에 데이터를 추가해보자. 숫자 123을 쓰거나 "enqueue"한다:
[ 123, , , , ]
r
---> w
데이터를 추가할 때마다 쓰기 포인터가 한 칸씩 앞으로 이동한다. 몇 개의 요소를 더 추가해보자:
[ 123, 456, 789, 666, ]
r
-------------> w
이제 배열에 한 자리가 남았지만, 앱이 데이터를 읽기로 결정했다. 쓰기 포인터가 읽기 포인터보다 앞서 있기 때문에 읽을 데이터가 있다. 읽기 포인터는 사용 가능한 데이터를 읽으면서 앞으로 이동한다:
[ 123, 456, 789, 666, ]
---> r w
두 개의 아이템을 더 읽어보자:
[ 123, 456, 789, 666, ]
--------> r w
이제 앱이 다시 쓰기를 결정하고 두 개의 데이터 아이템 333과 555를 enqueue한다:
[ 123, 456, 789, 666, 333 ]
r ---> w
쓰기 포인터가 배열의 끝에 도달했기 때문에 555를 저장할 공간이 없다. 이제 어떻게 해야 할까? 여기서 순환 버퍼의 개념이 등장한다. 쓰기 포인터를 배열의 시작 부분으로 돌려 나머지 데이터를 쓴다:
[ 555, 456, 789, 666, 333 ]
---> w r
이제 666, 333, 555 세 개의 아이템을 읽을 수 있다.
[ 555, 456, 789, 666, 333 ]
w --------> r
읽기 포인터가 버퍼의 끝에 도달하면 마찬가지로 순환한다:
[ 555, 456, 789, 666, 333 ]
w
---> r
이제 읽기 포인터가 쓰기 포인터를 따라잡았기 때문에 버퍼가 다시 비어 있다.
Swift로 구현한 매우 기본적인 예제는 다음과 같다:
public struct RingBuffer<T> {
fileprivate var array: [T?]
fileprivate var readIndex = 0
fileprivate var writeIndex = 0
public init(count: Int) {
array = [T?](repeating: nil, count: count)
}
public mutating func write(_ element: T) -> Bool {
if !isFull {
array[writeIndex % array.count] = element
writeIndex += 1
return true
} else {
return false
}
}
public mutating func read() -> T? {
if !isEmpty {
let element = array[readIndex % array.count]
readIndex += 1
return element
} else {
return nil
}
}
fileprivate var availableSpaceForReading: Int {
return writeIndex - readIndex
}
public var isEmpty: Bool {
return availableSpaceForReading == 0
}
fileprivate var availableSpaceForWriting: Int {
return array.count - availableSpaceForReading
}
public var isFull: Bool {
return availableSpaceForWriting == 0
}
}RingBuffer 객체는 데이터를 실제로 저장하는 배열과 배열 내의 "포인터" 역할을 하는 readIndex와 writeIndex 변수를 가지고 있다. write() 함수는 새로운 요소를 writeIndex 위치에 배열에 추가하고, read() 함수는 readIndex 위치의 요소를 반환한다.
하지만 여기서 의문이 생길 수 있다. 이 순환은 어떻게 작동하는 것일까? 이를 구현하는 방법은 여러 가지가 있지만, 여기서는 약간 논란이 될 수 있는 방법을 선택했다. 이 구현에서는 writeIndex와 readIndex가 항상 증가하며 실제로 순환하지 않는다. 대신 배열의 실제 인덱스를 찾기 위해 다음과 같이 계산한다:
array[writeIndex % array.count]그리고:
array[readIndex % array.count]즉, 읽기 인덱스와 쓰기 인덱스를 배열의 크기로 나눈 나머지를 사용한다.
이 방법이 약간 논란이 되는 이유는 writeIndex와 readIndex가 항상 증가하기 때문에 이론적으로는 이 값들이 정수형에 담기에는 너무 커져서 앱이 충돌할 수 있다는 점이다. 하지만 간단한 계산을 통해 이러한 걱정을 해소할 수 있다.
writeIndex와 readIndex는 64비트 정수이다. 초당 1000번씩 증가한다고 가정하면, 이는 매우 많은 횟수이다. 이를 1년 동안 계속한다면 ceil(log_2(365 * 24 * 60 * 60 * 1000)) = 35 비트가 필요하다. 따라서 28비트가 남으므로 문제가 발생하기까지 약 2^28년이 걸린다. 이는 매우 긴 시간이다. :-)
이 링 버퍼를 테스트하려면 코드를 플레이그라운드에 복사하고 위의 예제를 따라해보자:
var buffer = RingBuffer<Int>(count: 5)
buffer.write(123)
buffer.write(456)
buffer.write(789)
buffer.write(666)
buffer.read() // 123
buffer.read() // 456
buffer.read() // 789
buffer.write(333)
buffer.write(555)
buffer.read() // 666
buffer.read() // 333
buffer.read() // 555
buffer.read() // nil링 버퍼가 더 효율적인 큐를 만들 수 있지만 단점도 있다. 순환 구조 때문에 큐의 크기를 조정하는 것이 까다롭다. 하지만 고정 크기의 큐가 목적에 적합하다면 문제없이 사용할 수 있다.
링 버퍼는 데이터 생산자가 데이터를 쓰는 속도와 소비자가 데이터를 읽는 속도가 다를 때 매우 유용하다. 이는 파일이나 네트워크 I/O에서 자주 발생한다. 또한 링 버퍼는 고우선순위 스레드(예: 오디오 렌더링 콜백)와 다른 느린 시스템 부분 간의 통신에 선호되는 방식이다.
여기서 제공된 구현은 스레드 안전하지 않다. 이는 링 버퍼가 어떻게 작동하는지 보여주기 위한 예제일 뿐이다. 그러나 OSAtomicIncrement64()를 사용해 읽기와 쓰기 포인터를 변경함으로써 단일 읽기와 단일 쓰기에 대해 스레드 안전하게 만드는 것은 상당히 간단할 것이다.
매우 빠른 링 버퍼를 만드는 멋진 트릭은 운영 체제의 가상 메모리 시스템을 사용해 동일한 버퍼를 다른 메모리 페이지에 매핑하는 것이다. 복잡하지만 고성능 환경에서 링 버퍼를 사용해야 한다면 알아볼 만한 가치가 있다.
Swift Algorithm Club의 Matthijs Hollemans가 작성함