Hello World
Spiga

浅谈代码的执行效率(4):汇编优化

2010-01-14 00:08 by 老赵, 11203 visits

终于谈到这个话题了,首先声明我不是汇编优化的高手,甚至于我知道的所有关于汇编优化的内容,仅仅来自于学校的课程、书本及当年做过的一些简单练习。换句话说,我了解的东西只能算是一些原则,甚至也有一些“陈旧”了——不过我想既然是一些原则性的东西,还是能够用它来做一定程度的判断。至少我认为,我在博客园里看到的许多关于“汇编优化”也好,“内嵌汇编”也罢的说法,经常是有些问题的。

说到汇编优化,自然被人想到“高性能”。似乎用.NET或Java平台上的程序性能一定不佳,性能好的程序一定要用C++——不,至少一定要用C来写。为什么呢?因为一个“常识”:便是“封装”会损失性能。性能最高的是“机器码”,因为CPU直接执行机器吗;“汇编”作为机器码的直接对应产物性能自然是一致的;C语言对于汇编/机器码几乎没有任何封装,因此性能也很好;而到了C++语言时,性能就要比C慢一些了——不过,这个看法正确吗?

其实我最近这几篇文章谈的都是与程序性能,尤其是代码执行效率有关的话题。在上一篇文章里,我们可以知道即便是在使用汇编编写代码,同样绕不开“CPU缓存”这部分与计算机体系结构相关的内容,而它对程序性能的影响甚至远远超过几句指令本身。事实上这也只是一小个方面而已,我们平时在谈性能相关问题时,总是在做很多假设,例如我们会假设不同指令的执行速度是一样的,各级别存储的读取性能也是相同的,但这都只是一个“理想环境”,和“事实”有很大差距。而进行汇编级别的优化,往往也是在利用“事实”进行细枝末节的调整。

例如,假设编译器只是对代码做“直接翻译”的话,您认为以下两种做法性能哪个比较好?

int sum = 0;
for (int i = 0; i < 100; i++)
{
    sum += array[i];
}
int sum1 = 0, sum2 = 0;
for (int i = 0; i < 100; i += 2)
{
    sum1 += array[i];
    sum2 += array[i + 1];
}

int sum = sum1 + sum2;

从算法上看,两者完全相同,但是对于CPU来说,后一种做法比前一种做法性能要高。首先,第二段代码与前者相比,一个循环内部有两个完全不相关的加法运算,这样CPU便有机会将他们并行地执行,于是性能便会更好一些。其次,第二种做法的条件跳转次数少,一般来说性能就会更好一些。因为条件跳转直到最后一刻才知道要跳向何方,因此CPU流水线就很难对代码的走向进行预测了。当然,现在CPU设计已经引入了分支预测技术,如果预测成功,效率自然较高,但如果预测失败,那么便会有比较严重的损失了。因此,有时候“我们”会尽可能想办法去减少条件跳转的次数。

例如,求一个有符号32位整数的绝对值,按照我们普通的逻辑,它应该是这样的:

if (eax < 0) eax = -eax

这显然是一个条件跳转,但是它的汇编实现也完全可以是:

cdq           // 扩展eax的符号位到edx中,如果eax是正数则edx为0否则edx为0xffffffff
xor eax, edx  // 如果eax为负数,就把所有的位取反,否则不变
sub eax, edx  // 如果最开始eax为负数,则把这个数字取反加一

这样,原本的条件跳转消失了,但是我们使用顺序的汇编指令得到了正确的结果。

这样看来,内嵌汇编对于性能多么关键啊。但是,我们真需要亲自动手实现这些吗?无论是前面的“循环展开”还是后面的“取绝对值”都是机械的汇编级别的优化,这些正是编译器最(包括运行时里的JIT)擅长的优化手段了。如果我们想要代替编译器去做这些事情,基本上唯一的结果只是“丑陋的代码”而难以有性能的提高。

编译器其实是提高代码执行效率的重要工具,例如之前在谈这个话题的时候,有人谈到OCaml的性能比C/C++要高,这便是因为它的编译器并不需要像C/C++编译器那样作出最坏的打算——例如C/C++很多时候无法检测出两个变量之间的关系,因此只能按部就班地执行。同样,我们为什么说C语言中strlen()不应该放在循环内部,因为它会造成重复计算?因为C语言编译器不能假设在循环过程中strlen的返回值永远不变,因此它无法自动将其提取到循环外部,只能一遍遍地执行。

因此很多时候,我们在这方面必须为编译器做点什么。例如,一个关于处理器的“常识”便是,不管是整数还是浮点数,除法操作都比乘法要慢上许多,因此我们需要尽可能消除一些除法,例如在进行图片缩放的时候,我们需要确定缩放的依据是“宽”还是“高”,因此我们可能就会写这样的代码:

if (desiredWidth / originalWidth < desiredHeight / originalHeight)

事实上,如果您要在性能上作精细地追求,则这样是更好的做法:

if (desiredWidth * originalHeight < desiredHeight * originalWidth)

可惜的是,编译器可能无法为我们自动作这样的优化:我们的这些变量都是32为“有符号”整数,因此originalWidth可能会是负数。虽然我们知道图片的尺寸一定大于零,但是我们却没有办法把这些信息告诉编译器,因此编译器只能做最保守的计算了。

看到这里您可能会说,这些是在谈汇编优化吗?好像还是一直再说高级代码啊。没错,因为正向刚才所说那样,我不其实并不了解多少汇编优化的内容,我也只能说一些“大道理”。如果您对这方面有些“兴趣”的话,云风的《游戏之旅——我的编程感悟》一书似乎值得您一看(其实这篇文章的许多说法,都和这本书有密切关系)。在这本书里,云风总结他在多年游戏开发中总结到的经验,其中有相当部分便是汇编优化方面的内容。其中也讨论了许多其他方面的问题,如文章开始我提到的C++和C语言的性能高低,他认为C++的性能其实与C语言相比有过之而无不及,如果您在C语言里实现C++的特性(如多态)则几乎无法作的如C++一样好,而反过来,如果在C++中做C语言写过程式的代码,其性能往往会比C语言来的好。为什么?语言特性与编译器的威力呗。

如今的处理器,它的的优化手段已经非常高级,远不是在加快时钟频率上那么简单。这给了程序员手动进行汇编优化的动力,因为此时可能只要交换两条指令的顺序便可以有很明显的性能提高,而编译器的力量已经不足以作更细致的优化了。同时,CPU设计上的进步也在敦促程序员要不断更新自己的知识,因为可能在旧CPU上常用的优化方式,到了新的CPU上就不是那么明显了。例如《游戏之旅》就用了“不小”的篇幅“简单”描述了从Pentium到Pentium IV上渐进的优化方式。

当然,我并不赞同以性能为尊的程序编写方式,事实上汇编优化远比编写高级代码更可能遇到麻烦。云风在书上也强调,不要过于信任自己的汇编书写能力,即便像他这样有丰富经验的高手也遇到过不少令人大跌眼镜的事情。

更新:希望您在看了这篇文章以后,也可以关注一下下面的评论,不乏精妙说法。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

31 条回复

  1. 老赵
    admin
    链接

    老赵 2010-01-14 00:08:00

    唉,写自己不擅长的话题果然够呛……大家先看看有机会我再改改,还有就是各位高手帮忙纠错。

  2. epson
    *.*.*.*
    链接

    epson 2010-01-14 00:30:00

    但如果如厕失败,那么便会有比较严重的损失了。因此,有时候“我们”会尽可能想办法去减少条件跳转的次数。


    如厕。。错别字哦

    老赵写博客时肯定很想上厕所

  3. 只睡5小时
    *.*.*.*
    链接

    只睡5小时 2010-01-14 01:00:00

    已阅

  4. 老赵
    admin
    链接

    老赵 2010-01-14 01:03:00

    今天搞了一整天GG,没心情作别的事情了。

  5. ITniao
    *.*.*.*
    链接

    ITniao 2010-01-14 05:39:00

    搞精了 搞下破解,逆向不错.

  6. JimLiu
    *.*.*.*
    链接

    JimLiu 2010-01-14 09:08:00

    在我一直以来的经验和分析观点中,我一直认为对于CPU密集型计算,高级语言与低级语言的差异不会很大,甚至有过之,就是因为更强大的编译器优化。
    真正说C#/Java比C/C++什么的慢,在我看来主要是内存密集型计算中体现的比较明显。有托管内存和没有托管内存的区别就体现出来了,这个很大程度上要靠VM来优化,目前我们也没什么办法。

  7. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-14 09:25:00

    啊……想起之前写的一帖,一个普通Java程序员或许都不会去想循环会被如何优化,但如果知道VM里的JIT能做非常强悍的循环展开的话,一个有经验的Java程序员也不需要再多想这种细节问题了 >_<

  8. 嗷嗷
    *.*.*.*
    链接

    嗷嗷 2010-01-14 09:33:00

    汇编优化,是需要基于对CPU体系构架熟悉的基础上才能做的事情。
    一篇泛泛而谈的文章,于老手无益,除了让众外行顶礼膜拜,于新手亦无指导之功。
    如果真有人看了文章而用
    sum1 += array[i];
    sum2 += array[i + 1];
    来优化代码,并大谈其优化之道的话,那就有误导人之嫌了。
    这种写法,在当今的CPU体系结构之中,所能带来的性能提升已经是微乎其微的了。

    术业有专攻,为何一定要在自己不擅长的领域里面作文呢。
    如果一定要写这样一篇文章来组成一个系列的话,不如就这样写好了
    汇编优化,非有深厚功底者,请勿轻易尝试。
    风云的《游戏之旅——我的编程感悟》一书值得你一看。
    如有恒心大毅力者,请细读
    Intel 64 and IA-32 Architectures Optimization Reference Manual 以及
    Intel 64 and IA-32 Architectures Software Developer's Manual Volume 1: Basic Architecture
    http://www.intel.com/products/processor/manuals/

  9. DiggingDeeply
    *.*.*.*
    链接

    DiggingDeeply 2010-01-14 09:44:00

    @嗷嗷
    亦推荐intel的白皮书三卷,曾经在无聊的时候粗览过。

  10. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-14 09:59:00

    @嗷嗷
    @DiggingDeeply
    以前读Optimization Reference Manual的时候,看到inc和dec应该用add和sub来代替的时候我惊讶了……居然是在flag上出现了伪数据依赖 =_=||||

  11. 小城故事
    *.*.*.*
    链接

    小城故事 2010-01-14 10:11:00

    Jeffrey Zhao:唉,写自己不擅长的话题果然够呛……大家先看看有机会我再改改,还有就是各位高手帮忙纠错。


    知道什么就写什么呗,怕什么,关键是定位要对吧,老赵说了嘛 "浅谈"。对了,老赵去哪工作了?是盛大吗?

  12. Rain Shan
    *.*.*.*
    链接

    Rain Shan 2010-01-14 10:29:00

    老赵如果说的太深了,我这样的菜鸟就看不懂了。
    浅显易懂点好。 呵呵

  13. Arthas-Cui
    *.*.*.*
    链接

    Arthas-Cui 2010-01-14 10:33:00

    我听过一段反驳, 关于C语言和汇编语言的效率的:

    1 用C写一段代码。
    2 找个反编译工具反编译成汇编。
    3 找个汇编工具再编译过去。
    4 比较执行效率。

    可以证明:“相同功能的程序, 汇编写的, 比c语言要快”, 这个观点是错误的。
    在这个试验中, 相等~

    我没验证过。感觉这个逻辑很有意思。

  14. 极品拖拉机
    *.*.*.*
    链接

    极品拖拉机 2010-01-14 10:53:00

    @小城故事

    小城故事:

    Jeffrey Zhao:唉,写自己不擅长的话题果然够呛……大家先看看有机会我再改改,还有就是各位高手帮忙纠错。


    知道什么就写什么呗,怕什么,关键是定位要对吧,老赵说了嘛 "浅谈"。对了,老赵去哪工作了?是盛大吗?


    恩?盛大?哪个部门啊?
    盛大在线?
    怎么没听老赵透露口风

  15. 只睡5小时
    *.*.*.*
    链接

    只睡5小时 2010-01-14 11:18:00

    极品拖拉机:
    @小城故事

    小城故事:

    Jeffrey Zhao:唉,写自己不擅长的话题果然够呛……大家先看看有机会我再改改,还有就是各位高手帮忙纠错。


    知道什么就写什么呗,怕什么,关键是定位要对吧,老赵说了嘛 "浅谈"。对了,老赵去哪工作了?是盛大吗?


    恩?盛大?哪个部门啊?
    盛大在线?
    怎么没听老赵透露口风


    嗯,嗯,就在看完老赵的“2009年末,多少进行一些总结和展望吧”这篇文章的第二天偶就听说老赵去了盛大。

  16. Fisher WEI
    *.*.*.*
    链接

    Fisher WEI 2010-01-14 11:21:00

    没把握,别搞这个优化,到汇编曾,就是针对特性处理器进行优化了。pentium 4 和 core 2 都是不通用的。搞不好适得其反。

    - core只有14级流水,p4有31级。分支对p4是致命的,但是对core危害却要小很多。core提升频率的成本高于p4,所以高强度的程序适合core,低分支的适合p4。(core和p4比,不仅流水短,分支预测也强于p4,所以这种一边借钱,一边赊账的比较有点不合理。)

    - CPU一次会快取4KB(大学教科书上说的,不知道现在的CPU变没变)的code放在L2 cache里面,优化的话就要把关系最紧密的代码尽可能的放到一起,这种优化如何做?要手工对齐code段么?我没做过不知道。而且,如何比较代码之间的关系哪断比哪断更何哪断紧密?

    - 现在的4核CPU都有L3 Cache,这个高端东东是如何工作的?貌似他不分code和data。

    - 除了便宜的Atom CPU,好像现在的X86 CPU都有乱续执行功能,这也是程序员不可预估的。听说这个功能能大幅提升CPU性能。

    - 在 C++ 里面进行 CPU 优化,出来的代码堪比芙蓉姐姐:

    #if PLATFORM(SYMBIAN)
    ......
    #endif

    #if PLATFORM(WINNT_X86)
    ....
    #endif

    - 如果你做的程序同时在arm5, x86, power pc上运行,这就更复杂了(比如Qt)。很难想象,组建一个同时精通这三种cpu的汇编(精通是指不仅会用,而且还理解各cpu的长处,能写出优化度很高的代码)的team,需要多大的成本。

    所以呢,这些麻烦的问题,还是交给那些昂贵的编译器解决吧,x86上gcc/g++还可以用一下。但是 g++ 的那个 arm 版本,现阶段实在不敢恭维,还得用那好几块钱的那个。

  17. qiaojie
    *.*.*.*
    链接

    qiaojie 2010-01-14 11:45:00

    现代的CPU已经越来越像一个虚拟机了,指令经过解码以后会分解成若干微指令,微指令之间又可能重新融合成宏指令,指令执行顺序也不是顺序的,而是乱序执行,像乘法除法这些都有硬件流水线来处理,最高吞吐量可以达到1一个时钟周期一次乘法或者除法,当然会有比较长的延迟。所以要写出符合CPU体系架构的高性能汇编代码已经很困难了。而且随着编译器技术的不断完善,人肉汇编基本上已经难以超越编译器了。Intel Compiler很多年前就搞出了一项编译优化技术,首先静态编译出执行程序,跑一遍后收集相关的profiling信息,然后再次进行编译,重新排列指令顺序以提高分支预测效率,此项优化号称可以提高10%~20%的执行效率。,用人肉汇编的话这样的手段是不可想象的。

  18. Bob-wei
    *.*.*.*
    链接

    Bob-wei 2010-01-14 12:16:00

    B013 MOV AL,13
    CD10 INT 10
    C42F LES BP,[BX]
    AA STOSB
    11F8 ADC AX,DI
    64 DB 64
    13066C04 ADC AX,[046C]
    EBF6 JMP 0106

  19. Bob-wei
    *.*.*.*
    链接

    Bob-wei 2010-01-14 12:16:00

    想起一个DOS下16字节的COM文件,找出来秀一下:

  20. Bob-wei
    *.*.*.*
    链接

    Bob-wei 2010-01-14 12:26:00

    C#语言中,位运算符的结果为什么不是byte类型?而是Int32?

  21. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-14 12:35:00

    qiaojie:
    Intel Compiler很多年前就搞出了一项编译优化技术,首先静态编译出执行程序,跑一遍后收集相关的profiling信息,然后再次进行编译,重新排列指令顺序以提高分支预测效率,此项优化号称可以提高10%~20%的执行效率。,用人肉汇编的话这样的手段是不可想象的。


    PGO现在在静态编译器中已经不少见,不止ICC,Sun CC、gcc、MSVC之类的都可以做;在动态编译器中PGO更是重点开发领域……

  22. 老赵
    admin
    链接

    老赵 2010-01-14 13:24:00

    DiggingDeeply:
    @嗷嗷
    亦推荐intel的白皮书三卷,曾经在无聊的时候粗览过。


    大学里曾经想当过参考书来着,但始终没有细看……及粗看……

  23. 老赵
    admin
    链接

    老赵 2010-01-14 13:24:00

    嗷嗷:
    汇编优化,是需要基于对CPU体系构架熟悉的基础上才能做的事情。
    一篇泛泛而谈的文章,于老手无益,除了让众外行顶礼膜拜,于新手亦无指导之功。


    还好吧,如果我没有说错什么的话,谈谈也无妨。
    至少了解到我这个程度,看出一些错误的说法问题已经不大了,呵呵。


    如果真有人看了文章而用
    sum1 += array[i];
    sum2 += array[i + 1];
    来优化代码,并大谈其优化之道的话,那就有误导人之嫌了。
    这种写法,在当今的CPU体系结构之中,所能带来的性能提升已经是微乎其微的了。


    我文章里不都已经写了这些了吗?
    “如果我们想要代替编译器去做这些事情,基本上唯一的结果只是“丑陋的代码”而难以有性能的提高。”
    或者你可以再补充说点什么呢?

  24. 老赵
    admin
    链接

    老赵 2010-01-14 13:25:00

    qiaojie:现代的CPU已经越来越像一个虚拟机了,指令经过解码以后会分解成若干微指令,微指令之间又可能重新融合成宏指令,指令执行顺序也不是顺序的,而是乱序执行,像乘法除法这些都有硬件流水线来处理,最高吞吐量可以达到1一个时钟周期一次乘法或者除法,当然会有比较长的延迟。所以要写出符合CPU体系架构的高性能汇编代码已经很困难了。而且随着编译器技术的不断完善,人肉汇编基本上已经难以超越编译器了。Intel Compiler很多年前就搞出了一项编译优化技术,首先静态编译出执行程序,跑一遍后收集相关的profiling信息,然后再次进行编译,重新排列指令顺序以提高分支预测效率,此项优化号称可以提高10%~20%的执行效率。,用人肉汇编的话这样的手段是不可想象的。


    顶一下。

  25. 老赵
    admin
    链接

    老赵 2010-01-14 13:31:00

    JimLiu:
    在我一直以来的经验和分析观点中,我一直认为对于CPU密集型计算,高级语言与低级语言的差异不会很大,甚至有过之,就是因为更强大的编译器优化。
    真正说C#/Java比C/C++什么的慢,在我看来主要是内存密集型计算中体现的比较明显。有托管内存和没有托管内存的区别就体现出来了,这个很大程度上要靠VM来优化,目前我们也没什么办法。


    是的……

  26. 嗷嗷
    *.*.*.*
    链接

    嗷嗷 2010-01-14 14:19:00

    @Jeffrey Zhao
    老赵,这篇本身并无什么技术上的错误,这不过这样的浅谈于人于己帮助都不大。
    你有你所长的领域,你应该把你的精力放在那些领域去分享知识,去指导初学者。
    一篇高质量的博文对于大家的好处远远高于多篇肤浅的泛泛而谈。
    反而我还认为肤浅的泛泛而谈会让大家花费更多的时间,有弊而无益。
    老赵你也是这里的热心人士,热爱分享,所以我才会想提出这样的建议,对你自然要有更严格的要求。

    最后,"分享不是说把自己的知识写出来,告诉别人,分享是要让别人能够学到东西"。
    “我喜欢写些东西,别人能学多少就是多少了"这并非分享之道。
    希望这几句话能让你的博客更加出色。

  27. 老赵
    admin
    链接

    老赵 2010-01-14 14:32:00

    @嗷嗷
    呵呵,多谢你的建议,不过我想,如果让我重来一次的话,我还是会写这篇的吧。
    因为我觉得这篇于人于己都有帮助啊,初学者可以了解些不知道的概念,我也可以从高手的回复那里得到不少东西。
    例如,一些关于某些话题的论据,意见,资料引用等等……

    我的想法就是,如果我想写什么了,那么就会写一下,而不是以“指导”别人的方式写作的。
    如果这次写的不好,待高手来批评指正之后,下次再重写么。
    此外,其实我写博客的目的最主要是“交流”,关于这个“方针政策”我多次提到过:
    http://www.cnblogs.com/JeffreyZhao/archive/2009/12/31/summary-2009.html
    http://www.cnblogs.com/JeffreyZhao/archive/2009/10/16/talk-about-blogging.html

    不过你可以放心,此类文章肯定不会多。因为如果不是有想法,我也不会特地找些不擅长的东西来谈,呵呵。
    但是,我实在不能保证我以后会刻意不写这样的文章。

  28. Prime Li
    *.*.*.*
    链接

    Prime Li 2010-01-15 13:15:00

    不知道如何针对CPU的指令集进行优化,比如酷睿系列的SSE4.1。

  29. 金色海洋(jyk)
    *.*.*.*
    链接

    金色海洋(jyk) 2010-01-15 23:18:00

    这是用IE6遨游看的,小小的兴奋一把。

    回复也是。

  30. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2010-01-30 10:11:00

    虽然没有指导实际编程的太多内容,但至少让读者起到了了解汇编优化的作用。

  31. 链接

    gaobanana 2010-04-10 13:34:56

    开阔视野!支持

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我