std::atomic은 느리고 lock-free가 아니다

그리고 스핀락을 구현할 때, atomic operation을 계속 실행하도록 구현하는 사례를 많이 보는데. 이거 많이 느리다. 왜 그런지 알아두자.

Cache Coherence가 보장되는 cpu에서 atomic operation이 왜 필요할까. 하나의 operation은 여러 단계로 쪼개어질 수 있다. 예를 들어 i++ 이라는 코드는 다음과 같은 uop으로 쪼개어질 수 있다.

캐시 일관성 프로토콜은 저기서 “store를 수행할 때” 만 다른 코어들을 잠근다. 그래서 load 실행을 막지 못하기 때문에 Race condition 이 존재한다.

그렇다면 atomic opertion을 구현되려면, 위 세 단계 모두에 대해서 해당 캐시라인을 들고있는 모든 코어들의 캐시버스를 잠궈야 한다. 그렇게 되면 다른 코어들이 전부 방해를 받고 속도가 느려진다. (캐시 일관성 프로토콜도 마찬가지. 거기선 false sharing이란 이름으로 알려져 있음)

+ 위를 보면 알겠지만, 현재 x86의 atomic은 캐시 일관성의 MESI protocol을 사용해 주로 구현된다. MESI protocol이 불가능한 프로세서에서는 메모리 버스 전체를 잠궈버리는 식으로 구현된다.

그래서 atomic operation이 mutex같은 lock이 아니지만 lock을 사용하긴 한다. 물론 lock-free는 종류 구분을 위한거라 맞는 말.

atomic operation은 out-of-order 프로세서에서 명령어 reorder가 제대로 수행되지 못한다. 그래서 파이프라이닝을 제대로 수행하지 못해 오는 성능저하가 있다.

std::atomic 은 연산이 끝난 후, 즉시 다른 코어에서 연산결과를 관측할 수 있어야 하기 때문에 mfence 명령을 동반한다. (or lock 접두) 쓰기가 reorder되거나 버퍼링 되면 결과를 곧바로 기록하지 않을 수 있기 때문이다.

이 mfence는 위에서 말한 reodering 을 제한하기도 하고, cpu에는 write-combined buffer라고 하는 버퍼가 있는데 이를 flush해야 한다.

(cpu에서 bus transaction을 열려면 꽤 많은 시간이 들고, 한 번 열리면 burst mode로 캐시라인 단위로 빠르게 전송할 수 있다. 그래서 write할 메모리를 캐시라인 단위로 모아놨다가 버스 개통시 한 번에 flush 한다.)

여기서 flush를 해야 한다면 버스를 마스터링 하는 시간 걸리고, write-combined buffer가 캐시라인 단위로 꽉 채워지지 않았다면 캐시라인 단위로 한번에 전송하지 못하고 워드단위로 하나하나 메모리에 써야한다.

위에서 서술했듯이 atomic operation을 수행할 때 마다 다른 코어들의 캐시가 계속 잠긴다.

이럴 땐, 한 번 atomic으로 try_lock을 검사하고 락을 획득할 수 없다면 x86같은 경우에 pause라는 yield 명령어가 있다. 20-500클럭 정도 대기하는데, 이걸 써서 대기하다가 풀리면 atomic으로 한 번 더 검사하고 그래도 여전히 획득 할 수 없다면 wait상태로 들어가거나 아까 과정을 반복한다.

(pause를 하지 않고 지속적으로 cmp하면 메모리 순서 위반으로 파이프라인을 flush해야돼서 느릴 수 있다는데 그건 잘 모르겠다. Wait for memory pipeline to become empty라고 한다. 그 외에도 기다리는 동안 하이퍼스레드 등으로 다른 작업을 수행하고 있을 수 있다)