[haskell] Haskell 프로그램의 성능을 분석하기위한 도구

이 솔루션이 왜 그렇게 느린 지 알아내는 방법. 내 하스켈 프로그램의 어느 부분이 느린 지 알 수 있도록 대부분의 계산 시간이 어디에 소비되는지 알려주는 명령이 있습니까?

정확합니다! GHC는 다음을 포함한 많은 우수한 도구를 제공합니다.

• 런타임 통계
• 시간 프로파일 링
• 힙 프로파일 링
• 스레드 분석
• 핵심 분석.
• 비교 벤치마킹
• GC 튜닝

시간 및 공간 프로파일 링 사용에 대한 튜토리얼 은 Real World Haskell의 일부입니다 .

GC 통계

첫째, ghc -O2로 컴파일하고 있는지 확인하십시오. 최신 GHC (예 : GHC 6.12.x)인지 확인할 수 있습니다.

가장 먼저 할 수있는 일은 가비지 컬렉션이 문제가 아닌지 확인하는 것입니다. + RTS -s로 프로그램 실행

$ time ./A +RTS -s
./A +RTS -s
749700
   9,961,432,992 bytes allocated in the heap
       2,463,072 bytes copied during GC
          29,200 bytes maximum residency (1 sample(s))
         187,336 bytes maximum slop
               **2 MB** total memory in use (0 MB lost due to fragmentation)

  Generation 0: 19002 collections,     0 parallel,  0.11s,  0.15s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   13.15s  ( 13.32s elapsed)
  GC    time    0.11s  (  0.15s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   13.26s  ( 13.47s elapsed)

  %GC time       **0.8%**  (1.1% elapsed)

  Alloc rate    757,764,753 bytes per MUT second

  Productivity  99.2% of total user, 97.6% of total elapsed

./A +RTS -s  13.26s user 0.05s system 98% cpu 13.479 total

이미 많은 정보를 제공합니다. 힙이 2M에 불과하고 GC는 시간의 0.8 %를 차지합니다. 따라서 할당이 문제라고 걱정할 필요가 없습니다.

시간 프로필

프로그램의 시간 프로필을 얻는 것은 간단합니다. -prof -auto-all로 컴파일하십시오.

 $ ghc -O2 --make A.hs -prof -auto-all
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

N = 200의 경우 :

$ time ./A +RTS -p
749700
./A +RTS -p  13.23s user 0.06s system 98% cpu 13.547 total

다음을 포함하는 A.prof 파일을 만듭니다.

    Sun Jul 18 10:08 2010 Time and Allocation Profiling Report  (Final)

       A +RTS -p -RTS

    total time  =     13.18 secs   (659 ticks @ 20 ms)
    total alloc = 4,904,116,696 bytes  (excludes profiling overheads)

COST CENTRE          MODULE         %time %alloc

numDivs            Main         100.0  100.0

을 나타내는 모든 시간이 numDivs에서 소비되고, 그것은 또한 모든 할당의 원천입니다.

힙 프로필

또한 + RTS -p -hy를 실행하여 A.hp를 실행하여 이러한 할당을 분석 할 수도 있습니다. 그러면 A.hp를 포스트 스크립트 파일 (hp2ps -c A.hp)로 변환하여 볼 수 있습니다.

이것은 당신의 메모리 사용에 아무런 문제가 없다는 것을 말해줍니다 : 그것은 일정한 공간에 할당되고 있습니다.

따라서 문제는 numDivs의 알고리즘 복잡성입니다.

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

실행 시간의 100 % 인 문제를 해결하면 다른 모든 작업이 쉽습니다.

최적화

이 표현식은 스트림 융합 최적화에 적합한 후보 이므로 다음과 같이 Data.Vector 를 사용하도록 다시 작성하겠습니다 .

numDivs n = fromIntegral $
    2 + (U.length $
        U.filter (\x -> fromIntegral n `rem` x == 0) $
        (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))

불필요한 힙 할당없이 단일 루프로 융합되어야합니다. 즉, 목록 버전보다 더 복잡합니다 (일정한 요인에 의해). ghc-core 도구 (고급 사용자 용)를 사용하여 최적화 후 중간 코드를 검사 할 수 있습니다.

이것을 테스트, ghc -O2 –make Z.hs

$ time ./Z
749700
./Z  3.73s user 0.01s system 99% cpu 3.753 total

따라서 알고리즘 자체를 변경하지 않고도 N = 150의 실행 시간을 3.5 배 단축했습니다.

결론

문제는 numDivs입니다. 실행 시간의 100 %이며 끔찍한 복잡성이 있습니다. numDivs에 대해 생각해보십시오. 예를 들어 각 N에 대해 [2 .. n div2 + 1] N 번 생성하는 방법을 생각해보십시오 . 값이 변경되지 않으므로이를 메모 해보십시오.

어떤 함수가 더 빠른지 측정하려면 실행 시간의 마이크로 초 미만 개선에 대한 통계적으로 강력한 정보를 제공하는 기준 사용을 고려하세요 .

부록

numDivs는 실행 시간의 100 %이기 때문에 프로그램의 다른 부분을 만져도 큰 차이는 없지만 교육적 목적을 위해 스트림 융합을 사용하여 다시 작성할 수도 있습니다.

또한 trialList를 다시 작성하고 fusion을 사용하여 “prefix scan”기능 (scanl이라고도 함) 인 trialList2에서 직접 작성한 루프로 변환 할 수 있습니다.

triaList = U.scanl (+) 0 (U.enumFrom 1 top)
    where
       top = 10^6

sol의 경우 :

sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList

전체 실행 시간은 동일하지만 코드가 조금 더 깔끔합니다.

답변

triaList = 1 : zipWith (+) triaList [2..]

./program +RTS -P -sprogram.stats -RTS