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

zylthinking

回复 52# wlmqgzm

C++的，不够前沿，性能上也不好说，毕竟wait_free才是最快的

这两句， 前一句就不说什么了； 我不前沿就不前沿呗

第二句你什么意思？ 合着我一直说你推崇的那个只能在一个读一个写的情况下可以 wait free; 而我的自己认为多个写 一个读的情况下也是 wait free 压根就没看， 就闭眼睛重复念经了；

zylthinking

wlmqgzm 发表于 2017-04-18 00:52
要么楼主测试一下性能吧,  跟boost lockfree_spsc_queue可以对比测试一下, 那个是wait_free的, 我自己测试 ...

上边是你推崇的 boost ， 下边是我的 lkf; 测试的是 1读1写的； 你自己看结果， 单线程下是我的占优势；
多线程下， 发现 boost 这玩意居然不是线程安全的， 我说的线程安全意思是多个读多个写， 它文档中的线程安全很可能是一个读一个写彼此安全 。
多线程下看时间是它占点优势， 但不大； 但考虑到它结果都是错的， 你自己明白是什么意思boost 是 apt install 下载的， 优化选项可能没有优化到最好，  姑且存疑


单线程 boost：
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 17, read 17, nr = 0
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 13, read 13, nr = 0
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 14, read 14, nr = 0
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 12, read 12, nr = 0

单线程 lkf：
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 11, read 11, nr = 0
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 12, read 12, nr = 0
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 11, read 11, nr = 0
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
1 writer, 1 reader, nr = 100000
write 8, read 8, nr = 0



boost多线程 50 读， 2个写, 只看速度， 不管数据正确性

zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 243, read 311
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 248, read 176
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 250, read 305
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 252, read 298
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 246, read 279

boost多线程 500 读， 2个写, 只看速度， 不管数据正确性

zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2404, read 2475
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2477, read 2554
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2520, read 2328
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2474, read 2508
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2508, read 2528



lkf多线程 50 读， 2个写, 只看速度， 最终数据是正确的


zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 305, read 343
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 355, read 356
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 292, read 388
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 323, read 364
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
50 writer, 2 reader, nr = 5000000
write 316, read 373


lkf多线程 500 读， 2个写, 只看速度， 最终数据是正确的

zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2672, read 3622
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2589, read 3986
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2664, read 3614
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2709, read 3611
zylthinking@linux:~$ g++ c.cpp now.c -lpthread; ./a.out
run = 0
500 writer, 2 reader, nr = 50000000
write 2638, read 3717

zylthinking

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

测试代码：

1. 
   
2. #include <stdlib.h>
   
3. #include <unistd.h>
   
4. #include <stdio.h>
   
5. #include <pthread.h>
   
6. #include <boost/lockfree/spsc_queue.hpp>
   
7. 
   
8. #include "lkf.h"
   
9. static LKF_LIST(list);
   
10. 
    
11. #define nrp 100000
    
12. #define nrt 1
    
13. uint32_t now();
    
14. 
    
15. #define uselkf 0
    
16. int nnnnn = 0;
    
17. struct lkf_node** node_array = NULL;
    
18. 
    
19. static int run = 0;
    
20. static struct lkf_node* pool = NULL;
    
21. static int indx = 0;
    
22. static int nr = 0;
    
23. static uint32_t t1;
    
24. 
    
25. boost::lockfree::spsc_queue<lkf_node*, boost::lockfree::capacity<50000000> ,
    
26.                              boost::lockfree::fixed_sized<true> > spsc_queue;
    
27. void* writer(void* any)
    
28. {
    
29.     int* intp = (int *) any;
    
30.     while (run == 0) {
    
31.         usleep(100);
    
32.     }
    
33. #if uselkf
    
34.     for (int i = 0; i < nrp; ++i) {
    
35.         int idx = __sync_fetch_and_add(&indx, 1);
    
36.         struct lkf_node* nodep = &pool[idx];
    
37.         lkf_node_put(&list, nodep);
    
38.     }
    
39. #else
    
40.     for (int i = 0; i < nrp; ++i) {
    
41.         int idx = __sync_fetch_and_add(&indx, 1);
    
42.         struct lkf_node* nodep = &pool[idx];
    
43.         spsc_queue.push(nodep);
    
44.     }
    
45. #endif
    
46. 
    
47.     __sync_sub_and_fetch(&run, 1);
    
48.     intp[0] = (int) (now() - t1);
    
49.     return NULL;
    
50. }
    
51. 
    
52. void* reader(void* any)
    
53. {
    
54.     int* intp = (int *) any;
    
55.     while (run == 0) {
    
56.         usleep(100);
    
57.     }
    
58. #if uselkf
    
59.     while (nr > 0) {
    
60.         struct lkf_node* nodep = lkf_node_get(&list);
    
61.         if (nodep == NULL) {
    
62.             continue;
    
63.         }
    
64. 
    
65.         __sync_sub_and_fetch(&nr, 1);
    
66.         struct lkf_node* cur = NULL;
    
67.         do {
    
68.             cur = lkf_node_next(nodep);
    
69.             if (cur == nodep) {
    
70.                 break;
    
71.             }
    
72. 
    
73.             if (cur != NULL) {
    
74.                 __sync_sub_and_fetch(&nr, 1);
    
75.             }
    
76.         } while (1);
    
77.     }
    
78. #else
    
79.     while (nr > 0) {
    
80.         int n = (int) spsc_queue.pop(node_array, nnnnn);
    
81.         __sync_sub_and_fetch(&nr, n);
    
82.     }
    
83. #endif
    
84.     intp[0] = (int) (now() - t1);
    
85.     return NULL;
    
86. }
    
87. 
    
88. int main(int argc, char** argv)
    
89. {
    
90.     int n = 0;
    
91.     int used1[1024] = {0};
    
92.     for (int i = 0; i < nrt; ++i) {
    
93.         pthread_t tid;
    
94.         if(0 == pthread_create(&tid, NULL, writer, &used1[i])) {
    
95.             ++n;
    
96.             pthread_detach(tid);
    
97.         }
    
98.     }
    
99. 
    
100.     nr = nrp * n;
     
101. #if !uselkf
     
102.     nnnnn = nr;
     
103.     node_array = (struct lkf_node**) malloc(sizeof(struct lkf_node*) * nr);
     
104.     if (node_array == 0) {
     
105.         printf("memory\n");
     
106.         return 0;
     
107.     }
     
108. #endif
     
109. 
     
110.     pool = (struct lkf_node *) malloc(sizeof(struct lkf_node) * nr);
     
111.     if (pool == 0) {
     
112.         printf("memory\n");
     
113.         return 0;
     
114.     }
     
115. 
     
116.     int readers = 0;
     
117.     int used2[1024] = {0};
     
118.     for (int i = 0; i < 1; ++i) {
     
119.         pthread_t tid;
     
120.         if(0 == pthread_create(&tid, NULL, reader, &used2[i])) {
     
121.             ++readers;
     
122.             pthread_detach(tid);
     
123.         }
     
124.     }
     
125. 
     
126.     printf("run = %d\n", run);
     
127.     printf("%d writer, %d reader, nr = %d\n", n, readers, nr);
     
128. 
     
129.     t1 = now();
     
130.     run = n;
     
131. 
     
132.     sleep(10);
     
133.     int max1 = 0, max2 = 0;
     
134.     for (int i = 0; i < n; ++i) {
     
135.         if (used1[i] > max1) {
     
136.             max1 = used1[i];
     
137.         }
     
138.     }
     
139. 
     
140.     for (int i = 0; i < readers; ++i) {
     
141.         if (used2[i] > max2) {
     
142.             max2 = used2[i];
     
143.         }
     
144.     }
     
145. 
     
146.     printf("write %d, read %d, nr = %d\n", max1, max2, nr);
     
147.     return 0;
     
148. }
     

复制代码

zylthinking

wlmqgzm 发表于 2017-04-18 00:52
要么楼主测试一下性能吧,  跟boost lockfree_spsc_queue可以对比测试一下, 那个是wait_free的, 我自己测试 ...

编辑掉， 不吵架

zylthinking

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

没有真正无锁的代码； 这前提下， 更多的人在意的是函数的名称中是否有 lock 或 wait 的字眼

zylthinking

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

zylthinking

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

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

zylthinking

回复 69# wlmqgzm

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

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)  用汇编指令来实现实现

zylthinking

回复 73# wlmqgzm

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

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