Ottimizzazione calcolo parziale in Haskell

Question

Sono curioso come ottimizzare questo codice:

fun n = (sum l, f $ f0 l, g $ g0 l) 
    where l = map h [1..n] 

Supponendo che f, f0, g, g0 e h sono tutti costosi, ma la creazione e lo stoccaggio di l è estremamente costoso.

Come scritto, l viene memorizzato fino a quando la tupla restituita è completamente valutata o raccolta dati inutili. Invece, length l, f0 l e g0 l devono essere tutti eseguiti ogni volta che uno di essi viene eseguito, ma f e g devono essere ritardati.

Sembra questo comportamento poteva essere risolto scrivendo:

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

O il molto simile:

fun n = (a,b,c) `deepSeq` (a, f b, g c) 
    where ... 

Potremmo forse indicare una serie di tipi di interni per ottenere gli stessi effetti pure, che sembra doloroso. Ci sono altre opzioni?

Inoltre, sto ovviamente sperando con i miei inline s che il compilatore fusibili sum, f0, e g0 in un unico ciclo che costruisce e consuma l termine a termine. Potrei renderlo esplicito attraverso l'inlining manuale, ma quello farebbe schifo. Esistono modi per impedire esplicitamente che l'elenco l venga creato e/o forzato l'inlining? Direttive che producono avvertimenti o errori se l'inlining o la fusione falliscono durante la compilazione forse?

Per inciso, io sono curioso di sapere il motivo per cui seq, inline, lazy, ecc sono tutti definito dal let x = x in x nel preludio. È semplicemente per dare loro una definizione per il compilatore di scavalcare?

Answer 1

Se si vuole essere sicuri, l'unico modo è farlo da soli. Per qualsiasi versione del compilatore specificata, puoi provare diverse formulazioni di origine e controllare il core/assembly/llvm byte-code generato/qualunque sia l'azione che desideri. Ma questo potrebbe rompersi con ogni nuova versione del compilatore.

Se si scrive

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

o la versione deepseq della stessa, il compilatore potrebbe essere in grado di unire i calcoli di a, b e c da eseguire in parallelo (non nel senso concorrenza) nel corso di un singolo traversal of l, ma per il momento sono piuttosto convinto che GHC non lo sia, e sarei sorpreso se JHC o UHC lo facessero. E per questo la struttura di calcolo b e c deve essere abbastanza semplice.

L'unico modo per ottenere portabilmente il risultato desiderato tra compilatori e versioni del compilatore è farlo da soli. Per i prossimi anni, almeno.

seconda f0 e g0, potrebbe essere semplice come fare una piega rigida sinistra con un'appropriata accumulatore e la funzione di combinazione, come la media famoso

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Double 

average :: [Double] -> Double 
average = ratio . foldl' count (P 0 0) 
    where 
    ratio (P n s) = s/fromIntegral n 
    count (P n s) x = P (n+1) (s+x) 

ma se la struttura di f0 e/o g0 non si adatta, diciamo che una è una piega a sinistra e l'altra una piega a destra, potrebbe essere impossibile eseguire il calcolo in una traversata. In questi casi, la scelta è tra ricreare l e memorizzare l. Memorizzare l è facile da ottenere con la condivisione esplicita (where l = map h [1..n]), ma ricreare potrebbe essere difficile da ottenere se il compilatore esegue qualche eliminazione di sottoespressione comune (sfortunatamente, GHC ha la tendenza a condividere liste di quel modulo, anche se fa poco CSE). Per GHC, le bandiere fno-cse e -fno-full-laziness possono aiutare a evitare la condivisione indesiderata.