ghci 컴파일러 최적화 : 두 번 아래의 간단한 코드에서

Question

, 이진 검색 트리에서 요소를 삭제하는 함수의 정의의 일부를 같은 매개 변수가있는 함수를 호출 :

deleteB x (Node n l r) | x == n = Node (leastB r) l (deleteB (leastB r) r) 

는 컴파일러가 코드를 최적화하지 그래서 그것이 한 번만 호출하는 것처럼 (최소 B r) :

deleteB x (Node n l r) | x == n = Node k l (deleteB k r) 
          where k = leastB r 

?

즉, 매개 변수 r이 함수 deleteB의 본문 내에서 변경되지 않았기 때문에 동일한 함수 (leastB)를 호출 한 결과가 다른 결과를 줄 수 없다는 것을 컴파일러에서 이해할 수 있습니까? 따라서 두 번 계산하는 것은 쓸모가 없다?

더 일반적으로 컴파일러가이 최적화를 수행하는지 또는 놀라운 stackoverflow가 존재하지 않는지에 대해 이해할 수 있습니까? 덕분에

Answer 1

GHC이 최적화를 수행하지 않습니다.

예를 들어

은, 하나는이 일정한 공간에서 실행되도록 기대, 같은 하스켈 같은 게으른 언어에

n = 1000000 
x = (length $ map succ [1..n], length $ map pred [1..n]) 

을 고려하십시오. 실제로 표현식 [1..n]을 생성하는 목록은 한 번에 하나의 요소를 생성해야합니다. map 때문에 succ/ pred의 영향을 받아 length으로 계산됩니다. (더 좋게도 length은 목록 요소를 강제하지 않으므로 succ과 pred은 전혀 계산되지 않습니다. 그런 다음 생성 된 요소를 가비지 수집 할 수 있으며 목록 생성기는 다음 요소를 생성 할 수 있습니다.실제 구현에서는 모든 단일 요소가 즉시 가비지 수집 될 것이라고 기대하지 않지만 가비지 수집기가 양호하면 언제든지 일정량 만 메모리에 저장해야합니다.

비교하여 쓰레기를 허용하지 않는

n = 1000000 
l = [1..n] 
x = (length $ map succ l, length $ map pred l) 

코드

"최적"은 x의 두 성분이 평가 될 때까지 l 요소를 수집한다. 따라서 목록을 한 번만 생성하지만 O ( n) 개의 단어가 전체 목록을 저장하는 데 사용됩니다. 이것은 최적화되지 않은 코드보다 성능이 떨어질 수 있습니다.

Answer 2

GHC가 실제로 무엇을했는지 알고 싶다면 "코어"출력을보고 싶습니다.

GHC는 매우 높은 수준의 당신의 하스켈 소스 코드를 받아, 더 낮은 수준의 언어의 순서로 변환 :

하스켈 ⇒ 코어 ⇒ STG ⇒ C − − ⇒ 어셈블리 언어 ⇒ 기계 코드

거의 모든 고급 최적화가 코어에서 발생합니다. 당신이 요구하는 것은 기본적으로 "공통 부분 식 제거"(CSE)입니다. 당신이 그것에 대해 생각한다면, 이것은 시간/공간 상충 관계입니다; 이전 결과를 저장하면 CPU 시간이 줄어들지 만 더 많은 RAM을 사용하게됩니다. 저장하려는 결과가 작 으면 (즉, 정수형),이 값어치가 있습니다. 결과가 방대하면 (즉, 방금로드 한 17GB 텍스트 파일의 전체 내용), 이것은 아마도 매우 나쁜 생각입니다.

GHC는 CSE를 수행하지 않는 경향이 있습니다 (⇒!). 그러나 확실하게 알고 싶다면, 특정 경우에, 프로그램이 실제로 컴파일 된 코어를보고 싶습니다. I 스위치는 --ddump-prep입니다. 항상 최적화 공간 현명하지 않기 때문에

http://www.haskell.org/ghc/docs/7.0.2/html/users_guide/options-debugging.html