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

Question

Я работаю над реализацией одного из кандидатов SHA3, JH.Я нахожусь в точке, где алгоритм проходит все KAT (известные тесты ответов), предоставленные NIST, и также сделал его экземпляром Crypto-API.Таким образом, я начал изучать его производительность.Но я совершенно новичок в Haskell и не знаю, на что обращать внимание при профилировании.

В данный момент мой код постоянно медленнее, чем эталонная реализация, написанная на C, с коэффициентом 10 для всех входных длин (код C находится здесь: http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_bitslice_ref64.h).

MyКод на Haskell находится здесь: https://github.com/hakoja/SHA3/blob/master/Data/Digest/JHInternal.hs.

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

Tue Oct 25 19:01 2011 Time and Allocation Profiling Report  (Final)

   main +RTS -sstderr -p -hc -RTS jh e False

total time  =        6.56 secs   (328 ticks @ 20 ms)
total alloc = 4,086,951,472 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

roundFunction                  Data.Digest.JHInternal  28.4   37.4
word128Shift                   Data.BigWord.Word128  14.9   19.7
blockMap                       Data.Digest.JHInternal  11.9   12.9
getBytes                       Data.Serialize.Get     6.7    2.4
unGet                          Data.Serialize.Get     5.5    1.3
sbox                           Data.Digest.JHInternal   4.0    7.4
getWord64be                    Data.Serialize.Get     3.7    1.6
e8                             Data.Digest.JHInternal   3.7    0.0
swap4                          Data.Digest.JHInternal   3.0    0.7
swap16                         Data.Digest.JHInternal   3.0    0.7
swap8                          Data.Digest.JHInternal   1.8    0.7
swap32                         Data.Digest.JHInternal   1.8    0.7
parseBlock                     Data.Digest.JHInternal   1.8    1.2
swap2                          Data.Digest.JHInternal   1.5    0.7
swap1                          Data.Digest.JHInternal   1.5    0.7
linearTransform                Data.Digest.JHInternal   1.5    8.6
shiftl_w64                     Data.Serialize.Get     1.2    1.1

Detailed breakdown omitted ...

Теперь быстро об алгоритме JH:

Это алгоритм хеширования, который состоит из функции сжатия F8, котораяповторяется до тех пор, пока существуют входные блоки (длиной 512 бит). Именно так работают функции SHA. Функция F8 состоит из функции E8, которая применяет функцию округления 42 раза. Сама функция округления состоит из трех частей: sbox, линейное преобразование и перестановка (в моем коде это называется swap).

Таким образом, вполне разумно, что большую часть времени проводят в роутере.nd функция.Тем не менее, я хотел бы знать, как можно улучшить эти детали.Например: функция blockMap - это просто служебная функция, отображающая функцию на элементы в четырех кортеже.Так почему же так плохо?Любые предложения будут приветствоваться, и не только по отдельным функциям, то есть, есть ли структурные изменения, которые вы бы сделали, чтобы улучшить производительность?

Я попытался посмотреть на вывод Core, но, к сожалению, это намного выше моегоголова.

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

РЕДАКТИРОВАТЬ:

Я забыл упомянутьмои настройки и сборки.Я запускаю его на компьютере x86_64 Arch Linux, GHC 7.0.3-2 (я думаю), с параметрами компиляции:

ghc --make -O2 -funbox-strict-fields

К сожалению , похоже, есть ошибка на платформе Linux при компиляции через C или LLVM, которая выдает мне ошибку:

Ошибка: выражение .size для XXXXне оценивается как постоянная

, поэтому я не смог увидеть эффект этого.

Answer 1

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

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

Answer 2

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

Answer 3

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

• Переключен с массива на UnboxedArray (сделал Word128 типом экземпляра)
• Использовал UnboxedArray + fold в e8 вместо списков и (прелюдии) fold
• Использовал unsafeIndex вместо!
• Изменил тип Block1024 на реальный тип данных (аналогично Block512) и распаковал его аргументы
• Обновлен GHC до версии 7.2.1 в Arch Linux, что устраняет проблему компиляции через C или LLVM
• Переключен мод на rem в некоторых местах, но НЕ в 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

  куда идти! 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), или потому что они просто худшие варианты.

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

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

   Почему это произошло? Это из-за UnboxedArray? А что означает СИСТЕМА?

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

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

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

Answer 4

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

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

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

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