我为需要跨线程同步的非常简单的数据块编写了一个容器。我想要最好的表现。我不想使用锁。
我想使用“放松”的原子。部分是为了那一点额外的魅力,部分是为了真正理解它们。
我一直在做这方面的工作,而且我正处于这段代码通过了我对其进行的所有测试的地步。不过,这还不是“证据”,所以我想知道我是否缺少任何东西,或者我可以通过其他任何方式来测试它吗?
这是我的前提:
- 唯一重要的是正确推送和弹出节点,并且堆栈永远不会失效。
- 我相信内存中的操作顺序只在一个地方很重要:
- 在 compare_exchange 操作本身之间。即使使用宽松的原子,也可以保证这一点。
- “ABA”问题通过向指针添加标识号来解决。在 32 位系统上,这需要双字 compare_exchange,而在 64 位系统上,指针的未使用的 16 位用 id 号填充。
- 因此:堆栈将始终处于有效状态。 (正确的?)
这就是我的想法。“通常”,我们对正在阅读的代码进行推理的方式是查看它的编写顺序。内存可以“乱序”读取或写入,但不能以使程序正确性无效的方式。
这在多线程环境中发生了变化。这就是内存栅栏的用途——这样我们仍然可以查看代码并能够推断它是如何工作的。
所以,如果这里一切都乱了套,那我用宽松的原子做什么呢?是不是有点太远了?
我不这么认为,但这就是我在这里寻求帮助的原因。
compare_exchange 操作本身保证了彼此的顺序不变性。
对原子进行读取或写入的唯一其他时间是在 compare_exchange 之前获取头部的初始值。它被设置为变量初始化的一部分。据我所知,此操作是否带回“正确”值是无关紧要的。
当前代码:
struct node
{
node *n_;
#if PROCESSOR_BITS == 64
inline constexpr node() : n_{ nullptr } { }
inline constexpr node(node* n) : n_{ n } { }
inline void tag(const stack_tag_t t) { reinterpret_cast<stack_tag_t*>(this)[3] = t; }
inline stack_tag_t read_tag() { return reinterpret_cast<stack_tag_t*>(this)[3]; }
inline void clear_pointer() { tag(0); }
#elif PROCESSOR_BITS == 32
stack_tag_t t_;
inline constexpr node() : n_{ nullptr }, t_{ 0 } { }
inline constexpr node(node* n) : n_{ n }, t_{ 0 } { }
inline void tag(const stack_tag_t t) { t_ = t; }
inline stack_tag_t read_tag() { return t_; }
inline void clear_pointer() { }
#endif
inline void set(node* n, const stack_tag_t t) { n_ = n; tag(t); }
};
using std::memory_order_relaxed;
class stack
{
public:
constexpr stack() : head_{}{}
void push(node* n)
{
node next{n}, head{head_.load(memory_order_relaxed)};
do
{
n->n_ = head.n_;
next.tag(head.read_tag() + 1);
} while (!head_.compare_exchange_weak(head, next, memory_order_relaxed, memory_order_relaxed));
}
bool pop(node*& n)
{
node clean, next, head{head_.load(memory_order_relaxed)};
do
{
clean.set(head.n_, 0);
if (!clean.n_)
return false;
next.set(clean.n_->n_, head.read_tag() + 1);
} while (!head_.compare_exchange_weak(head, next, memory_order_relaxed, memory_order_relaxed));
n = clean.n_;
return true;
}
protected:
std::atomic<node> head_;
};
与其他问题相比,这个问题有什么不同?轻松的原子。他们对这个问题有很大的影响。
所以你怎么看?有什么我想念的吗?