标签: compiler-optimization

我注意到我的电脑上有一个奇怪的东西。^*手写的可分性测试明显比%算子快。考虑最小的例子：

^{* _{AMD 锐龙 Threadripper 2990WX，GCC 9.2.0}}

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

该示例受奇数a和 的限制m > 0。然而，它可以很容易地推广到所有a和m。代码只是将除法转换为一系列加法。

现在考虑使用以下命令编译的测试程序-std=c99 -march=native -O3：

    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m …

刚刚在gdb中检查以下内容:

char *a[] = {"one","two","three","four"};
char *b[] = {"one","two","three","four"};
char *c[] = {"two","three","four","five"};
char *d[] = {"one","three","four","six"};

我得到以下内容:

(gdb) p a
$17 = {0x80961a4 "one", 0x80961a8 "two", 0x80961ac "three", 0x80961b2 "four"}
(gdb) p b
$18 = {0x80961a4 "one", 0x80961a8 "two", 0x80961ac "three", 0x80961b2 "four"}
(gdb) p c
$19 = {0x80961a8 "two", 0x80961ac "three", 0x80961b2 "four", 0x80961b7 "five"}
(gdb) p d
$20 = {0x80961a4 "one", 0x80961ac "three", 0x80961b2 "four", 0x80961bc "six"}

我真的很惊讶字符串指针对于相同的单词是相同的.我原以为每个字符串都会在堆栈上分配自己的内存,无论它是否与另一个数组中的字符串相同.

这是某种编译器优化的示例,还是这种字符串声明的标准行为？

添加在数学上保持关联属性:

(a + b) + c = a + (b + c)

在一般情况下,此属性不适用于浮点数,因为它们表示有限精度的值.

作为优化的一部分,是否允许编译器在从C程序生成机器代码时进行上述替换？它在C标准中的确切位置在哪里？

我最近通过Herb Sutter获得了"Exceptional C++",我对他在第6项 - 临时对象中提出的特别建议表示严重怀疑.

他提供了在以下代码中查找不必要的临时对象:

string FindAddr(list<Employee> emps, string name) 
{
  for (list<Employee>::iterator i = emps.begin(); i != emps.end(); i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

作为示例之一,他建议预先计算emps.end()循环之前的值,因为每次迭代都会创建一个临时对象:

对于大多数容器(包括列表),调用end()返回一个必须构造和销毁的临时对象.因为值不会改变,所以在每次循环迭代中重新计算(并重建和重新描述)它都是不必要的低效和不美观的.该值应仅计算一次,存储在本地对象中,然后重复使用.

他建议用以下内容代替:

list<Employee>::const_iterator end(emps.end());
for (list<Employee>::const_iterator i = emps.begin(); i != end; ++i)

对我来说,这是不必要的并发症.即使用compact替换丑陋的类型声明auto,他仍然会获得两行代码而不是一行代码.更重要的是,他end在外部范围内有这个变量.

我确信现代编译器无论如何都会优化这段代码,因为我实际上const_iterator在这里使用并且很容易检查循环内容是否以某种方式访问​​容器.编译器在过去的13年里变得更聪明,对吧？

无论如何,i != emps.end()在大多数情况下,我更喜欢第一个版本,我不太担心性能.但我想知道,这是否是一种我可以依靠编译器进行优化的结构？

更新

感谢您就如何更好地制作这些无用的代码提出建议.请注意,我的问题是关于编译器,而不是编程技术.现在唯一相关的答案来自NPE和Ellioh.

Constexpr对编译优化非常有用.例如...

strlen(char*)

可以使用....预编译

constexpr inline size_t strlen_constexpr(char* baseChar) {
    return (
            ( baseChar[0] == 0 )
            ?(// if {
              0
              )// }
            :(// else {
              strlen_constexpr( baseChar+1 ) + 1 
              )// }
            );
}

这在优化时给它的运行时成本为"0"但是在运行时速度超过10 + x

// Test results ran on a 2010 macbook air
--------- strlen ---------
Time took for 100,000 runs:1054us.
Avg Time took for 1 run: 0.01054us.
--------- strlen_constexpr ---------
Time took for 100,000 runs:19098us.
Avg Time took for 1 run: 0.19098us.

是否有任何现有的宏/模板黑客可以使用单个统一功能.即.

constexpr …

(出于测试目的)我编写了一个简单的方法来计算nxn矩阵的转置

void transpose(const size_t _n, double* _A) {
    for(uint i=0; i < _n; ++i) {
        for(uint j=i+1; j < _n; ++j) {
            double tmp  = _A[i*_n+j];
            _A[i*_n+j] = _A[j*_n+i];
            _A[j*_n+i] = tmp;
        }
    }
}

当使用优化级别O3或Ofast时,我期望编译器展开一些循环,这将导致更高的性能,尤其是当矩阵大小是2的倍数(即,每次迭代可以执行双循环体)或类似时.相反,我测量的恰恰相反.2的权力实际上表明执行时间显着增加.

这些尖峰也是64的固定间隔,间隔128更明显,依此类推.每个尖峰延伸到相邻的矩阵大小,如下表所示

size n  time(us)
1020    2649
1021    2815
1022    3100
1023    5428
1024    15791
1025    6778
1026    3106
1027    2847
1028    2660
1029    3038
1030    2613

我使用gcc版本4.8.2编译但是同样的事情发生在clang 3.5上,所以这可能是一些通用的东西？

所以我的问题基本上是:为什么执行时间周期性增加？是否有一些通用的东西与任何优化选项一起出现(就像clang和gcc一样)？如果是这样的优化选项导致了这个？

这怎么可能如此重要,即使O0版本的程序在512的倍数时优于03版本？

编辑:注意此(对数)图中峰值的大小.转换具有优化的1024x1024矩阵实际上花费的时间与在没有优化的情况下转置1300x1300矩阵一样多.如果这是一个缓存故障/页面错误问题,那么有人需要向我解释为什么内存布局对于程序的优化版本是如此显着不同,它失败的功能为2,只是为了恢复高性能稍大的矩阵.缓存故障是否应该创建更多类似步骤的模式？为什么执行时间会再次下降？(为什么优化会创建以前不存在的缓存错误？)

编辑:以下应该是gcc生成的汇编代码

没有优化(O0):

_Z9transposemRPd:
.LFB0:
    .cfi_startproc
    push    rbp …

问题:

我试图找出如何编写代码(C preffered,ASM仅在没有其他解决方案的情况下),这将使分支预测在50%的情况下失败.

所以它必须是一段代码"对于与分支相关的编译器优化"是"imune",而且所有HW分支预测都不应该超过50%(抛硬币).即使是更大的挑战,也能够在多个CPU架构上运行代码并获得相同的50%未命中率.

我设法编写了一个在x86平台上达到47%分支未命中率的代码.我怀疑失踪可能有3%来自:

• 程序启动开销已经分支(尽管很小)
• Profiler开销 - 基本上对于每个计数器读取都会引发中断,因此可能会添加其他可预测的分支.
• 在后台运行的系统调用包含循环和可预测的分支

我编写了自己的随机数生成器,以避免调用rand,它的实现可能隐藏了可预测的分支.当可用时它也可以使用rdrand.延迟对我来说无关紧要.

问题:

1. 我能比我的代码版做得更好吗？更好的意思是为所有CPU架构获得更高的分支错误预测和相同的结果.
2. 这段代码可以预测吗？那是什么意思？

代码:

#include <stdio.h>
#include <time.h>

#define RDRAND
#define LCG_A   1103515245
#define LCG_C   22345
#define LCG_M   2147483648
#define ULL64   unsigned long long

ULL64 generated;

ULL64 rand_lcg(ULL64 seed)
{
#ifdef RDRAND
    ULL64 result = 0;
    asm volatile ("rdrand %0;" : "=r" (result));
    return result;
#else
    return (LCG_A * seed + LCG_C) % LCG_M;
#endif
}

ULL64 rand_rec1()
{ …

编译器在优化RELEASE构建方面做得很好,但有时候确保为本地函数关闭优化(但不是通过unticking来关闭整个项目Project Options > Optimize code)会很有用.

在C++中,这是使用以下内容实现的(#pragma通常注释掉):

#pragma optimize( "", off )
// Some code such as a function (but not the whole project)
#pragma optimize( "", on )

C#中有等价物吗？

UPDATE

几个很好的答案建议用这个方法装饰MethodImplOptions.NoOptimization.这是在.NET 3.5中实现的,但不是在Compact Framework(CF)版本中.一个相关的后续问题是,是否相当于:

* projects targeting .NET 3.0 or earlier?
* projects deployed to a device such as Windows CE 6.0 using the .NET 3.5 CF?

我有一个宏在我的代码中使用,在调试模式下:

#define contract(condition) \
    if (!(condition)) \
        throw exception("a contract has been violated");

...但在发布模式下:

#define contract(condition) \
    if (!(condition)) \
        __builtin_unreachable();

这样做的原因assert()是,在发布版本中,由于UB传播,编译器可以大量优化代码.

例如,使用以下代码进行测试:

int foo(int i) {
    contract(i == 1);
    return i;
}

// ...

foo(0);

...在调试模式下抛出异常,但return 1;在释放模式下为无条件生成程序集:

foo(int):
        mov     eax, 1
        ret

条件以及依赖它的一切都已经过优化.

我的问题出现在更复杂的条件下.当编译器无法证明条件没有副作用时,它不会将其优化出来,与不使用合同相比,这是一个严重的惩罚.

有没有办法表明合同中的条件没有副作用,所以总是优化出来？

我有四个身份函数，它们基本上什么都不做。只有乘法1才能通过 clang 优化为单个ret语句。

float id0(float x) {
    return x + 1 - 1;
}

float id1(float x) {
    return x + 0;
}

float id2(float x) {
    return x * 2 / 2;
}

float id3(float x) {
    return x * 1;
}

以下编译器输出是：(clang 10, at -O3)

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   3212836864              # float -1
id0(float):                                # @id0(float)
        addss   xmm0, dword ptr [rip + .LCPI0_0]
        addss   xmm0, dword ptr [rip + .LCPI0_1] …