락프리 링 버퍼 최적화

AI 요약

단일 생산자·단일 소비자(SPSC) 큐는 제약을 활용해 동기화 비용을 줄이는 사례입니다. 글은 고정 용량 배열과 두 인덱스로 구성한 링 버퍼를 구현한 뒤, 스레드 안전성을 확보하고 병목을 단계적으로 제거합니다. 링 버퍼는 선입선출(FIFO) 순서를 지키며, 가득 차면 생산자가 대기하거나 아직 읽지 않은 항목을 덮어쓰도록 설계합니다.

배열과 인덱스로 시작하기

첫 구현은 배열과 head, tail 인덱스를 사용합니다. head는 다음에 쓸 위치를, tail은 다음에 읽을 위치를 가리킵니다. 비어 있는 상태와 가득 찬 상태를 구분하려고 슬롯 하나를 항상 비워 둡니다. head가 tail 바로 앞에 있으면 가득 찬 상태이고, 두 인덱스가 같으면 빈 상태입니다. push는 현재 head 위치에 값을 쓴 뒤 인덱스를 한 칸 옮깁니다. pop은 tail 위치의 값을 읽고 tail을 전진시킵니다. 배열 크기가 2의 거듭제곱이면 나머지 연산이나 분기 대신 비트 마스크로 순환 위치를 계산할 수도 있다고 설명합니다.

뮤텍스에서 원자 연산으로

여러 스레드가 동시에 접근하는 버전에서는 push와 pop에 뮤텍스를 적용합니다. 정확하고 충분히 빠른 상황도 있지만, 글의 벤치마크에서는 초당 약 1,200만 회를 기록합니다. 생산자만 head를 쓰고 소비자만 tail을 쓴다는 점을 이용하면 두 작업을 매번 하나의 잠금으로 묶지 않아도 됩니다. 각 인덱스를 원자 변수로 바꾸고 서로 다른 캐시 라인에 배치해 false sharing을 줄입니다. 이 방식은 초당 3,500만 회를 기록합니다.

메모리 순서 조정

원자 변수의 기본 메모리 순서는 순차 일관성(seq_cst)입니다. 글은 이를 명시적으로 조정합니다. 스레드가 자기 인덱스를 읽을 때는 다른 스레드가 해당 인덱스를 쓰지 않으므로 relaxed를 사용합니다. 상대 스레드의 인덱스를 확인할 때는 acquire로 읽고, 자신의 인덱스를 갱신할 때는 release로 저장합니다. release 이전의 쓰기가 acquire로 읽는 쪽에 보이도록 순서를 보장하면서 불필요한 제약을 덜어냅니다. 조정 뒤 처리량은 초당 1억 800만 회로 올라갑니다.

상대 인덱스 읽기 줄이기

남은 병목은 생산자와 소비자가 상대방 인덱스를 자주 읽으면서 캐시 라인이 코어 사이를 오가는 현상입니다. 이를 줄이려고 생산자는 tail의 로컬 캐시를, 소비자는 head의 로컬 캐시를 유지합니다. 캐시된 값만으로 공간이나 데이터가 있다고 판단할 수 없을 때에만 원자 인덱스를 다시 읽고 캐시를 갱신합니다. 이 최적화까지 적용한 버전은 초당 3억 500만 회를 기록합니다. 글은 캐시 미스도 perf stat의 cache-misses 이벤트로 비교할 수 있다고 안내합니다.

벤치마크 결과와 조건

비교 결과는 뮤텍스 버전 초당 1,200만 회, 기본 원자 연산 버전 3,500만 회, 메모리 순서를 조정한 버전 1억 800만 회, 상대 인덱스 캐시를 추가한 버전 3억 500만 회입니다. 단일 스레드 버전은 스레드 안전하지 않아 수치 비교에서 제외합니다. 측정은 Intel Core Ultra 5 135U에서 생산자와 소비자를 각각 전용 코어에 고정해 진행했습니다. clang으로 컴파일하고 -O3, -march=native, -ffast-math 옵션을 사용했습니다. 글은 재현을 위해 최소 -O3 최적화를 권하며, 두 스레드를 전용 코어에 고정해 스케줄링 변수를 줄였다고 설명합니다.

원문: David Alvarez Rosa / 번역·요약: Trawling