Perché l'aggiunta di una tilde davanti a un pattern match rallenta la mia funzione?

Question

Ho due funzioni definite in un pezzo di codice Haskell:

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

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

Quando entrambi provo in ghci (utilizzando :set +s), trovo che lengthwtilde (quello con una tilde davanti al pattern match) è notevolmente più lento di lengthwotilde di circa tre secondi.

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

Perché è questo?

Answer 1

L'aggiunta di uno ~ di fronte a una corrispondenza di modello rende tale corrispondenza irrefutabile. Si può pensare a ciò aggiungendo ulteriore pigrizia a un pattern, in modo che non fallisca mai la corrispondenza a meno che quella corrispondenza sia assolutamente necessaria per la valutazione. Ecco un semplice esempio:

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

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

Con il pattern match inconfutabile, anche se il pattern match non riesce in una lista vuota, in quanto non variabili legate vengono valutate, non c'è nessun errore. In sostanza, il pattern match inconfutabile trasforma la funzione di:

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

E 'questo involucro supplementare di pigrizia che rallenta la funzione lunghezza. Se si applica la stessa let-binding trasformare a lengthwtilde si ottiene

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

pensare a come questo viene valutato. Al livello più alto, ottieni 1+lengthwtilde xs. Ma xs non è nemmeno valutato, poiché è una variabile let-bound. Pertanto, nella fase successiva, il primo xs viene valutato per determinarne la corrispondenza con il secondo caso di lengthwtilde e il processo si ripete.

Contrasto a lengthwotilde. In questa funzione, l'atto di corrispondenza sul secondo caso della funzione impone anche l'argomento da valutare. Il risultato finale è lo stesso, ma è più efficiente essere in grado di scartarlo prima piuttosto che lasciare un altro thunk forzato.

Tecnicamente lengthwtilde è leggermente più complesso: l'argomento è già valutato nel secondo ramo in quanto questo è il modo determiniamo quale ramo ci troviamo, tuttavia esso viene ri-avvolto quando passa nella chiamata ricorsiva.

È utile poter vedere il core prodotto. Ecco l'output di lengthwotilde (prodotto da 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 

Nota la funzione lengthwotilde1_af2 immediatamente fa un case sull'argomento ds_dgd (questa è la lista di input), e quindi ricorsivamente all'interno del caso, formando un thunk (con qualche espansioni):

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

che richiede infine la valutazione di 1 + (1 + (1 + (1 + ..)))

Ecco 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 

La valutazione di questa forma un thunk diversa:

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

che si traduce poi nella stessa catena di aggiunte che hai la prima volta, ma con qualche extra logica per gestire i fallimenti irrefutabili del modello.

Ora, se stavi eseguendo codice compilato con qualsiasi ottimizzazione, ghc avrebbe quasi sicuramente notato che gli argomenti non potevano assolutamente essere nulli, dal momento che sono già stati valutati e noto per utilizzare il costruttore (:) a questo punto. E quando compilo il codice con ghc -O2 ed eseguirlo, entrambe le funzioni vengono eseguite nello stesso intervallo di tempo. Sono entrambi piuttosto cattivi, perché in entrambi i casi si ottiene una catena di thunk. La definizione standard di length è molto meglio, come sarebbe una buona definizione foldl'.