(РЕДАКТИРОВАТЬ: Давайте назовем это «Уроки того, как измерения могут пойти не так». Я до сих пор не понял, что именно вызывает расхождение.)
Я нашел здесь очень быструю целочисленную функцию квадратного корня Марка Крауна. По крайней мере, с GCC на моей машине, это явно самая быстрая функция квадратного корня, которую я тестировал (включая функции в Hacker's Delight, this page , и 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 .)
Короче говоря, есть ли способ записать это как inline без потери скорости? (Я не профилировал, но sqrt - одна из тех фундаментальных операций, которые всегда следует выполнять быстро, так как я могу использовать ее во многих других программах, кроме той, которая мне сейчас интересна. Кроме того, мне просто любопытно .)
Я даже пробовал использовать шаблоны для «запекания» постоянного значения, но мне кажется, что два других параметра с большей вероятностью вызовут попадание (и макрос может этого избежать, так как он использует локальный переменные напрямую) ... ну, либо это, либо компилятор упорно отказывается встраивать.
ОБНОВЛЕНИЕ: пользователь 1034749, приведенный ниже, получает одинаковый вывод сборки от обеих функций, когда помещает их в отдельные файлы и компилирует их. Я попробовал его точную командную строку и получил тот же результат, что и он. Фактически этот вопрос решен.
Однако я все же хотел бы знать, почему мои измерения получаются иначе.Очевидно, из-за моего кода измерения или исходного процесса сборки все было по-другому. Код выложу ниже. Кто-нибудь знает, в чем заключалась сделка? Может быть, мой компилятор действительно встраивает всю функцию mcrowne_isqrt () в цикл моей функции main (), но не встраивает всю другую версию?
ОБНОВЛЕНИЕ 2 (сжато перед тестированием кода): обратите внимание, что если я поменяйте порядок тестов и сделайте встроенную версию первой, встроенная версия выходит быстрее, чем макро-версия на то же количество. Это проблема кеширования, или компилятор встраивает один вызов, а другой нет, или что?
#include
#include // Linux high-resolution timer
#include
/* 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);
}