logo标签列表

GCC优化对位运算的有效性

coptimizationassemblyx86
14

以下是在x86-64上用C语言设置单个比特的两种方式：

inline void SetBitC(long *array, int bit) {
   //Pure C version
   *array |= 1<<bit;
}

inline void SetBitASM(long *array, int bit) {
   // Using inline x86 assembly
   asm("bts %1,%0" : "+r" (*array) : "g" (bit));
}

使用GCC 4.3版本和-O3 -march=core2选项，C语言版本在使用常量bit时需要花费90%更多的时间。（两个版本编译成完全相同的汇编代码，除了C语言版本使用or [1<<num],%rax指令而不是bts [num],%rax指令）

当使用变量bit时，C语言版本性能表现更好，但仍然比内联汇编慢得多。

重置、切换和检查位具有类似的结果。

为什么GCC对于这样一个常见的操作优化得如此差？我在C语言版本中做错了些什么吗？

编辑：抱歉等待这么久，这里是我用于基准测试的代码。实际上它起初是一个简单的编程问题...

int main() {
    // Get the sum of all integers from 1 to 2^28 with bit 11 always set
    unsigned long i,j,c=0;
    for (i=1; i<(1<<28); i++) {
        j = i;
        SetBit(&j, 10);
        c += j;
    }
    printf("Result: %lu\n", c);
    return 0;
}

gcc -O3 -march=core2 -pg test.c
./a.out
gprof
with ASM: 101.12      0.08     0.08                             main
with C:   101.12      0.16     0.16                             main

time ./a.out 也会给出类似的结果。

1
这真的是一个“常见操作”吗？我最常见到位操作使用的场景是在人们进行过早优化时，他们认为通过将一堆标志位打包到单个字节中可以节省内存。 - Anon.
3
嗯...说得好。不过，这是一个相当简单的操作，在硬件驱动程序中很常见。无论如何，重点是性能下降了90%。 - Dumb Guy
1
在驱动程序编程中，“左移1位以确定掩码”的惯用法并不常用。相反，您会使用预定义的标志进行“或”运算。 - Anon.
你说得对。当位数是常量时，编译器确实会优化掉移位操作。但仍然很奇怪它的速度慢了90%。 - Dumb Guy
1
我对“慢90%”这件事感到惊讶。编译器可能期望or所需的时钟比通常更少的bts少。 - Anon.
显示剩余2条评论
5个回答
13

为什么GCC对于如此常见的操作优化效果如此之差？

前言：自20世纪80年代末以来，编译器优化的重点已经从关注单个操作的微基准测试转向了关注人们关心速度的应用的宏基准测试。现在，大多数编译器编写者都专注于宏基准测试，并且开发良好的基准套件是被认真对待的事情。

答案：GCC中没有使用过这样一种基准测试，即or和bts之间的差异对于实际程序的执行时间有影响。如果您能够制作这样的程序，您可能会引起GCC领域内的人们的注意。

我在C语言版本中做错了什么吗？

不，这是完全符合标准的C语言。实际上，非常易读和惯用。

2

针对下面的代码：

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

int main() {
  volatile long long i = 0;
  time_t start = time (NULL);
  for (long long n = 0; n < (1LL << 32); n++) {
    i |= 1 << 10;
  }
  time_t end = time (NULL);
  printf("C took %ds\n", (int)(end - start));
  start = time (NULL);
  for (long long n = 0; n < (1LL << 32); n++) {
    __asm__ ("bts %[bit], %[i]"
                  : [i] "=r"(i)
                  : "[i]"(i), [bit] "i" (10));
  }
  end = time (NULL);
  printf("ASM took %ds\n", (int)(end - start));
}

结果是：

C took 12s
ASM took 10s

我的标志是 (-std=gnu99 -O2 -march=core2)。如果没有使用volatile，则循环会被优化掉。gcc 4.4.2。

在以下情况下也没有任何区别：

__asm__ ("bts %[bit], %[i]"
              : [i] "+m"(i)
              : [bit] "r" (10));

可能答案是 - 没有人在意。在微基准测试中，两种方法之间的唯一区别是实际代码中这样的代码不会占用太多CPU资源。

此外，针对这样的代码：

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

int main() {
  volatile long long i = 0;
  time_t start = time (NULL);
  for (long long n = 0; n < (1L << 32); n++) {
    i |= 1 << (n % 32);
  }
  time_t end = time (NULL);
  printf("C took %ds\n", (int)(end - start));
  start = time (NULL);
  for (long long n = 0; n < (1L << 32); n++) {
    __asm__ ("bts %[bit], %[i]"
                  : [i] "+m"(i)
                  : [bit] "r" (n % 32));
  }
  end = time (NULL);
  printf("ASM took %ds\n", (int)(end - start));
}

结果如下：
C took 9s
ASM took 10s

两个结果都是“稳定的”。测试CPU为“Intel（R）Core（TM）2 Duo CPU T9600 @ 2.80GHz”。

long long suffix is LL, not L - phuclv
1
@LưuVĩnhPhúc 说得好。已经修复了，但这不应该影响结果，因为Linux是LP64平台（它可能会影响Windows或其他LLP平台）。 - Maciej Piechotka
看看你的第二个测试，这似乎不是一个“公平”的比较。你强制i存储在内存中，而不是寄存器中，而C代码可能不会这样做。那么使用 __asm__ ("bts %[bit], %[i]" : [i] "+r"(i) : [bit] "r" (n % 32));怎么样？ - David Wohlferd
“我认为在大多数实际应用中，这不是一个会有很大差别的操作” - 我同意。我甚至不确定是什么让我看到了这个问题，但内联汇编的东西往往会引起我的注意，而“m”看起来不太对劲。值得一提的是，在使用“r”的计算机上速度稍快的是I7（820QM）。我不确定还有什么可以在这里学习的，而且OP早已离开。 - David Wohlferd
@DavidWohlferd 我猜 - 基准测试很有趣但也很难。 - Maciej Piechotka
显示剩余4条评论
2

你能发一下用于计时的代码吗？这种操作往往很难准确计时。

理论上来说，这两个代码序列应该是同样快的，所以我认为最可能的解释是某些因素导致你的计时代码给出了错误的结果。

是的。在我所知道的所有x86 CPU上，像OR这样的基本ALU操作至少与BTS这样的“奇特”操作一样快。一个可能性是，你计时循环中的增量+测试使用了与OR相同的CPU执行单元，导致争用，而BTS则使用不同的单元。 - j_random_hacker
在最近的x86硬件上，“or”可以分配到多个执行单元，因此不应该有任何争用。 - Stephen Canon
1
这是嵌入式系统上非常常见的操作，通常资源受限。在这样的系统中，10个周期与5个周期的差别是一个可怕的性能惩罚。有很多情况下，人们希望访问IO端口或使用16或32位寄存器作为布尔位标志来节省内存。
事实上，if(bit_flags& 1<<12)比汇编等效语更易读[并且使用库时更具可移植性]。同样，对于IO_PINS|= 1<<5;，它们不幸地慢得多，因此笨拙的asm宏继续存在。
在许多方面，嵌入式和用户空间应用程序的目标是相反的。对外部通信的响应（对用户界面或机器接口）的重要性较小，而确保控制环路（相当于微基准）以最短的时间完成则绝对至关重要，可以决定选择的处理器或控制策略成败。
显然，如果一个人负担得起多GHz的CPU以及支持它所需的所有相关外设、芯片组等，则根本不需要担心低级优化。在实时控制系统中，速度慢1000倍的微控制器意味着节省时钟周期的重要性增加了1000倍。
0

我认为你对优化器的要求有点过高。

你可以通过执行“register long z = 1L << bit;"，然后将其与数组进行或操作，来稍微帮助一下它。

不过，我猜你所说的90%更多时间是指C版本需要10个周期，而汇编版本只需要5个周期，对吗？在-O2或-O1下性能如何比较？

1
“register”将被编译器忽略。 - Laurynas Biveinis
@Laurynas Biveinis：「register」可能会被编译器忽略，毕竟它只是一个提示。 - Hasturkun
这个想法是通过执行 long |= register long 可能会鼓励编译器进行优化 :) - Seth
1
@Hasturkun：大多数（GCC，MSVC等）现有编译器肯定会忽略它。 - Laurynas Biveinis
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接