구현

Question

을 treap 개선하는 것은 여기 (암시 적 키와 노드에 포함 할 몇 가지 추가 정보) treap의 종류의 내 구현의 : 데이터 GC 프로파일에 따르면 http://hpaste.org/42839/treap_with_implicit_keys

이 프로그램 시간의 80 %를합니다. 내가 아는 한, 노드가 '수정'될 때마다 루트 경로의 각 노드가 다시 생성된다는 사실이 원인입니다.

여기 성능 향상을 위해 할 수있는 일이 있습니까, 아니면 ST 모나드의 영역으로 내려 가야합니까?

Answer 1

GHC 7.0.3을 사용하여, 나는 무거운 GC의 동작을 재현 할 수 있습니다

$ time ./A +RTS -s 
    %GC time  92.9% (92.9% elapsed) 
    ./A +RTS -s 7.24s user 0.04s system 99% cpu 7.301 total 

내가이 프로그램을 통해가는 10 분을 보냈다. 여기에 내가 위해, 무슨 짓을했는지 :

• 설정 GHC의 -H 플래그는 GC에 한계를 증가
• 는 1 세대 할당 영역을 조정
• 를 인라인 개선 풀고 확인

결과적으로 10 배의 속도 향상, GC는 약 45 %의 시간 증가를 가져옵니다. 위해

---

, GHC의 마법 -H 플래그를 사용하여, 우리는 그 실행 시간을 상당히 줄일 수 있습니다 : 나쁜

$ time ./A +RTS -s -H 
    %GC time  74.3% (75.3% elapsed) 
    ./A +RTS -s -H 2.34s user 0.04s system 99% cpu 2.392 total 

을!

Tree 노드의 UNPACK pragma는 아무 것도하지 않으므로 제거하십시오. 우리는 할당을 테스트하고 있기 때문에, 결국 -이 빠른 반면, GC는 여전히 압도하지 그래서 height

./A +RTS -s -H 1.74s user 0.03s system 99% cpu 1.777 total 

를 인라인으로

./A +RTS -s -H 1.84s user 0.04s system 99% cpu 1.883 total 

:

인라인 update 더 런타임을 면도 .

./A +RTS -s -A100M 0.74s user 0.09s system 99% cpu 0.826 total 

, 우리가 시작보다 10 배 빠른 무엇 인, JohnL이 제안,

$ time ./A +RTS -s -A200M 
%GC time  45.1% (40.5% elapsed) 
./A +RTS -s -A200M 0.71s user 0.16s system 99% cpu 0.872 total 

그리고 전개 임계 값을 증가 조금 도움 : 우리가 할 수있는 것은 첫 번째 세대의 크기를 증가입니다 ? 나쁘지 않다. ghc-gc-tune를 사용

---

, 당신은 흥미롭게도

는 최고의 실행 시간이 예를 들어, 매우 큰 -A 값을 사용 -A 및 -H의 함수로 런타임을 볼 수 있습니다

$ time ./A +RTS -A500M 
./A +RTS -A500M 0.49s user 0.28s system 99% cpu 0.776s