하스켈 재귀리스트 최적화

Question

하스켈 최적화 질문 중 하나가 previous입니다. 나는, 재귀 적으로 많은 소개 하스켈 기사에있는 FIB를 기능과 유사한 목록을 생성해야합니다

generateSchedule :: [Word32] -> [Word32] 
generateSchedule blkw = take 80 ws 
    where 
    ws   = blkw ++ zipWith4 gen (drop 13 ws) (drop 8 ws) (drop 2 ws) ws 
    gen a b c d = rotate (a `xor` b `xor` c `xor` d) 1 

위의 기능은 나에게 가장 많은 시간과 ALLOC의 -consuming 함수로 잡았다. 프로파일 러는 나에게 다음과 같은 통계를 제공합니다

COST CENTRE  MODULE    %time %alloc ticks  bytes 
generateSchedule Test.Hash.SHA1  22.1 40.4 31  702556640 

내가 목록을 계산하는 언 박싱 벡터를 적용 생각하지만,리스트가 순환하기 때문에 그것을 할 수있는 방법을 알아낼 수 없습니다. 이것은 C에서 자연스러운 구현을 가지지 만, (변수 선언을 80 줄 언 롤링하고 쓰는 것 이외에) 이것을 더 빠르게 만들 방법은 없습니다. 어떤 도움이 필요합니까?

업데이트 : 실제로 도움이되는지 확인하기 위해 실제로 풀어 봤습니다. 코드는 here입니다. 그것은보기 흉하고 사실 더 느립니다.

COST CENTRE  MODULE    %time %alloc ticks  bytes 
generateSchedule GG.Hash.SHA1  22.7 27.6 40  394270592 

Answer 1

import Data.Array.Base 
import Data.Array.ST 
import Data.Array.Unboxed 

generateSchedule :: [Word32] -> UArray Int Word32 
generateSchedule ws0 = runSTUArray $ do 
    arr <- unsafeNewArray_ (0,79) 
    let fromList i [] = fill i 0 
     fromList i (w:ws) = do 
      unsafeWrite arr i w 
      fromList (i+1) ws 
     fill i j 
      | i == 80 = return arr 
      | otherwise = do 
       d <- unsafeRead arr j 
       c <- unsafeRead arr (j+2) 
       b <- unsafeRead arr (j+8) 
       a <- unsafeRead arr (j+13) 
       unsafeWrite arr i (gen a b c d) 
       fill (i+1) (j+1) 
    fromList 0 ws0 

는 목록에 해당하는 박스 없음 배열을 만들 것입니다. 목록 인수에 14 개 이상 80 개 이하의 항목이 들어 있다고 가정합니다. 그렇지 않으면 잘못 입력 된 것입니다. 난 항상 16 항목 (64 바이트), 그래서 당신을 위해 안전해야한다고 생각합니다. (하지만 중간 목록을 작성하는 대신 ByteString에서 직접 채우기를 시작하는 것이 좋습니다.)

해싱 라운드를하기 전에 이것을 엄격하게 평가하면 목록 구성과 해시 사이의 전환이 저장됩니다 게으른 구조 목록은 필요한 시간을 줄여야합니다. 박스 화되지 않은 배열을 사용하면 목록의 할당 오버 헤드를 피할 수 있으므로 속도가 향상 될 수 있습니다 (그러나 ghc의 할당자는 매우 빠르므로 그로부터 너무 많은 영향을 기대하지 마십시오).

해싱 라운드에서는 불필요한 경계 검사를 피하기 위해 unsafeAt array t을 통해 Word32을 필요로합니다.

부록 : 목록 작성을 푸시 은 각 wn에 강타를 넣는 것이 더 빠르지 만 잘 모르겠습니다. 이미 코드를 가지고 있기 때문에 강약을 추가하고 검사하는 것이 그리 큰 일이 아닙니다. 그렇습니까? 궁금해.

Answer 2

가변 배열을 사용하여 변경 가능하고 순수한 목록을 사용하는 중간 집을 얻을 수 있습니다. 재귀 적 정의의 이점을 얻지 만, 그 이유 때문에 목록보다 덜하지만 게으름과 복싱의 가격을 지불합니다. 강제 I가 -O2로 컴파일 된 코드

module Main where 
import Data.Bits 
import Data.List 
import Data.Word 
import qualified Data.Vector as LV 
import Data.Array.ST 
import Data.Array.Unboxed 
import qualified Data.Array as A 
import Data.Array.Base 
import Criterion.Main 

gen :: Word32 -> Word32 -> Word32 -> Word32 -> Word32 
gen a b c d = rotate (a `xor` b `xor` c `xor` d) 1 

gss blkw = LV.toList v 
    where v = LV.fromList $ blkw ++ rest 
      rest = map (\i -> gen (LV.unsafeIndex v (i + 13)) 
           (LV.unsafeIndex v (i + 8)) 
           (LV.unsafeIndex v (i + 2)) 
           (LV.unsafeIndex v i) 
        ) 
       [0..79 - 14] 

gss' blkw = A.elems v 
    where v = A.listArray (0,79) $ blkw ++ rest 
      rest = map (\i -> gen (unsafeAt v (i + 13)) 
           (unsafeAt v (i + 8)) 
           (unsafeAt v (i + 2)) 
           (unsafeAt v i) 
        ) 
       [0..79 - 14] 

generateSchedule :: [Word32] -> [Word32] 
generateSchedule blkw = take 80 ws 
    where 
    ws   = blkw ++ zipWith4 gen (drop 13 ws) (drop 8 ws) (drop 2 ws) ws 

gs :: [Word32] -> [Word32] 
gs ws = elems (generateSched ws) 

generateSched :: [Word32] -> UArray Int Word32 
generateSched ws0 = runSTUArray $ do 
    arr <- unsafeNewArray_ (0,79) 
    let fromList i [] = fill i 0 
     fromList i (w:ws) = do 
      unsafeWrite arr i w 
      fromList (i+1) ws 
     fill i j 
      | i == 80 = return arr 
      | otherwise = do 
       d <- unsafeRead arr j 
       c <- unsafeRead arr (j+2) 
       b <- unsafeRead arr (j+8) 
       a <- unsafeRead arr (j+13) 
       unsafeWrite arr i (gen a b c d) 
       fill (i+1) (j+1) 
    fromList 0 ws0 

args = [0..13] 

main = defaultMain [ 
     bench "list" $ whnf (sum . generateSchedule) args 
     ,bench "vector" $ whnf (sum . gss) args 
     ,bench "array" $ whnf (sum . gss') args 
     ,bench "uarray" $ whnf (sum . gs) args 
     ] 

및 -funfolding-use-threshold=256 다음 코드는 두 개의 지연 어레이 용액 (표준 배열을 사용하고, 벡터)뿐만 아니라 원래 목록 코드 및 상기 다니엘 가변 uarray 코드를 테스트 기준을 사용 많은 인라인. ,

benchmarking list 
mean: 8.021718 us, lb 7.720636 us, ub 8.605683 us, ci 0.950 
std dev: 2.083916 us, lb 1.237193 us, ub 3.309458 us, ci 0.950 

benchmarking vector 
mean: 6.829923 us, lb 6.725189 us, ub 7.226799 us, ci 0.950 
std dev: 882.3681 ns, lb 76.20755 ns, ub 2.026598 us, ci 0.950 

benchmarking array 
mean: 6.212669 us, lb 5.995038 us, ub 6.635405 us, ci 0.950 
std dev: 1.518521 us, lb 946.8826 ns, ub 2.409086 us, ci 0.950 

benchmarking uarray 
mean: 2.380519 us, lb 2.147896 us, ub 2.715305 us, ci 0.950 
std dev: 1.411092 us, lb 1.083180 us, ub 1.862854 us, ci 0.950 

는 너무 기본적인 프로파일을 실행 :

판단 기준 벤치 마크는 벡터 솔루션이 약간 더 나은 것을 증명하고 언 박싱 변경 가능한 솔루션이 여전히 압도적으로 승리 배열 솔루션 약간 더 나은 아직,하지만 게으른/박스형 배열 솔루션이 목록 솔루션보다 약간 좋았지 만, 박스 처리되지 않은 배열 방식보다 훨씬 심각하다는 것을 알게되었습니다.