Как сделать мою программу Haskell быстрее? Сравнение с C

Ответ 1

• Переключение на unboxed Vectors (из массива, используемого для констант)
• Используйте unsafeIndex вместо того, чтобы выполнять проверку границ и зависимость данных от надежной индексации (т.е. !)
• Распакуйте Block1024, как вы это сделали с Block512 (или, по крайней мере, используйте UnboxedTuples)
• Используйте unsafeShift{R,L}, чтобы вы не выполняли проверку значения сдвига (в GHC 7.4).
• Разверните roundFunction, чтобы у вас была одна довольно уродливая и многословная функция e8. Это было значительным в pureMD5 (свернутая версия была красивее, но значительно медленнее, чем развернутая версия). Возможно, вы сможете использовать TH для этого и сохранить код маленьким. Если вы это сделаете, вам не понадобится constants, так как эти значения будут явными в коде и приведут к созданию более кэширующего двоичного файла.
• Распакуйте свои значения Word128.
• Определите свое собственное дополнение для Word128, не поднимайте Integer. См. LargeWord для пример того, как это можно сделать.
• rem not mod
• Скомпилируйте с оптимизацией (-O2) и попробуйте llvm (-fllvm)

РЕДАКТИРОВАТЬ: и забросьте репозиторий git вместе с эталоном, чтобы мы могли помочь вам легче;-). Хорошая работа над включением экземпляра crypto-api.

Ответ 2

Нижний график показывает, что большая часть памяти занята списками. Если в других модулях больше скрываться, они могут появляться только от e8. Возможно, вам придется укусить пулю и сделать эту петлю вместо складки, но для начала, так как Block1024 - это пара, foldl' не делает много оценки "на лету" (если только анализатор строгости не имеет становятся значительно лучше). Попробуйте сделать это более строгим, data Block1024 = B1024 !Block512 !Block512, возможно, ему также нужны {-# UNPACK #-} прагмы. В roundFunction используйте rem вместо mod (это будет иметь незначительное влияние, но оно немного быстрее) и строгие привязки let. В функциях swapN вы можете получить лучшую производительность, дающую константы в форме W x y, а не как 128-битные шестнадцатеричные числа. Я не могу гарантировать, что эти изменения помогут, но это выглядит наиболее перспективным после короткого взгляда.

Ответ 3

Хорошо, поэтому я подумал, что буду переписываться с обновлением того, что я сделал, и результатами, полученными до сих пор. Сделанные изменения:

• Переключен из массива в UnboxedArray (сделал тип экземпляра Word128)
• Используется UnboxedArray + складывается в e8 вместо списков и (прелюдия) fold
• Использовать unsafeIndex вместо!
• Изменен тип Block1024 на реальный тип данных (аналогичный Block512) и распакован его аргументы
• Обновлен GHC до версии 7.2.1 на Arch Linux, тем самым устраняя проблему с компиляцией через C или LLVM
• Переключить модем в некоторых местах, но НЕ в roundFunction. Когда я это делаю, время компиляции внезапно занимает очень много времени, а время работы становится в 10 раз медленнее! Кто-нибудь знает, почему это может быть? Это происходит только с GHC-7.2.1, а не с GHC-7.0.3.

Я компилирую со следующими параметрами:

ghc-7.2.1 --make -O2 -funbox-strict-fields main.hs./Tests/testframe.hs -fvia-C -optc-O2

И результаты? Сокращение времени на 50%. На входе ~ 107 МБ код теперь использует 3 минуты по сравнению с предыдущими 6-7 минутами. Версия C использует 42 секунды.

Вещи, которые я пробовал, но которые не привели к лучшей производительности:

• Развернута функция e8 следующим образом:

  e8! h = go h 0

  где go! x! n

        | n == 42   = x
        | otherwise = go h' (n + 1)
        where !h' = roundFunction x n
  

• Попробовал разбить функции swapN для непосредственного использования базового Word64:

  swap1 (W xh hl) =

       shiftL (W (xh .&. 0x5555555555555555) (xl .&. 0x5555555555555555)) 1 
       .|. 
       shiftR (W (xh .&. 0xaaaaaaaaaaaaaaaa) (xl .&. 0xaaaaaaaaaaaaaaaa)) 1 
  

• Пробовал использовать бэкэнд LLVM

Все эти попытки дали худшую производительность, чем у меня в настоящее время. Я не знаю, если это потому, что я делаю это неправильно (особенно разворачивание e8), или потому, что они просто хуже.

Тем не менее у меня есть несколько новых вопросов с этими новыми настройками.

• Внезапно я получил эту особенность в использовании памяти. Взгляните на следующие профили кучи:

  Почему это произошло? Это из-за UnboxedArray? И что означает SYSTEM?

• Когда я скомпилирую через C, я получаю следующее предупреждение:

  Предупреждение: флаг -fvia-C ничего не делает; он будет удален в будущем выпуске GHC

  Это правда? Почему же тогда я вижу лучшую работу с ней, а не нет?

Ответ 4

Похоже, что вы уже много сделали для настройки; Мне любопытно, что такое производительность, без явных аннотаций строгости (BangPatterns) и различных прагм компиляторов (UNPACK, INLINE)... Кроме того, тупой вопрос: какие флаги оптимизации вы используете?

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

• Используйте unboxed примитивные типы, где вы можете (например, заменить Data.Word.Word64 на GHC.Word.Word64#, убедитесь, что word128Shift использует Int# и т.д.), чтобы избежать выделения кучи. Это, конечно, не переносится.
• Попробуйте Data.Sequence вместо []

Во всяком случае, вместо того, чтобы смотреть на вывод Core, попробуйте вместо этого посмотреть промежуточные файлы C (*.hc). Это может быть трудно проскочить, но иногда делает очевидным, где компилятор не был столь резким, как вы надеялись.