Timing Quake III hack 仅在使用优化编译时有效
Timing Quake III hack only works when compiled with optimizations
所以我刚刚发现了非常有趣的 Quake III 平方根倒数技巧。在了解了它的工作原理之后，我决定对其进行测试。我发现在启用优化的情况下编译时，hack 的性能仅优于 math.h 1/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) 的硬件解决方案。毕竟，CPU自从快速反根黑客的发展以来有了突飞猛进的变化。
我不明白的是编译器会应用什么类型的优化来使其更快。当然，也许我的基准设计不当？
感谢您的帮助！！
正如您所说，大多数现代 CPU 都包含一个浮点单元，该单元通常提供硬件指令来计算平方根。 FPU 还提供除法指令，因此我希望您的处理器（虽然我不知道）能够仅通过几条汇编指令计算出平方反比。你的结果有点令人惊讶：你应该检查 FPU 是否真的被使用了。我不了解 Ryzen，但在 ARM 处理器上，您可以编译软件以使用硬件浮点指令或软件库。
现在回答您的问题：GCC 优化是一个复杂的故事，通常不可能准确预测给定级别对性能的影响。所以 运行 像你一样做一些测试，或者看看 here 理论。
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/ 检查编译器的汇编输出，使用各种不同的标志并检查它如何影响输出。
所以我刚刚发现了非常有趣的 Quake III 平方根倒数技巧。在了解了它的工作原理之后，我决定对其进行测试。我发现在启用优化的情况下编译时，hack 的性能仅优于 math.h 1/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) 的硬件解决方案。毕竟，CPU自从快速反根黑客的发展以来有了突飞猛进的变化。
我不明白的是编译器会应用什么类型的优化来使其更快。当然，也许我的基准设计不当？
感谢您的帮助！！
正如您所说，大多数现代 CPU 都包含一个浮点单元，该单元通常提供硬件指令来计算平方根。 FPU 还提供除法指令，因此我希望您的处理器（虽然我不知道）能够仅通过几条汇编指令计算出平方反比。你的结果有点令人惊讶：你应该检查 FPU 是否真的被使用了。我不了解 Ryzen，但在 ARM 处理器上，您可以编译软件以使用硬件浮点指令或软件库。
现在回答您的问题：GCC 优化是一个复杂的故事，通常不可能准确预测给定级别对性能的影响。所以 运行 像你一样做一些测试，或者看看 here 理论。
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/ 检查编译器的汇编输出，使用各种不同的标志并检查它如何影响输出。