среда, 31 августа 2011 г.

задача компилятора

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

Думаю что это очень опасное заблуждение - компилятор в большинстве случаев не может оптимизировать даже куда более простые конструкции. Возьмем для примера библиотеку хешей FEHASHMAC и посмотрим какой код генерируется для хеша blake. Мой выбор пал на fehashmac например потому что она написана на plain C, генерация кода для которого намного проще чем для C++

Как это в open-source принято под windows на visual studio она не собирается. Если вас испугали чуть более 600 ошибок при компиляции - никогда вам не удастся приспособить open-source для чего-нть полезного, бгг. Ошибки впрочем все практически одинаковы и легко фиксятся за пол-часа примерно

Рассмотрим например такую операцию как конвертацию dword из big-endian в little-endian. Традиционно такой код пишут примерно так (файл include/blake_opt32.h):

#define U8TO32_BE(p) \
  (((u32)((p)[0]) << 24) | \
   ((u32)((p)[1]) << 16) | \
   ((u32)((p)[2]) <<  8) | \
   ((u32)((p)[3])      ))

А теперь посмотрим что нам сгенерировали компиляторы (смотреть проще всего в самом начале ф-ции compress32)

Visual Studio 2008 32bit

movzx   ecx, byte ptr [eax]
shl     ecx, 8
movzx   edx, byte ptr [eax+1]
or      ecx, edx
shl     ecx, 8
movzx   edx, byte ptr [eax+2]
or      ecx, edx
shl     ecx, 8
movzx   edx, byte ptr [eax+3]
or      ecx, edx
mov     [esp+0A0h+var_40], ecx


Практически то что было запрошено

gcc 4.2.4 64bit

movzx   eax, byte ptr [rax]
movzx   eax, al
mov     edx, eax
shl     edx, 18h
mov     rax, [rbp+var_A0]
add     rax, 1
movzx   eax, byte ptr [rax]
movzx   eax, al
shl     eax, 10h
or      edx, eax
mov     rax, [rbp+var_A0]
add     rax, 2
movzx   eax, byte ptr [rax]
movzx   eax, al
shl     eax, 8
or      edx, eax
mov     rax, [rbp+var_A0]
add     rax, 3
movzx   eax, byte ptr [rax]
movzx   eax, al
or      eax, edx
mov     [rbp+var_90], eax


мде...

gcc 4.2.4 64bit с опцией -O2

movzx   eax, byte ptr [rsi]
movzx   edx, byte ptr [rsi+3]
shl     eax, 18h
or      edx, eax
movzx   eax, byte ptr [rsi+1]
shl     eax, 10h
or      edx, eax
movzx   eax, byte ptr [rsi+2]
shl     eax, 8
or      edx, eax
mov     [rsp+60h+var_78], edx


уже получше, код практически такого же качества как visual studio

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

Я для vs2008 добавил примерно такое определение U8TO32_BE с использованием _byteswap_ulong:

#ifdef _MSC_VER
#define U8TO32_BE(p)    _byteswap_ulong(*(unsigned long *)(p))
#else
#define U8TO32_BE(p) \
  (((u32)((p)[0]) << 24) | \
   ((u32)((p)[1]) << 16) | \
   ((u32)((p)[2]) <<  8) | \
   ((u32)((p)[3])      ))
#endif /* _MSC_VER */


в результате получается:

mov     ecx, [eax]

bswap   ecx
mov     [esp+9Ch+var_40], ecx

Намного короче (-6Kb кода) и работает быстрее (прирост производительности ~5%), но оптимизатор до такого решения не додумался. А вы например утверждаете что он вам AVX автоматически будет использовать, ага-ага

6 комментариев:

  1. ознакомился
    ключевое слово - "переписал программу". в таком случае проще переписать с использованием intrinsics functions, чем надеяться что компилятор таки понял нас правильно

    ОтветитьУдалить
  2. См дополнение в конце поста.

    ОтветитьУдалить
  3. и как это "дополнение" опровергает факт того, что для оптимизации (полагаем что она нужна в данном случае - я бы иначе наверное не стал морочиться ?) прогу все равно требуется переписывать даже для таких элементарных вещей ?

    ОтветитьУдалить
  4. Я лишь говорю, что, возможно, вы выполняете оптимизацию там, где она не нужна.

    Допустим, я даже поверил в то, что вычисление хэш-функции является узким местом вашего реального приложения (профайлер говорит, что вычисление хэш-функции занимает более 50% времени работы программы) и заказчик действительно недоволен скоростью приложения. Что вы делаете - бросаетесь переписывать на ассемблер. Что я говорю - что, возможно, есть более простой путь. Например, переписать один макрос. Или докупить железо на сервере (если приложение серверное). Или распараллелить то место, где используется хэш-функция. Или сменить саму хэш-функцию. Или ее реализацию. Если у вас там брутфорс, эффективнее задействовать побольше компьютеров. Я почти уверен, что одним из этих способов вы достигните прироста производительности более, чем на 5%.

    Но если все альтернативы рассмотрены и остается только переписывать код на асм (в данном конкретном узком месте), тогда, конечно, Вы правы.

    ОтветитьУдалить
  5. есличо - в исходном псто речь шла про то что компиляторы неспособны поддерживать даже весьма простые случаи оптимизации. И еще более неспособны поддерживать специализированные семейства инструкций типа AVX

    ОтветитьУдалить