Dlaczego dodanie tyldy przed dopasowaniem wzoru spowolni moją funkcję?

Question

Mam dwie funkcje określone w kawałek kodu Haskell:

lengthwtilde [] = 0 
lengthwtilde ~(_:xs) = 1 + lengthwtilde xs 

lengthwotilde [] = 0 
lengthwotilde (_:xs) = 1 + lengthwotilde xs 

Kiedy je przetestować zarówno w ghci (używając :set +s), uważam, że lengthwtilde (jeden z tyldą przed meczu wzór) wykonuje znacznie wolniej niż lengthwotilde o około trzy sekundy.

*Main> lengthwtilde [1..10000000] 
10000000 
(19.40 secs, 1731107132 bytes) 
*Main> lengthwotilde [1..10000000] 
10000000 
(16.45 secs, 1531241716 bytes) 

Dlaczego tak jest?

Answer 1

Dodanie ~ przed dopasowaniem wzorców powoduje, że dopasowanie jest niezastąpione. Możesz myśleć o tym jako dodając dodatkowe lenistwo do wzoru, tak aby nigdy nie zawiodło, chyba że dopasowanie jest absolutnie wymagane do oceny. Oto prosty przykład:

Prelude> (\ (_:_) -> "non-empty") [] 
"*** Exception: <interactive>:2:2-23: Non-exhaustive patterns in lambda 

Prelude> (\ ~(_:_) -> "oops") [] 
"oops" 

Z niepodważalny wzór meczu, choć nie mecz wzór na pustą listę, ponieważ nie są oceniane zmienne bound, nie ma błędu. Zasadniczo, przemienia niepodważalny wzór mecz funkcję do:

\ xs -> let (_:_) = xs in "oops" 

Jest to dodatkowy owijania lenistwa który spowalnia funkcji długości. Jeśli stosuje się takie same niech wiążące przekształcić do lengthwtilde masz

lengthwtilde [] = 0 
lengthwtilde xs' = let (_:xs) = xs' in 1 + lengthwtilde xs 

Pomyśl o tym, jak to jest oceniany. Na najwyższym poziomie otrzymujesz 1+lengthwtilde xs. Ale xs nie jest nawet oceniany, ponieważ jest zmienną let-bound. Tak więc w następnym kroku najpierw oceniany jest xs, aby ustalić, że pasuje on do drugiego przypadku lengthwtilde, a proces się powtarza.

Porównaj to z lengthwotilde. W tej funkcji akt dopasowania w drugim przypadku funkcji wymusza również ocenę argumentu. Efekt końcowy jest taki sam, ale skuteczniej jest go rozwinąć wcześniej, niż zostawiać na siłę następny thunk.

Technicznie lengthwtilde jest nieco bardziej złożona: argument jest już oceniano w drugiej gałęzi, ponieważ to w jaki sposób określić, które jesteśmy w oddział, jednak zostaje ponownie owinięty kiedy przeszedł do rekurencyjnego wywołania.

Przydaje się możliwość zobaczenia wyprodukowanego rdzenia. Oto wyjście lengthwotilde (produkowany od ghc -O0:

Foo.lengthwotilde = 
    \ (@ t_afD) 
    (@ a_afE) 
    ($dNum_afF :: GHC.Num.Num a_afE) 
    (eta_B1 :: [t_afD]) -> 
    letrec { 
     lengthwotilde1_af2 [Occ=LoopBreaker] :: [t_afD] -> a_afE 
     [LclId, Arity=1] 
     lengthwotilde1_af2 = 
     \ (ds_dgd :: [t_afD]) -> 
      case ds_dgd of _ { 
      [] -> GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 0); 
      : ds1_dge xs_af1 -> 
       GHC.Num.+ 
       @ a_afE 
       $dNum_afF 
       (GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 1)) 
       (lengthwotilde1_af2 xs_af1) 
      }; } in 
    lengthwotilde1_af2 eta_B1 

Uwaga Funkcja lengthwotilde1_af2 natychmiast robi case na argumencie ds_dgd (jest to lista wejście), a następnie recurses wewnątrz obudowy, tworząc thunk (niektóre rozszerzenia):

1 + len [2..] 
1 + (1 + len [3..]) 
1 + (1 + (1 + len [4..]) 

która ostatecznie wymaga oceny 1 + (1 + ((1 + 1 + ..)))

Oto lengthwtilde

Foo.lengthwtilde = 
    \ (@ t_afW) 
    (@ a_afX) 
    ($dNum_afY :: GHC.Num.Num a_afX) 
    (eta_B1 :: [t_afW]) -> 
    letrec { 
     lengthwtilde1_afM [Occ=LoopBreaker] :: [t_afW] -> a_afX 
     [LclId, Arity=1] 
     lengthwtilde1_afM = 
     \ (ds_dgh :: [t_afW]) -> 
      case ds_dgh of wild_X9 { 
      [] -> GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 0); 
      : ipv_sgv ipv1_sgw -> 
       GHC.Num.+ 
       @ a_afX 
       $dNum_afY 
       (GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 1)) 
       (lengthwtilde1_afM 
        (case wild_X9 of _ { 
         [] -> 
         (Control.Exception.Base.irrefutPatError 
          @() "foo.hs:(3,1)-(4,42)|(_ : xs)") 
         `cast` (UnsafeCo() [t_afW] ::() ~# [t_afW]); 
         : ds1_dgk xs_aeH -> xs_aeH 
        })) 
      }; } in 
    lengthwtilde1_afM eta_B1 

ocena ta tworzy inny thunk:

len [1..] 
1 + (len (if null [1..] then error else [2..])) 
1 + (len [2..]) 
1 + (1 + len (if null [2..] then error else [3..])) 

co ostatecznie prowadzi do tego samego łańcucha dodatków jakie zostały po raz pierwszy, ale z kilku dodatkowych logika do obsługi niepowstrzymanych błędów wzorca.

Teraz, jeśli używasz skompilowanego kodu z dowolnymi optymalizacjami, ghc prawie na pewno zauważy, że argumenty nie mogą mieć wartości NULL, ponieważ są już ocenione i są znane z tego, że używają konstruktora (:). A kiedy skompiluję kod za pomocą ghc -O2 i uruchomię, obie funkcje będą wykonywane w tym samym czasie. Obaj są dość źli, ponieważ w obu wypadkach dochodzi do łańcucha kłaków. Standardowa definicja length jest znacznie lepsza, jak na dobrą definicję foldl'.