Concurrent Data Structures

References

• Ch 6, The Art of Writing Efficient Programs

Contents

• Building Blocks for Concurrent Programming
• Counters and Accumulators
• Publishing Protocol
• Publishing Pointer
• Thread-Safe Shared Pointer (Atomic Shared Pointer)

---

포스팅에서 사용된 모든 코드는 link에서 확인할 수 있음

 

동시 프로그램 개발은 일반적으로 상당히 어려운 편에 속한다. 특히 몇 가지 요소에 의해서 더 어려워진다. 예를 들어, 정확성과 효율성을 모두 만족하는 동시 프로그램, 뮤텍스가 많은 복잡한 프로그램이나 lock-free 프로그램은 더욱 어렵다.

 

이러한 복잡성을 관리하는 좋은 솔루션은 이를 작고 잘 정의된 모듈로 모으는 것이다. 인터페이스와 요구 사항이 명확한 모듈이 있으면 사용자는 구현의 세부 사항은 알 필요가 없다. 다만, 이는 성능에 영향을 미치므로 최적화될 때까지 특정 요구 사항에 비해 모듈의 성능이 너무 느릴 수 있다. 하지만, 필요에 따라 이러한 최적화를 특정 모듈에만 국한되게 적용할 수 있다.

 

이번에는 동시 프로그래밍을 위한 데이터 구조를 구현하는 모듈에 중점을 둔다. 데이터 구조는 알고리즘이 의존할 수 있는 보장과 제한 사항들을 결정하기 때문에 매우 중요한 역할을 한다. 동일한 데이터에 대해 어떠한 동시 작업을 안전하게 수행할 수 있는지, 서로 다른 스레드에서 볼 수 없는 데이터의 일관성은 어떠한지에 대한 대답은 선택한 데이터 구조에 따라 결정된다.

 

이와 동시에 인터페이스 및 모듈 경계를 선택하는 것과 같은 설계는 동시 프로그램을 구현할 때 발생하는 선택에 결정적인 영향을 미칠 수 있다. 동시성을 설계 중간에 추가할 수 없으며, 설계는 처음부터 동시성을 염두에 두고 작성되어야 한다. 특히 데이터 구성은 필수이다.

 

The Basics of Concurrent Data Structures

여러 스레드를 사용하는 동시 프로그램에는 당연히 스레드로부터 안전한(thread-safe) 데이터 구조가 필요하다. 여기서 스레드 안전성이란 무엇이며, 데이터 구조를 스레드로부터 안전하게 만드는 것은 무엇일까? 여러 스레드에서 동시에 데이터 구조를 사용할 수 있으면 thread-safe로 간주할 수 있다. 언뜻보면 간단해 보이지만, 사실 이 정의는 너무 단순하긴 하다. 예를 들어, STL 컨테이너는 모드 스레드로부터 안전하지 못하다. 또한, 스레드로부터 안전한 데이터 구조는 매우 높은 비용을 수반하며 불필요한 경우가 많다. 무엇보다 대부분의 경우에는 쓸모 없을 때가 많다.

 

이러한 고려 사항들을 하나씩 살펴보자.

 

멀티스레드 프로그램에서조차 스레드로부터 안전한 데이터 구조가 불필요한 이유는 무엇일까? 한 가지 자명한 가능성은 단일 스레드 부분에서 사용되는 것이다. 전체 런타임에서 단일 스레드로만 수행되는 경우를 최소화하려고 하지만, 대부분의 프로그램에서 이런 부분은 불가피하다. 이를 더 빠르게 만드는 방법 중 하나는 불필요한 오버헤드를 제거하는 것이다. 일반화시키면 다중 스레드 프로그램에서 객체가 하나의 스레드에서만 독점적으로 사용되는 경우에 thread-safe가 필요없다고 말할 수 있다. 이는 매우 일반적이고 바람직하다. 공유 데이터는 동시 프로그램의 비효율성의 주요 원인이므로 지역 변수와 데잍어만 사용하여 각 스레드에서 독립적으로 최대한 많은 작업을 수행해야 한다.

 

각 객체가 스레드 간 공유되지 않더라도 반드시 클래스나 데이터 구조가 멀티스레드 프로그램에서 사용하기 안전한 것은 아니다. 인터페이스 수준에서는 공유되지 않더라도 구현 수준에서 여러 객체가 내부적으로 동일한 데이터를 공유할 수도 있다. 예를 들어, malloc()으로 호출하여 할당받은 메모리가 스레드로부터 안전하다고 생각하는 경향이 있다.

 

반면, 많은 데이터 구조들은 스레드들이 객체를 수정하지 않는 한 다중 스레드 코드에서 완벽하게 안전히 사용할 수 있다. 명백한 부분이지만 구현을 다시 고려해야 한다. 인터페이스 자체는 읽기 전용일 수 있지만 구현에서는 여전히 수정할 수 있다. 이에 대한 예시가 바로 C++의 std::shared_ptr 이다. 공유 포인터에 대한 복사본을 만들 때, const reference를 통해 새로운 포인터의 생성자가 전달되지만 동시에 객체의 참조 카운트가 증가한다. 즉, 복사한 객체가 변경되었음을 의미한다. std::shared_ptr의 thread-safe에 대해서는 조금 미묘한 부분이 있으며, 여기서 shared_ptr 자체가 중요한 주제는 아니기 때문에 기회가 되면 따로 다루도록 하겠다.

 

결론은 thread-safe에 대해서 보다 세부적인 정의가 필요하다는 것이다. 아쉽지만 이러한 일반적인 개념에 대한 공통적으로 지칭하는 용어는 없지만 흔히 사용되는 두 가지 버전의 용어가 있다.

• strong thread safety guarantee - 최고 수준의 스레드 안전성. 이러한 보장을 제공하는 객체는 data race나 기타 undefined behabior를 일으키지 않고 여러 스레드에서 동시에 사용할 수 있다.
• weak thread safety guarantee - 약한 수준의 스레드 안전성. 모든 스레드가 read-only 액세스로 제한되는 한 여러 스레드에서 동시에 액세스할 수 있음을 보장하는 객체를 의미한다.

강력한 안전성 보장을 제공하는 클래스를 간단히 thread-safe라고 부르고, 약한 스레드 안전성을 보장하는 객체는 thread-compatible이라고 부르는 경우도 있다. 대부분의 STL 컨테이너는 thread-compatible 보장을 제공한다. 즉, 컨테이너 객체가 여러 스레드에 공유되는 경우, const 멤버 함수만 호출할 수 있다. 마지막으로 스레드 안전성을 전혀 보장하지 않는 객체를 thread-hostile이라고 부르며, 멀티스레드 프로그램에서 전혀 사용할 수 없다.

 

실제 경우에서는 강한 보장과 약한 보장이 혼합된 경우를 자주 접하게 되며, 일반적으로 일부 인터페이스는 강한 보장을 제공하지만 나머지는 약한 보장을 제공한다.

 

일반적으로 성능 오버헤드와 객체가 스레드 간에 공유되지 않아서 강력한 보장이 불필요한 경우가 많기 때문에 강력한 스레드 안전성을 보장하는 모든 객체를 설계하려고 노력하지 않는다. 그리고, 효율적인 프로그램의 핵심은 피할 수 있는 작업을 수행하지 않는 것이다. 또한, 객체가 스레드 안전성을 요구하더라도 강력한 스레드 안전성은 불필요할 수 있다.

 

결론을 이야기하자만 스레드 안전성은 설계 단계부터 고려되어야 한다는 것이다. 프로그램에서 사용되는 데이터 구조와 인터페이스를 설계 초기부터 고려해야 스레드 간 상호작용이 발생하는 수준에서 적절한 레벨의 추상화와 올바른 트랜잭션을 나타낼 수 있다. 이를 염두하여 이번 포스팅에서는 더 복잡한 빌딩 블록으로 사용할 수 있는 몇 가지 기본적인 thread-safe 데이터 구조를 설계하고 구현하는 방법과 보다 복잡한 데이터 구조를 설계하는 데 사용할 수 있는 thread-safe 클래스를 구축하기 위한 기본 기법을 중점으로 살펴본다.

 

Counters and Accumulators

가장 간단한 스레드에 안전한 객체 중 하나는 카운터, 일반화하면 누산기(accumulator)이다. 카운터는 단순히 스레드에서 발생하는 이벤트를 카운트하며, 모든 스레드는 카운터를 증가시키거나 현개 값에 액세스할 수 있으므로 경쟁 조건이 발생할 가능성이 있다. 멀티스레드 환경에서 이를 사용하려면 강력한 스레드 안전성이 필요하다. 약한 스레드 안전성은 당연하다. 이전 포스팅(Lock-Based, Lock-Free, Wait-Free Program)에서 여러 가지 종류의 락을 살펴봤었다 (아토믹 연산, lock-free CAS loop).

 

락의 성능은 구현에 따라 다르지만 일반적으로 스핀락이 선호된다. 카운터에 즉시 액세스하지 못한 스레드의 대기 시간은 매우 짧기 때문에 스레드를 유휴 상태로 전환했다가 다시 깨우는 비용이 더 클 수 있다. Busy waiting으로 인해 낭비되는 CPU 시간은 무시할 수 있을 정도로 작다.

 

아토믹 명령어는 성능이 좋지만 사용할 수 있는 연산에 제약이 있다. 예를 들어, C++에서는 정수를 원자적으로 더할 수 있지만 곱하는 등의 작업은 할 수 없다. 기본적인 카운터에는 충분할 수 있으나, 일반화된 누산기에는 충분하지 않다. 하지만, 더하는 것만으로 충분하다면 아토믹 연산이 가장 단순하다.

 

CAS 루프는 사용하는 연산에 관계없이 모든 누산기를 구현하는데 사용할 수 있다. 그러나 대부분의 최신 하드웨어에서 가장 빠른 옵션은 아니며, 이전 포스팅의 결과를 보면 스핀락보다 성능이 떨어진다.

 

스핀락의 경우, 단일 변수나 단일 객체에 액세스하는 데 사용되는 경우 더 최적화될 수 있다. 제너릭한 플래그 대신 락 자체를 객체에 대한 유일한 참조로 만들어 사용할 수 있다(포인터 스핀락). 아토믹 변수는 정수가 아닌 포인터가 되지만, 락 메커니즘은 변하지 않는다. 다만, lock() 함수는 카운터에 대한 포인터를 반환하므로 비표준이 되어서 std::lock()과 같은 유틸리티 함수를 사용할 수 없다.

class Ptrlock
{
public:
    Ptrlock(std::atomic<unsigned long*>& p) : p_{p}, p_save_{nullptr} {}
    unsigned long* lock() {
        static const timespec ns = { 0, 1 };
        unsigned long* p = nullptr;
        
        for (int i = 0; !p_.load(std::memory_order_relaxed) || !(p = p_.exchange(nullptr, std::memory_order_acquire)); ++i) {
            if (i == 8) {
                i = 0;
                nanosleep(&ns, NULL);
            }
        }
        return p_save_ = p;
    }
    void unlock() {
        p_.store(p_save_, std::memory_order_release);
    }

private:
    std::atomic<unsigned long*>& p_;
    unsigned long* p_save_;
};

스핀락 구현과 비교해보면 아토믹 변수의 의미가 반전된다. 아토믹 변수 p_가 nullptr이 아니라면 락을 획득할 수 있고, 그렇지 않으면 대기 한다. 스핀락에 적용한 모든 최적화는 여기에도 동일하게 적용된다. 스핀락과 마찬가지로 완벽한 구현은 아니다 (non-copyable 등이 구현되지 않음).

 

포인터 스핀락의 한 가지 장점은 보호되는 객체에 액세스할 수 있는 유일한 방법을 제공하는 한 실수로 경쟁 조건을 만들거나 락 없이 공유 데이터에 액세스하는 것이 불가능하다는 것이다. 두 번째 장점은 이 구현이 일반 스핀락보다 성능이 약간 더 뛰어나다는 것이다. 스핀락이 아토믹 연산보다 성능이 뛰어난지 여부는 하드웨어에 따라 다르며, 동일한 벤치마크라도 프로세서마다 다른 결과가 나온다. 아래 그래프는 서로 다른 두 프로세서에서 동일한 벤치마크를 테스트한 결과이다 (위 결과에 사용된 프로세서가 아래 결과의 프로세서보다 더 높은 세대의 intel CPU이다).

M1 Mac의 경우, 아래와 같은 성능을 보여준다.

일반적으로 최신 프로세서는 락 및 busy waiting을 더 잘 처리하며, 스핀락이 더 나은 성능을 제공할 가능성이 높다. 작업을 실행하는데 걸리는 평균 시간(또는 처리량)은 대부분의 HPC 시스템에서 주로 관심을 갖는 측정 메트릭이다. 하지만, 동시 프로그램의 성능을 측정하는데 사용되는 유일한 기준은 아니다. 예를 들어, 모바일 장치에서 실행되는 경우에는 전력 소비가 더 중요할 수 있다. 이런 경우에는 전력 소비가 더 중요할 수 있다. 모든 스레드가 사용하는 총 CPU 시간은 평균 전력 소비를 측정하는데 합리적일 수 있다. 아래는 각 락에 대한 CPU 시간 측정 결과이다.

 

결과를 살펴보면, 구현에 관계없이 여러 스레드가 동시에 공유 데이터에 액세스하는 비용은 스레드 수에 따라 증가한다는 것이다. 그러나 효율성은 구현마다 크게 다르며, 특정 구현은 스레드가 8개가 될 때까지 크게 증가하지 않는 모습을 보여주기도 한다. 결과는 하드웨어마다 다르므로 타겟 플랫폼을 염두하고 측정한 뒤 선택해야 한다.

 

그런 다음, 구현에 관계없이 스레드로부터 안전한 카운터나 누산기를 노출하기 않고 클래스에 캡슐화해야 한다. 이렇게 하는 첫 번째 이유는 구현을 최적화하면서도 클래스 사용자에게 안정적인 인터페이스를 제공하기 위함이다.

 

두 번째 이유는 조금 미묘하며, 카운터가 제공하는 정확한 보장과 관련이 있다. 지금까지 카운터 값 자체에 초점을 맞추어 데이터 경합 없이 모든 스레드에서 해당 값이 수정되고 액세스되는지 확인했다. 이것이 충분한지 여부는 카운터를 어떻게 사용하느냐에 따라 다르다. 원하는 동작이 일부 이벤트의 수를 계산하는 것 뿐이며, 그 외에 카운터 값에 의존하는 것이 없다면 값 자체가 올바른지 여부만 고려하면 된다. 반면, 카운터 값이 배열 요소의 갯수라면 데이터 종속성을 다루고 있다는 것이다. 미리 할당된 큰 배열이 있고, 모든 스레드가 이 배열에 삽입될 새 요소를 계산하고 있다고 가정해보자. 카운터는 계산되고 배열에 삽입될 요소의 갯수를 카운트하고, 이 값은 다른 스레드에서 사용할 수 있다. 즉, 스레드가 카운터로부터 N이라는 값을 읽으면 배열에서 N개의 요소를 읽어도 안전하다는 것이 보장되어야 한다 (다른 스레드가 더 이상 수정하지 않음). 그러나 배열 자체는 원자적이지 않고 락으로 보호되지도 않는다. 락으로 전체 배열에 대한 액세스를 보호할 수 있지만 프로그램의 성능을 저하시킬 것이다. 반면, 우리는 어떤 상수나 불변 데이터는 락 없이 여러 스레드에서 읽어도 안전하다는 것을 알고 있다. 따라서, 우리는 불변 데이터와 변경되는 데이터의 경계를 알아야 하며, 이것이 바로 카운터가 제공해야 하는 것이다. 여기서 중요한 문제는 메모리 가시성(memory visiblity)인데, 카운터 값이 N-1에서 N으로 변경되기 전에 배열의 처음 N개의 요소에 대한 모든 변경사항이 다른 모든 스레드에 표시된다는 보장이 필요하다.

 

메모리 가시성을 제어하는 방법은 메모리 순서(memory order)를 제한하거나 메모리 장벽(memory barrier)을 사용하는 것이다. 멀티스레드 프로그램에서 카운트와 인덱스의 주요한 차이점은 인덱스는 추가적인 보장을 제공한다는 것이다. 만약 인덱스 값을 N-1에서 N으로 증가시키는 스레드가 인덱스 값을 증가시키기 전에 배열 요소 N의 초기화를 완료하는 경우, 이 인덱스를 읽고 N 또는 그보다 큰 값을 얻는 다른 스레드는 최소한 N개의 배열 요소가 완전히 초기화되어 안전하게 읽을 수 있음을 보장한다 (다른 스레드가 이러한 요소에 write하지 않는다는 가정 하에). 이는 중요한 보장이며 쉽게 무시해서는 안된다. 이러한 보장이 없다면 배열에 대한 모든 액세스를 보호해야 하며, 단 하나의 스레드만 배열에 액세스할 수 있도록 해야 한다.

 

아토믹 카운터와 아토믹 인덱스 클래스 구현은 다음과 같다.

class AtomicCount {
    std::atomic<unsigned long> c_;

public:
    unsigned long incr() noexcept {
        return 1 + c_.fetch_add(1, std::memory_order_relaxed);
    }
    unsigned long get() const noexcept {
        return c_.load(std::memory_order_relaxed);
    }
};

class AtomicIndex {
    std::atomic<unsigned long> c_;

public:
    unsigned long incr() noexcept {
        return 1 + c_.fetch_add(1, std::memory_order_release);
    }
    unsigned long get() const noexcept {
        return c_.load(std::memory_order_acquire);
    }
};

유일한 차이점은 메모리 가시성 보장이다. 아토믹 카운터의 경우, 어떠한 보장도 제공하지 않는다.

 

둘 사이의 성능 차이 여부는 하드웨어에 따라 다르다. x86 CPU의 경우에는 아토믹 카운터는 atomic increment와 atomic read에 대한 하드웨어 명령이 요청하는 메모리 순서에 관계없이 아토믹 인덱스와 유사한 메모리 장벽을 가지므로, 성능 차이가 없다. ARM CPU에서는 relaxed memory 연산이 더 빠르다. M1 Mac에서의 성능은 다음과 같다.

 

Publishing Protocol

우리가 해결하고자 하는 일반적인 문제는 데이터 구조 설계와 동시 프로그램 개발에서 매우 흔하다. 하나의 스레드에서 새로운 데이터를 생성하고 나머지 다른 스레드들은 이 데이터가 준비되면 볼 수 있어야 한다. 데이터를 생성하는 스레드를 writer thread 또는 producer thread라고 부르고, 다른 모든 스레드들은 reader 또는 consumer threads라고 부른다.

 

가장 확실한 해결 방법은 락을 사용하고 데이터 경합을 피하도록 하는 것이다. 여러 스레드가 동일한 메모리 위치에 액세스하고 적어도 하나의 스레드가 이 위치에 값을 변경하는 경우, 모든 스레드는 이 메모리 위치에 액세스하기 전에 락을 획득해야 한다. 이 방법의 단점은 성능이다. 생산자 스레드가 데이터 생성을 완료한 이후에도 모든 소비자 스레드는 동시에 데이터를 읽을 수 없도록 락을 사용한다. read-only 액세스에는 락이 전혀 필요하지 않지만, 락을 사용하지 않으려면 이전에 모든 write가 발생하고 모든 read는 이후에 발생하도록 프로그램 내에서 보장되는 시점이 있어야 한다는 것이다. 이를 만족하면 모든 소비자 스레드는 read-only 환경에서 동작하여 락이 필요하지 않다고 말할 수 있다. 여기서의 문제는 read와 write 사이의 경계를 보장하는 것이다. 일종의 동기화를 수행하지 않으면 메모리 가시성이 보장되지 않음에 주의해야 하며, 생성자 스레드가 메모리 수정을 마쳤더라도 소비자 스레드에서 해당 메모리의 최종 상태를 볼 수 있는 것은 아니다.

 

락 없이 위와 같은 보장을 얻기 위한 솔루션은 아래와 같이 생산자 스레드와 소비자 스레드 간에 정보를 전달하기 위한 매우 구체적인 프로토콜에 의존한다.

• 생산자 스레드는 다른 스레드가 액세스할 수 없는 메모리에 데이터를 준비한다. 이는 생산자 스레드에 의해 할당된 메모리일 수도 있고, 사전에 할당되어 있는 메모리일 수도 있지만, 중요한 것은 생산자가 이 메모리에 대한 유효한 참조를 가진 유일한 스레드이며 다른 스레드와 공유되지 않는다는 것이다. 다른 스레드가 이 메모리에 액세스할 수 있는 방법이 있을 순 있지만, 이는 범위 외의 배열 요소에 인덱싱하는 것과 같은 프로그램의 버그이다. 새로운 데이터에 액세스하는 스레드는 하나만 존재하므로 동기화가 필요하지 않다.
• 모든 소비자 스레드는 데이터에 대한 액세스를 위해 root pointer라고 부르는 단일 공유 포인터를 사용해야 하며, null로 초기화된다. 생산자 스레드가 데이터를 생성하는 동안, 이 포인터는 null로 유지된다. 포인터라고 언급했지만, 실제 포인터일 필요는 없다. 메모리 위치에 대한 액세스를 제공하고 미리 결정된 유효하지 않은 값으로 설정될 수 있는 한 모든 종류의 핸들이나 참조를 사용할 수 있다.
• 이 프로토콜의 핵심은 소비자가 데이터에 액세스할 수 있는 유일한 방법이 root pointer를 통하는 것이며, 이 포인터는 생산자가 데이터를 공개할 준비가 될 때까지 null로 유지된다는 것이다. 데이터는 공유하는 방법은 매우 간단한데, 생산자 스레드가 root pointer에 데이터의 메모리 위치를 원자적으로 저장하는 것이다. 이 아토믹 연산에는 release memory order를 사용해야 한다.
• 소비자 스레드는 언제든지 원자적으로 root pointer를 쿼리할 수 있다. 이 결과가 null인 경우, 데이터가 없다는 것이며 소비자 스레드는 기다리거나 다른 작업을 수행해야 한다. null이 아닌 값이라면 데이터가 준비되었다는 것이며, 생산자는 더 이상 이를 변경하지 않는다. 이 쿼리는 생산자 측의 release barrier와 함께 포인터 값의 변경이 관측될 때 새로운 데이터가 소비자 측에 표시되도록 보장하는 acquire memory barrier를 사용하여 수행되어야 한다.

위 프로세스는 생산자 스레드가 데이터 경합을 보장하지 않는 방식으로 다른 스레드가 소비할 정보를 발행하도록 허용하기 때문에 publishing protocol이라고도 부른다. 사용되는 핸들은 포인터가 가장 일반적이며 그 다음으로는 배열 인덱스가 자주 사용된다.

 

생산자 스레드가 발행하는 데이터는 단순할 수도 있고 복잡할 수도 있다. 이는 중요하지 않으며, 단일 객체이거나 단일 메모리 위치일 필요도 없다. Root pointer가 가리키는 객체 자체에는 더 많은 데이터 포인터가 포함될 수 있다. 이 프로토콜의 핵심 요소는 다음과 같다.

• 모든 소비자 스레드는 하나의 root pointer를 통해 특정 데이터에 액세스한다. 데이터를 액세스하는 유일한 방법은 root pointer가 null이 아닌 값을 읽는 것이다.
• 생산자는 원하는 방식으로 데이터를 준비할 수 있지만, 이때 root pointer는 null로 유지된다. 생산자는 이 스레드에 로컬인 데이터에 대한 자체 참조를 갖는다.
• 생산자가 데이터를 발행하려고 할 때, root pointer를 release barrier를 사용하여 원자적으로 올바른 메모리 주소로 설정한다. 그런 다음에는 생산자가 이를 변경할 수 없다 (다른 스레드도 마찬가지).
• 소비자 스레드는 acquire barrier를 사용하여 root pointer를 원자적으로 읽는다. null이 아닌 값을 읽으면 root pointer를 통해 데이터에 액세스할 수 있다.

이를 구현하는데 사용되는 atomic read 및 write는 코드 전체에 분산되어 있으면 안되며, 캡슐화된 publishing pointer 클래스를 구현해야 한다. 아래에서 이를 위한 간단한 구현을 살펴보자.

Smart Pointers for Concurrent Programming

스레드로부터 안전한 데이터 구조체의 챌린지는 특정 스레드 안전성을 보장하는 방식으로 데이터를 추가하고, 제거하고, 변경하는 방법이다. 위에서 설명한 publishing protocol을 위한 publishing pointer 구현을 살펴보자.

Publishing Pointer

기본적인 publishing pointer 구현은 다음과 같다. unique, owning, pointing 기능을 포함하고 있어서 이를 thread-safe unique pointer라고 부를 수 있다.

template<typename T>
class ts_unique_ptr
{
std::atomic<T*> p_{nullptr};

public:
    ts_unique_ptr() = default;
    explicit ts_unique_ptr(T* p) : p_{p} {}

    ts_unique_ptr(ts_unique_ptr const&) = delete;
    ts_unique_ptr& operator=(ts_unique_ptr const&) = delete;

    ~ts_unique_ptr() {
        delete p_.load(std::memory_order_relaxed);
    }

    void publish(T* p) noexcept {
        p_.store(p, std::memory_order_release);
    }
    const T* get() const noexcept {
        return p_.load(std::memory_order_acquire);
    }
    const T& operator*() const noexcept {
        return *this->get();
    }
    ts_unique_ptr& operator=(T* p) noexcept {
        this->publish(p);
        return *this;
    }
};

위 구현은 매우 기본적인 구현이며, 완전하려면 std::unique_ptr과 유사한 몇 가지 추가 기능들을 지원해야 한다. 하지만 표준에서 std::unique_ptr 객체에 저장된 포인터 값에 대한 액세스가 아토믹이거나 필요한 메모리 장벽이 사용된다는 것을 보장하지 않으므로 위 구현을 통해 publishing protocol을 구현할 수 있다.

 

위 구현의 핵심은 publish()와 get() 메소드이며, 이들이 publishing protocol을 구현한다. publish() 메소드는 이전 데이터를 삭제하지 않으며, 생산자 스레드는 null 포인터를 가리키는 이 객체에서 단 한 번만 publish()를 호출한다고 가정한다.

 

역참조 성능을 위한 벤치마크 구현은 다음과 같다.

ts_unique_ptr<A> p(new A(42));

void BM_ptr_deref(benchmark::State& state) {
    volatile A x;
    for (auto _ : state) {
        REPEAT(benchmark::DoNotOptimize(x = *p);)
    }
    state.SetItemsProcessed(32 * state.iterations());
}

std::unique_ptr<A> rp(new A(42));

void BM_raw_ptr_deref(benchmark::State& state) {
    volatile A x;
    for (auto _ : state) {
        REPEAT(benchmark::DoNotOptimize(x = *rp);)
    }
    state.SetItemsProcessed(32 * state.iterations());
}

생산자 스레드 관점에서 역참조 성능은 raw pointer나 std::unique_ptr의 역참조의 성능과 비슷하다. 당연히 성능 결과는 하드웨어에 따라 다를 수 있다. M1 Mac의 경우에는 일반 포인터나 std::unique_ptr의 역참조의 성능이 훨씬 더 빨랐다.

publish()의 성능을 비교해보진 않았지만, 일반적으로 publish는 단 한 번만 이루어지지만 소비즈 스레드의 역참조는 여러 번 발생하기 때문에 소비자 스레드 측면에서의 성능이 더 중요하다.

 

Publishing pointer가 무엇을 하지 않는지 이해하는 것도 중요하다. 먼저, 포인터 구성/생성에서는 스레드 안전성이 없다. 우리는 생산자 스레드와 소비자 스레드가 null로 초기화되는 이미 생성된 포인터에 대한 액세스를 공유한다고 가정했다. 이 초기화는 데이터 구조를 구성/생성한 스레드에 의해 초기화된다. 지금까지는 단 하나의 데이터가 있고, 단 한 번 publish 한다고 가정했지만, 실제로는 이렇게 간단하지 않을 것이다. 일부 데이터 요소가 root pointer 역할을 하고 그들 자신이 다른 데이터 요소를 가지고 있는 경우를 생각해보자. 간단히 'next' 포인터를 가진 연결 리스트(linked list)를 생각해보면 된다. 리스트의 요소를 생성하는 스레드는 'next' 포인터를 null로 초기화해야 한다. 그런 다음 다른 생산자가 새 요소를 추가하고 publish() 할 수 있다. 하지만, 이는 일단 publish된 데이터는 변경할 수 없다는 일반적인 규칙을 벗어난다는 점에 유의해야 한다. 하지만 스레드에 안전한 unique pointer는 원자적이므로 괜찮다. 어떤 식으로든 포인터가 생성되는 동안 스레드가 그 포인터에 액세스할 수 없도록 하는 것이 중요하다.

 

Publishing pointer가 수행하지 않는 다른 작업은 여러 생산자 스레드에 대한 동기화를 제공하지 않는다는 것이다. 두 스레드가 동일한 포인터를 통해 새로운 데이터를 publish 하려고 시도하면 그 결과는 정의되지 않으며 데이터 경합이 발생한다. 생산자 스레드가 두 개 이상인 경우에는 동기화를 위한 다른 메커니즘을 사용해야 한다.

 

마지막으로 이 포인터는 스레드로부터 안전한 publish protocol을 구현하지만 데이터를 안전하게 un-publish하고 삭제하는 것은 수행하지 않는다. 이 구현은 포인터를 소유하는 것이므로 삭제될 때 데이터도 삭제된다. 하지만 모든 소비자 스레드는 포인터가 삭제된 이후에도 이전에 획득한 값을 사용하여 데이터에 액세스할 수 있다. 데이터 소유권 및 수명 문제는 다른 방식으로 처리되어야 한다. 즉, 스레드로부터 안전한 방식으로 데이터 생성과 삭제를 모두 관리하는 포인터가 필요할 수 있는데, 이 경우에는 thread-safe shared pointer가 필요하다.

 

Atomic Shared Pointer

프로그램에서 데이터를 안전하게 삭제할 수 있는 지점이 있다고 보장할 수 없는 경우에는 데이터에 대한 유효한 포인터를 보유하는 소비자 스레드의 갯수를 추적해야 한다. 이 데이터를 삭제하려면 전체 프로그램에서 해당 데이터에 대한 포인터가 하나만 있을 때까지 기다려야 한다. 그런 다음에 데이터와 포인터 자체를 삭제하는 것이 안전하다. 이는 레퍼런스 카운팅(reference counting)을 수행하는 shared pointer의 일반적인 작업이다. Shared pointer는 동일한 객체에 대한 포인터가 프로그램에 아직 남아 있는지 계산하며, 데이터는 마지막 포인터에 의해서 삭제된다.

 

스레드로부터 안전한 shared pointer에 대해서 이야기할 때는 포인터에 요구되는 보장이 무엇인지 정확하게 이해하는 것이 중요하다. C++ 표준의 std::shared_ptr은 종종 스레드로부터 안전하다고 이야기하며, 다음과 같은 보장을 제공한다.

• 여러 스레드가 모두 동일한 객체를 가리키는 서로 다른 shared pointer에서 동작하는 경우, 두 스레드가 동시에 카운터를 변경하더라도 레퍼런스 카운터에 대한 작업은 스레드로부터 안전하다. 예를 들어, 한 스레드가 shared pointer의 복사본을 만드는 동안 다른 스레드가 shared pointer를 삭제하고 카운트가 N이었다면, 카운터는 N+1로 증가되었다가 다시 N으로 감소되어 결국 동일한 값 N을 갖게 된다. 중간값은 N-1이나 N+1일 수 있지만, 데이터 경합은 없으며 최종 상태를 포함한 동작이 잘 정의된다. 이러한 보장은 레퍼런스 카운터의 작업이 원자적으로 수행된다는 것을 의미한다. 실제로 레퍼런스 카운터는 aotmic integer이며 구현에서는 fetch_add()를 사용하여 원자적으로 증가하거나 감소시킨다.

위 보장은 두 스레드가 동일한 shared pointer에 대한 액세스를 공유하지 않는 한 적용된다. 동일한 객체를 가리키는 모든 shared pointer는 첫 번째 포인터에서 생성되어야 하며, 이러한 포인터는 특정 시점에 한 스레드에서 다른 스레드로 전달되어야 했다. shared pointer의 복사본이 모든 스레드에 분배되면 공유의 오너쉽은 유지되고 객체의 삭제는 스레드 안전한 방식으로 처리된다. 이는 각각의 shared pointer가 둘 이상의 스레드에 의해 처리되지 않는다고 가정했기 때문이다.

 

만약 두 스레드가 동일한 shared pointer에 액세스하려고 시도하지 않는다고 보장할 수 없다면 어떻게 될까? 이러한 액세스에 대한 예시가 바로 이전에 구현한 publishing pointer이다. 소비자 스레드는 포인터 값을 읽지만 생산자 스레드는 포인터 값을 변경할 수 있다 (여러 생산자 스레드가 동일한 publishing pointer를 수정하면 정의되지 않은 동작이 발생하게 된다. 따라서, shared pointer 자체에 대한 작업이 원자적으로 수행되어야 한다. C++20에서는 std::atomic<std::shared_ptr<T>>를 제공하여 이를 지원한다.

 

C++20 호환 컴파일러나 해당 표준 라이브러리가 없고, C++20을 사용할 수 없는 상황에서도 std::shared_ptr에 대한 아토믹 연산을 수행할 순 있지만 명시적으로 수행해야 한다. 모든 스레드 간에 공유되는 shared pointer p_를 사용하여 publish를 수행하려면 생산자 스레드는 아래와 같이 수행해야 한다.

std::shared_ptr<T> p_;
T* data = new T;
... finish initializing the date ...
std::atomic_store_explicit(&p_, std::shared_ptr<T>(data), std::memory_order_release);

반면, 소비자 스레드는 포인터를 얻기 위해서 다음과 같이 수행해야 한다.

std::shared_ptr<T> p_;
const T* data = std::atomic_load_explicit(&p_, std::memory_order_acquire).get();

C++20의 atomic shared pointer와 비교할 때, 위 접근 방식의 주요한 단점은 우연한 non-atomic 액세스에 대한 보호 기능이 없다는 것이다. Shared pointer를 사용하기 위해 항상 아토믹 함수를 사용하는 것은 프로그래머의 책임이다.

 

위 구현처럼 명시적인 아토믹 연산으로 사용하면 편리하긴 하지만 아토믹 액세스로 인해 효율적이지 못하고 속도가 더욱 느려진다. std::shared_ptr 또한 특별히 효율적인 포인터가 아니다. 위에서 구현한 thread-safe unique pointer(publishing pointer)와 일반 shared pointer, 그리고 명시적 atomic shared pointer의 성능을 비교해보면 다음과 같다.

Thread-safe unique pointer와 비교하면 60배 이상 더 느리고, 스레드 수가 증가할수록 더 비효율적이다는 것을 알 수 있다. 물론 shared pointer의 요점은 소유권을 공유하므로 당연히 더 많은 작업을 수행하고 더 많이 시간이 걸린다는 것이다.

 

소유권 공유가 필요하더라도 일부 제한된 기능과 최적의 구현으로 자신만의 레퍼런스 카운트 포인터를 디자인하면 훨씬 더 좋은 결과를 얻을 수 있다. 일반적은 접근 방식은 intrusive shared pointer를 사용하는 것이다. 이는 자신이 가리키는 객체 자체에 레퍼런트 카운트를 저장한다.

// T - type the pointer points to
// U - T with reference counter
//     U must have the following member functions:
//     void AddRef() - atomically increment reference count by 1
//     bool DelRef() - atomically decrement reference count by 1, return true if the counter dropped to 0
template<typename T, typename U = T>
class intr_shared_ptr
{
    struct get_ptr {
        std::atomic<U*>& aptr;
        U* p;
        get_ptr(std::atomic<U*>& ptr) : aptr(ptr), p() {
            static const timespec ns = { 0 , 1 };
            for (int i = 0; aptr.load(std::memory_order_relaxed) == (U*)(locked) || (p = aptr.exchange((U*)(locked), std::memory_order_acquire)) == (U*)(locked); ++i) {
                if (i == 8) {
                    i = 0;
                    nanosleep(&ns, NULL);
                }
            }
        }
        ~get_ptr() {
            aptr.store(p, std::memory_order_release);
        }
        static const uintptr_t locked = uintptr_t(-1);
    };

public:
    class shared_ptr {
    public:
        shared_ptr() : p_(nullptr) {}
        shared_ptr(shared_ptr const& x) : p_(x.p_) {
            if (p_) p_->AddRef();
        }
        ~shared_ptr() {
            if (p_ && p_->DelRef()) {
                delete p_;
            }
        }
        T& operator*() const { return *p_; }
        T* operator->() const { return p_; }
        explicit operator bool() const { return p_ != nullptr; }
        shared_ptr& operator=(shared_ptr const& x) {
            if (this == &x) return *this;
            if (p_ && p_->DelRef()) {
                delete p_;
            }
            p_ = x.p_;
            if (p_) p_->AddRef();
            return *this;
        }
        bool operator==(shared_ptr const& rhs) const {
            return p_ == rhs.p_;
        }
        bool operator!=(shared_ptr const& rhs) const {
            return p_ != rhs.p_;
        }
    
    private:
        friend class intr_shared_ptr;
        explicit shared_ptr(U* p) : p_(p) {
            if (p_) p_->AddRef();
        }
        void reset(U* p) {
            if (p_ == p) return;
            if (p_ && p_->DelRef()) {
                delete p_;
            }
            p_ = p;
            if (p_) p_->AddRef();
        }
        U* p_;
    };

    explicit intr_shared_ptr(U* p = nullptr) : p_(p) {
        if (p) p->AddRef();
    }
    explicit intr_shared_ptr(shared_ptr const& x) : p_() {
        if (x.p_) x.p_->AddRef();
        p_.store(x.p_, std::memory_order_relaxed);
    }
    explicit intr_shared_ptr(intr_shared_ptr const& x) : p_() {
        get_ptr px(x.p_);
        if (px.p) px.p->AddRef();
        p_.store(px.p, std::memory_order_relaxed);
    }
    ~intr_shared_ptr() {
        get_ptr p(p_);
        if (p.p && p.p->DelRef()) {
            delete p.p;
        }
        p.p = nullptr;
    }

    intr_shared_ptr& operator=(intr_shared_ptr const& x) {
        if (this == &x) return *this;
        
        U* pxp;
        {
            get_ptr px(x.p_);
            pxp = px.p;
            if (px.p) px.p->AddRef();
        }
        get_ptr p(p_);
        if (p.p && p.p->DelRef()) {
            delete p.p;
        }
        p.p = pxp;
        return *this;
    }
    explicit operator bool() const {
        return p_.load(std::memory_order_relaxed) != nullptr;
    }
    void reset(U* x) {
        get_ptr p(p_);
        if (p.p == x) return;
        if (p.p && p.p->DelRef()) {
            delete p.p;
        }
        p.p = x;
        if (x) x->AddRef();
    }
    void reset(shared_ptr const& x) {
        get_ptr p(p_);
        if (p.p == x.p_) return;
        if (p.p && p.p->DelRef()) {
            delete p.p;
        }
        p.p = x.p_;
        if (x.p_) x.p_->AddRef();
    }
    shared_ptr get() const {
        get_ptr p(p_);
        return shared_ptr(p.p);
    }
    bool compare_exchange_strong(shared_ptr& expected_ptr, shared_ptr const& new_ptr) {
        get_ptr p(p_);
        if (p.p == expected_ptr.p_) {
            if (p.p && p.p->DelRef()) {
                delete p.p;
            }
            p.p = new_ptr.p_;
            if (p.p) p.p->AddRef();
            return true;
        }
        else {
            expected_ptr.reset(p.p);
            return false;
        }
    }
    bool compare_exchange_strong(shared_ptr& expected_ptr, U* new_ptr) {
        get_ptr p(p_);
        if (p.p == expected_ptr.p_) {
            if (p.p && p.p->DelRef()) {
                delete p.p;
            }
            p.p = new_ptr;
            if (p.p) p.p->AddRef();
            return true;
        }
        else {
            expected_ptr.reset(p.p);
            return false;
        }
    }

private:
    mutable std::atomic<U*> p_;
};

static unsigned long B_count = 0;
struct B : public A {
    std::atomic<unsigned long> ref_cnt_;

    B(int i = 0) : A(i), ref_cnt_(0) {
        ++B_count;
    }
    ~B() { --B_count; }
    B(B const& x) = delete;
    B& operator=(B const& x) = delete;
    void AddRef() {
        ref_cnt_.fetch_add(1, std::memory_order_acq_rel);
    }
    bool DelRef() {
        return ref_cnt_.fetch_sub(1, std::memory_order_acq_rel) == 1;
    }
};

구현이 생각보다 길긴 하지만, 기본적인 기능만 포함하고 있다. 이렇게 구현하면 명시적인 아토믹 연산을 사용하는 것보다 더 효율적이고 빠르게 역참조를 수행할 수 있다. 성능 결과는 다음과 같다.

여기서는 역참조의 성능만 측정했지만, 포인터 할당 및 재할당, 아토믹 교환 등 기타 아토믹 연산에도 마찬가지로 효율적이다. 하지만 unique_ptr 보다는 덜 효율적이므로 레퍼런스 카운트없이 명시적으로 소유권을 관리할 수 있다면 이를 피하는 것이 좋다.

 

이러한 atomic shared pointer를 사용하면 비용이 발생하긴 하지만 스레드 전체에서 소유권을 추적하고 관리할 수 있게 된다.