lock-free 와 최적화에서 트랙백
위 글 말미에 T아저씨도 언급했지만, 공짜 점심의 시대는 끝나가고 있다. (Your free lunch will soon be over. What can you do about it?) 물론 최근에 출시되신 진리의 네할렘님께서 아직 남겨진 공짜 점심이 있다는 걸 보여주긴 했지만, 어쨌든 곧 공짜 점심의 시대가 끝날 것 같긴 하다.
바라든 바라지 않든, 시대가 parallel로 가고 있으니 시대의 고전인 Amdahl’s law를 다시 살펴보자.
Amdahl's law
우리의 목표는
Break Amdahl’s Law!에서 Herb Sutter가 언급한 것처럼 s를 줄이거나 p를 늘리는 데에 있다. lock-free의 지향점 또한 s를 p로 변환하여 s를 줄이는데 있다.
하지만, 현실은 좀 시궁창이라서, 가장 많이 쓰고 널리 알려진 lock-free alogorithm인 lock-free queue의 경우에도 s를 p로 변환하지는 못한다. lock-free queue가 lock을 이용한 구현에 비한 장점은 push와 pop이 동시에 이루어진다는 것 뿐이고, 이는 단지 이상적인 경우에 Amdahl’s law의 밑변에 있는 s를 s/2로 바꿔줄 뿐이다. 거기에 그렇게 바꾸는 데 필요한 비용또한 싼 편은 아니다.(reorder와 lock-free algorithm 참고)
s를 p로 완전히 전환시켜줄 lock-free alogorithm이 나타난다면, 쓰지 않을 이유는 없다. 하지만 적어도 지금은 아니다.:p 차라리 그걸 도입할 시간에 s를 줄이거나 p를 늘려줄 contents specific한 디자인의 변경을 찾아보는 게 낫다.
한줄요약. 닥치고 spin-lock.
volatile 과 memory barrier에서 트랙백
회사에서 일하다가 T아저씨의 꼬임에 빠져 함께 몇가지 자료를 수집했다. 정리해보자면
Fun programming problem: a simple lock-free algorithm에 따르면 volatile keyword는 원래 MM I/O를 위해 고안되었었고, C++ Standard에 명시된 기능은 아래와 같다.
- volatile 변수에 대한 R/W 작업은 compiler에 의해 삭제되지 않는다.
- volatile 변수에 대한 R/W 작업 간의 순서는 compiler에 의해 reorder되지 않는다.
그리고 MS VC Compiler는 여기에 세가지를 추가했다.
- global 변수(volatile이 아닐지라도)에 대한 R/W작업은 volatile 변수에 대한 read 이전으로 reorder되지 않는다.
- global 변수(volatile이 아닐지라도)에 대한 R/W작업은 volatile 변수에 대한 write 이후로 reorder되지 않는다.
- 이 규칙들은 hardware level에서도 적용된다.
위 포스팅에서, Eric Eilebrecht는 volatile만으로 구현했을 때 오류가 발생할 수 있는 간단한 lock-free algorithm을 소개하고 있다. 포스팅에서 언급한 바와 같이, reorder에 의해 발생한 버그는
- 발생 확률이 극단적으로 낮고
- 어셈블리를 직접 보지 않고서는 왜 발생했는지 찾기가 불가능하다.
이는 단순히 compiler level에만 국한되지 않는다. 많은수의 CPU는 Out-of-Order로 동작하며, 때문에 byte code의 순서가 옳다 하더라도 CPU level에서 변경될 수 있다.(In-Order CPU라고 무조건 예외는 아니다. Lockless Programming Considerations for Xbox 360 and Microsoft Windows) 다행히 주종인 x86/x64 CPU의 경우 이러한 문제점을 방지하기 위한 몇가지 규칙을 가지고 있는데 Who ordered memory fences on an x86?에 따르면
- Load명령어끼리는 서로 reorder되지 않는다.
- Store명령어끼리는 서로 reorder되지 않는다.
- Store명령어는 이전의 Load명령어와 reorder되지 않는다.
- MP환경에서 reorder는 인과 관계를 따른다.(transitive visibility)
- MP환경에서 같은 메모리 주소에 대한 Store는 total order를 가진다.(모든 CPU의 시점에서 같은 순서로 값이 저장된다.)
- MP환경에서, locked instruction들은 total order를 가진다.
- Load/Store명령어는 locked instruction과 reorder되지 않는다.
와 같은 규칙을 가지고 있고, 1, 2, 3번 규칙만으로도 대부분의 경우에 발생할 수 있는 문제는 해결된다. (포스팅에서 문제가 되는 경우에 대한 간단한 예제를 확인할 수 있다.)
CPU에 의한 reorder를 명시적으로 막기 위한 instruction들을 Memory Barrier(memory fence, fence instruction)라고 부른다. 다만, x86/x64의 경우 locked instruction을 호출하는 것만으로 reorder를 방지할 수 있기 때문에, How Does KeMemoryBarrier Work?에서처럼 명시적인 fence instruction을 호출하지 않고, 의미없는 locked instruction을 호출함으로써 fence instruction을 대체할 수 있다.
compiler reorder를 방지하기 위해서는
- 인라인 어셈블리를 사용하여 어셈블리 구문 위 아래로 최적화를 방지해 reorder를 막거나
- compiler에게 hint를 주는 intrinsic(_ReadWriteBarrier)을 사용하여 방지할 수 있다.
문제는, 위에서도 언급했듯 reorder로 인해 발생하는 버그는 디버깅이 극히 어렵기 때문에(compiler reorder의 경우 byte code를 보고 찾을 가능성이라도 가지고 있지만, hardware reorder는 천부적인 감각으로 찾아내는 방법 외엔 답이 없다.) 검증되지 않은 lock-free algorithm을 쓰는 것은 매우 위험하다. 더군다나 quick-sort가 만들어졌을 때와 마지막 버그가 잡혔을 때 사이의 시간 간격을 생각해보면, 충분히 검증되었다고 생각되는 알고리즘도 그렇지 않을 가능성이 충분하다.(거기에 platform dependent하기까지 하다.)
한줄요약. 어지간히 크리티컬한 게 아니라면, 쓸데없는 곳에 로망을 꽃피우지 말고 lock과 함께 사는 것이 정신건강에 이롭다.
도메인은 되찾았으나, 게으름이 천성이다 보니 포스팅은 안하는 날들이 계속되고, 새 기분이라도 내보려 WordPress로 갈아타봤음.
그리하여, 환영합니다:p