Haskell Performance di Esempio

Question

ho questi tipi di base nel mio codice:

newtype Foo (m :: Factored) = Foo Int64 deriving (NFData) 

foo :: forall m . (Fact m) => Foo m -> Foo m 

class T t where t :: (Fact m) => t m -> t m 

instance T Foo where t = foo 

newtype Bar t (m :: Factored) = Bar (t m) deriving (NFData) 

bar :: (Fact m, T t) => Bar t m -> Bar t m 
bar (Bar v) = Bar $ t v 

(ignorare Fact e Factored per il momento). Sto analizzando il codice a diversi livelli, confrontando le prestazioni di foo, t e bar. Nei benchmark, t = foo e bar si applica solo t tramite newtype. Quindi il loro runtime dovrebbe essere essenzialmente identico, ma criterion segnala che foo prende 9,2ns, t prende circa il doppio di quello a 17,45 ns, e il numero bar prende un 268,1 n enorme.

Ho sperimentato con l'aggiunta di INLINABLE e anche un pragma SPECIALIZE, ma non stanno aiutando. Voglio credere che GHC abbia qualche sintassi/ottimizzazione/ecc magico che può essere coerentemente applicato per risolvere questi tipi di problemi di prestazioni. Ad esempio, ho visto casi in cui scrivere codice in stile point-free ha implicazioni drammatiche sulle prestazioni.

Il codice completo può essere trovato here. Prometto che non è intimidatorio. I moduli sono:

• Foo: definisce Foo, foo e T
• Bar: definisce Bar e bar
• FooBench: definisce un punto di riferimento per foo
• TBench: definisce un punto di riferimento per t
• BarBench: definisce un punto di riferimento per bar
• Principale: gestisce i tre parametri di riferimento
• scomposto: definisce Fact e Factored utilizzando singletons

maggior parte dei moduli sono minuscole; Ho definito i tre benchmark in file separati in modo da poter esaminare il loro nucleo. Ho generato il core per i tre moduli *Bench e li ho allineati il ​​meglio che potevo. Sono solo ~ 250 linee ciascuno, e le prime ~ 200 righe sono identiche, fino alla ridenominazione. Il problema è che non so cosa fare delle ultime 50 linee. L'(core) diff per FooBench vs TBench è here, il diff per TBench vs BarBench è here, e il diff per FooBench vs BarBench è here.

Solo alcune delle domande che ho:

1. Ad alto livello, qual è la differenza essenziale tra i file di base? Sto cercando qualcosa come "Qui puoi vedere che GHC non sta mettendo in riga la chiamata a x". Cosa dovrei cercare?

2. Cosa si può fare per far funzionare tutti e tre i benchmark in circa 9,2ns? Ottimizzazioni GHC? INLINE/INLINABLE pragmi? SPECIALIZE pragmi che mi sono perso?(Non è consentito specializzarsi per F128::Factored, nella mia libreria reale questo valore può essere reificato in fase di esecuzione.) Limitazione/ritardo dell'integrazione in una particolare fase?

Anche se sto cercando una soluzione reale per rendere i benchmark tutto veloce, è possibile che i trucchi che lavorano per questo esempio non scala alla mia vera biblioteca. Di conseguenza, sto anche cercando la spiegazione "di alto livello" sul perché una particolare tecnica dovrebbe funzionare.

Answer 1

In primo luogo, guardando bar:

bar :: (Fact m, T t) => Bar t m -> Bar t m 
bar (Bar v) = Bar $ t v 

possiamo scrivere questo senza bisogno l'argomento utilizzando coerce:

bar :: (Fact m, T t) => Bar t m -> Bar t m 
bar = (coerce :: (t m -> t m) -> Bar t m -> Bar t m) t 

questa (come avremmo speriamo) ottiene bar eseguendo la stessa t . (In effetti, il core per TBench e BarBench è esattamente lo stesso, escludendo le firme del tipo).

io non sono del tutto sicuro perché, ma utilizzando INLINE invece di INLINEABLE rende t e bar eseguire la stessa foo. Non sono un esperto, ma di solito è meglio usare INLINE per le piccole funzioni che sei sicuro di voler allineare.

Detto questo, penso che alcuni di questi problemi derivino dal modo in cui il criterio definisce i parametri di riferimento per bloccare gli imbrogli ghc. Ad esempio, la scrittura bench "Bar" $ nf (GHC.Magic.inline bar) x sul codice originale ha bar con lo stesso valore di foo. Sospetto che un programma "reale" non sarebbe così delicato.