20行经典C代码,很多人看不明白,你来试一下?

2023年 12月 26日 39.3k 0

大家好,我是江南一散人。周末逛知乎时,无意间看到阿里云开发者官方账号的一篇文章中,居然引用了我三年前在今日头条写的一篇文章。有些感概,看来还真的在互联网上留下了点痕迹。

那篇文章,其实和那篇《改几行代码,for循环耗时从3.2秒降到0.3秒!真正看懂的都是牛人!》是相关的,算是前传吧,所以在这里发一下,感兴趣的小伙伴不妨围观下!

全文如下,仅作微调。

引言

昨天发了一段有趣的代码,引来很多童鞋围观。很多童鞋表示不太明白,于是就有了本文,详细解释下这段代码的来龙去脉。

代码如下图所示:

图片图片

如果你是第一次看到的话,不妨试一下,看你能得出正确答案吗?

其实,这个题目还是源自大师之手,我只是做了少许修改。先来聊一下这段历史渊源吧。

注:为了尽量解释清楚,篇幅有点长,请耐心读完,相信你会有收获的!

历史渊源

1983年11月,一位叫Tom Duff的大牛在编写串口通信程序时,发现使用一般的写法时,性能总是不能让人满意。后来,这位老兄凭借深厚的编程功底和精湛的C语言技艺,利用C语言中switch语句的一个鲜为人知的特性,发明如了下图所示的经典代码:

图片图片

结果,引来无数吃瓜群众膜拜。在此之前,还没有人发现并利用过C语言的这个特性,于是他便以自己的名字命名这段代码,叫做Duff's Device,一般译为"达夫设备"。

先看一下大牛的风采吧:

图片图片

下面讲解一下这段代码。

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%!

无法充分发挥ILP技术优势

现代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.10GHz
Cache 大小:22MB
Cache line 大小:64 Bytes

测试代码:

图片图片

loop1.c和loop2.c做的事情一样,唯一的区别是:

• loop1.c每次循环迭代执行一次k++

  • • loop2.c每次循环执行8次k++,但是循环的次数比loop1.c少了8倍

编译:

gcc loop1.c -o loop1
gcc loop2.c -o loop2

测试结果:

图片图片

做同样的事情,通过循环展开优化,所消耗时间直接从25.4秒降到了14.7秒!

第一次优化尝试

了解了循环展开对性能提升的好处之后,我们就可以对上面的简单实现进行第一次优化尝试了。

我们先尝试把每次循环内拷贝字节的个数,由1个提高到到8个,这样就可以把迭代次数降低8倍。

我们先假设,send()函数的参数count总是8的倍数,那么上面的代码就可以修改为:

图片图片

上面的代码很好理解,就是把原来迭代里的操作复制了8次,然后把迭代次数降低到了8倍。

但是,我们前面做了一个假设,就是count是8的倍数。那如果不是8的整数倍呢,比如20?那我们可能会想到这样的实现:

图片图片

其实,到了这里,相比原始的实现来说,性能已经能提升了不少了。但是,Duff仍然不满意,他看着第二个while循环非常不爽,尽管对整体性能已经没有太大影响了。

也许这就是大牛异于常人之处,大牛总是追求极致,总是可以在看似不可能的时候,再往前走一步。

C语言switch-case的一些特性

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 = 3
count % 8 = 4

所以:

  • 1. switch语句会落入case 4的标签内,然后依次执行了case 4、3、2、1四条语句。自此之后,其实就跟switch-case语句再也没有关系了。
  • 2. while语句判断--n > 0,条件成立,于是跳转到case 0进入循环体执行,于是依次执行case 0、7、6、5、4、3、2、1一共8条语句。此时n = 2.
  • 3. 再次进入while语句处判断--n >0,条件成立,再次跳转到case 0处进入循环体执行。此时n = 1。
  • 4. 此时,while语句处判断--n >0,条件失败,退出循环,函数结束。
  • 好了,到这里,大家应该理解Duff's Device了吧?还是不清楚的话,可以尝试单步跟踪一下,就会很清晰了。

    揭晓答案

    理解了Duff's Device之后,文章开头的那个题目就很好理解了,现在揭晓答案:

    再看一下源码:

    图片图片

    编译运行:

    图片图片

    所以,答案是:20

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论