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

starwing83

回复 40# __BlueGuy_


    这东西是用在服务器里用来提高多线程服务器数据处理吞吐量的，简而言之：很有用。

zylthinking

我主贴改了你好歹给我升到前面去吧................

wlmqgzm

mark下来慢慢看

mr_sev

不存在真正无锁

wlmqgzm

wait_free 队列是未来的主流， lock_free 慢慢都会被淘汰，
我们公司目前已经主要应用wait_free_queue的各种实践，性能比有锁队列快的多,  即使是单消费者单生产者队列测试， 都可以跑到199%的CPU占有率，不会被队列阻塞，平均时延大约是1微秒。
Boost库里面有一个wait_free_spsc_queue的实现，值得学习。

zylthinking

回复 45# wlmqgzm

我看了一下说明， 没看实现， 如何理解 [size=13.3333px]single-writer/single-reader？[size=13.3333px]
[size=13.3333px]The [size=13.3333px]spsc_queue[size=13.3333px] class provides a single-writer/single-reader fifo queue, pushing and popping is wait-free.[size=13.3333px]



814     /** Pushes as many objects from the array t as there is space.
815      *
816      * \pre only one thread is allowed to push data to the spsc_queue
817      * \return number of pushed items
818      *
819      * \note Thread-safe and wait-free
820      */
821     size_type push(T const * t, size_type size)
822     {
823         return base_type::push(t, size);
824     }



852     /** Pops a maximum of size objects from ringbuffer.
853      *
854      * \pre only one thread is allowed to pop data to the spsc_queue
855      * \return number of popped items
856      *
857      * \note Thread-safe and wait-free
858      * */
859     size_type pop(T * ret, size_type size)
860     {
861         return base_type::pop(ret, size);
862     }
863



如果照字面意思， 那我觉得还是我的高明些； 我的好歹在 多写/一读 的情况下保证 wait_free

dorodaloo

算是见识了。

lxyscls

wlmqgzm 发表于 2017-03-30 15:05
wait_free 队列是未来的主流， lock_free 慢慢都会被淘汰，
我们公司目前已经主要应用wait_free_queue的各 ...

SPSC Queue已经在七十年代末被Lamport证明在sequence consistent内存模型下是wait-free的

不过网上有好些个论文专门优化SPSC Q的，原始的Lamport SPSC Queue的cache亲和性不太好，P/C需要同时检查head和tail

wlmqgzm

回复 46# zylthinking

Wait_free 的实现性能要好一些，最简单的是单消费者单生产者队列， 一般都是先实现这个，
然后再以此为基础实现多生产者 和 多消费者队列，也很简单，基本就是多组映射， 所以， 一般只要实现了单消费者单生产者队列就OK, 其他都不是问题，
一般传送int这样的简单内容， 3.2G主频下单消费者单生产者2个线程， 1个生产者1个消费者， wait_free_spsc_queue每秒收发次数可以达到3亿次，lock_free达不到这个性能,
C++模板是个好东西, 实现好一个完整的模块，就可以推广到任意对象，然后就可以方便的替换原来的有锁队列了，

C++ template特化后，还可以支持 std::function 队列， 实现一个高性能的任务调度队列，。。。。
总之，扩展开来，能够做越来越多的组件，工具多了以后，在一些对性能要求高的场合就比较简单，最起码多几个可靠的工具包，实现起来也简单，

最近主要是做KV数据库，优化单机性能中，现在已经比 memcache / redis 快很多了，上个版本查询性能已经比memcache快64%，单核性能也超过redis单核性能,
本周还有一个版本会发布，内部测试中， 还会有大幅度的性能提升，觉得工具包还是要做C++模板，然后才可以适应更多的场合。
最近开发的各类加速的东西，单点测试成功后，最后都是做成了类似std/boost 一样的C++标准库, 开发过程中，全部代码的60%都是能够在下一个项目中使用的标准库。
C/C++的一些库还是有点旧，不少算法都过时了，这几年有不少论文，所以用最新的算法重写会有不少提高，
但是如果算法不变的话，重写基本是毫无意义的，-O3优化下，性能不会有提升。