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

Ответ 1

Убедитесь, что вы используете соответствующую настройку -march, сначала выключите. GCC по умолчанию не использует никаких инструкций, которые не поддерживались на исходном i386 - позволяя ему использовать новые наборы инструкций, может время от времени увеличивать BIG! На -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 здесь может помочь вам избежать задержки ветвления - и вы получите его без какого-либо встроенного asm, просто перейдя в -march. Когда он встроен в более крупную функцию, это может быть еще более эффективным, возможно, всего четыре операции сборки. Если вам нужно что-то быстрее, чем это, посмотрите, можете ли вы использовать векторные операции SSE в контексте вашего общего алгоритма.

Ответ 2

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

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

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

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

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

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

Ответ 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 встроенный ассемблер всегда является проблемой для оптимизатора, поэтому штраф оптимизации для окружающего кода может привести к снижению веса.

Btw Sudhanshu, было бы интересно узнать, как этот код выполняет ваши тестовые данные.

Ответ 4

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

Ответ 5

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

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.

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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;
}

Ответ 9

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

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;
}

Ответ 10

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