Я не уверен, что алгебраические манипуляции в сочетании с целочисленной арифметикой обязательно приводят к быстрейшему решению.В этом случае вам понадобится много скалярных умножений (что не очень быстро), и / или предсказание ветвления может потерпеть неудачу, что может снизить производительность.Очевидно, что вам придется тестировать, чтобы увидеть, какое решение является самым быстрым в вашем конкретном случае.
Один из способов сделать sqrt немного быстрее - добавить параметр -fno-math-errno в gcc или clang.В этом случае компилятору не нужно проверять наличие отрицательных входных данных.При использовании icc это значение по умолчанию.
Более эффективное улучшение возможно при использовании векторизованной инструкции sqrt sqrtpd вместо скалярной инструкции sqrt sqrtsd.Питер Кордес показал , что clang способен автоматически векторизовать этот код, так что он генерирует этот sqrtpd.
Однако успешность автоматической векторизации в значительной степени зависит от правильных настроек компилятораи используемый компилятор (clang, gcc, icc и т. д.).При -march=nehalem или старше clang не векторизируется.
Более надежные результаты векторизации возможны с помощью следующего встроенного кода, см. Ниже.Для переносимости мы предполагаем только поддержку SSE2, которая является базовой для x86-64.
/* gcc -m64 -O3 -fno-math-errno smaller.c */
/* Adding e.g. -march=nehalem or -march=skylake might further */
/* improve the generated code */
/* Note that SSE2 in guaranteed to exist with x86-64 */
#include<immintrin.h>
#include<math.h>
#include<stdio.h>
#include<stdint.h>
int is_smaller_v5(unsigned a1, unsigned b1, unsigned a2, unsigned b2) {
uint64_t a64 = (((uint64_t)a2)<<32) | ((uint64_t)a1); /* Avoid too much port 5 pressure by combining 2 32 bit integers in one 64 bit integer */
uint64_t b64 = (((uint64_t)b2)<<32) | ((uint64_t)b1);
__m128i ax = _mm_cvtsi64_si128(a64); /* Move integer from gpr to xmm register */
__m128i bx = _mm_cvtsi64_si128(b64);
__m128d a = _mm_cvtepi32_pd(ax); /* Convert 2 integers to double */
__m128d b = _mm_cvtepi32_pd(bx); /* We don't need _mm_cvtepu32_pd since a,b < 1e6 */
__m128d sqrt_b = _mm_sqrt_pd(b); /* Vectorized sqrt: compute 2 sqrt-s with 1 instruction */
__m128d sum = _mm_add_pd(a, sqrt_b);
__m128d sum_lo = sum; /* a1 + sqrt(b1) in the lower 64 bits */
__m128d sum_hi = _mm_unpackhi_pd(sum, sum); /* a2 + sqrt(b2) in the lower 64 bits */
return _mm_comilt_sd(sum_lo, sum_hi);
}
int is_smaller(unsigned a1, unsigned b1, unsigned a2, unsigned b2) {
return a1+sqrt(b1) < a2+sqrt(b2);
}
int main(){
unsigned a1; unsigned b1; unsigned a2; unsigned b2;
a1 = 11; b1 = 10; a2 = 10; b2 = 10;
printf("smaller? %i %i \n",is_smaller(a1,b1,a2,b2), is_smaller_v5(a1,b1,a2,b2));
a1 = 10; b1 = 11; a2 = 10; b2 = 10;
printf("smaller? %i %i \n",is_smaller(a1,b1,a2,b2), is_smaller_v5(a1,b1,a2,b2));
a1 = 10; b1 = 10; a2 = 11; b2 = 10;
printf("smaller? %i %i \n",is_smaller(a1,b1,a2,b2), is_smaller_v5(a1,b1,a2,b2));
a1 = 10; b1 = 10; a2 = 10; b2 = 11;
printf("smaller? %i %i \n",is_smaller(a1,b1,a2,b2), is_smaller_v5(a1,b1,a2,b2));
return 0;
}
См. эту ссылку Godbolt для созданной сборки.
В простом тесте пропускной способности на Intel Skylake с параметрами компилятора gcc -m64 -O3 -fno-math-errno -march=nehalem я обнаружил пропускную способность is_smaller_v5() который был в 2,6 раза лучше, чем исходный is_smaller(): 6,8 такта процессора против 18 циклов процессора, с учетом накладных расходов цикла.Однако в (слишком?) Простом тесте задержки, где входные данные a1, a2, b1, b2 зависели от результата предыдущего is_smaller(_v5), я не увидел никаких улучшений.(39,7 цикла против 39 циклов).