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

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

Я нашел очень быструю функцию целочисленного квадратного корня здесь Марка Крауна. По крайней мере, с GCC на моей машине это явно самая быстрая функция извлечения квадратного корня из целых чисел, которую я тестировал (включая функции в Hacker's Delight, этой страницы и floor(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,92 с для (2 ^ 28 - 1) итераций со сборкой -O2, тогда как встроенная версия обычно занимает около 3,25 с. РЕДАКТИРОВАТЬ: я сказал 2 ^ 32 - 1 итерация раньше, но я забыл, что изменил его. Для полной гаммы требуется немного больше времени.

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

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

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

ОБНОВЛЕНИЕ: пользователь 1034749 ниже получает один и тот же вывод сборки из обеих функций, когда он помещает их в отдельные файлы и компилирует их. Я попробовал его точную командную строку, и я получаю тот же результат, что и он. Для всех намерений и целей, этот вопрос решен.

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

ОБНОВЛЕНИЕ 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;
}

ОБНОВЛЕНИЕ 3: я до сих пор понятия не имею, как надежно сравнивать время работы разных функций без учета времени, зависящего от порядка тестов. Буду очень признателен за любые советы!

Однако, если кто-то еще, читающий это, заинтересован в быстрой реализации sqrt, я должен упомянуть: код Марка Крауна тестируется быстрее, чем любая другая чистая версия 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);
}