性能优化的方法和技巧：算法

作者 | 2011-06-30 00:45 | 类型 行业动感 | 10条用户评论 »

Sina WeiboBaiduLinkedInQQGoogle+RedditEvernote分享




系列目录 性能优化方法和技巧

  1. 性能优化的方法和技巧：概述
  2. 性能优化的方法和技巧：代码
  3. 性能优化的方法和技巧：工具
  4. 性能优化的方法和技巧：系统
  5. 性能优化的方法和技巧：总结
  6. 性能优化的方法和技巧：算法

算法的种类和实现浩如烟海，但是在这篇文章里面，不讨论单核，单线程的算法，而是讨论多核，多线程的算法；不讨论所有的算法类型（这个不是本文作者能力范围之内的事），而是讨论在多核网络设备里面常见的算法，以及可能的优化途径，这些途径有些经过了验证，有些还是处于想法阶段，暂时没有实现数据的支持。

多核算法优化的目标无非两种：lock-free和lock-less。

lock-free是完全无锁的设计，有两种实现方式：

  • Per-cpu data，顾名思义，每个核或者线程都有自己私有的数据结构（这里的私有和thread local data是有区别的，这里的私有是逻辑上私有，并不意味着别的线程无法访问这些数据；而thread local data是线程私有的数据结构，别的线程是无法访问的。当然，不管是逻辑上私有，还是物理上私有，把共享数据转化成线程私有数据，就可以避免锁，避免竞争）。全局变量是共享的，而局部变量是私有的，所以多使用局部变量，同样可以达到无锁的目的。
  • CAS based，CAS是compare and swap，这是一个原子操作（spinlock的实现同样需要compare and swap，但区别是spinlock只有两个状态LOCKED和UNLOCKED，而CAS的变量可以有多个状态）；其次，CAS的实现必须由硬件来保障（原子操作），CAS一次可以操作32 bits，也有MCAS，一次可以    比较修改一块内存。基于CAS实现的数据结构没有一个统一，一致的实现方法，所以有时不如lock based的算法那么简单，直接，针对不同的数据结构，有不同的CAS实现方法，读者可以自己搜索。

lock-less的目的是减少锁的争用（contention），而不是减少锁。这个和锁的粒度（granularity）相关，锁的粒度越小，等待的时间就越短，并发的时间就越长。

锁的争用，需要考虑不同线程在获取锁后，会执行哪些不同的动作。以session pool的分配释放为例：假设多个线程都会访问同一个session pool，分配或者释放session。session pool是个tailq，分配在head上进行；而释放在tail上进行。

如果多个线程同时访问session pool，需要一个spinlock来保护这个session pool。那么分配和释放两个不同的动作，相互之间就会有争用，而且多个线程上的分配，或者释放本身也会有争用。

现在我们可以考虑分配用一个锁，释放用一个锁，生成一个双端队列，这样可以减少分配和释放之间的争用。

http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ （参考这篇文章）。

也可以考虑用两个pool，分配一个pool，释放一个pool，在分配pool用完之后，交换两个pool的指针（这时要考虑两个pool都是空的情况，这里只是减少了分配和释放的争用，但不能完全消除这种争用）。

不管是lock-based还是CAS-based (lock-free)的数据结构，都需要一个状态机。不同状态下，做不同的事，而增加锁的粒度，也就是增加了状态机的数量（不是状态的数量），减小状态保护的范围。这个需要在实践中体会。

参考资料：

1：http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms

2：http://yongsun.me/2010/01/%E4%BD%BF%E7%94%A8cas%E5%AE%9E%E7%8E%B0lock-free%E7%9A%84%E4%B8%80%E4%B8%AA%E7%B1%BB%E6%AF%94/

3：http://www.cppblog.com/johndragon/archive/2010/01/08/105207.html

4：http://kb.cnblogs.com/page/45904/

5：http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/

系列前一篇
(没有打分)

工具箱
本文链接 | | 打印此页 | 10条用户评论 »

雁过留声

“性能优化的方法和技巧：算法”有10个回复

  1. 陈怀临 于 2011-06-30 2:54 上午

    在给你编辑全集了。你可真有面子。

  2. yfydz 于 2011-06-30 6:41 下午

    用两pool固然可以减少锁冲突，但总是需要取新内存，对cache就有影响了吧？在需要频繁获取释放资源的场景感觉不一定比单pool有效

  3. kernelchina 于 2011-06-30 6:47 下午

    分配和释放两个动作分离，可以减少分配和释放之间的冲突，释放多，也就意味着分配多，分开以后，冲突的几率小一点。
    弯曲评论和推荐是每个作者的荣幸，感谢首席的关注和支持。

  4. wangee 于 2011-06-30 7:15 下午

    kernelchina兄，在下十分敬仰您的全才及分享精神，但如玉有瑕，兄台之笔犹如蜻蜓点水，有抛玉引砖之嫌，吾等无尔之智，见璞玉，不识，故欲抛砖，却不忍。

  5. if 于 2011-06-30 7:32 下午

    不同状态下，做不同的事，而增加锁的粒度，也就是增加了状态机的数量（不是状态的数量），减小状态保护的范围。这个需要在实践中体会。

  6. kernelchina 于 2011-06-30 7:35 下午

    批评使人进步，欢迎把砖抛过来，呵呵:)

  7. if 于 2011-06-30 7:35 下午

    “不同状态下，做不同的事，而增加锁的粒度，也就是增加了状态机的数量（不是状态的数量），减小状态保护的范围。这个需要在实践中体会。”对此优点不解，请Kenelchina指教：增加锁的粒度，然后缩小资源保护范围？

  8. if 于 2011-06-30 7:48 下午

    很是赞同状态机的概念，免锁(CAS)的本质也就是数据自身做状态，自然而然，减少额外的状态变量资源同时将锁导致任务级切换开销降低至CPU流水线级的刷新开销。不知理解是否正确？请Kernel兄指点。

  9. shuyong 于 2011-07-01 1:07 上午

    文章的最后一段理解深刻。赞一个。

  10. kernelchina 于 2011-07-01 1:34 上午

    转一个很专业的评论，不是亲自动手，没有这样的体会。
    “实践起来很困难 new
    Submitted by Claud on Tue, 2011-06-28 16:15.
    前一阵写的代码正好是这个问题，当时也仔细看了冠诚的博文。是一个线程池，一个生产者添加任务，多个消费者并行领取任务。一些实践经验如下：

    1、不适合设计成per-cpu data的，在那个特定场景下，不同任务的计算时间相差百倍，而且事先无法确定。轮流分配任务，可能带来高延迟，以及部分CPU空转。

    2、C里面没法做CAS，除非有机器指令支持。在Java里面有专门的虚拟机指令。即便支持，看了冠诚的文章，也不敢自己写一个……

    3、尝试了一下任务队列的头尾分离，对性能的改进极低。应该和我的模型有关，第一是有多个消费者在竞争，二是消费者处理任务的时间是主要瓶颈（2/3）。最后考虑到代码可维护性，以及潜在的字节对齐原子访问问题（部署在64位下），还是没有用。

    4、考虑过两个池轮换，这个引入更多的问题。比如说，生产者和多个消费者如何判断当前在用哪个池子？如果引入一个全局标志，又带来了互斥问题；其他同步方法则开销更大；而各线程自动判断，在生产者还好做，消费者没想到怎么实现。如果是用交换指针的方法，指针值本身也有读写互斥问题。

    这些结论应该与实际的模型和应用有关，仅供参考吧~

    我的看法是，在锁和同步成为瓶颈的场景下，尝试能否用异步消息驱动，或者改造成map-reduce可能会更好。”