オブジェクト指向とリソース競合は関係がない

# はじめに

オブジェクト指向とは, 問題の抽象化のひとつです. 問題がデータの塊を順番に処理し, システムに状態がないならば, Data Flow Diagram (DFD)や, 純粋関数型が抽象化として適しています. 具体的なリソース競合なども同じく抽象化されるべきです.

これだけではただのマサカリなので, 公平に私にもマサカリが飛んでくるようにしましょう. この世には, とても恐ろしい"辻Lock-free"という文化があります. つぶやいたーで"Lock-free"などと気軽にさえずってはいけません.

## オブジェクト指向
データと操作をひとつにしたオブジェクトを考えて, メッセージでオブジェクト間の相互作用を抽象化する, 問題の抽象化です. 次のような感じです, やばいすげー力作.

![OO00_.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/119ce4ef-0639-5777-1244-ad90e5acc16f.png)

# Lock-free linked stack

ロックフリーなリンクスタックです. まともにテストしていないので, 今日中に私の首は胴から離れるでしょう, Windows以外は特に. おっと, スタックについて, ファミレスなどにあるこれです. 後に詰めたものが, 最初に出てくる構造です.

![stack00_.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/0c88d94e-8de2-54d4-6c33-5efac5bd990c.png)


## Tagged pointer
仕込みです. アトミックに処理する, 参照カウントなどの付加情報とポインタの組です. 32bitマシンだと64bitをアトミックに処理する命令が必要になるなど, 環境に縛られます.

<details><summary>tagged pointer</summary><div>

```cpp
//------------------------------------------------
//--- TaggedPointer
//------------------------------------------------
#if defined(__i386__) || defined(__x86_64__) || defined(_WIN32) || defined(_WIN64)
template<class T>
class TaggedPointer
{
public:
#    if defined(_WIN64)
    typedef u64 tag_type;
#    elif defined(_WIN32)
    typedef u32 tag_type;
#    elif defined(__x86_64__)
    typedef u64 tag_type;
#    elif defined(__i386__)
    typedef u32 tag_type;
#    endif

    TaggedPointer() noexcept;
    TaggedPointer(T* pointer, tag_type tag = 0) noexcept;

    void load(T*& pointer, tag_type& tag, std::memory_order order = std::memory_order_seq_cst) const noexcept;
    T* load_ptr(std::memory_order order = std::memory_order_seq_cst) const noexcept;
    tag_type load_tag(std::memory_order order = std::memory_order_seq_cst) const noexcept;

    void store(T* pointer, tag_type tag, std::memory_order order = std::memory_order_seq_cst) noexcept;
    void store_ptr(T* pointer, std::memory_order order = std::memory_order_seq_cst) noexcept;
    void store_tag(tag_type tag, std::memory_order order = std::memory_order_seq_cst) noexcept;

    bool compare_exchange_weak(T* expected_ptr, T* desired_ptr, std::memory_order order = std::memory_order_seq_cst) noexcept;
    bool compare_exchange_weak(tag_type expected_tag, tag_type desired_tag, std::memory_order order = std::memory_order_seq_cst) noexcept;
    bool compare_exchange_weak(T* expected_ptr, tag_type expected_tag, T* desired_ptr, tag_type desired_tag) noexcept;

    void swap(TaggedPointer<T>& other);

private:
    TaggedPointer(const TaggedPointer&) = delete;
    TaggedPointer(TaggedPointer&&) = delete;
    TaggedPointer& operator=(const TaggedPointer&) = delete;
    TaggedPointer& operator=(TaggedPointer&&) = delete;

#    if defined(_WIN64)
    union Pointer
    {
        Pointer(T* pointer = nullptr, tag_type tag = 0)
            : tagged_{pointer, tag}
        {
        }
        struct
        {
            std::atomic<T*> pointer_;
            std::atomic<tag_type> tag_;
        } tagged_;
        __int64 raw_[2];
    };
    __declspec(align(16)) Pointer pointer_;
#    elif defined(_WIN32)
    union Pointer
    {
        Pointer(T* pointer = nullptr, tag_type tag = 0)
            : tagged_{pointer, tag}
        {
        }
        struct
        {
            std::atomic<T*> pointer_;
            std::atomic<tag_type> tag_;
        } tagged_;
        __int64 raw_;
    };
    __declspec(align(8)) Pointer pointer_;
#    elif defined(__x86_64__)
    union Pointer
    {
        Pointer(T* pointer = nullptr, tag_type tag = 0)
            : tagged_{pointer, tag}
        {
        }
        struct
        {
            std::atomic<T*> pointer_;
            std::atomic<tag_type> tag_;
        } tagged_;
        __int128_t raw_;
    };
    Pointer pointer_ __attribute__((aligned(16)));
#    elif defined(__i386__)
    union Pointer
    {
        Pointer(T* pointer = nullptr, tag_type tag = 0)
            : tagged_{pointer, tag}
        {
        }
        struct
        {
            std::atomic<T*> pointer_;
            std::atomic<tag_type> tag_;
        } tagged_;
        __int64_t raw_;
    };
    Pointer pointer_ __attribute__((aligned(8)));
#    endif
};

template<class T>
TaggedPointer<T>::TaggedPointer() noexcept
    : pointer_{nullptr, 0}
{
}

template<class T>
TaggedPointer<T>::TaggedPointer(T* pointer, tag_type tag) noexcept
    : pointer_{pointer, tag}
{
}

template<class T>
void TaggedPointer<T>::load(T*& pointer, tag_type& tag, std::memory_order order) const noexcept
{
    pointer = pointer_.tagged_.pointer_.load(order);
    tag = pointer_.tagged_.tag_.load(order);
}
template<class T>
T* TaggedPointer<T>::load_ptr(std::memory_order order) const noexcept
{
    return pointer_.tagged_.pointer_.load(order);
}

template<class T>
typename TaggedPointer<T>::tag_type TaggedPointer<T>::load_tag(std::memory_order order) const noexcept
{
    return pointer_.tagged_.tag_.load(order);
}

template<class T>
void TaggedPointer<T>::store(T* pointer, tag_type tag, std::memory_order order) noexcept
{
    pointer_.tagged_.pointer_.store(pointer, order);
    pointer_.tagged_.tag_.store(tag, order);
}

template<class T>
void TaggedPointer<T>::store_ptr(T* pointer, std::memory_order order) noexcept
{
    pointer_.tagged_.pointer_.store(pointer, order);
}

template<class T>
void TaggedPointer<T>::store_tag(tag_type tag, std::memory_order order) noexcept
{
    pointer_.tagged_.tag_.store(tag, order);
}

template<class T>
bool TaggedPointer<T>::compare_exchange_weak(T* expected_ptr, T* desired_ptr, std::memory_order order) noexcept
{
    return pointer_.tagged_.pointer_.compare_exchange_weak(expected_ptr, desired_ptr, order);
}

template<class T>
bool TaggedPointer<T>::compare_exchange_weak(tag_type expected_tag, tag_type desired_tag, std::memory_order order) noexcept
{
    return pointer_.tagged_.tag_.compare_exchange_weak(expected_tag, desired_tag, order);
}

template<class T>
bool TaggedPointer<T>::compare_exchange_weak(T* expected_ptr, tag_type expected_tag, T* desired_ptr, tag_type desired_tag) noexcept
{
    Pointer expected;
    expected.tagged_.pointer_ = expected_ptr;
    expected.tagged_.tag_ = expected_tag;

    Pointer desired;
    desired.tagged_.pointer_ = desired_ptr;
    desired.tagged_.tag_ = desired_tag;
#    if defined(_WIN64)
    return TRUE == InterlockedCompareExchange128(pointer_.raw_, desired.raw_[1], desired.raw_[0], expected.raw_);
#    elif defined(_WIN32)
    return TRUE == InterlockedCompareExchange64(pointer_.raw_, desired.raw_[1], desired.raw_[0], expected.raw_);
#    else
    return atomic_compare_and_set(&pointer_.raw_, expected.raw_, desired.raw_);
#    endif
}

template<class T>
void TaggedPointer<T>::swap(TaggedPointer<T>& other)
{
    T* pointer0;
    tag_type tag0;
    load(pointer0, tag0, std::memory_order_relaxed);

    T* pointer1;
    tag_type tag1;
    other.load(pointer1, tag1, std::memory_order_relaxed);

    store(pointer1, tag1, std::memory_order_relaxed);
    other.store(pointer1, tag1, std::memory_order_relaxed);
}
#endif
```
</div></details>

## Stack
私たちはアトミックに参照カウントができるポインタを手に入れたので, lock-freeなコンテナを作ることができます.

<details><summary>lock-free stack</summary><div>

```cpp
//------------------------------------------------
//--- LockFreeLinkedStack
//------------------------------------------------
template<class T>
class LockFreeLinkedStack
{
public:
    typedef typename TaggedPointer<T>::tag_type tag_type;

    LockFreeLinkedStack();
    ~LockFreeLinkedStack();

    void push(T* item);
    T* pop();

    bool empty() const;
private:
    LockFreeLinkedStack(const LockFreeLinkedStack&) = delete;
    LockFreeLinkedStack(LockFreeLinkedStack&&) = delete;
    LockFreeLinkedStack& operator=(const LockFreeLinkedStack&) = delete;
    LockFreeLinkedStack& operator=(LockFreeLinkedStack&&) = delete;

    TaggedPointer<T> top_;
};

template<class T>
LockFreeLinkedStack<T>::LockFreeLinkedStack()
    : top_(nullptr)
{
}

template<class T>
LockFreeLinkedStack<T>::~LockFreeLinkedStack()
{
}

template<class T>
void LockFreeLinkedStack<T>::push(T* item)
{
    assert(nullptr!= item);
    T* top;
    tag_type top_tag;
    T* old_top;
    do {
        top_.load(top, top_tag, std::memory_order_acquire);
        item->next_ = old_top = top;
    } while(!top_.compare_exchange_weak(old_top, top_tag, item, top_tag + 1));
}

template<class T>
T* LockFreeLinkedStack<T>::pop()
{
    T* old_top;
    tag_type old_tag;
    T* next_top;
    do {
        top_.load(old_top, old_tag, std::memory_order_acquire);
        if(nullptr == old_top) {
            return nullptr;
        }
        next_top = old_top->next_;
    } while(!top_.compare_exchange_weak(old_top, old_tag, next_top, old_tag + 1));
    return old_top;
}

template<class T>
bool LockFreeLinkedStack<T>::empty() const
{
    return nullptr == top_.load_ptr(std::memory_order_acquire);
}
```
</div></details>

# そして, オブジェクト指向
TaggedPointerとLockFreeLinkedStackは, 結局どのような問題を抽象化して解決しているのか.

- TaggedPointerは,
    - ポインタと付随情報のアトミックな更新を実現する
- LockFreeLinkedStackは,
    - 後入れ先出し(LIFO)のデータ構造を実現し, その操作において排他制御を保障する
- 再利用とは何か
    - TaggedPointerが解決したことを利用すると, lock-free queueぐらいは簡単に実現できます

このような問題は, オブジェクト指向でなくとも上手く抽象化できると思います. 結局のところ, パラダイムは問題をどのように捉えているかであって, この言語を使っているからこのパラダイムを使うべき, ではないのです. C言語からHaskellの関数が簡単に呼び出せるなら, 私はぜひそうするでしょう.

# まとめ
ものすごく雑なのは, 条件反射で記事を書いたからです. リソース競合？なにそれ, おいしいの？