Могу ли я изменить этот макрос на встроенную функцию без удара производительности?

Question

(EDIT:. Название Давайте это, «Уроки, как измерения могут пойти не так» я до сих пор не понял, что именно это вызывает несоответствие хотя)

Я нашел очень быстро целочисленного квадратного корня here Маркой Краун. По крайней мере, с GCC на моей машине, это, несомненно, самая быстрая функция квадратного корня, которую я тестировал (включая функции в Delight, Hacker's Delight, this page и пол (sqrt()) из стандартной библиотеки).

После очистки форматирования немного, переименования переменного и использования фиксированной ширины типов, это выглядит следующим образом:

static uint32_t mcrowne_isqrt(uint32_t val) 
{ 
    uint32_t temp, root = 0; 

    if (val >= 0x40000000) 
    { 
     root = 0x8000; 
     val -= 0x40000000; 
    } 

    #define INNER_ISQRT(s)        \ 
    do             \ 
    {             \ 
     temp = (root << (s)) + (1 << ((s) * 2 - 2)); \ 
     if (val >= temp)        \ 
     {            \ 
      root += 1 << ((s)-1);      \ 
      val -= temp;        \ 
     }            \ 
    } while(0) 

    INNER_ISQRT(15); 
    INNER_ISQRT(14); 
    INNER_ISQRT(13); 
    INNER_ISQRT(12); 
    INNER_ISQRT(11); 
    INNER_ISQRT(10); 
    INNER_ISQRT(9); 
    INNER_ISQRT(8); 
    INNER_ISQRT(7); 
    INNER_ISQRT(6); 
    INNER_ISQRT(5); 
    INNER_ISQRT(4); 
    INNER_ISQRT(3); 
    INNER_ISQRT(2); 

    #undef INNER_ISQRT 

    temp = root + root + 1; 
    if (val >= temp) 
     root++; 
    return root; 
} 

INNER_ISQRT макрос не слишком зол, так как он местный и сразу же неопределенный после того, как он больше не нужен. Тем не менее, я все равно хотел бы преобразовать его в встроенную функцию в принципе. Я читал утверждения в нескольких местах (включая документацию GCC), что встроенные функции «так же быстро», как и макросы, но у меня были проблемы с преобразованием без ускорения.

Моя текущая итерация выглядит следующим образом (обратите внимание на always_inline атрибут, который я бросил для хорошей мерой):

static inline void inner_isqrt(const uint32_t s, uint32_t& val, uint32_t& root) __attribute__((always_inline)); 
static inline void inner_isqrt(const uint32_t s, uint32_t& val, uint32_t& root) 
{ 
    const uint32_t temp = (root << s) + (1 << ((s << 1) - 2)); 
    if(val >= temp) 
    { 
     root += 1 << (s - 1); 
     val -= temp; 
    } 
} 

// Note that I just now changed the name to mcrowne_inline_isqrt, so people can compile my full test. 
static uint32_t mcrowne_inline_isqrt(uint32_t val) 
{ 
    uint32_t root = 0; 

    if(val >= 0x40000000) 
    { 
     root = 0x8000; 
     val -= 0x40000000; 
    } 

    inner_isqrt(15, val, root); 
    inner_isqrt(14, val, root); 
    inner_isqrt(13, val, root); 
    inner_isqrt(12, val, root); 
    inner_isqrt(11, val, root); 
    inner_isqrt(10, val, root); 
    inner_isqrt(9, val, root); 
    inner_isqrt(8, val, root); 
    inner_isqrt(7, val, root); 
    inner_isqrt(6, val, root); 
    inner_isqrt(5, val, root); 
    inner_isqrt(4, val, root); 
    inner_isqrt(3, val, root); 
    inner_isqrt(2, val, root); 

    const uint32_t temp = root + root + 1; 
    if (val >= temp) 
     root++; 
    return root; 
} 

Независимо от того, что я делаю, встраиваемая функция не всегда медленнее, чем макро. Макро версия обычно занимает около 2.92s для (2^28 - 1) итераций с -O2 build, тогда как встроенная версия обычно занимает около 3.25s. EDIT: Я сказал 2^32 - 1 итераций раньше, но я забыл, что я изменил его. Они занимают довольно много времени для полной гаммы.

Возможно, что компилятор просто глуп и отказывается вставлять его (обратите внимание снова на атрибут always_inline!), Но если это так, это сделало бы вариант макросов вообще предпочтительным в любом случае. (Я попытался проверить сборку, чтобы увидеть ее, но она была слишком сложной, как часть программы. Оптимизатор опустил все, когда я попытался скомпилировать только функции, конечно, и у меня возникли проблемы с компиляцией его как библиотеки из-за noobishness с GCC .)

Вкратце, есть ли способ написать это как встроенную линию без быстрого удара? (Я не профилировал, но sqrt - одна из тех фундаментальных операций, которые всегда должны выполняться быстро, поскольку я могу использовать ее во многих других программах, кроме тех, которые мне сейчас интересны. Кроме того, мне просто интересно .)

Я даже пробовал использовать шаблоны для «запекания» постоянного значения, но я чувствую, что другие два параметра, скорее всего, будут причиной хита (и макрос может избежать этого, поскольку он использует локальные переменные напрямую) ... ну, либо это, либо компилятор упрямо отказывается от встроенного.

---

UPDATE: user1034749 ниже получает тот же результат сборки с обеих функций, когда он помещает их в отдельные файлы и компилирует их. Я пробовал его точную командную строку, и я получаю тот же результат, что и он. По всем вопросам и задачам этот вопрос решен.

Однако мне все же хотелось бы знать, почему мои измерения выходят по-другому. Очевидно, что мой код измерения или исходный процесс сборки вызывали разные вещи. Я отправлю код ниже. Кто-нибудь знает, что это за сделка? Может быть, мой компилятор фактически встраивает всю функцию mcrowne_isqrt() в цикле моей функции main(), но это не вложение всей другой версии?

UPDATE 2 (сжимается перед тестированием кода): Обратите внимание: если я поменяю порядок тестов и сделаю встроенную версию первой, встроенная версия выйдет быстрее, чем версия макроса на ту же сумму. Является ли это проблемой кэширования или компилятор, содержащий один вызов, а не другой, или что?

#include <iostream> 
#include <time.h>  // Linux high-resolution timer 
#include <stdint.h> 

/* Functions go here */ 

timespec timespecdiff(const timespec& start, const timespec& end) 
{ 
    timespec elapsed; 
    timespec endmod = end; 
    if(endmod.tv_nsec < start.tv_nsec) 
    { 
     endmod.tv_sec -= 1; 
     endmod.tv_nsec += 1000000000; 
    } 

    elapsed.tv_sec = endmod.tv_sec - start.tv_sec; 
    elapsed.tv_nsec = endmod.tv_nsec - start.tv_nsec; 
    return elapsed; 
} 


int main() 
{ 
    uint64_t inputlimit = 4294967295; 
    // Test a wide range of values 
    uint64_t widestep = 16; 

    timespec start, end; 

    // Time macro version: 
    uint32_t sum = 0; 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint64_t num = (widestep - 1); num <= inputlimit; num += widestep) 
    { 
     sum += mcrowne_isqrt(uint32_t(num)); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 
    timespec markcrowntime = timespecdiff(start, end); 
    std::cout << "Done timing Mark Crowne's sqrt variant. Sum of results = " << sum << " (to avoid over-optimization)." << std::endl; 


    // Time inline version: 
    sum = 0; 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint64_t num = (widestep - 1); num <= inputlimit; num += widestep) 
    { 
     sum += mcrowne_inline_isqrt(uint32_t(num)); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 
    timespec markcrowninlinetime = timespecdiff(start, end); 
    std::cout << "Done timing Mark Crowne's inline sqrt variant. Sum of results = " << sum << " (to avoid over-optimization)." << std::endl; 

    // Results: 
    std::cout << "Mark Crowne sqrt variant time:\t" << markcrowntime.tv_sec << "s, " << markcrowntime.tv_nsec << "ns" << std::endl; 
    std::cout << "Mark Crowne inline sqrt variant time:\t" << markcrowninlinetime.tv_sec << "s, " << markcrowninlinetime.tv_nsec << "ns" << std::endl; 
    std::cout << std::endl; 
} 

---

UPDATE 3: Я до сих пор не знаю, как достоверно сравнить сроки различных функций без времени в зависимости от порядка испытаний. Я бы очень признателен за любые советы!

Однако, если кто-либо еще читает это, заинтересованы в быстрых реализациях sqrt, я должен упомянуть: тесты кода Mark Crowne быстрее, чем любая другая чистая версия C/C++, которую я пробовал на приличном уровне (несмотря на проблемы с безопасностью при тестировании) , но следующий код SSE кажется, что он может быть немного быстрее для скалярного 32-битного целого sqrt. Он не может быть обобщен для полноразмерных 64-битных беззнаковых целочисленных входов без потери точности (и первое подписанное преобразование также должно быть заменено нагрузкой, характерной для дескрипторов> = 2^63):

uint32_t sse_sqrt(uint64_t num) 
{ 
    // Uses 64-bit input, because SSE conversion functions treat all 
    // integers as signed (so conversion from a 32-bit value >= 2^31 
    // will be interpreted as negative). As it stands, this function 
    // will similarly fail for values >= 2^63. 
    // It can also probably be made faster, since it generates a strange/ 
    // useless movsd %xmm0,%xmm0 instruction before the sqrtsd. It clears 
    // xmm0 first too with xorpd (seems unnecessary, but I could be wrong). 
    __m128d result; 
    __m128d num_as_sse_double = _mm_cvtsi64_sd(result, num); 
    result = _mm_sqrt_sd(num_as_sse_double, num_as_sse_double); 
    return _mm_cvttsd_si32(result); 
} 

Answer 1

Я пробовал ваш код с gcc 4.5.3. я изменил свою вторую версию кода, чтобы соответствовать первый, , например:

(1 << ((s) * 2 - 2) 

против

(1 << ((s << 1) - 1) 

да, с * 2 == s < < 1, а "-2" и "-1"?

Также я изменил ваши типы, заменив uint32_t на «unsigned long», потому что на моей 64-битной машине «long» не является 32-битным номером.

А потом я бегу:

g++ -ggdb -O2 -march=native -c -pipe inline.cpp 
g++ -ggdb -O2 -march=native -c -pipe macros.cpp 
objdump -d inline.o > inline.s 
objdump -d macros.o > macros.s 

я мог бы использовать «-S» вместо «-c» на ассемблере, но я хотел бы видеть ассемблер без дополнительной информации.

и знаете что?
Ассемблер полностью такой же, в первой и второй версиях. Итак, я думаю, что ваши измерения времени просто неправильны.