Изменчивый (возможно параллельный) код на Haskell и настройка производительности

Question

У меня сейчас реализован еще один кандидат SHA3, а именно Grøstl. Это все еще в стадии разработки (очень много), но на данный момент 224-битная версия проходит все KAT. Так что теперь я задаюсь вопросом о производительности (снова: ->). Разница на этот раз в том, что я решил более точно отразить реализацию (оптимизированная) C , то есть я сделал порт из C в Haskell. Оптимизированная версия C использует поиск таблиц для реализации алгоритма. Кроме того, код в значительной степени основан на обновлении массива, содержащего 64-битные слова. Таким образом, я решил использовать изменяемые неупакованные векторы в Haskell.

Мой код Grøstl можно найти здесь: https://github.com/hakoja/SHA3/blob/master/Data/Digest/GroestlMutable.hs

Краткое описание алгоритма: это конструкция Меркле-Дамгарда, с итерацией функции сжатия ( f512M в моем коде) до тех пор, пока остаются 512-битные блоки сообщения. Функция сжатия очень проста: она просто запускает две разные независимые 512-битные перестановки P и Q ( permP и permQ в моем код) и объединяет их вывод. Это их перестановки, которые реализуются с помощью таблиц поиска.

Q1) Первое, что меня беспокоит, это то, что использование изменяемых векторов делает мой код действительно беспорядочным. Я впервые пишу какой-либо основной изменчивый код на Haskell, поэтому я не знаю, как это улучшить. Любые советы о том, как мне лучше структурировать монадический код, будут приветствоваться.

Q2) Второе - производительность. На самом деле это не так уж и плохо, потому что на данный момент код на Haskell медленнее всего в 3 раза. Использование GHC-7.2.1 и компиляция так:

ghc -O2 -Odph -fllvm -optlo-O3 -оптло-петля-уменьшить -оптло-петля-удаление

код Haskell использует 60-е годы. на входе ~ 1 ГБ, в то время как C-версия использует 21-22 с. Но есть некоторые вещи, которые я нахожу странными:

(1) Если я попытаюсь встроить rnd512QM , код займет в 4 раза больше времени, но если я встроу rnd512PM ничего бывает! Почему это происходит? Эти две функции практически идентичны!

(2) Возможно, это сложнее. Я экспериментировал с выполнением двух перестановок параллельно. Но в настоящее время безрезультатно. Это один из примеров того, что я пробовал:

f512 h m = V.force outP `par` (V.force outQ `pseq` (V.zipWith3 xor3 h outP outQ))
   where xor3 x1 x2 x3 = x1 `xor` x2 `xor` x3
         inP = V.zipWith xor h m
         outP = permP inP
         outQ = permQ m

При проверке статистики времени выполнения и использовании ThreadScope я заметил, что было создано правильное количество SPARKS, но практически ни одно из них не было фактически преобразовано в полезную параллельную работу. Таким образом, я ничего не получил в ускорении. Мой вопрос становится:

1. Функции P и Q слишком малы, чтобы среда выполнения не могла работать параллельно?
2. Если нет, неправильно ли я использую пар и pseq (и, возможно, Vector.Unboxed.force)?
3. Получу ли я что-нибудь, переключившись на стратегии? И как бы я поступил так?

Большое вам спасибо за ваше время.

EDIT:

Извините, что не предоставил никаких реальных тестов производительности. Тестовый код в репо был предназначен только для себя. Для тех, кто хочет протестировать код, вам нужно скомпилировать main.hs , а затем запустить его как:

. / Main "алгоритм" "testvariant" "выровненный байт"

Например:

. / Main groestl short224 False

или

. / Main groestl e False

( e расшифровывается как «Extreme». Это очень длинное сообщение, предоставляемое с NIST KATS).

Answer 1

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

1) Я почти уверен, что force не делает то, что вы хотите - это фактически вызывает копию основного вектора.

2) Я думаю, что использование unsafeThaw и unsafeFreeze довольно странно.Я бы просто поместил f512M в монаду ST и покончил с этим.Затем запустите его примерно так:

otherwise = \msg -> truncate G224 . outputTransformation . runST $ foldM f512M h0_224 (parseMessage dataBitLen 512 msg)

3) V.foldM' глупо - вы можете просто использовать обычный (строгий) foldM над списком - сворачивать вектор во втором аргументекажется, ничего не покупает.

4) Я сомневаюсь в ударах в columnM и в отношении unsafeReads.

Также ...

a) Я подозреваю, что ксероксирование незарегистрированных векторов может, вероятно,быть реализован на более низком уровне, чем zipWith, используя внутренние компоненты Data.Vector.

b) Однако, может быть, лучше этого не делать, поскольку это может помешать слиянию векторов.

в) При осмотре extractByte выглядит несколько неэффективно?Вместо того чтобы использовать fromIntegral для усечения, возможно, используйте mod или quot, а затем единственный fromIntegral, чтобы привести вас непосредственно к Int.

Answer 2

1. Обязательно скомпилируйте с -threaded -rtsopts и выполните с +RTS -N2.Без этого у вас не будет более одного потока ОС для выполнения вычислений.

2. Попробуйте запустить вычисления, на которые ссылаются в другом месте, в противном случае они могут быть собраны:

_

f512 h m = outP `par` (outQ `pseq` (V.zipWith3 xor3 h outP outQ))
   where xor3 x1 x2 x3 = x1 `xor` x2 `xor` x3
         inP = V.zipWith xor h m
         outP = V.force $ permP inP
         outQ = V.force $ permQ m

_

3) Если вы включите все так, чтобы parseBlock принимал строгие строки (или блоки и ленивые при необходимости), тогдаможно использовать Data.Vector.Storable и, возможно, избежать копирования.