Самый быстрый способ узнать минимум 3 номера?

Question

В написанной мною программе 20% времени тратится на поиск не менее 3 чисел во внутреннем цикле, в этой подпрограмме:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) m = c;
    return m;
}

Есть ли способ ускорить это? Я в порядке с ассемблером код тоже для x86 / x86_64.

Редактировать: В ответ на некоторые комментарии:
* Используется компилятор gcc 4.3.3
* Что касается сборки, я здесь только новичок. Я попросил сборку здесь, чтобы узнать, как это сделать. :)
* У меня работает четырехъядерный процессор Intel 64, поэтому поддерживаются MMX / SSE и т. Д.
* Здесь сложно опубликовать цикл, но я могу сказать, что это сильно оптимизированная реализация алгоритма Левенштейна.

Это то, что дает мне компилятор для не встроенной версии min:

.globl min
    .type   min, @function
min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %eax
    movl    16(%ebp), %ecx
    cmpl    %edx, %eax
    jbe .L2
    movl    %edx, %eax
.L2:
    cmpl    %ecx, %eax
    jbe .L3
    movl    %ecx, %eax
.L3:
    popl    %ebp
    ret
    .size   min, .-min
    .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
    .section    .note.GNU-stack,"",@progbits

Встроенная версия находится в оптимизированном для -O2 коде (даже мои маркеры mrk = 0xfefefefe, до и после вызова min ()) оптимизируются gcc, поэтому я не смог его достать.

Обновление: Я протестировал изменения, предложенные Nils, ephemient, однако ощутимого прироста производительности я не получаю, используя версии сборки min (). Тем не менее, я получаю увеличение на 12,5%, компилируя программу с параметром -march = i686, что, как я полагаю, объясняется тем, что вся программа получает преимущества от новых более быстрых инструкций, которые gcc генерирует с этой опцией. Спасибо за вашу помощь, ребята.

P.S. - Я использовал профилировщик ruby ​​для измерения производительности (моя C-программа является общей библиотекой, загружаемой ruby-программой), поэтому я мог получать время, затрачиваемое только на функцию C верхнего уровня, вызываемую ruby-программой, которая в итоге вызывает min ( ) вниз по стеку. Пожалуйста, посмотрите этот вопрос .

Answer 1

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

Если вы опубликуете сборку, которую на самом деле генерирует ваш компилятор, мы увидим, есть ли что-то ненужное, что замедляет его.

Первое, что нужно проверить, это то, что рутина на самом деле становится встроенной. Компилятор не обязан это делать, и если он генерирует вызов функции, это будет очень дорого для такой простой операции.

Если вызов действительно становится встроенным, то развертывание цикла может быть полезным, как сказал DigitalRoss, или возможна векторизация.

Редактировать: Если вы хотите векторизовать код и используете новейший процессор x86, вам нужно использовать инструкцию SSE4.1 pminud (встроенная: _mm_min_epu32), которая принимает два вектора по четыре беззнаковых целых и создают вектор из четырех беззнаковых целых. Каждый элемент результата является минимумом соответствующих элементов в двух входах.

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

Answer 2

Убедитесь, что вы используете соответствующую настройку -march, сначала выключите. По умолчанию GCC не использует никаких инструкций, которые не были поддержаны в исходном i386 - позволяя ему использовать более новые наборы инструкций, время от времени может быть ОГРОМНАЯ разница! На -march=core2 -O2 я получаю:

min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    movl    16(%ebp), %eax
    cmpl    %edx, %ecx
    leave
    cmovbe  %ecx, %edx
    cmpl    %eax, %edx
    cmovbe  %edx, %eax
    ret

Использование cmov здесь может помочь вам избежать задержек ветвления - и вы получите его без какого-либо встроенного ассемблера, просто передав -march. Если встроить в более крупную функцию, это, вероятно, будет еще более эффективным, возможно, всего четыре операции сборки. Если вам нужно что-то быстрее этого, посмотрите, сможете ли вы заставить векторные операции SSE работать в контексте вашего общего алгоритма.

Answer 3

Мой взгляд на реализацию ассемблера x86, синтаксис GCC. Должен быть тривиален перевод в другой синтаксис встроенного ассемблера:

int inline least (int a, int b, int c)
{
  int result;
  __asm__ ("mov     %1, %0\n\t"
           "cmp     %0, %2\n\t" 
           "cmovle  %2, %0\n\t"
           "cmp     %0, %3\n\t"
           "cmovle  %3, %0\n\t" 
          : "=r"(result) : 
            "r"(a), "r"(b), "r"(c)
          );
  return result;
}

---

Новая и улучшенная версия:

int inline least (int a, int b, int c)
{
  __asm__ (
           "cmp     %0, %1\n\t" 
           "cmovle  %1, %0\n\t"
           "cmp     %0, %2\n\t"
           "cmovle  %2, %0\n\t" 
          : "+r"(a) : 
            "%r"(b), "r"(c)
          );
  return a;
}

---

ПРИМЕЧАНИЕ. Может быть или не быть быстрее, чем C-код.

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

Кстати, Судханшу, было бы интересно услышать, как этот код работает с вашими тестовыми данными.

Answer 4

Эта замена на моем AMD AMD Phenom работает примерно на 1,5% быстрее:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    asm("cmp   %1,%0\n"
        "cmova %1,%0\n"
        "cmp   %2,%0\n"
        "cmova %2,%0\n"
        : "+r" (a) : "r" (b), "r" (c));
    return a;
}

Результаты могут отличаться; некоторые процессоры x86 не очень хорошо справляются с CMOV.

Answer 5

Расширения инструкций SSE2 содержат целочисленную min инструкцию, которая может выбирать 8 минимумов за раз См _mm_mulhi_epu16 в http://www.intel.com/software/products/compilers/clin/docs/ug_cpp/comm1046.htm

Answer 6

Сначала посмотрите на разборку. Это многое вам скажет. Например, как написано, есть 2 оператора if (что означает, что есть 2 возможных неверных прогноза ветвления), но я предполагаю, что приличный современный компилятор C будет иметь некоторую умную оптимизацию, которая может сделать это без ветвления. Мне было бы интересно узнать.

Во-вторых, если ваш libc имеет специальные встроенные функции min / max, используйте их. Например, в GNU libc есть fmin / fmax для чисел с плавающей запятой, и они утверждают, что «на некоторых процессорах эти функции могут использовать специальные машинные инструкции для выполнения этих операций быстрее, чем эквивалентный код на Си». Может быть, есть что-то подобное для уинтс.

Наконец, если вы делаете это для группы чисел параллельно, вероятно, есть векторные инструкции для этого, которые могут обеспечить значительное ускорение. Но я даже видел, что не векторный код будет быстрее при использовании векторных модулей. Что-то вроде «загрузить одну uint в векторный регистр, вызвать функцию min вектора, получить результат» выглядит глупо, но на самом деле может быть быстрее.

Answer 7

Это все хорошие ответы. Рискуя быть обвиненным в том, что я не отвечу на вопрос, я бы также посмотрел на остальные 80% времени. Stackshots - мой любимый способ найти код, который стоит оптимизировать, особенно если это вызовы функций, которые вам абсолютно не нужны.

Answer 8

Да, пост сборка, но моя наивная оптимизация:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) return c;
    return m;
}

Answer 9

Вы можете попробовать что-то вроде этого, чтобы сэкономить на декларации и ненужных сравнениях:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{ 
    if (a < b)
    {
        if (a < c) 
             return a; 
        else 
             return c;
    }

    if (b < c)
        return b;
    else return c;
}

Answer 10

Если вы делаете только одно сравнение, вы можете развернуть цикл вручную.

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