首页 文章

编码实践,使编译器/优化器能够制作更快的程序

提问于
浏览
114

许多年前,C编译器并不是特别聪明 . 作为一种解决方法,K&R发明了 register 关键字,提示编译器,将这个变量保存在内部寄存器中可能是个好主意 . 他们还使第三级运营商帮助生成更好的代码 .

随着时间的推移,编译器逐渐成熟 . 他们变得非常聪明,他们的流量分析使他们能够更好地决定寄存器中的值,而不是你可能做的 . register关键字变得不重要了 .

由于alias问题,FORTRAN对某些操作的速度可能比C快 . 从理论上讲,仔细编码可以解决这个限制,使优化器能够生成更快的代码 .

What coding practices are available that may enable the compiler/optimizer to generate faster code?

  • 识别您使用的平台和编译器,将不胜感激 .

  • 为什么这项技术似乎有效?

  • 鼓励使用示例代码 .

这是related question

[Edit] 此问题与分析和优化的整个过程无关 . 假设程序编写正确,编译完全优化,测试并投入 生产环境 . 您的代码中可能有一些构造禁止优化器尽其所能地完成最佳工作 . 您可以做什么来重构将删除这些禁令,并允许优化器生成更快的代码?

[Edit] Offset related link

30 回答

  • 9

    写入局部变量而不是输出参数!这对于消除混叠减速可能是一个巨大的帮助 . 例如,如果您的代码看起来像

    void DoSomething(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
    {
        for (int i=0; i<numFoo, i++)
        {
             barOut.munge(foo1, foo2[i]);
        }
    }
    

    编译器不知道foo1!= barOut,因此每次循环时都必须重新加载foo1 . 在写入barOut完成之前,它也无法读取foo2 [i] . 你可以开始搞乱限制指针,但这样做有效(并且更清晰):

    void DoSomethingFaster(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
    {
        Foo barTemp = barOut;
        for (int i=0; i<numFoo, i++)
        {
             barTemp.munge(foo1, foo2[i]);
        }
        barOut = barTemp;
    }
    

    这听起来很愚蠢,但编译器可以更聪明地处理局部变量,因为它不可能在内存中与任何参数重叠 . 这可以帮助您避免可怕的load-hit-store(Francis Boivin在此主题中提到) .

  • 4

    这是一个编码实践,帮助编译器创建快速代码 - 任何语言,任何平台,任何编译器,任何问题:

    不要使用任何强制或甚至鼓励编译器将变量放在内存中(包括缓存和寄存器)的巧妙技巧 . 首先编写一个正确且可维护的程序 .

    接下来,分析您的代码 .

    然后,只有这样,您可能想要开始研究告诉编译器如何使用内存的效果 . 一次进行1次更改并测量其影响 .

    期望失望并且必须非常努力地进行小的性能改进 . 成熟语言(如Fortran和C)的现代编译器非常非常好 . 如果您阅读了一个“技巧”的帐户以获得更好的代码性能,请记住编译器编写者也已阅读过它,如果值得这样做,可能会实现它 . 他们可能首先写了你读的内容 .

  • 71

    您遍历内存的顺序会对性能产生深远的影响,而编译器并不擅长确定并修复它 . 如果您关心性能,则在编写代码时必须充分考虑缓存局部性问题 . 例如,C中的二维数组以行主格式分配 . 以列主格式遍历数组将使您有更多的缓存未命中并使您的程序比处理器绑定更多的内存限制:

    #define N 1000000;
    int matrix[N][N] = { ... };
    
    //awesomely fast
    long sum = 0;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        sum += matrix[i][j];
      }
    }
    
    //painfully slow
    long sum = 0;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        sum += matrix[j][i];
      }
    }
    
  • 11

    通用优化

    这里有一些我最喜欢的优化 . 通过使用这些,我实际上增加了执行时间并减少了程序大小 .

    将小函数声明为内联或宏

    每次调用函数(或方法)都会产生开销,例如将变量推送到堆栈上 . 某些功能也可能导致返回开销 . 低效的函数或方法在其内容中的语句少于组合的开销 . 这些是内联的良好候选者,无论是 #define 宏还是 inline 函数 . (是的,我知道 inline 只是一个建议,但在这种情况下,我认为它是对编译器的提醒 . )

    删除死机和冗余代码

    如果代码未使用或对程序的结果没有贡献,请将其删除 .

    简化算法设计

    我曾经删除了很多程序中的汇编代码和执行时间通过写下它正在计算的代数方程,然后简化代数表达式 . 简化代数表达式的实现比原始函数占用更少的空间和时间 .

    循环展开

    每个循环都有递增和终止检查的开销 . 要获得性能因子的估计,请计算开销中的指令数(最小3:增量,检查,循环开始)并除以循环内的语句数 . 数字越低越好 .

    Edit: 提供了一个循环展开示例之前:

    unsigned int sum = 0;
    for (size_t i; i < BYTES_TO_CHECKSUM; ++i)
    {
        sum += *buffer++;
    }
    

    展开后:

    unsigned int sum = 0;
    size_t i = 0;
    **const size_t STATEMENTS_PER_LOOP = 8;**
    for (i = 0; i < BYTES_TO_CHECKSUM; **i = i / STATEMENTS_PER_LOOP**)
    {
        sum += *buffer++; // 1
        sum += *buffer++; // 2
        sum += *buffer++; // 3
        sum += *buffer++; // 4
        sum += *buffer++; // 5
        sum += *buffer++; // 6
        sum += *buffer++; // 7
        sum += *buffer++; // 8
    }
    // Handle the remainder:
    for (; i < BYTES_TO_CHECKSUM; ++i)
    {
        sum += *buffer++;
    }
    

    在此优点中,获得了第二个好处:在处理器必须重新加载指令高速缓存之前执行更多语句 .

    当我将一个循环展开到32个语句时,我得到了惊人的结果 . 这是程序必须计算2GB文件的校验和以来的瓶颈之一 . 这种优化与块读取相结合,可将性能提高1小时至5分钟 . 循环展开在汇编语言中也提供了出色的性能,我的 memcpy 比编译器的 memcpy 快得多 . - TM值 .

    减少if语句

    处理器讨厌分支或跳转,因为它迫使处理器重新加载其指令队列 .

    布尔算术(编辑:应用代码格式代码片段,添加示例)

    if 语句转换为布尔赋值 . 某些处理器可以有条件地执行指令而无需分支:

    bool status = true;
    status = status && /* first test */;
    status = status && /* second test */;
    

    如果 statusfalseLogical AND 运算符( && )的短路将阻止执行测试 .

    例:

    struct Reader_Interface
    {
      virtual bool  write(unsigned int value) = 0;
    };
    
    struct Rectangle
    {
      unsigned int origin_x;
      unsigned int origin_y;
      unsigned int height;
      unsigned int width;
    
      bool  write(Reader_Interface * p_reader)
      {
        bool status = false;
        if (p_reader)
        {
           status = p_reader->write(origin_x);
           status = status && p_reader->write(origin_y);
           status = status && p_reader->write(height);
           status = status && p_reader->write(width);
        }
        return status;
    };
    

    循环外的因子变量分配

    如果在循环内动态创建变量,则将创建/分配移动到循环之前 . 在大多数情况下,不需要在每次迭代期间分配变量 .

    在循环之外的因子常量表达式

    如果计算或变量值不依赖于循环索引,则将其移动到循环之外(之前) .

    块中的I / O.

    以大块(块)读写数据 . 越大越好 . 例如,一次读取一个八位字节比一次读取读取1024个八位字节效率低 .
    例:

    static const char  Menu_Text[] = "\n"
        "1) Print\n"
        "2) Insert new customer\n"
        "3) Destroy\n"
        "4) Launch Nasal Demons\n"
        "Enter selection:  ";
    static const size_t Menu_Text_Length = sizeof(Menu_Text) - sizeof('\0');
    //...
    std::cout.write(Menu_Text, Menu_Text_Length);
    

    可以在视觉上证明该技术的效率 . :-)

    不要将printf系列用于常量数据

    可以使用块写入输出常量数据 . 格式化写入将浪费时间扫描文本以格式化字符或处理格式化命令 . 见上面的代码示例 .

    格式化为内存,然后写入

    使用多个 sprintf 格式化为 char 数组,然后使用 fwrite . 这也允许将数据布局分解为"constant sections"和可变部分 . 想想邮件合并 .

    将常量文本(字符串文字)声明为静态const

    在没有 static 的情况下声明变量时,某些编译器可能会在堆栈上分配空间并从ROM复制数据 . 这是两个不必要的操作 . 这可以通过使用 static 前缀来修复 .

    最后,代码就像编译器一样

    有时,编译器可以比一个复杂版本更好地优化几个小语句 . 此外,编写代码以帮助编译器优化也有帮助 . 如果我希望编译器使用特殊的块传输指令,我将编写看起来应该使用特殊指令的代码 .

  • 26

    优化器并不能真正控制程序的性能 . 使用适当的算法和结构以及配置文件,配置文件,配置

    也就是说,你不应该从另一个文件中的一个文件内部循环一个小函数,因为这样就不会内联它 .

    如果可能,避免使用变量的地址 . 要求指针不是“自由”,因为它意味着变量需要保存在内存中 . 如果你避免使用指针,即使数组也可以保存在寄存器中 - 这对于矢量化很重要 .

    这导致下一点,阅读^#$ @手册!如果你在这里撒一个 __restrict__ 和那里有一个 __attribute__( __aligned__ ) ,GCC可以矢量化普通的C代码 . 如果您想要优化器中非常具体的东西,您可能必须具体 .

  • 1

    在大多数现代处理器上,最大的瓶颈是内存 .

    别名:Load-Hit-Store在紧密循环中可能是毁灭性的 . 如果您正在读取一个内存位置并写入另一个内存位置并知道它们是不相交的,小心地在函数参数上放置一个alias关键字可以真正帮助编译器生成更快的代码 . 但是,如果内存区域重叠并且您使用了'alias',那么您可以进行未定义行为的良好调试会话!

    缓存未命中:不确定如何帮助编译器,因为它主要是算法,但有预取内存的内在函数 .

    也不要尝试将浮点值转换为int,反之亦然,因为它们使用不同的寄存器并从一种类型转换为另一种类型意味着调用实际的转换指令,将值写入存储器并在适当的寄存器集中读回 .

  • 18

    人们编写的绝大多数代码都是I / O限制的(我相信我在过去30年里为所有代码编写的代码都受到了限制),因此对于大多数人来说,优化器的活动将是学术性的 .

    但是,我要提醒人们,为了优化代码,你必须告诉编译器优化它 - 很多人(包括我在忘记的时候)在这里发布C基准,如果没有启用优化器就毫无意义 .

  • 11

    在代码中尽可能使用const正确性 . 它允许编译器更好地优化 .

    在本文档中有大量其他优化技巧:CPP optimizations(虽然有点旧文档)

    强调:

    • 使用构造函数初始化列表

    • 使用前缀运算符

    • 使用显式构造函数

    • 内联函数

    • 避免临时对象

    • 了解虚拟功能的成本

    • 通过参考参数返回对象

    • 考虑每班分配

    • 考虑stl容器分配器

    • 'empty member'优化

  • 4

    尝试尽可能使用静态单一分配进行编程 . SSA与大多数函数式编程语言中的结果完全相同,并且's what most compilers convert your code to to do their optimizations because it'更易于使用 . 通过这样做,编译器可能会混淆的地方被揭露出来 . 它还使除了最差的寄存器分配器之外的所有寄存器分配器都能像最好的寄存器分配器一样工作,并且允许您更容易地进行调试,因为您几乎不必怀疑变量从何处获得它的值,因为它只分配了一个位置 .
    避免全局变量 .

    通过引用或指针处理数据到局部变量时,执行您的工作,然后将其复制回来 . (除非你有充分的理由不这样做)

    利用大多数处理器在进行数学运算或逻辑运算时给出的几乎免费的0比较 . 你几乎总是得到一个== 0和<0的标志,你可以从中轻松获得3个条件:

    x= f();
    if(!x){
       a();
    } else if (x<0){
       b();
    } else {
       c();
    }
    

    几乎总是比测试其他常数便宜 .

    另一个技巧是使用减法来消除范围测试中的一个比较 .

    #define FOO_MIN 8
    #define FOO_MAX 199
    int good_foo(int foo) {
        unsigned int bar = foo-FOO_MIN;
        int rc = ((FOO_MAX-FOO_MIN) < bar) ? 1 : 0;
        return rc;
    }
    

    这通常可以避免在布尔表达式上短路的语言跳转,并避免编译器必须试图在执行第二次比较然后组合它们时如何处理第一次比较的结果 . 这可能看起来有可能耗尽额外的寄存器,但它几乎从未这样做 . 通常你不再需要foo了,如果你做了rc还没有使用它所以它可以去那里 .

    在c中使用字符串函数时(strcpy,memcpy,...)记住它们返回的内容 - 目的地!您可以通过“忘记”指向目标的指针副本来获得更好的代码,并从这些函数的返回中获取它 .

    永远不要忽视机会返回与你调用的最后一个函数完全相同的东西 . 编制者并不那么认真:

    foo_t * make_foo(int a, int b, int c) {
            foo_t * x = malloc(sizeof(foo));
            if (!x) {
                 // return NULL;
                 return x; // x is NULL, already in the register used for returns, so duh
            }
            x->a= a;
            x->b = b;
            x->c = c;
            return x;
    }
    

    当然,如果且只有一个返回点,你可以反转逻辑 .

    (后来我回忆起的技巧)

    在可能的情况下将函数声明为静态总是一个好主意 . 如果编译器可以向自己证明它已经占用了特定函数的每个调用者,那么它可以在优化名称中破坏该函数的调用约定 . 编译器通常可以避免将参数移动到寄存器或堆栈位置,这些位置调用函数通常期望它们的参数存在(它必须在被调用函数和所有调用者的位置都有偏差才能执行此操作) . 编译器通常也可以利用知道被调用函数需要的内存和寄存器,并避免生成代码以保留寄存器中的变量值或被调用函数不会打扰的内存位置 . 当对函数的调用很少时,这种方法特别有效 . 这得到了内联代码的大部分好处,但没有实际内联 .

  • 2

    我写了一个优化的C编译器,这里有一些非常有用的东西需要考虑:

    • 使大多数功能静止 . 这允许过程间常量传播和别名分析完成其工作,否则编译器需要假设可以从翻译单元外部调用该函数,其中参数的值完全未知 . 如果你看一下着名的开源库,他们都会将函数标记为静态,除了真正需要extern的函数 .

    • 如果使用全局变量,请尽可能将它们标记为静态和常量 . 如果它们被初始化一次(只读),最好使用初始化列表,如static const int VAL [] = {1,2,3,4},否则编译器可能不会发现变量实际上是初始化的常量和将无法使用常量替换变量中的负载 .

    • 永远不要在循环内部使用goto,大多数编译器都不会再识别循环,并且不会应用任何最重要的优化 .

    • 仅在必要时使用指针参数,并在可能的情况下将其标记为限制 . 这有助于别名分析,因为程序员保证没有别名(过程间别名分析通常非常原始) . 非常小的struct对象应该通过值传递,而不是通过引用传递 .

    • 尽可能使用数组而不是指针,尤其是在循环内(a [i]) . 数组通常为别名分析提供更多信息,并且在一些优化之后,无论如何都将生成相同的代码(如果好奇则搜索环路强度降低) . 这也增加了应用循环不变代码运动的机会 .

    • 尝试在循环调用之外提升大函数或没有副作用的外部函数(不依赖于当前循环迭代) . 在许多情况下,小函数被内联或转换为易于提升的内在函数,但是大型函数可能看起来编译器在它们实际上没有副作用时会产生副作用 . 外部函数的副作用是完全未知的,除了标准库中的某些函数(有时由某些编译器建模),使得循环不变代码运动成为可能 .

    • 在编写具有多个条件的测试时,最有可能将其放在首位 . if(a || b || c)应该是if(b || a || c),如果b比其他b更可能是真的 . 编译器通常不了解条件的可能值以及更多的分支(通过使用配置文件信息可以知道,但很少有程序员使用它) .

    • 使用开关比执行if(a || b || ... || z)等测试更快 . 首先检查你的编译器是否自动执行此操作,有些执行此操作,并且具有if但更具可读性 .

  • 47

    对于嵌入式系统和用C / C编写的代码,我尽量避免使用 dynamic memory allocation . 我这样做的主要原因不一定是性能,但这个经验法则确实有性能影响 .

    在某些平台(例如,vxworks)中,用于管理堆的算法非常慢 . 更糟糕的是,从调用返回到malloc所需的时间在很大程度上取决于堆的当前状态 . 因此,任何调用malloc的函数都会受到无法轻易解释的性能影响 . 如果堆仍然是干净的,那么性能损失可能是最小的,但是在该设备运行一段时间后,堆可能变得碎片化 . 这些电话需要更长的时间,你无法轻易计算出性能会随着时间的推移而降低的程度 . 你无法真正产生更糟糕的案例估计 . 在这种情况下,优化器也无法为您提供任何帮助 . 更糟糕的是,如果堆碎片过于分散,则调用将完全失败 . 解决方案是使用内存池(例如,glib slices)而不是堆 . 如果你做对了,分配调用会更加快速和确定 .

  • 2

    一个愚蠢的小技巧,但是会为你节省一些微观的速度和代码 .

    始终以相同的顺序传递函数参数 .

    如果你有f_1(x,y,z)调用f_2,则将f_2声明为f_2(x,y,z) . 不要将其声明为f_2(x,z,y) .

    原因是C / C平台ABI(AKA调用约定)承诺在特定寄存器和堆栈位置传递参数 . 当参数已经在正确的寄存器中时,它不必移动它们 .

    在阅读反汇编代码时,我看到一些荒谬的寄存器改组,因为人们没有遵循这条规则 .