Каков пример простой функции C, которая быстрее реализуется во встроенной сборке?

Question

Мне трудно побить мой компилятор, используя встроенную сборку.

Что за хорошие, необдуманные примеры функций, которые компилятору трудно сделать действительно, действительно быстро и просто? Но это относительно просто сделать с помощью встроенной сборки.

Answer 1

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

Вот очень базовый учебник SSE (один из наборов инструкций SIMD для x86). Он предназначен для встроенной сборки Visual C ++.

Редактировать: вот небольшая пара функций, если вы хотите попробовать сами. Это вычисление точечного произведения длины n. Один использует встроенные инструкции SSE 2 (встроенный синтаксис GCC), другой - очень простой C.

Это очень очень просто, и я был бы очень удивлен, если бы хороший компилятор не смог векторизовать простой цикл C, но если этого не произойдет, вы должны увидеть ускорение в SSE2. Версия SSE 2 могла бы быть быстрее, если бы я использовал больше регистров, но я не хочу расширять свои очень слабые навыки SSE:).

 float dot_asm(float *a, float*b, int n)
{
  float ans = 0;
  int i; 
  // I'm not doing checking for size % 8 != 0 arrays.
  while( n > 0) {
    float tmp[4] __attribute__ ((aligned(16)));

     __asm__ __volatile__(
            "xorps      %%xmm0, %%xmm0\n\t"
            "movups     (%0), %%xmm1\n\t"
            "movups     16(%0), %%xmm2\n\t"
            "movups     (%1), %%xmm3\n\t"
            "movups     16(%1), %%xmm4\n\t"
            "add        $32,%0\n\t"
            "add        $32,%1\n\t"
            "mulps      %%xmm3, %%xmm1\n\t"
            "mulps      %%xmm4, %%xmm2\n\t"
            "addps      %%xmm2, %%xmm1\n\t"
            "addps      %%xmm1, %%xmm0"
            :"+r" (a), "+r" (b)
            :
            :"xmm0", "xmm1", "xmm2", "xmm3", "xmm4");

    __asm__ __volatile__(
        "movaps     %%xmm0, %0"
        : "=m" (tmp)
        : 
        :"xmm0", "memory" );             

   for(i = 0; i < 4; i++) {
      ans += tmp[i];
   }
   n -= 8;
  }
  return ans;
}

float dot_c(float *a, float *b, int n) {

  float ans = 0;
  int i;
  for(i = 0;i < n; i++) {
    ans += a[i]*b[i];
  }
  return ans;
}

Answer 2

Поскольку это связано с iPhone и ассемблерным кодом, я приведу пример, который будет актуален в мире iPhone (а не какой-нибудь sse или x86 asm). Если кто-то решит написать ассемблерный код для какого-либо реального приложения, то, скорее всего, это будет своего рода цифровая обработка сигналов или манипулирование изображениями. Примеры: преобразование цветового пространства пикселей RGB, кодирование изображений в формат jpeg / png или кодирование звука в mp3, amr или g729 для приложений voip. В случае кодирования звука есть много подпрограмм, которые не могут быть преобразованы компилятором в эффективный асм-код, они просто не имеют эквивалента в C. Примеры часто используемых вещей в обработке звука: насыщенная математика, подпрограммы с множественным накоплением, умножение матриц.

Пример насыщенного сложения: 32-битное целое со знаком имеет диапазон: 0x8000 0000 <= int32 <= 0x7fff ffff. Если вы добавите два целых числа, результат может переполниться, но в некоторых случаях это может быть неприемлемо при цифровой обработке сигналов. По сути, если результат переполнения или насыщения переполнен, add должен вернуть 0x8000 0000 или 0x7fff ffff. Это была бы полная функция c, чтобы проверить это. оптимизированная версия насыщенного добавления может быть: </p>

int saturated_add(int a, int b)
{
    int result = a + b;

    if (((a ^ b) & 0x80000000) == 0)
    {
        if ((result ^ a) & 0x80000000)
        {
            result = (a < 0) ? 0x80000000 : 0x7fffffff;
        }
    }
    return result;
} 

вы также можете сделать несколько if / else для проверки на переполнение или на x86 вы можете проверить флаг переполнения (который также требует использования asm). iPhone использует процессор armv6 или v7, у которого есть dsp asm. Таким образом, функция saturated_add с несколькими ответвлениями (операторы if / else) и 2 32-битными константами может быть одной простой инструкцией asm, которая использует только один цикл процессора. Таким образом, просто сделав насыщенный_адд с использованием инструкции asm, можно сделать весь алгоритм в два-три раза быстрее (и меньше по размеру). Вот руководство QADD: QADD

другими примерами кода, который часто выполняется в длинных циклах, являются

res1 = a + b1*c1;
res2 = a + b2*c2;
res3 = a + b3*c3;

похоже, что здесь ничего нельзя оптимизировать, но в процессоре ARM вы можете использовать специальные инструкции dsp, которые занимают меньше циклов, чем простое умножение! Это верно, a + b * c с конкретными инструкциями может выполняться быстрее, чем простой a * b. Для такого рода случаев компиляторы просто не могут понять логику вашего кода и не могут напрямую использовать эти инструкции dsp, и поэтому вам нужно вручную написать asm для оптимизации кода, НО вам нужно только вручную написать некоторые части кода, которые необходимо оптимизировано. Если вы начнете писать простые циклы вручную, то почти наверняка вы не победите компилятор! В Интернете есть много хороших статей для встроенной сборки, чтобы кодировать фильтры, кодировать / декодировать amr и т. Д.

Answer 3

Если вы не являетесь гуру сборки вероятность избиения компилятора очень низкая .

Фрагмент из вышеуказанной ссылки,

Например, бит-ориентированный XOR Инструкция% EAX,% EAX самый быстрый способ установить регистр на ноль в ранних поколениях x86, но большая часть кода генерируется компиляторы и компиляторы редко сгенерированная инструкция XOR. Итак, ИА дизайнеры решили перенести часто встречающийся компилятор сгенерированные инструкции до фронта комбинационной логики декодирования делая буквальное выражение "MOVL $ 0,% EAX" инструкция выполняется быстрее чем Инструкция XOR.

Answer 4

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

//rotate word n right by b bits
#define ROR16(n,b) (((n)>>(b))|(((n)<<(16-(b)))&0xFFFF))

//... and inside the inner loop: 
sum ^= ROR16(val, pos);

В сборку выпуска VisualStudio добавлено следующее: (val в топоре, pos в dx, sum в bx)

mov         ecx,10h 
sub         ecx,edx 
mov         ebp,eax 
shl         ebp,cl 
mov         cx,dx 
sar         ax,cl 
add         esi,2 
or          bp,ax 
xor         bx,bp 

Более эффективная эквивалентная сборка, созданная вручную:

 mov       cl,dx
 ror       ax,cl
 xor       bx,ax

Я не выяснил, как выдать инструкцию ror из чистого кода 'c'. Однако ...
При написании этого я вспомнил присущие компилятору. Я могу сгенерировать второй набор инструкций с помощью:

sum ^= _rotr16(val,pos);

Итак, мой ответ: даже если вы думаете, что можете побить чистый компилятор c, проверьте встроенные функции перед тем, как прибегнуть к встроенной сборке.

Answer 5

Я реализовал простую взаимную корреляцию, используя общую реализацию "пролива С". И затем, когда это заняло больше времени, чем у меня был временный интервал, я прибег к явному распараллеливанию алгоритма и использованию встроенного процессора, чтобы заставить конкретные инструкции использоваться в вычислениях. Для этого конкретного случая время вычислений было сокращено с> 30 мс до чуть более 4 мс. У меня было окно 15 мс для завершения обработки до следующего сбора данных.

Это была оптимизация типа SIMD на процессоре VLWI. Это требует только 4 или около того встроенных функций процессора, которые в основном являются инструкциями на ассемблере, которые создают видимость вызова функции в исходном коде. Вы могли бы сделать то же самое со встроенной сборкой, но управление синтаксисом и регистрами немного лучше с внутренними процессорами.

Кроме того, если размер имеет значение, ассемблер - король. Я пошел в школу с парнем, который написал полноэкранный текстовый редактор менее чем 512 байтов.

Answer 6

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

Answer 7

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

Это было около 6 лет назад, с каким-то проприетарным компилятором неизвестного качества. Мне нужно будет выкопать код, который у меня был, и попробовать его сейчас с GCC; Я не знаю, что это могло бы стать быстрее, но я бы не стал этого исключать.

В конце концов, даже несмотря на то, что моя memcpy была в среднем примерно в 15 раз быстрее, чем в нашей C-библиотеке, я просто держал ее в своем заднем кармане на всякий случай. Для меня было игрушкой играть со сборкой КПП, и в нашем приложении повышение скорости не требовалось.