у меня есть хорошая реализация LSFR C, я решил попробовать то же самое в Haskell - просто чтобы посмотреть, как это происходит. До сих пор я придумал, что на два порядка медленнее, чем реализация C, и возникает вопрос:Как можно улучшить производительность? Очевидно, что операции с битами являются узким местом, и профилировщик подтверждает это.

Вот базовый код на Haskell с использованием списков иData.Bits:

import           Control.Monad      (when)
import           Data.Bits          (Bits, shift, testBit, xor, (.&.), (.|.))
import           System.Environment (getArgs)
import           System.Exit        (exitFailure, exitSuccess)

tap :: [[Int]]
tap = [
    [],            [],            [],            [3, 2],
    [4, 3],        [5, 3],        [6, 5],        [7, 6],
    [8, 6, 5, 4],  [9, 5],        [10, 7],       [11, 9],
    [12, 6, 4, 1], [13, 4, 3, 1], [14, 5, 3, 1], [15, 14],
    [16,15,13,4],  [17, 14],      [18, 11],      [19, 6, 2, 1],
    [20, 17],      [21, 19],      [22, 21],      [23, 18],
    [24,23,22,17], [25, 22],      [26, 6, 2, 1], [27, 5, 2, 1],
    [28, 25],      [29, 27],      [30, 6, 4, 1], [31, 28],
    [32,22,2,1],   [33,20],       [34,27,2,1],   [35,33],
    [36,25],       [37,5,4,3,2,1],[38,6,5,1],    [39,35],
    [40,38,21,19], [41,38],       [42,41,20,19], [43,42,38,37],
    [44,43,18,17], [45,44,42,41], [46,45,26,25], [47,42],
    [48,47,21,20], [49,40],       [50,49,24,23], [51,50,36,35],
    [52,49],       [53,52,38,37], [54,53,18,17], [55,31],
    [56,55,35,34], [57,50],       [58,39],       [59,58,38,37],
    [60,59],       [61,60,46,45], [62,61,6,5],   [63,62]        ]

xor' :: [Bool] -> Bool
xor' = foldr xor False

mask ::  (Num a, Bits a) => Int -> a
mask len = shift 1 len - 1

advance :: Int -> [Int] -> Int -> Int
advance len tap lfsr
    | d0        = shifted
    | otherwise = shifted .|. 1
    where
        shifted = shift lfsr 1 .&. mask len
        d0 = xor' $ map (testBit lfsr) tap'
        tap' = map (subtract 1) tap

main :: IO ()
main = do
    args <- getArgs
    when (null args) $ fail "Usage: lsfr <number-of-bits>"
    let len = read $ head args
    when (len < 8) $ fail "No need for LFSR"
    let out = last $ take (shift 1 len) $ iterate (advance len (tap!!len)) 0
    if out == 0 then do
        putStr "OK\n"
        exitSuccess
    else do
        putStr "FAIL\n"
        exitFailure

В основном это проверяет, является лиLSFR определяется вtap :: [[Int]] для любой заданной длины битов имеет максимальную длину. (Точнее, он просто проверяет, достигает ли LSFR начального состояния (ноль) после 2n итераций.)

Согласно профилировщику самой дорогой строкой является бит обратной связиd0 = xor' $ map (testBit lfsr) tap'.

Что я пробовал до сих пор:

использованиеData.Array: Попытка прекращена, потому что нет фолд / риспользованиеData.Vector: Немного быстрее базовой линии

Опции компилятора, которые я использую:-O2, LTS Haskell 8.12 (GHC-8.0.2).

Справочную программу на C ++ можно найти наgist.github.com.

Нельзя ожидать, что код на Haskell (?) Будет работать так же быстро, как и код на C, но на два порядка это слишком много, поэтому должен быть лучший способ выполнить битовую обработку.

Обновление: результаты применения оптимизаций, предложенных в ответах

Эталонная программа C ++ с вводом 28, скомпилированная с LLVM 8.0.0, работает на моей машине за 0.67 с (то же самое с clang 3.7 немного медленнее, 0,68 с)Базовый код на Haskell работает примерно в 100 раз медленнее (из-за неэффективности пространства не пробуйте его с входными данными больше 25)С переписью@ Томас М. ДюбюссонПри использовании бэкэнда GHC по умолчанию время выполнения снижается до 5,2 с.С переписью@ Томас М. Дюбюссон, теперь с помощью бэкэнда LLVM (опция GHC-O2 -fllvm), время выполнения уменьшается до 1.7сИспользование опции GHC-O2 -fllvm -optlc -mcpu=native приносит это до 0,73 сЗаменаiterate сiterate' из @cirdec не имеет значения, когда используется код Томаса (как с «родным» внутренним интерфейсом по умолчанию, так и с LLVM). Тем не менее, этоделает иметь значение, когда используется базовый код.

Итак, мы выросли со 100х до 8х до 1,09х, то есть всего на 9% медленнее, чем С!

Заметка Бэкэнд LLVM для GHC 8.0.2 требует LLVM 3.7. В Mac OS X это означает установку этой версии сbrew а затем символические ссылкиopt а такжеllc, Увидеть7,10. GHC Backends.