Timing Quake III hack只有在使用优化进行编译时才有效

Question

所以我刚刚发现了非常有趣的Quake III平方根反比破解。在了解了它的工作原理之后，我决定对它进行测试。我发现hack只有在启用优化的情况下编译时才优于math.h1/sqrt(X)。

黑客的实现：

float q_sqrt(float x) {
    float x2 = x * 0.5F;
    int i = *( int* )&x;                  // evil floating point bit hack
    i = 0x5f3759df - (i >> 1);            // what the fuck?
    x = *( float* )&i;
    x = x * ( 1.5F - ( (x2 * x * x) ) );  //1st iteration
  //y = y * ( 1.5F - ( (x2 * y * y) ) );  //2nd iteration, can be removed
    return x;
}

要测试1/sqrt(x)与q_sqrt(X)的运行速度，请执行以下操作：

//qtest.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

/*
Implementation of 1/sqrt(x) used in tue quake III game
*/
float q_sqrt(float x) {
    float x2 = x * 0.5F;
    int i = *( int* )&x;                  // evil floating point bit hack
    i = 0x5f3759df - (i >> 1);            // what the fuck?
    x = *( float* )&i;
    x = x * ( 1.5F - ( (x2 * x * x) ) );  //1st iteration
  //y = y * ( 1.5F - ( (x2 * y * y) ) );  //2nd iteration, can be removed
    return x;
}


int main(int argc, char *argv[]) {
    struct timespec start, stop;
    //Will work on floats in the range [0,100]
    float maxn = 100;
    //Work on 10000 random floats or as many as user provides
    size_t num = 10000;
    //Bogus
    float ans = 0;
    //Measure nanoseconds
    size_t ns = 0;
    if (argc > 1)
        num = atoll(argv[1]);
    if (num <= 0) return -1;
    //Compute "num" random floats 
    float *vecs = malloc(num * sizeof(float));
    if (!vecs) return -1;
    for (int i = 0; i < num; i++)
        vecs[i] = maxn * ( (float)rand() / (float)RAND_MAX );

    fprintf(stderr, "Measuring 1/sqrt(x)\n");
    clock_gettime( CLOCK_REALTIME, &start);
    for (size_t i = 0; i < num; i++)
        ans += 1 / sqrt(vecs[i]);
    clock_gettime( CLOCK_REALTIME, &stop);
    ns = ( stop.tv_sec - start.tv_sec ) * 1E9 + ( stop.tv_nsec - start.tv_nsec );
    fprintf(stderr, "1/sqrt(x) took %.6f nanosecods\n", (double)ns/num );


    fprintf(stderr, "Measuring q_sqrt(x)\n");
    clock_gettime( CLOCK_REALTIME, &start);
    for (size_t i = 0; i < num; i++)
        ans += q_sqrt(vecs[i]);
    clock_gettime( CLOCK_REALTIME, &stop);
    ns = ( stop.tv_sec - start.tv_sec ) * 1E9 + ( stop.tv_nsec - start.tv_nsec );
    fprintf(stderr, "q_sqrt(x) took %.6f nanosecods\n", (double)ns/num );

    //Side by side
  //for (size_t i = 0; i < num; i++)
  //    fprintf(stdout, "%.6f\t%.6f\n", 1/sqrt(vecs[i]),q_sqrt(vecs[i]));
    free(vecs);
}

在我的系统(Ryzen 3700X)上，我得到：

gcc -Wall -pedantic -o qtest qtest.c -lm
./qtest
Measuring 1/sqrt(x)
1/sqrt(x) took 4.470000 nanosecods
Measuring q_sqrt(x)
q_sqrt(x) took 4.859000 nanosecods


gcc -Wall -pedantic -O1 -o qtest qtest.c -lm
./qtest
Measuring 1/sqrt(x)
1/sqrt(x) took 0.378000 nanosecods
Measuring q_sqrt(x)
q_sqrt(x) took 0.497000 nanosecods


gcc -Wall -pedantic -O2 -o qtest qtest.c -lm
qtest.c: In function ‘q_sqrt’:
qtest.c:11:14: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
  11 |     int i = *( int* )&x;                  // evil floating point bit hack
     |
qtest.c:13:10: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
  13 |     x = *( float* )&i;
     |
./qtest
Measuring 1/sqrt(x)
1/sqrt(x) took 0.500000 nanosecods
Measuring q_sqrt(x)
q_sqrt(x) took 0.002000 nanosecods

我的期望是q_sqrt(x)会比开箱即用的1/sqrt(X)工作得更好。在阅读了更多之后，我现在知道libm优化得更好了，或者我的CPU配备了针对sqrt(X)的硬件解决方案。毕竟，自从快速反向root hack的开发以来，CPU已经有了飞跃的变化。

我不明白的是，编译器会应用什么类型的优化来让它更快。当然，也许我的基准是考虑不周的？

谢谢你的帮助！！

Answer 1

正如您所说，大多数现代CPU都包含一个浮点单元，它通常提供计算平方根的硬件指令。FPU还提供除法指令，所以我希望你的处理器(尽管我不知道)能够在几条汇编指令中计算出一个逆sqrt。您的结果有点令人惊讶:您应该检查FPU是否真的被使用了。我不知道Ryzen，但在ARM处理器上，你可以编译你的软件，使用硬件浮点指令或软件库。

现在来回答您的问题: GCC优化是一个复杂的故事，通常不可能准确地预测给定级别对性能的影响。所以，像你做的那样运行一些测试，或者看看理论的here。

Answer 2

CLang/LLVM的具体区别是：

不进行优化(-O0)：

q_sqrt(float):                             # @q_sqrt(float)
        push    rbp
        mov     rbp, rsp
        movss   dword ptr [rbp - 4], xmm0
        movss   xmm0, dword ptr [rip + .LCPI0_1] # xmm0 = mem[0],zero,zero,zero
        mulss   xmm0, dword ptr [rbp - 4]
        movss   dword ptr [rbp - 8], xmm0
        mov     eax, dword ptr [rbp - 4]
        mov     dword ptr [rbp - 12], eax
        mov     ecx, dword ptr [rbp - 12]
        sar     ecx, 1
        mov     eax, 1597463007
        sub     eax, ecx
        mov     dword ptr [rbp - 12], eax
        movss   xmm0, dword ptr [rbp - 12]      # xmm0 = mem[0],zero,zero,zero
        movss   dword ptr [rbp - 4], xmm0
        movss   xmm0, dword ptr [rbp - 4]       # xmm0 = mem[0],zero,zero,zero
        movss   xmm2, dword ptr [rbp - 8]       # xmm2 = mem[0],zero,zero,zero
        mulss   xmm2, dword ptr [rbp - 4]
        mulss   xmm2, dword ptr [rbp - 4]
        movss   xmm1, dword ptr [rip + .LCPI0_0] # xmm1 = mem[0],zero,zero,zero
        subss   xmm1, xmm2
        mulss   xmm0, xmm1
        movss   dword ptr [rbp - 4], xmm0
        movss   xmm0, dword ptr [rbp - 4]       # xmm0 = mem[0],zero,zero,zero
        pop     rbp
        ret

使用优化(-Ofast)：

q_sqrt(float):                             # @q_sqrt(float)
        movd    eax, xmm0
        sar     eax
        mov     ecx, 1597463007
        sub     ecx, eax
        movd    xmm1, ecx
        mulss   xmm0, dword ptr [rip + .LCPI0_0]
        movdqa  xmm2, xmm1
        mulss   xmm2, xmm1
        mulss   xmm0, xmm2
        addss   xmm0, dword ptr [rip + .LCPI0_1]
        mulss   xmm0, xmm1
        ret

您可以使用https://godbolt.org/检查编译器的汇编输出，使用各种不同的标志，并检查它对输出的影响。