论程序底层优化一些方法与技巧

论程序底层优化的一些方法与技巧 成都七中骆可强 T n O f n 效率 时间效率 空间效率 算法 T n f n C C1 C2 算法 底层优化 最初版程序intget max int a intl intmx 0 i for i 0 imx mx a i returnmx 第一次优化intget max int a intl intmx 0 ed a l while a ed if a mx mx a a returnmx 第二次优化intget max int a intl assert l 8 0 defineD x mx x 0intD 0 D 1 D 2 D 3 D 4 D 5 D 6 D 7 ed a l defineCMP x if a x mx x mx x a x while a ed CMP 0 CMP 1 CMP 2 CMP 3 CMP 4 CMP 5 CMP 6 CMP 7 a 8 defineCC x1 x2 if mx x1 mx x2 mx x2 mx x1 CC 1 0 CC 3 2 CC 5 4 CC 7 6 CC 2 0 CC 6 4 CC 4 0 returnmx0 第三次优化intget max int a intl intret asm volatile movl 0 eax n t p2align4 15 n LP1 n t cmpl 4 1 2 4 eax n t jgeED n t movl 4 1 2 4 eax n ED n t loopLP1 n t decl 2 n t jnzLP1 n t movl eax 0 n t m ret r a c l eax returnret 第四个优化intget max int a intl assert l 2 0 intret asm volatile movl 0 eax n t movl 0 edx n t p2align4 15 n LP2 n t cmpl 1 eax n t jgeED2 n t movl 1 eax n ED2 n t cmpl4 1 edx n t jgeED3 n t movl4 1 edx n ED3 n t addl 8 1 n t subl 2 2 n t jnzLP2 n t cmpl edx eax n t cmovll edx eax n t movl eax 0 n t m ret r a r l eax edx returnret 第五次优化intget max int a intl assert l 4 0 assert sse2 intret tmp 4 asm volatile txorps xmm0 xmm0 n LP3 n tmovdqa xmm0 xmm1 n tpcmpgtd 1 xmm1 n tandps xmm1 xmm0 n tandnps 1 xmm1 n torps xmm1 xmm0 n taddl 16 1 n tsubl 4 2 n tjnzLP3 n tmovdqu xmm0 3 n tmovl 3 eax n tcmpl4 3 eax n tcmovll4 3 eax n tcmpl8 3 eax n tcmovll8 3 eax n tcmpl12 3 eax n tcmovll12 3 eax n tmovl eax 0 n m ret r a r l r tmp eax returnret 第六次优化intget max int a intl assert l 4 0 assert sse4 intret tmp 4 asm volatile txorps xmm0 xmm0 n LP4 n tpmaxsd 1 xmm0 n taddl 16 1 n tsubl 4 2 n tjnzLP4 n tmovdqu xmm0 3 n tmovl 3 eax n tcmpl4 3 eax n tcmovll4 3 eax n tcmpl8 3 eax n tcmovll8 3 eax n tcmpl12 3 eax n tcmovll12 3 eax n tmovl eax 0 n m ret r a r l r tmp eax returnret 一个简单的例子 7 53 6 6012 3 4854 2 1372 1 7477 1 5980 优化寻址 多路求值 内嵌汇编 内嵌汇编 多路求值 SIMD SSE4 求最大值 论文中所覆盖的主题 CPU指令运行的效率表现 CPU优化特性 数值运算的优化 高维数组的使用 位运算技巧 除法 高精度 乘法 缓存机制 乱序执行 分支预测 位压缩 消除分支 打包统计 寻址 底层表现 浮点 除常数 高维数组访问的底层表现 inta 2048 2048 intmain inti x y for i 1 i 100 i for x 0 x 2048 x for y 0 y 2048 y a x y x y return0 inta 2048 2048 intmain inti x y for i 1 i 100 i for y 0 y 2048 y for x 0 x 2048 x a x y x y return0 inta 2049 2049 intmain inti x y for i 1 i 100 i for y 0 y 2049 y for x 0 x 2049 x a x y x y return0 Time1 1 760s Time2 18 757s Time3 4 644s 尽量按照数据在内存中放置顺序去访问它 避免高维数组的尺寸是2的方幂 编译器对除以常数的优化 movl 8 ebp ecxmovl 613566757 edxmovl ecx eaxmull edxsubl edx ecxshrl ecxaddl ecx edxshrl 2 edxmovl edx 8 ebp a 613566757 232 35 a 7 除以常数比除以变量更快 在某些场合 我们需要多次除以同一个变量 也可以事先计算出这些常数起到优化效果 a i i 2 a i rand 2 CPU的分支预测机制 x x a b a intabs intx returnx 0 x x intcmp inta if a return0 returna 0 1 1 intt 0 for inti 0 i N i if a i t 1 elset 2 intcmp inta return a 31 a 31 intabs intx inty x 31 return x y y x a b 测量结果1 3 2 107个时钟周期 测量结果2 1 02 108个时钟周期 ifa i else 消除条件分支 在信息学奥赛中的实践 题目 麦森数 mason 来源 NOIP2003算法 朴素的高精度计算测试情况 优化 消除除法与条件分支优化情况 100分 题目 瑰丽的华尔兹 adv1900 来源 NOI2005算法 朴素的动态规划 O N4 测试情况 优化 优化高维数组寻址优化情况