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

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

Мой код на 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).

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

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

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

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

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

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

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

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

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