(转载)编译器能帮我们把代码优化到什么程度?

本贴最后更新于 1124 天前,其中的信息可能已经事过境迁

转载

TODO: 用 while 写法的程序会不会循环展开?

一个简单的累加求和程序:

TYPE S=0;  
for(int i = 0;i < SIZE; i++) {  
	S += a[i];  
}

很多人都觉得这个程序写得不好,编译器不能生成很好的汇编代码。于是有了以下的几种“优化”:

#include <iostream>
using namespace std;
 
void main(int argc,char **argv)
{
#define TYPE int
#define SIZE 10000
 
	TYPE* a=new TYPE[SIZE];  
	for(int i = 0; i<SIZE; ++i){
		a[i] = i;
	}
	//求和,通常版本
	TYPE S=0;  
	for(int i = 0;i < SIZE; i++) {  
		S += a[i];  
	}
	cout<<S<<endl;
 
	TYPE S2 = 0;
	//版本1:认为中间产生的变量i是多余的,改为用移动指针
	TYPE* end = a + SIZE;
	for( ; a != end; ) {  
		S2 += *(a++);  
	}
	cout<<S2<<endl;
 
	//版本1中把a移到了数组的最后,现在移回原来的位置
	a = end - SIZE;
 
	//版本2:认为循环次数太多了,可以改为减少循环次数
	TYPE S3 = 0;
	for(int i = 0; i < SIZE; ){ //仅当SIZE为偶数时
		S3 += a[i++];
		S3 += a[i++];
	}
	cout<<S3<<endl;
 
	//版本3:认为版本2中会使CPU不能乱序执行,降低了效率,应该改为汇编,把中间结果放到独立的寄存器中
	//谢谢 menzi11 的文章,让我认识到程序中相关的数据会让CPU不能乱序执行。
	//这里用伪汇编代替
	TYPE S4 = 0;
 
	register TYPE r1 = 0;
	register TYPE r2 = 0;
	for(int i = 0; i < SIZE; ){ //仅当SIZE为偶数时
		r1 += a[i++];
		r2 += a[i++];
	}
 
	cout<<r1 + r2<<endl;
}

上面的几种版本都合理,但是这些优化都是建立在编译器不能生成高效的汇编代码的假设上的。

下面来看下编译器生成的结果(vs2010,release):

for(int i = 0;i < SIZE; i++) {  
		S += a[i];  
013B1040  mov         ebx,dword ptr [eax+4]  //把a[0],a[4],a[8]...累加到ebx中
013B1043  add         ecx,dword ptr [eax-8]  //把a[1],a[5],a[9]...累加到ecx中
013B1046  add         edx,dword ptr [eax-4]  //把a[2],a[6],a[10]...累加到edx中
013B1049  add         esi,dword ptr [eax]    //把a[3],a[7],a[11]...累加到esi中
013B104B  add         dword ptr [ebp-4],ebx  
013B104E  add         eax,10h  
013B1051  dec         dword ptr [ebp-8]  
013B1054  jne         main+40h (13B1040h)  
	}
	cout<<S<<endl;
013B1056  mov         eax,dword ptr [ebp-4]  
013B1059  add         eax,esi  		      
013B105B  add         eax,edx  
013B105D  mov         edx,dword ptr [__imp_std::endl (13B204Ch)]  
013B1063  add         ecx,eax                //上面的3条add指令把ebx,ecx,edx,edi都加到ecx中,即ecx是累加结果

可见编译器生成的代码是最好的代码,消灭了中间变量 i,减少了循环次数,消灭了会造成 CPU 不能乱序执行的因素。

BTW:

有人可能会有疑问:要是 size 不是偶数,编译器能生成类似的高效汇编代码不?

当 SIZE = 9999 时:

//当SIZE = 9999时,编译器把中间结果放到三个寄存器中,perfect
	for(int i = 0;i < SIZE; i++) {  
		S += a[i];  
01341030  add         ecx,dword ptr [eax-8]  
01341033  add         edx,dword ptr [eax-4]  
01341036  add         esi,dword ptr [eax]  
01341038  add         eax,0Ch  
0134103B  dec         ebx  
0134103C  jne         main+30h (1341030h)  
	}

当 SIZE = 9997 时:

//当SIZE = 9997时,有点复杂,先把a[0]到a[9995]累加到ecx和edx中
//再把a[9996]入到edi中,最后把ecx,edi都加到edx中
//edx压栈,调用operator<< 函数
	for(int i = 0;i < SIZE; i++) {  
00D31024  xor         eax,eax  
		S += a[i];  
00D31026  add         ecx,dword ptr [esi+eax*4]  
00D31029  add         edx,dword ptr [esi+eax*4+4]  
00D3102D  add         eax,2  
00D31030  cmp         eax,270Ch  
00D31035  jl          main+26h (0D31026h)  
	for(int i = 0;i < SIZE; i++) {  
00D31037  cmp         eax,270Dh  
00D3103C  jge         main+41h (0D31041h)  
		S += a[i];  
00D3103E  mov         edi,dword ptr [esi+eax*4]  
	}
	cout<<S<<endl;
00D31041  mov         eax,dword ptr [__imp_std::endl (0D3204Ch)]  
00D31046  add         edx,ecx  
00D31048  mov         ecx,dword ptr [__imp_std::cout (0D32050h)]  
00D3104E  push        eax  
00D3104F  add         edx,edi  
00D31051  push        edx  
00D31052  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (0D32048h)]

上面的分析都是 SIZE,即数组的大小是已知情况下,那个数组大小是未知情况下,编译器又会怎样?

TYPE mySum(TYPE* a, int size){
	TYPE s = 0;
	for(int i = 0; i < size; ++i){
		s += a[i];
	}
	return s;
}

生成的汇编代码:

//先累加a[0] 到 a[size-2]
	TYPE s = 0;
00ED100C  xor         esi,esi  
	for(int i = 0; i < size; ++i){
00ED100E  xor         eax,eax  
00ED1010  cmp         ebx,2  
00ED1013  jl          mySum+27h (0ED1027h)  
00ED1015  dec         ebx  
		s += a[i];
00ED1016  add         ecx,dword ptr [edi+eax*4]    //a[0],a[2],a[4]...加到ecx中
00ED1019  add         edx,dword ptr [edi+eax*4+4]  //a[1],a[3],a[5]...加到edx中
00ED101D  add         eax,2  
00ED1020  cmp         eax,ebx  
00ED1022  jl          mySum+16h (0ED1016h)  
00ED1024  mov         ebx,dword ptr [size]  
	for(int i = 0; i < size; ++i){
00ED1027  cmp         eax,ebx                       //判断最后一个元素有没有加上
00ED1029  jge         mySum+2Eh (0ED102Eh)  
		s += a[i];
00ED102B  mov         esi,dword ptr [edi+eax*4]     //当size是奇数是会执行,偶数时不会执行
00ED102E  add         edx,ecx  
	}

总结

C++ 的编译器生成的汇编代码在绝大多数情况下都和人写出的最好的汇编代码相当。

关键的一点是编译器会不断升级,适应新的 cpu 指令,体系等,手写的汇编代码则通常悲剧了。

知道编译器能优化到什么程度,编译器到底怎样优化,是程序员很重要的素质。

  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    106 引用 • 152 回帖 • 2 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
zhaozhizheng
没有人会关心你付出过多少努力,撑得累不累,摔得痛不痛,他们只会看你最后站在什么位置,然后羡慕或者鄙夷 德里

推荐标签 标签

  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 381 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    25 引用 • 215 回帖 • 160 关注
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    362 引用 • 1212 回帖 • 580 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 21 关注
  • 安全

    安全永远都不是一个小问题。

    189 引用 • 813 回帖 • 2 关注
  • 百度

    百度(Nasdaq:BIDU)是全球最大的中文搜索引擎、最大的中文网站。2000 年 1 月由李彦宏创立于北京中关村,致力于向人们提供“简单,可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”,象征着百度对中文信息检索技术的执著追求。

    63 引用 • 785 回帖 • 249 关注
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    129 引用 • 793 回帖 • 1 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    18150 引用 • 66978 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 126 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 45 关注
  • CAP

    CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。

    11 引用 • 5 回帖 • 552 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    14 引用 • 7 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    37 引用 • 24 回帖 • 1 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 594 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    123 引用 • 168 回帖
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 284 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 498 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    9 引用 • 32 回帖 • 178 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    261 引用 • 662 回帖 • 1 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    5 引用 • 15 回帖 • 223 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 248 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 402 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 427 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 33 关注