mutex,spinlock,cas performance

《一个无锁消息队列引发的血案》 提到了多个版本的线程安全的RingQueue, 我把原作者放在github上的代码整理了下， 写了一个单文件版本 (有所简化，只支持linux)，先上测试结果(测试代码)：

• 每次测试的push/pop总次数为10000000, 记录完成的时间,时间单位为ms。运行6次,取平均值。
• 测试环境： CentOS 6.6 (64bit), Kernel 2.6.32, CPU: Inter(R) Xeon E5606 @ 2.13GHz(8核), Memory 8G。
• 编译器版本 4.9.1, O3 优化。
• 横轴nThread=消费者数目=生产者数目。 Na表示运行时间太长，没有计入比较。

各种同步实现方式:

• mutex : 使用 pthread_mutex_lock / pthread_mutex_unlock
• spin1 : 使用 pthread_spin_lock / pthread_spin_unlock
• spin2 : 使用 __sync_lock_test_and_set / __sync_lock_release, 对应skynet_mq.c,自旋锁另一种实现形式
• cas : 使用 __sync_bool_compare_and_swap, 对应原文的q3_new.h
• mixed1 : 混合使用 __sync_bool_compare_and_swqp / __mm_pause / sleep / sched_yield, 对应原文的spin2_push/spin2_pop
• mixed2 : 改写自mixed1，有所简化。

• 具体代码见RingQueue.h_;

• mutex是最常用的线程间同步方法，一般认为拿不到锁就睡眠(实际似乎并非如此?）
• spin1/spin1都是自旋锁,cas实现了所谓的"无锁队列",三者在拿不到锁时都死等。区别在于 cas是乐观锁。
• mixed1/mixed2 拿不到锁时先自旋一段时间，还拿不到就退让,直到获取锁。

测试结果：

• 当竞争不激烈（总线程数小于等于主机核心数)时，mutex、自旋锁、cas的性能相差不大
• 当总线程数大于主机核心数时，cas性能迅速恶化;两种自旋锁性能基本一样，随线程数增多而逐渐变差; mutex较稳定,
• 两个混合型的mixed1和mixed2性能相近，至少是mutex的3倍,而且一直很稳定;

对测试结果的分析与猜测:

• cas性能迅速恶化：随线程数增加，cas冲突越来越激烈，尤其在并发线程数大于核数的时候.cas更容易在以下两处代码执行前或者执行过程中被抢占或者被休眠，导致其它线程因为 write_finish_以及read_finished_更新不及时而则停在这个while循环内(经测试while循环次数大幅增加)：

while(write_finish_ != head)
  _mm_pause();

while(read_finish_ != tail)
  _mm_pause();

• 线程数大于核数时，由于mixed1和mixed2有sched_yield()/nanosleep()机制,会在前面自旋若干次数之后，主动放弃CPU进行退让，获取了较好的实际性能。
• 竞争不激烈时，spin性能按理应该比mutex性能好(spin上下文切换少)，但测试结果却相反。原来在较新的mutex实现中，使用了futex(fast userspace mutex), 其策略也是先在用户空间自旋，一段时间后仍未获取锁才由系统仲裁。详见pthreads-mutex-vs-pthread-spinlock。

结论:

• mutex适应性最强，而且性能也不差,所以优先考虑用mutex,起码代码简单、可读性高
• 性能瓶颈真的在mutex时,再考虑用无锁或者其他锁来优化,但要意识到，优化的空间是有限的,可能更好的办法是改架构。
• 无锁队列没有想象中那么美…

待进一步研究

• 降低锁的粒度,分为读锁、写锁