Лучшая assembly или компиляция для минимум трех значений

Я просматриваю код, созданный GCC-4.8 для x86_64, и задаюсь вопросом, есть ли лучший (более быстрый) способ вычисления минимума трех значений.

Вот выдержка из модуля коллекций Python, который вычисляет минимум m , rightindex+1 и leftindex :

  ssize_t m = n; if (m > rightindex + 1) m = rightindex + 1; if (m > leftindex) m = leftindex; 

GCC генерирует последовательно зависимый код с CMOV:

 leaq 1(%rbp), %rdx cmpq %rsi, %rdx cmovg %rsi, %rdx cmpq %rbx, %rdx cmovg %rbx, %rdx 

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

редактирует:

  • Как показано, код использует подписанную арифметику, но также поможет и арифметический ответ без знака.
  • Я спросил о минимуме-трех, но также интересуюсь минимумом-n, где n мало.
  • Напоминания Линуса о CMOV: http://ondioline.org/mail/cmov-a-bad-idea-on-out-of-order-cpus

Минимум двух беззнаковых чисел имеет classическое решение:

 ; eax = min(eax, ebx), ecx - scratch register. .min2: sub ebx, eax sbb ecx, ecx and ecx, ebx add eax, ecx 

Этот подход, вероятно, быстрее, чем решение с cmov, но для большей скорости инструкции должны быть отделены другими инструкциями для параллельного выполнения.

Возможна реализация этого метода для трех чисел:

 ; eax = min(eax, ebx, edx), ecx - scratch register. .min3: sub ebx, eax sbb ecx, ecx and ecx, ebx add eax, ecx sub edx, eax sbb ecx, ecx and ecx, edx add eax, ecx 

Другая попытка – проверить вариант с условными переходами. Для современных процессоров это может быть еще быстрее, особенно если прыжки очень предсказуемы:

 .min3: cmp eax, ebx jle @f mov eax, ebx @@: cmp eax, edx jle @f mov eax, edx @@: 

Ниже приведены сравнительные результаты для предложенных методов. Процессор Intel Core i7 2600K работает на частоте 4 ГГц. Единицы – наносекунды на петлю (меньше – лучше). Измерения include в себя генерацию псевдослучайных тестовых данных и служебные служебные вызовы функций, в дополнение к фактическому тестируемому min3-коду.

  gcc cmov conditional classical sequence branches branchless pseudo-random data 2.24 6.31 2.39 fixed data 2.24 2.99 2.39 

Исходный код

functions.s: оцениваются 3 решения:

 //---------------------------------------------------------------------------- .text .intel_syntax noprefix //----------------------------------------------------------------------------- // uint64_t min3_a (uint64_t rcx, uint64_t rdx, uint64_t r8) .globl min3_a min3_a: mov rax, rcx cmp rax, rdx cmovg rax, rdx cmp rax, r8 cmovg rax, r8 retq //----------------------------------------------------------------------------- // uint64_t min3_b (uint64_t rcx, uint64_t rdx, uint64_t r8) .globl min3_b min3_b: mov rax, rcx cmp rax, rdx jle skip1 mov rax, rdx skip1: cmp rax, r8 jle skip2 mov rax, r8 skip2: retq //----------------------------------------------------------------------------- // uint64_t min3_c (uint64_t rcx, uint64_t rdx, uint64_t r8) .globl min3_c min3_c: sub rdx, rcx sbb rax, rax and rax, rdx add rcx, rax sub r8, rcx sbb rax, rax and rax, r8 add rax, rcx retq //----------------------------------------------------------------------------- 

min3test.c, основная программа (mingw64 / windows):

 #define __USE_MINGW_ANSI_STDIO 1 #include  #include  #include  uint64_t min3_a (uint64_t rcx, uint64_t rdx, uint64_t r8); uint64_t min3_b (uint64_t rcx, uint64_t rdx, uint64_t r8); uint64_t min3_c (uint64_t rcx, uint64_t rdx, uint64_t r8); //----------------------------------------------------------------------------- // // queryPerformanceCounter - similar to QueryPerformanceCounter, but returns // count directly. uint64_t queryPerformanceCounter (void) { LARGE_INTEGER int64; QueryPerformanceCounter (&int64); return int64.QuadPart; } //----------------------------------------------------------------------------- // // queryPerformanceFrequency - same as QueryPerformanceFrequency, but returns count direcly. uint64_t queryPerformanceFrequency (void) { LARGE_INTEGER int64; QueryPerformanceFrequency (&int64); return int64.QuadPart; } //---------------------------------------------------------------------------- // // lfsr64gpr - left shift galois type lfsr for 64-bit data, general purpose register implementation // static uint64_t lfsr64gpr (uint64_t data, uint64_t mask) { uint64_t carryOut = data >> 63; uint64_t maskOrZ = -carryOut; return (data << 1) ^ (maskOrZ & mask); } //--------------------------------------------------------------------------- uint64_t min3 (uint64_t a, uint64_t b, uint64_t c) { uint64_t smallest; smallest = a; if (smallest > b) smallest = b; if (smallest > c) smallest = c; return smallest; } //--------------------------------------------------------------------------- static void runtests (uint64_t pattern, uint64_t mask) { uint64_t startCount, elapsed, index, loops = 800000000; double ns; startCount = queryPerformanceCounter (); for (index = 0; index < loops; index++) { pattern = lfsr64gpr (pattern, mask); min3_a (pattern & 0xFFFFF, (pattern >> 20) & 0xFFFFF, (pattern >> 40) & 0xFFFFF); } elapsed = queryPerformanceCounter () - startCount; ns = (double) elapsed / queryPerformanceFrequency () * 1000000000 / loops; printf ("%7.2f ns\n", ns); startCount = queryPerformanceCounter (); for (index = 0; index < loops; index++) { pattern = lfsr64gpr (pattern, mask); min3_b (pattern & 0xFFFFF, (pattern >> 20) & 0xFFFFF, (pattern >> 40) & 0xFFFFF); } elapsed = queryPerformanceCounter () - startCount; ns = (double) elapsed / queryPerformanceFrequency () * 1000000000 / loops; printf ("%7.2f ns\n", ns); startCount = queryPerformanceCounter (); for (index = 0; index < loops; index++) { pattern = lfsr64gpr (pattern, mask); min3_c (pattern & 0xFFFFF, (pattern >> 20) & 0xFFFFF, (pattern >> 40) & 0xFFFFF); } elapsed = queryPerformanceCounter () - startCount; ns = (double) elapsed / queryPerformanceFrequency () * 1000000000 / loops; printf ("%7.2f ns\n", ns); } //--------------------------------------------------------------------------- int main (void) { uint64_t index, pattern, mask; uint64_t count_a = 0, count_b = 0, count_c = 0; mask = 0xBEFFFFFFFFFFFFFF; pattern = 1; // sanity check the asm functions for (index = 0; index < 1000000; index++) { uint64_t expected, result_a, result_b, result_c; uint64_t pattern1 = (pattern >> 0) & 0xFFFFF; uint64_t pattern2 = (pattern >> 20) & 0xFFFFF; uint64_t pattern3 = (pattern >> 40) & 0xFFFFF; pattern = lfsr64gpr (pattern, mask); expected = min3 (pattern1, pattern2, pattern3); result_a = min3_a (pattern1, pattern2, pattern3); result_b = min3_b (pattern1, pattern2, pattern3); result_c = min3_c (pattern1, pattern2, pattern3); if (result_a != expected) printf ("min3_a fail, %llu %llu %llu %llu %llu\n", expected, result_a, pattern1, pattern2, pattern3); if (result_b != expected) printf ("min3_b fail, %llu %llu %llu %llu %llu\n", expected, result_b, pattern1, pattern2, pattern3); if (result_c != expected) printf ("min3_c fail, %llu %llu %llu %llu %llu\n", expected, result_c, pattern1, pattern2, pattern3); if (expected == pattern1) count_a++; if (result_b == pattern2) count_b++; if (result_c == pattern3) count_c++; } printf ("pseudo-random distribution: %llu, %llu, %llu\n", count_a, count_b, count_c); // raise our priority to increase measurement accuracy SetPriorityClass (GetCurrentProcess (), REALTIME_PRIORITY_CLASS); printf ("using pseudo-random data\n"); runtests (1, mask); printf ("using fixed data\n"); runtests (0, mask); return 0; } //--------------------------------------------------------------------------- 

построить командную строку:

 gcc -Wall -Wextra -O3 -omin3test.exe min3test.c functions.s 

Функция min(x,y,z) непрерывна, но ее производная нет. Эта производная имеет норму 1 везде, где она определена. Просто невозможно выразить это как арифметическую функцию.

Насыщающая арифметика имеет свои собственные разрывы, поэтому предыдущие рассуждения не могут быть использованы в этом случае. Однако точка насыщения не зависит от входа. Это, в свою очередь, подразумевает, что вам нужно будет масштабировать входы, после чего я уверен, что полученный код не будет быстрее.

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