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

lxyscls

folklore 发表于 2017-04-18 12:25
第一次听到无锁读***写***队例， 就觉得很神奇。怎么可能无锁呢？？？？？？
想啊想， 还是觉得怎么可能无 ...

lockfree不是不要锁的意思

In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)

From wiki Non-blocking algorithm

lxyscls

zylthinking 发表于 2017-04-18 11:49
上边是你推崇的 boost ， 下边是我的 lkf; 测试的是 1读1写的； 你自己看结果， 单线程下是我的占优势；  ...

spsc queue就是single producer/single consumer的意思啊，本来就是限制了只能有一个写一个读

cokeboL

更多的人在意的是函数的名称中是否有 lock 或 wait 的字眼

—_— 94，没锁怎么写服务器

lxyscls

cokeboL 发表于 2017-04-18 16:42
更多的人在意的是函数的名称中是否有 lock 或 wait 的字眼

—_— 94，没锁怎么写服务器

一读一写场景，在"顺序一致性内存模型"下，确实就不需要lock，七十年代Lamport已经证明了(L. Lamport. Concurrent reading and writing. Commun. ACM, 20(11):806–811, 1977.)，链接超慢且全是公式，只是证明有这回事就是了
不过目前的物理设备还没有哪个是支持"Sequential consistency"的，Java的volatile和C++的atomic（默认）是支持的

这个是C++关于seq_cst的解释：http://en.cppreference.com/w/cpp ... consistent_ordering

cokeboL

回复 64# lxyscls

我不看我不看

wlmqgzm

回复 55# lxyscls


对的， 这个才是正确版本的 wait_free_queue, 性能的评测也完全正确， 确实这种写法的wait_free_queue可以达到每秒2亿。
我公司的wait_free_queue代码与此代码大同小异， 要继续提高性能，主要是靠改善内存的依存性来解决， 就是利用 alignas 64 和内存对生产者和消费者的内存进一步划分， 甚至要将一部分const 内存变量拷贝2份分别存放来提高性能。

凡是在代码中没有 一行 std::memory_order 的 所谓“wait_free_queue", 基本就是 连基本正确性都无法保证的东西。除非楼主将整个wait_free体系都推翻。

楼主的代码也看了，虽然有点不好听，我说句实话，lock_free/wait_free领域， 楼主还有很长的路要走。。。。。
我只说两点，

1） 凡是代码中有 CAS spin 循环代码的， 实质都是lock_free,  wait_free的实现是不会有CAS Spin，
wait_free 主要是靠std::memeory_order来保证 数据的原子性，数据的正确性。。
wait_free方面的论文很多了，基本讨论的就是内存的一致性这些东西。

2）楼主的测试代码有问题，按照楼主的测试报告，wait_free_queue的整数传递性能是： 17毫秒传送10万数据， 计算下来 boost wait_free_spsc_queue 每秒只有588万TPS, 这个数据拿到任何地方都会被笑话的。
总之，我们的测试代码都是 测出标准版的 wait_free_spsc_queue大约每秒2亿TPS， 与楼主的测试代码，有近40倍的性能差距。

zylthinking

真是够扯淡的， 我也送你句： 你还需要继续加强编程能力，加强理论学习
为啥这么说， 下面是理由
1. 你知道你吹牛逼的 boost 里面的 atomic 实现里用了 CAS 吗
2. 你知道 gcc builtin 系列函数本身自带了内存屏障效果吗， 你知道 std::memeory_order 不等于机器指令吗， 你知道相同的指令会以你不知道的面目出现吗？
3. 你知道我用的机器不是你用的机器吗， 你知道看性能对比是看相同外部条件下的表现吗？ 你知道你那句话拿到任何地方都会被笑话的吗

zylthinking

测试代码有问题请指出来， 那一句有问题， 有什么问题
张嘴就说有问题， 却不说什么问题；

就和张嘴就说你的是 lock free, 不是 wait free 一样， 你别把自己太当回事， 没有证据的话， 基本上就是风

wlmqgzm

回复 68# zylthinking

1)标准版的wait_free_queue确实不依靠 CAS spin 工作， 代码如下：

• #include <cstddef>
• #include <atomic>
• template <typename T, int capacity> class spsc_queue {
•   public:
•     spsc_queue(const T &val) : head(0), tail(0), invalid_val(val) {
•         for (int i = 0; i < capacity; i++) {
•             buf = invalid_val;
•         }
•     }
•     spsc_queue(const spsc_queue &) = delete;
•     spsc_queue &operator=(const spsc_queue &) = delete;
•     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;
•     }
•   private:
•     static constexpr size_t CACHELINE = 64;
•     alignas(CACHELINE) unsigned int head;
•     alignas(CACHELINE) unsigned int tail;
•     char padding[CACHELINE - sizeof(tail)];
•     std::atomic<T> buf[capacity];
•     T invalid_val;
• };
  
  

2. 你知道 gcc builtin 系列函数本身自带了内存屏障效果吗， 你知道 std::memeory_order 不等于机器指令吗， 你知道相同的指令会以你不知道的面目出现吗？
标准版的wait_free主要是靠内存一致性来实现无锁的， 所以必须要靠 std::memeory_order 来保证正确性。具体读代码吧。

3. 你知道我用的机器不是你用的机器吗， 你知道看性能对比是看相同外部条件下的表现吗？ 你知道你那句话拿到任何地方都会被笑话的吗

近40倍的性能差距，你究竟用的是什么机器啊，我当年测试用的是 intel G3258@3.2G 双核CPU， 你的机器比这个还烂40倍？？？

zylthinking

回复 69# wlmqgzm

你找找我代码里面的 CAS spin 试试？至于机器差异， 这个好办， 我代码都在这里了， 你要不要在你的机器上跑跑？ 或者找出来我在测试代码中哪里偏向我自己的实现了；