多线程读写无锁链表： 之前有没有相同的实现？ (更新)

zylthinking

回复 69# wlmqgzm

读毛代码，一看就知道buf[tail].load(std::memory_order_acquire) == invalid_val

buf[tail].load(std::memory_order_acquire) ！= invalid_val

这两个带着互斥语意的判断就不是单纯机器指令级别的内存屏障能做到的
有异议的话你可以将 load(std::memory_order_acquire)  用汇编指令来实现实现

wlmqgzm

回复 71# zylthinking

读毛代码，一看就知道buf[tail].load(std::memory_order_acquire) == invalid_val

buf[tail].load(std::memory_order_acquire) ！= invalid_val

这两个带着互斥语意的判断就不是单纯机器指令级别的内存屏障能做到的
有异议的话你可以将 load(std::memory_order_acquire)  用汇编指令来实现实现


这两行代码的机器码内部实现是依靠： 内存读屏障来实现的。

wlmqgzm

zylthinking 发表于 2017-04-18 18:47
回复 69# wlmqgzm

你找找我代码里面的 CAS spin 试试？至于机器差异， 这个好办， 我代码都在这里了，  ...

__sync_lock_test_and_set(&(list->root.next), NULL);  
我很奇怪，难道不是CAS spin???
楼主既然没有使用 std::memeory_order之类的东西， 难道连CAS指令都可以不用吗？

楼主的测试代码肯定没有用心认真去写，或者测试代码本身也存在瓶颈，
不然不会与我们的测试 wait_free_queue 性能差距这么大， 近40倍的差距，所以， 最终测试结果就无法说明任何问题。

zylthinking

回复 73# wlmqgzm

你没有 spin？ 我代码还没有完全分析出来， 但似乎味道不对哈， 我继续分析

你只说代码有问题， 就是不撸袖子
我就奇怪了你要我提供测试数据， 我动手就干， 到你头上怎么就只动口呢

zylthinking

回复 73# wlmqgzm

这么说吧， x64 cpu 上， 整体表现， CAS 指令与相同功能的不考虑竞态的普通指令对比， 慢约 7 倍； 与线程数量无关， 与核心数量似乎也无关；是否是 CAS spin,  似乎有些不重要了

zylthinking

回复 73# wlmqgzm

你说你没有 spin?


    bool enqueue(const T &data) {
        if (buf[tail].load(std::memory_order_acquire) == invalid_val) {
            buf[tail].store(data, std::memory_order_release);
            tail = (tail + 1) % capacity;
            return true;
        }
        return false;
    }


    bool dequeue(T &data) {
        if (buf[head].load(std::memory_order_acquire) != invalid_val) {
            data = buf[head].load(std::memory_order_relaxed);
            buf[head].store(invalid_val, std::memory_order_release);
            head = (head + 1) % capacity;
            return true;
        }
        return false;
    }


我猜应该是如下逻辑吧
enqueue:

read require
n = buf[tail]
if (n == invalid_val) {
     buf[tail] = data;
}
write release


dequeue:

read require
n = buf[head]
buf[head] = invalid_val;
write release

好， 现在
dequeue 在：
buf[head] = invalid_val;


enqueue在
n = buf[tail]

其中 head == tail
现在， 因为 buf[head] = invalid_val; 已经执行了， 所以 n = buf[tail] 期待 n == invalid_val, 但 write release 还没做， 因此， n 可能 != invalid_val; 导致 false 退出

现在你告诉我， 你有没有 spin

wlmqgzm

回复 76# zylthinking

数据容器没有存放满的时候， 是不会有重试的，概率为零， 除非数据容器已经满了的情况，就插不进数据了， 因此，99.9%的以上的情况， 是没有重试的场景的。

zylthinking

wlmqgzm 发表于 2017-04-18 19:46
回复 76# zylthinking

数据容器没有存放满的时候， 是不会有重试的，概率为零， 除非数据容器已经满了 ...

那我的一次 get __sync_lock_test_and_set 导致的冲突引起的延迟， 会以 get 出来的链表会更长表现出来，
从而在 lkf_node_next 中循环更多次， 进而降低 get 与 put 的碰撞

wlmqgzm

zylthinking 发表于 2017-04-18 20:00
那我的一次 get __sync_lock_test_and_set 导致的冲突引起的延迟， 会以 get 出来的链表会更长表现出 ...

你说的这种， 按照准确的定义， 仍然是属于lock_free范畴，只是改善了冲突，但是并没有消除冲突，
Lock_free冲突发生的概率大，即使是在正常存取数据时， 也会有冲突，并且随着线程数量的增加，冲突的概率也增加， 性能不能随CPU数量的增加平滑增长，存在明显的性能瓶颈，

wait_free的场景，基本消除了冲突，除了空间满这一种情况，所有的线程都全速并发，几乎跟单线程场景的性能是一致的， 并且性能随CPU数量的增加平滑增长，没有明显的性能瓶颈。
随着单机CPU数量的急剧增加，因此， 主流公司目前更关注wait_free这个领域，新开发的组件都是wait_free架构。

zylthinking

回复 79# wlmqgzm

没错， 在纯理论上， 我的实现的理论基础是站在下风但要注意, 我的碰撞降低是倾向于稳定的； 只要一旦又一次能 get 出足够长的链表， 那么两个线程频繁程度相等的假设下， 很大概率就会持续 get 出长的链表
而你的也不是 100% 就一定是极低碰撞率， 一旦 head == tail 了， 然后读写线程持续纠缠的话， 碰撞会稳定在很高水平

考虑到特定 cpu 架构比如 x64,  经测试得到的结论是 CAS 指令稳定在一个固定的速度， 既和线程数无关， 也和核数无关， 如果这个结论是正确的， 那么 cas spin 存不存在就要存疑了