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

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

Мой код Грёстля можно найти здесь: https://github.com/hakoja/SHA3/blob/master/Data/Digest/GroestlMutable.hs

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

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

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

ghc -O2 -Odph -fllvm -optlo-O3 -optlo-loop-reduce -optlo-loop-deletion

, код 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. Если нет, то использую ли я par и pseq (и, возможно, Vector.Unboxed.force) неправильно?
3. Получу ли я что-нибудь, переключившись на стратегии? И как мне это сделать?

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

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

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

./ main "algorithm" "testvariant" "byte bound"

Для Пример:

./ main groestl short224 False

или

./ main groestl e False

( e означает «Extreme». Это очень длинное сообщение, поставляемое с NIST КАЦ).