왜 엄격한 길이 함수가 현저하게 빠르게 수행됩니까?

Question

평가 모델을 더 잘 이해하기 위해 정의를 가지고 놀고 목록의 길이에 대해 두 개를 썼습니다.

순진 정의 :

len :: [a] -> Int 
len [] = 0 
len (_:xs) = 1 + len xs 

엄격한 (꼬리 재귀) 정의 :

slen :: [a] -> Int -> Int 
slen [] n = n 
slen (_:xs) !n = slen xs (n+1) 

len [1..10000000] 수행 5-6 초 정도 걸립니다.
slen [1..10000000] 0은 수행하는 데 약 3-4 초가 걸립니다.

이유가 궁금합니다. 공연을 확인하기 전에 나는 len에 최대로 평가할 수있는 썽크가 하나 밖에 없기 때문에 같은 것을 수행 할 것이라고 확신했습니다.

len [a,b,c,d] 
= 1 + len [b,c,d] 
= 1 + 1 + len [c,d] 
= 1 + 1 + 1 + len [d] 
= 1 + 1 + 1 + 1 + len [] 
= 1 + 1 + 1 + 1 + 0 
= 4 

그리고 눈에 띄게 빨라 slen하게 무엇

slen [a,b,c,d] 0 
= slen [b,c,d] 1 
= slen [c,d] 2 
= slen [d]  3 
= slen []  4 
= 4 

: 데모 목적을 위해?

P. 또한 tail-recursive lazy 함수 (그냥 slen와 같은)를 닫으려는 시도를했습니다. 어쩌면 tail-recursive 때문일 수도 있지만, 순진한 정의와 거의 동일하게 수행되었습니다.

Answer 1

len의 최종 단계는 O (1)가 아닙니다. n 개의 숫자를 더하는 것은 O (n)입니다. len도 O (n) 메모리를 사용하고 slen은 O (1) 메모리를 사용합니다.

O (n) 메모리를 사용하는 이유는 각 썽크가 일부 메모리를 사용한다는 것입니다. 이 같은 뭔가를 그래서 :

1 + 1 + 1 + 1 + len [] 

이 GHCi에서

(len [] 포함) 다섯 평가되지 않은 썽크가, 우리는 :sprint 명령을 좀 더 쉽게이 썽크 동작을 검사 할 수 있습니다. :sprint 명령은 썽크를 평가하지 않고 지정된 값을 인쇄합니다 (자세한 내용은 :help에서 알 수 있음). 우리는 consens ((:))를 사용할 것이므로 한 번에 각 썽크를 더 쉽게 평가할 수 있기 때문에 원칙은 동일합니다. 서로 내에 중첩 4 썽크 ([] 포함)에서의 각 부분에 대해 하나가 존재

λ> let ys = map id $ 1 : 2 : 3 : [] :: [Int] -- map id prevents GHCi from being too eager here 
λ> :sprint ys 
ys = _ 
λ> take 1 ys 
[1] 
λ> :sprint ys 
ys = 1 : _ 
λ> take 2 ys 
[1,2] 
λ> :sprint ys 
ys = 1 : 2 : _ 
λ> take 3 ys 
[1,2,3] 
λ> :sprint ys 
ys = 1 : 2 : 3 : _ 
λ> take 4 ys 
[1,2,3] 
λ> :sprint ys 
ys = [1,2,3] 

미 평가 썽크 _로 표현되며 원래의 ys 것을 알 수있다.

평가가 더 많거나 전혀 없기 때문에 이것을 Int에서 알 수있는 좋은 방법은 없지만 같은 방법으로 중첩 된 썽크를 계속 만듭니다. 이런 식으로 볼 수 있다면, 평가는 다음과 같이 보일 것입니다 :

len [a,b,c,d] 
= 1 + len [b,c,d] 
= 1 + 1 + len [c,d] 
= 1 + 1 + 1 + len [d] 
= 1 + 1 + 1 + 1 + len [] 
= 1 + 1 + 1 + 1 + 0 
= 1 + 1 + 1 + 1  -- Here it stops building the thunks and starts evaluating them 
= 1 + 1 + 2 
= 1 + 3 
= 4 

Answer 2

David Young의 대답은 평가 순서의 차이에 대한 올바른 설명을 제공합니다. Haskell 평가 방법에 대해 생각해야합니다.

코어의 차이를 어떻게 볼 수 있는지 보여 드리겠습니다. 평가가 명시적인 case 문으로 끝나기 때문에 실제로 최적화가 실행되면 더 눈에.니다. 전에 Core와 같이 해 본 적이 없다면, Reading GHC Core 주제에 대한 표준 질문을 참조하십시오.

ghc -O2 -ddump-simpl -dsuppress-all -ddump-to-file SO27392665.hs으로 코어 출력을 생성하십시오. GHC는 len과 slen을 재귀 적 "작업자"함수 인 $wlen 또는 $wslen과 비 재귀 "래퍼"함수로 나눕니다. 시간의 대부분은 "노동자"초점 그들에 재귀에서 소비되기 때문에 : $wlen 두 가지를 가지고있는 동안

Rec { 
$wlen 
$wlen = 
    \ @ a_arZ w_sOR -> 
    case w_sOR of _ { 
     [] -> 0; 
     : ds_dNU xs_as0 -> 
     case $wlen xs_as0 of ww_sOU { __DEFAULT -> +# 1 ww_sOU } 
    } 
end Rec } 

len 
len = 
    \ @ a_arZ w_sOR -> 
    case $wlen w_sOR of ww_sOU { __DEFAULT -> I# ww_sOU } 

Rec { 
$wslen 
$wslen = 
    \ @ a_arR w_sOW ww_sP0 -> 
    case w_sOW of _ { 
     [] -> ww_sP0; 
     : ds_dNS xs_asW -> $wslen xs_asW (+# ww_sP0 1) 
    } 
end Rec } 

slen 
slen = 
    \ @ a_arR w_sOW w1_sOX -> 
    case w1_sOX of _ { I# ww1_sP0 -> 
    case $wslen w_sOW ww1_sP0 of ww2_sP4 { __DEFAULT -> I# ww2_sP4 } 
    } 

당신은 $wslen는 하나의 case 것을 볼 수 있습니다. David의 대답을 살펴보면, $wlen에서 일어나는 일을 추적 할 수 있습니다. 바깥 쪽 목록 생성자 ([]/:)에 대한 사례 분석을 수행 한 다음 $wlen xs_as0 (즉 len xs)으로 재귀 호출을합니다.이 또한 case입니다. 즉 축적 된 썽크를 강요합니다.

$wslen에는 case 문만 있습니다. 재귀 분기에는 덩어리를 생성하지 않는 unboxed 덧셈 인 (+# ww_sP0 1)이 있습니다.

(참고 :.이 답변의 이전 버전이 -O와 GHC는 $wslen를 전문으로 할 수 있지만 $wlen는 언 박싱 Int#의를 사용하는 그런 경우가 아니라고 주장했다.)