Aunque tengo una buena implementación de LSFR C, pensé que intentaría lo mismo en Haskell, solo para ver cómo funciona. Lo que se me ocurrió, hasta ahora, es dos órdenes de magnitud más lento que la implementación de C, lo que plantea la pregunta:¿Cómo se puede mejorar el rendimiento? Claramente, las operaciones de violín de bits son el cuello de botella, y el perfilador lo confirma.

Aquí está el código de referencia de Haskell usando listas yData.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

Básicamente prueba si elLSFR definido entap :: [[Int]] para cualquier longitud de bits dada es de longitud máxima. (Más precisamente, solo verifica si el LSFR alcanza el estado inicial (cero) después de 2n iteraciones)

Según el perfilador, la línea más costosa es el bit de retroalimentaciónd0 = xor' $ map (testBit lfsr) tap'.

Lo que he probado hasta ahora:

utilizarData.Array: Intento abandonado porque no hay foldl / rutilizarData.Vector: Ligeramente más rápido que la línea de base

Las opciones del compilador que uso son:-O2, LTS Haskell 8.12 (GHC-8.0.2).

El programa de referencia C ++ se puede encontrar engist.github.com.

No se puede esperar que el código de Haskell (?) Se ejecute tan rápido como el código C, pero dos órdenes de magnitud es demasiado, debe haber una mejor manera de hacer el violín.

Actualización: resultados de la aplicación de las optimizaciones sugeridas en las respuestas

El programa de referencia C ++ con entrada 28, compilado con LLVM 8.0.0, se ejecuta en 0.67s en mi máquina (lo mismo con clang 3.7 es marginalmente más lento, 0.68s)El código de referencia de Haskell se ejecuta aproximadamente 100 veces más lento (debido a la ineficiencia del espacio, no lo intente con entradas mayores de 25)Con la reescritura de@Thomas M. DuBuisson, aún utilizando el backend GHC predeterminado, el tiempo de ejecución se reduce a 5.2sCon la reescritura de@Thomas M. DuBuisson, ahora usando el backend LLVM (opción GHC-O2 -fllvm), el tiempo de ejecución baja a 1.7sUsando la opción GHC-O2 -fllvm -optlc -mcpu=native trae esto a 0.73sSustitucióniterate coniterate' de @cirdec no hace ninguna diferencia cuando se usa el código de Thomas (ambos con el backend 'nativo' predeterminado y LLVM). De todos modos, esohace hacer una diferencia cuando se usa el código de línea base.

Entonces, hemos pasado de 100x a 8x a 1.09x, es decir, ¡solo un 9% más lento que C!

Nota El backend LLVM a GHC 8.0.2 requiere LLVM 3.7. En Mac OS X esto significa instalar esta versión conbrew y luego simularopt yllc. Ver7.10. Backends de GHC.