forked from GHScan/TechNotes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path9.html
5 lines (4 loc) · 18.5 KB
/
9.html
1
2
3
4
5
<head>
<meta http-equiv=Content-Type content="text/html; charset=utf-8">
</head>
<div>■ 8. 单词：aggressive-激进的<br> ■ 保守优化，激进优化：conservative, aggressive<br>■ 11. GCC的优化选项<br> ■ -Ofast:比-O3多开了-ffast-math,不精确的浮点计算，但最快；结合在-O3自动开启的-ftree-vectorize，能够尽量多的进行auto-vectorization<br> ■ -msse3:-mavx:在自动向量化的基础上进行SIMD优化<br> ■ -ftree-vectorizer-verbose=9:-fdump-tree-vect-details:显示auto-vectorization的进行情况<br>■ 13. CSAPP：第5章第0节<br> ■ 优化的几个层次：语言无关的算法优化=>语言相关的编码优化=>机器相关的编码优化。最后一点只有native语言（C/C++、Go）或者jit编译器能做到（Java、Luajit）。第2点旨在给编译器足够的提示，这就要求了解编译器；第3点旨在更好的利用硬件<br> ■ C语言的一些特性阻碍优化：指针，强制类型转换<br> ■ 优化是"实现、维护的简单性"vs"速度"的权衡。优化应该放在hotspot上<br> ■ 理想中的编译器应该足够聪明，但事实上，一些optimization blocker会阻碍优化<br> ■ 机器级优化依赖于特定的ISA和时序<br> ■ 优化应该先通过profiler找到hotspot，然后重点优化<br> ■ 根据Amdahl定律，很难仅仅通过优化很少的模块将程序的性能提高一倍以上。故，优化要先定目标，要适可而止<br>■ 13. CSAPP：第5章第1节：优化编译器的能力和局限性<br> ■ optimization blocker 1: memory aliasing(pinter aliasing)<br> ■ optimization blocker 2: procedure side effect<br>■ 13. CSAPP：第5章第2节：表示程序的性能<br> ■ CPE：cycles per element，每元素的周期数<br>■ 13. CSAPP：第5章第4节：消除循环的低效率<br> ■ loop invariant code motion：循环不变量的提取。比如循环判断条件的,size()，编译器要判断这是一个循环不变量，要进行深入的分析，尤其是body内含有写操作的时候，分析尤其困难，因此最好手工提取以帮助编译器<br>■ 13. CSAPP：第5章第5节：减少过程调用<br> ■ 过程调用开销很大，bounds checking开销很大<br>■ 13. CSAPP：第５章第６节：消除不必要的存储器引用<br> ■ 由于memory aliasing的存在，有时候编译器无法将计算中间值缓存在寄存器中，而L1的访问开销是寄存器的1~10倍，所以会慢很多。可以在C中显示的增加临时变量，或者开启编译器的激进优化<br>■ 13. CSAPP：第5章第7节：理解现代处理器<br> ■ 除了直接针对特定型号机器编码外，我们还是可以在稍高一点的层次，针对一类处理器进行优化的<br> ■ 在ISA之下，实际的硬件机制可能包括pipeline、superpipeline、superscale以及out of order<br> ■ ICU：instruction control unit，即指令控制单元，从IL1取指，译码并翻译为一系列的micro-operation，再交给EU执行。这应该是CISC的行为（或者复杂的RISC指令）？retirement unit（退役单元）也在这部分，一个指令执行完毕并retire后，其副作用才会生效（在这期间，中间值通过register renaming保存），能够实现branch prediction。取指时有instruction prefetch<br> ■ EU：execution unit，执行单元，执行微操作。常见硬件单元包括：（1）整数/转移操作，即加减比较逻辑和转移（2）其他整数操作，包括乘除（3）浮点加法（4）浮点乘除法（5）加载（6）存储<br> ■ 常见的CPI（cycles per instruction，即latency）：加减法=1；乘法=3；除法=10*n；浮点稍慢，也是除法最慢；load、store=3<br> ■ ISA中的指令被翻译成微操作的时候，结合register renaming，结果类似SSA-form<br> ■ 实际制约EU性能的因素包括：latency、data dependency、control depedency（mispredict）、硬件单元数<br>■ 16. CSAPP：第5章第8节：降低循环的开销<br> ■ loop unrolling是想合并多次迭代动作到一个迭代中，降低了迭代计算在整个计算中的比例。除了增加代码尺寸外，没有明显额外副作用<br> ■ 由于ILP的存在，循环除法的瓶颈在除法本身的执行时间，迭代计算是可以并行的。因此，循环的除法、乘法受loop unrolling的影响较小，而循环加减法收益更多<br>■ 16. CSAPP：第5章第9节：转换到指针的代码<br> ■ 指针对数组的优势：loop unrolling过后的多次访存是静态偏移如p[0],p[1],p[2],p[3]（对比数组访问的a[i],a[i+1],a[i+2],a[i+3]）<br> ■ 数组对指针的优势：没有pointer aliasing的干扰，编译器更容易进行优化<br> ■ 结合可读性的考虑，一般用数组<br>■ 16. CSAPP：第5章第10节：提高并行性<br> ■ loop splitting(iteration splitting)：当运算满足交换律和结合律的时候（比如整数的二进制补码运算），将数据分成多组来计算，降低了data dependency，提高了ILP，因此可以得到跟高的性能<br> ■ 由于浮点乘法和除法不满足交换律和结合律（精度原因），因此编译器一般不会主动进行优化（除非开启aggressive的-Ofast优化），所以浮点运算更容易从手工的loop splitting优化中受益<br> ■ loop splitting的一个缺点是，由于一趟迭代中进行了过多的计算，因此需要更多的寄存器，否则会发生regsiter spilling，考虑到IA32的通用寄存器只有6个，因此循环分割的次数不要太多（比如不超过4）；由于IA32有独立的浮点寄存器，所以浮点运算可以分割更多次（比如不超过6）。<br> ■ 自动向量化(auto vectorization)在满足4点后更容易被优化编译器实施：(1)countable，因此可以进行4/8路的前期loop unrolling(2)no data dependency(3)no control flow(4)constant stride，常量跨度(最好是1)，然后进行gather和并行优化。自动向量化至少可以从ILP中受益，如果开启了sse优化，更能从DLP中受益<br> ■ 内循环中"ret=ret*(a*b*c)"和"ret=(a*b*c)*ret"可能性能是不同的，因为，如果编译器不进行乱序的话，前者在两次迭代之间的ret数据依赖性更大，而后者依赖性更小，更利于并行<br>■ 16. CSAPP：第5章第11节：浮点性能异常<br> ■ IA32（或者某特殊的DSP）下，浮点寄存器的位宽和C语言使用的IEEE单/双精度浮点位宽都不一样（IA32寄存器是80位），这就造成两个结果：(1)内存<->寄存器，寄存器<->内存，会有32<->80,64<->80的浮点数换算（2）将临时结果缓存在寄存器栈中计算（st）和总是从内存中load、计算、再store的计算方式，结果可能迥然不同，前者精度更高，后者则是符合IEEE规则<br> ■ 编译器对于浮点运算可能给出三个选择（如MSVC）：（1）精度(precise)，即精度不低于IEEE规定；在IA32（代表高位宽机器）上，就是尽量在80位的寄存器中计算；在低位宽的DSP上，就是尽量软件模拟（2）严格（strict），结算结果总是和IEEE规定相符；在IA32上，相当于总是访存，不用寄存器进行cache；在低位宽DSP上，总是模拟（3）性能（fast），总是使用寄存器<br> ■ 因为对NAN/INF/-INF的计算往往很少发生，因此浮点单元的硬件实现者可能不会在他们上做太多优化，因此当计算中间结果溢出后，可能会很慢。要注意避免这种情况发生在内循环中<br> ■ 简写power of 2为PO2，考虑乘除PO2的情况：（1）如果PO2是整数（a）PO2是编译期常量，则编译器优化其为移位（b）PO2是运行时变量，则只能期待硬件能够检测并优化为移位（2）如果PO2是浮点（a）PO2是编译期常量，编译器几乎没办法(但可以在fast优化下将除法优化为乘倒数)（b）PO2是运行时变量，我很确定硬件会检测并优化<br>■ 16. CSAPP：第5章第12节：转移预测和预测错误处罚<br> ■ 到1998年以前，分支预测都只是超级计算器独享的技术；在那以后，集成电路才开始集成专门的预测单元<br> ■ always taken能够提供60%的预测率；backward taken forward not taken这种总是取低地址的方案，能够有65%命中率；而今天的硬件，在行为预测上，已经能够有90~90%的hit rate<br> ■ 可以这样计算mispredict的开销：先统计全true path的CPE得到CPE1；再统计随机数据的数据驱动控制流，得到50%的命中率的CPE2。于是(CPE2-CPE1)*2可以近似的看做mispredict的开销。<br> ■ 三元运算符在语义上和if/else等价，但是因为它模式简单，编译器更容易将三元运算符优化为cmov指令，后者在很多硬件上都有实现，只是一个两路选择<br> ■ 由于分支预测失败的惩罚甚至能到20周期，按95%的命中率算，每次分支的额外开销仍然是1个时钟；一个程序中非立即跳转的比例大概在15%，因此，程序会被拖慢大概5~15%。假设由于数据分支的干扰或者DSP没有独立的分支预测单元，命中率降到60%，那程序将因为分支惩罚变慢100~120% !<br> ■ 对于逻辑性为预测，硬件的命中率已经达到95%，因此编译器和程序员无需干涉；而随机分布的数据驱动控制流，硬件命中率只能到50%，因此编译器和人工优化及其重要：（1）编译器可以进行cmov优化；以及将简单的数据选择控制流转换为多次数值计算。此皆为移除分支（2）人工将数据选择变换为数值计算序列，此为移除分支；或者在不改变程序语义的情况下，先整理数据得到规律分布（如排序），再执行，从而得近乎100%的硬件命中率，此为刷满命中率。<br>■ 16. CSAPP：第5章第13节：理解存储器的性能<br> ■ 加载：连续加载是高ILP的；而类似对链表各节点求累加的算法，是加载的data depedency的，并行性低。<br> ■ 存储：任何方式的连续存储都是高ILP的。<br> ■ 先加载再存储：高ILP<br> ■ 先存储再加载：可能会因为data dependency，造成stalling。存储器在读操作的时候，会判断写地址cache（表示有写操作正在执行）是否等于读地址，如是，则stalling。<br> ■ memcpy(a + 1, a, n)、memcpy(a, a + 1, n)、memcpy(a, a, n)性能是不同的，三者分别是：先写再读、先读再写、读写无关，因此后两者并行性很高，更快。这里的1增大到字长、cache line size，可能结果仍然相同。<br>■ 16. CSAPP：第5章第15节：确认和消除性能瓶颈<br> ■ 前面讲了怎么优化代码段，另一个很重要的问题是找出关键代码在哪里，这就需要借助profiler<br> ■ profiling包括这样一个程序版本：其中插入了工具代码，以确定程序的各个部分需要多少时间。<br> ■ 用-pg选项调用gcc编译程序，得到一个profiling版本的程序(-o main)，运行它，会输出一个gmon.out的统计文件，最后调用gprof main查看统计结果<br> ■ gprof的调用次数、caller/callee关系很可靠，但具体计时不够准确（当函数耗时很小的时候）<br> ■ Amdahl定律：考虑优化一个耗时占总时间40%的关键模块，极限情况下，将其加速1000倍，总时间变为原来的60.04%，最终也仅仅加速不到1倍。所以，很难通过优化单一模块来将程序提速1倍以上，要想得到如此大的加速比，需要优化整个程序。<br>■ 18. 程序员修炼之道：15. shell游戏<br> ■ 木匠用工作台来放置和使用工具；对应的，shell是工具的组织和调度中心<br> ■ GUI的好处是：WYSIWYG(what you see is what you get); 而GUI的坏处是：WYSIAYG(what you see is all you get)<br> ■ 可以用"find . -mtime -7"活着"find . -newer a.txt"这样的模式查找文件<br> ■ shell可以让工作自动化<br>■ 22. 程序员修炼之道：16. 强力编辑<br> ■ 下面是强力编辑器的一些特性：<br> ■ 可配置：字体、颜色、窗口尺寸和键绑定<br> ■ 可扩展：能够通过插件、脚本的方式支持新的语言、文本格式<br> ■ 可编程：支持宏等<br> ■ IDE特性：语法高亮；自动完成；自动缩进；帮助系统；编译、调试<br>■ 23. 程序员修炼之道：17. 源代码控制<br> ■ 不能记住过去的人，必将重复过去<br> ■ VCS是一个大的UNDO按键，是一个时光机器<br> ■ VCS可以用来进行自动、可重复的产品构建（比如脚本化的clone、make）<br>■ 25. 程序员修炼之道：18. 调试<br> ■ 14世纪以来，bug一词被用来描述“恐怖的东西”。第一只计算机虫子，是造成早期计算机没能正常工作的继电器中的真正的蛾子<br> ■ 比起抵赖、推诿、蹩脚的借口或者无动于衷，你更应该向难题发起进攻<br> ■ Fix the problem, not the blame. 修正问题，而不是指责<br> ■ bug是你的过错还是别人的过错，这不重要，重要的是它都变成了你的问题<br> ■ 调试步骤1：关闭自我保护，忘掉其他方面的压力，让自己放松。记住“Don't panic”（不要恐慌！即使dead line快要到来，即使的boss在脖子后喘气）。不要将脑细胞放在“那不可能”上，因为不仅可能，而且已经发生了。不要止于修正现象，更应该寻根朔源修复根本<br> ■ 调试步骤2：开启最高级别警告并处理掉。搜集bug相关的所有数据，注意报告的准确性会因第三方介入而降低<br> ■ 调试步骤3：重现bug。reproduction<br> ■ 调试步骤4：让数据可视化。可以通过GUI debuger或者print等<br> ■ 调试步骤5：跟踪。步骤4在内存空间上做到了诊断，而跟踪(日志等)可以在时间上提供咨询<br> ■ 调试步骤6：橡皮鸭，把你的问题描述给其他人听，哪怕对方不说话只是点头，你仍然可能在你描述假定的过程中对问题有新的洞见。<br> ■ 调试步骤7：bug的确有可能发生在OS、编译器、第三方库甚至硬件中，但它几乎总是在你的代码中。"Select isn't broken"。看见马蹄印要想到马而不是斑马。注意可以用二分查找来定位bug<br> ■ 调试步骤8：bug之所以会带来惊讶，因为你对代码有信心，可能因为历史等（比如用了几年都没问题）——“Don't assume it, prove it”，不要假设它的正确性，去证明它！用单元测试！如果发现bug，汲取经验，让下次发现bug更容易、确认是否有类似的bug；对于bug高发点，重写它<br>■ 26. 程序员修炼之道：19. 文本操纵<br> ■ Learn a text manipulation language，学习一门文本操纵语言，比如sed、awk、perl、tcl、python等。用它们来建立原型、构建quick and dirty的实用程序的时候，他们的效率比传统语言高5~10倍<br>■ 27. 程序员修炼之道：20. 代码生成器<br> ■ 木匠会通过制作模具来重复制作某种东西，程序也可以制作代码生成器<br> ■ 被动代码生成器：目的就是一次性的生成框架代码。生成器一经调用，生成代码，代码不再依赖生成器，可以独立的编辑、维护。比如IDE的模板代码、GUI布局器生成的代码、查表优化中的表格生成（比如早期用查表计算sin的方法）、源代码翻译等。<br> ■ 主动代码生成器：目的是根据一个数据源，生成多份代码，保持了DRY性，总是检测改动并同步。例如yacc、protobuf。<br> ■ 可以生成的不只是代码，还可以是html、xml、json、二进制数据等各种数据表示<br>■ 29. 程序员修炼之道：第4章：注重实效的偏执<br> ■ You can't wirte perfect software. 注重实效的程序员应该怎样把它转化为有力条件<br> ■ 开车的时候每个人都把其他人想象成糟糕的司机，他们会乱冲停车标记、在车道间摆来摆去，因此自己防卫性的开车。编程也是类似的，在和别人的代码接合的时候，对方的代码标准可能也低于我们的要求，因此我们防卫性编程，验证信息、用断言检测数据，检查一致性、给数据库列加约束。<br> ■ 注重实效的程序员会进一步，“他们连自己也不信”，会针对自己可能的错误进行防卫性编码。<br> ■ 当每个人都可能对你不利时，偏执就是一个好主意。<br><br></div>