大家好，我是江南一散人。周末逛知乎时，无意间看到阿里云开发者官方账号的一篇文章中，居然引用了我三年前在今日头条写的一篇文章。有些感概，看来还真的在互联网上留下了点痕迹。
那篇文章，其实和那篇《改几行代码，for循环耗时从3.2秒降到0.3秒！真正看懂的都是牛人！》是相关的，算是前传吧，所以在这里发一下，感兴趣的小伙伴不妨围观下！
全文如下，仅作微调。
昨天发了一段有趣的代码，引来很多童鞋围观。很多童鞋表示不太明白，于是就有了本文，详细解释下这段代码的来龙去脉。
代码如下图所示：
图片
如果你是第一次看到的话，不妨试一下，看你能得出正确答案吗？
其实，这个题目还是源自大师之手，我只是做了少许修改。先来聊一下这段历史渊源吧。
注：为了尽量解释清楚，篇幅有点长，请耐心读完，相信你会有收获的！
1983年11月，一位叫Tom Duff的大牛在编写串口通信程序时，发现使用一般的写法时，性能总是不能让人满意。后来，这位老兄凭借深厚的编程功底和精湛的C语言技艺，利用C语言中switch语句的一个鲜为人知的特性，发明如了下图所示的经典代码：
图片
结果，引来无数吃瓜群众膜拜。在此之前，还没有人发现并利用过C语言的这个特性，于是他便以自己的名字命名这段代码，叫做Duff's Device，一般译为"达夫设备"。
先看一下大牛的风采吧：
图片
下面讲解一下这段代码。
当时，Duff的需求，是把一段起始地址为from，长度为count的数据，写入到一个内存映射的I/O(Memory Mapped I/O)寄存器to中。
需求很简单，对吧？很容易想到直接用for或者while循环就可以解决了，如下图所示：
图片
代码清晰简洁，很直观，简直完美，对吧？
Duff却对此很不满意，因为他觉得这种写法虽然简单，但太过低效，无法接受。
如此简单的代码，为何说它性能低下呢？主要有两个问题：
• "无用"指令太多
• 无法充分发挥CPU的ILP(Instruction-Level Parallelism)技术
我们来分析一下。
所谓无用指令，是指不直接对所期望的结果产生影响的指令。
对于这段代码，我们期望的结果就是把数据都拷贝到I/O寄存器to中。那么，对于这个期望的结果来说，真正有用的代码，其实只有中间那一行赋值操作：
*to = *from++;而每次迭代过程中的while (--count > 0)产生的指令，以及每次迭代结束后的跳转指令，对结果来说都是无用指令。
上面最简单的实现中，每次循环迭代只拷贝一个字节数据。这就意味着，有多少个字节的数据，就需要执行多少次跳转和条件判断，以及--count的操作。
我们看一下汇编代码：
图片
有些童鞋对汇编不太熟悉，我简单讲解一下：
• x64上优先使用寄存器传递，对于send()函数，第一个参数to存放在寄存器rdi中，第二个参数from存放在rsi中，第三个参数count存放在寄存器edx中。
• 第2~7行，把三个参数分别压入栈中；
• 第9~14行，对应C语言的*to = *from++；
• 第15~19行，对应C语言的while (--count > 0)；
• 最后几句，恢复栈帧并返回
所以，第9-19行属于热点路径，也就是主循环体。第9-14行属于有效指令，第15-19行对于期望的数据结果来说就是无用指令。
我们看到，热点路径中，无用指令数占了整个热点路径指令数的一半，其开销也占到整个函数的50%！
现代CPU为了提高指令执行的速度和吞吐率，提升系统性能，不仅一直致力于提升CPU的主频，还实现了多种ILP(Instruction-Level Parallelism 指令级并行)技术，如超流水线、超标量、乱序执行、推测执行、分支预测等。
一个设计合理的程序，往往能够充分利用CPU的这些ILP机制，以使性能达到最优。
但是，在代码热点路径上，无用指令太多，且每个迭代只执行一条*to = *from++，无法充分发挥ILP的技术优势。
注：这里解释不够清楚，详细讲解请参看文末推荐阅读的两篇文章，详细介绍了ILP技术(如超流水线、超标量、推测执行、分支预测)。
现在，知道上面那个简单实现性能差的原因了，那么如何去优化它呢？
所谓循环展开，是通过增加每次迭代内数据操作的次数，来减小迭代次数，甚至彻底消除循环迭代的一种优化手段。
循环展开，有以下优点：
• 有效减少循环控制指令。前面说过，这些指令，是对结果不产生影响的无用指令。减少这些指令，就可以减少这些指令本身执行所需的开销，从而提升整体性能。
• 通过合理的展开，可以更加有效地利用指令级并行ILP(Instruction-Level Parallelism 指令级并行)技术。
循环展开是一个很常用的性能优化手段，所有现代编译器，通过合适的选项，都支持循环展开优化。
注：关于循环展开的详细讲解，请参看文末推荐阅读的两篇文章(如果你还没看过的话)。
有童鞋可能会好奇，循环展开到底能提升多少性能呢？我们还是用数据说话，看一个实例吧。
测试环境：
OS：Ubuntu 19.04(Linux Kernel 5.0.0)CPU：Intel(R) Xeon(R) Gold 6130主频：2.10GHzCache 大小：22MBCache line 大小：64 Bytes测试代码：
图片
loop1.c和loop2.c做的事情一样，唯一的区别是：
• loop1.c每次循环迭代执行一次k++
编译：
gcc loop1.c -o loop1gcc loop2.c -o loop2测试结果：
图片
做同样的事情，通过循环展开优化，所消耗时间直接从25.4秒降到了14.7秒！
了解了循环展开对性能提升的好处之后，我们就可以对上面的简单实现进行第一次优化尝试了。
我们先尝试把每次循环内拷贝字节的个数，由1个提高到到8个，这样就可以把迭代次数降低8倍。
我们先假设，send()函数的参数count总是8的倍数，那么上面的代码就可以修改为：
图片
上面的代码很好理解，就是把原来迭代里的操作复制了8次，然后把迭代次数降低到了8倍。
但是，我们前面做了一个假设，就是count是8的倍数。那如果不是8的整数倍呢，比如20？那我们可能会想到这样的实现：
图片
其实，到了这里，相比原始的实现来说，性能已经能提升了不少了。但是，Duff仍然不满意，他看着第二个while循环非常不爽，尽管对整体性能已经没有太大影响了。
也许这就是大牛异于常人之处，大牛总是追求极致，总是可以在看似不可能的时候，再往前走一步。
Duff注意到C语言中switch-case语句的一些特性：
• case语句后面的break语句不是必须的。
• 在switch语句内，case标号可以出现在任意的子语句之前，甚至运行出现在if、for、while等语句内。
于是，Duff便利用switch-case的特性，用来处理第一个while循环之后仍然剩余的count % 8个字节的数据。于是便有了这样的代码：
图片
解释下这段代码：
我们假设count = 20，那么：
n = (count + 7) / 8 = 27 / 8 = 3count % 8 = 4所以：
好了，到这里，大家应该理解Duff's Device了吧？还是不清楚的话，可以尝试单步跟踪一下，就会很清晰了。
理解了Duff's Device之后，文章开头的那个题目就很好理解了，现在揭晓答案：
再看一下源码：
图片
编译运行：
图片
所以，答案是：20
本文链接：http://www.28at.com/showinfo-26-54184-0.html20行经典C代码，很多人看不明白，你来试一下？
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
上一篇： Jedis连接池究竟是何物
下一篇： 一文看懂：函数式编程为何这么火？
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号