BITWISE AND操作如何在C程序中占用比ARITHMETIC ADDITION操作更多的CPU时钟？

Question

我想测试按位运算是否真的比算术运算更快.我以为他们是.

我写了一个小的C程序来测试这个假设,令我惊讶的是,加法平均比按位AND运算少.这对我来说是令人惊讶的,我无法理解为什么会这样.

根据我所知的附加,来自较低有效位的进位应该被携带到下一位,因为结果也取决于进位.对我来说逻辑运算符比加法更慢是没有意义的.

我的鳕鱼在下面:

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

int main() 
{
   int x=10;
   int y=25;
   int z=x+y;
   printf("Sum of x+y = %i", z);
   time_t start = clock();
   for(int i=0;i<100000;i++)z=x+y;
   time_t stop = clock();

   printf("\n\nArithmetic instructions take: %d",stop-start);
   start = clock();
   for(int i=0;i<100000;i++)z=x&y;
   stop = clock();

   printf("\n\nLogic instructions take: %d",stop-start);
}

一些结果:

Arithmetic instructions take: 327
Logic instructions take: 360

Arithmetic instructions take: 271
Logic instructions take: 271

Arithmetic instructions take: 287
Logic instructions take: 294

Arithmetic instructions take: 279
Logic instructions take: 266

Arithmetic instructions take: 265
Logic instructions take: 296

这些结果来自该计划的连续运行.

正如您可以看到的那样,逻辑运算符平均需要比算术运算符更长的时间.

Answer 1

好吧,让我们把它"测量"并将它炸掉,100k就是一点点

#include<stdio.h>
#include<time.h>
#define limit 10000000000

int main() 
{
   int x=10, y=25, z;

   time_t start = clock();
   for(long long i=0;i<limit;i++)z=x+y;
   time_t stop = clock();
   printf("Arithmetic instructions take: %ld\n",stop-start);

   start = clock();
   for(long long i=0;i<limit;i++)z=x&y;
   stop = clock();
   printf("Logic instructions take: %ld\n",stop-start);
}

这会运行一段时间.首先让我们尝试没有优化:

thomas@TS-VB:~/src$ g++ -o trash trash.c 
thomas@TS-VB:~/src$ ./trash 
Arithmetic instructions take: 21910636
Logic instructions take: 21890332

你看,两个循环大约需要同一时间.

用-S编译揭示了为什么(这里只显示.s文件的相关部分):

// this is the assembly for the first loop
.L3:
    movl    32(%esp), %eax
    movl    28(%esp), %edx
    addl    %edx, %eax             // <<-- ADD
    movl    %eax, 40(%esp)
    addl    $1, 48(%esp)
    adcl    $0, 52(%esp)
.L2:
    cmpl    $2, 52(%esp)
    jl  .L3
    cmpl    $2, 52(%esp)
    jg  .L9
    cmpl    $1410065407, 48(%esp)
    jbe .L3

// this is the one for the second
.L9:
    movl    32(%esp), %eax
    movl    28(%esp), %edx
    andl    %edx, %eax             // <<--- AND
    movl    %eax, 40(%esp)
    addl    $1, 56(%esp)
    adcl    $0, 60(%esp)
.L5:
    cmpl    $2, 60(%esp)
    jl  .L6
    cmpl    $2, 60(%esp)
    jg  .L10
    cmpl    $1410065407, 56(%esp)
    jbe .L6
.L10:

查看CPU指令集告诉我们,ADD和AND都将采用相同的循环次数 - > 2个循环将运行相同的时间量

现在进行优化:

thomas@TS-VB:~/src$ g++ -O3 -o trash trash.c 
thomas@TS-VB:~/src$ ./trash 
Arithmetic instructions take: 112
Logic instructions take: 74

循环已经优化了.永远不需要计算的值,因此编译器决定不运行它

结论:如果你向森林射击3次,并且击中2只公猪和1只兔子,那并不意味着公猪的数量是兔子的两倍.

Answer 2

让我们从查看代码开始吧.循环实际上没有做任何事情.任何合理的编译器都会看到你z在第一次调用后没有使用变量printf,所以扔掉它是完全安全的.当然,编译器不必这样做,但任何具有任何合理优化级别的合理编译器都会这样做.

让我们看看编译器对你的代码做了什么(标准的clang与-O2优化级别):

    leaq    L_.str(%rip), %rdi
    movl    $35, %esi
    xorl    %eax, %eax
    callq   _printf

这是第一个printf("总和......"),注意如何生成的代码实际上并未添加任何东西,编译器知道的价值观x和y,只是计算其总和,并与35 printf的调用.

    callq   _clock
    movq    %rax, %rbx
    callq   _clock

调用时钟,将其结果保存在临时寄存器中,再次调用时钟,

    movq    %rax, %rcx
    subq    %rbx, %rcx
    leaq    L_.str.1(%rip), %rdi
    xorl    %eax, %eax
    movq    %rcx, %rsi

从头开始减去,为printf设置参数,

    callq   _printf

打电话给printf.

以等效方式移除第二个循环.没有循环,因为编译器做了合理的事情 - 它注意到z在循环中修改后没有使用它,因此编译器会抛弃任何存储.然后由于没有任何东西存储在其中,它也可以扔掉x+y.而现在,由于循环的主体没有做任何事情,循环可以被抛弃.所以你的代码基本上变成:

printf("\n\nArithmetic instructions take: %d", clock() - clock());

现在,为什么这是相关的.了解一些重要概念是相关的.编译器不会将一个语句一次性地翻译成代码.编译器会读取您的所有代码(或尽可能多的代码),尝试找出您实际意味着什么,然后生成行为"好像"执行所有这些语句的代码.语言和编译器只关心保留我们可以称之为可观察的副作用的东西.如果计算值不可观察,则不需要计算它.执行某些代码的时间不是我们关心的副作用,因此编译器不关心保留它,毕竟我们希望我们的代码尽可能快,所以我们希望有时间执行某些代码完全没有观察到.

第二部分为什么这是相关的.如果你在没有优化的情况下编译它会花多长时间来测量它是没有用的.这是在没有优化的情况下编译的代码中的循环:

LBB0_1:
        cmpl    $100000, -28(%rbp)
        jge     LBB0_4
        movl    -8(%rbp), %eax
        addl    -12(%rbp), %eax
        movl    %eax, -16(%rbp)
        movl    -28(%rbp), %eax
        addl    $1, %eax
        movl    %eax, -28(%rbp)
        jmp     LBB0_1
LBB0_4:

你以为你在addl这里测量指令.但整个循环包含更多.实际上,循环中的大部分时间都花在维护循环上,而不是实际执行指令.大部分时间用于在堆栈上读取和写入值并计算循环变量.您恰好测量的任何时间将完全由循环的基础设施主导,而不是您想要测量的操作.

你循环很少次.我很确定你实际测量的大部分时间都花在了clock()而不是你实际想要测量的代码上.clock需要做很多工作,阅读时间往往相当昂贵.

然后我们回答你关心的实际指示的问题.他们花费的时间完全相同.这是与x86上的指令时序相关的所有内容的规范来源.

但.对个别指令进行推理是非常困难的,几乎没有用处.在过去几十年中,几乎每个CPU都是超标量的.这意味着它将同时执行许多指令.事情花费多少时间的重要性在于指令之间的更多依赖性(如果那些输入是由先前的指令计算的,则无法在输入就绪之前开始执行指令)而不是实际指令.虽然每纳秒可以在寄存器中进行数十次计算,但从主存储器获取数据可能需要数百纳秒.因此,即使我们知道一条指令需要一个周期而且你的CPU每纳秒执行两个周期(通常是那个周期),这意味着我们可以在100ns内完成的指令数量可以在1之间(如果你需要等待)对于主内存)和12800(我不知道真正的确切数字,但我记得Skylake可以在每个周期退出64个浮点运算).

这就是微基准测试不再严重的原因.如果事情的微小变化可以影响结果一万二千,你可以很快看到为什么测量单个指令是无用的.今天的大多数测量都是在大部分程序或整个程序上完成的.我在工作中做了很多这样的事情,我有几种情况,改进算法改变了内存访问模式,即使算法可以在数学上证明更快,整个程序的行为因为更改的内存访问模式等而受到影响.

很抱歉这样一个漫无边际的答案,但是我想知道为什么即使你的问题有一个简单的答案:"你的测量方法很糟糕"而且还有一个真正的答案:"它们是相同的",实际上有问题本身无法回答的有趣原因.