Riscrittura come tecnica di ottimizzazione pratica in GHC: è davvero necessaria?

Question

Stavo leggendo il documento scritto da Simon Peyton Jones, et al. chiamato “Playing by the Rules: Rewriting as a practical optimization technique in GHC”. Nella seconda sezione, cioè “ L'idea di base ” scrivono:

consideri la funzione map familiare, che applica una funzione per ogni elemento di una lista. Scritto in Haskell, map assomiglia a questo:

map f []  = [] 
map f (x:xs) = f x : map f xs 

Supponiamo ora che il compilatore incontra la seguente chiamata di map:

map f (map g xs) 

Sappiamo che questa espressione è equivalente a

map (f . g) xs 

(dove “. ” è la composizione della funzione) e sappiamo che quest'ultima espressione è più efficiente della prima perché non esiste una lista intermedia. Ma il compilatore non ha tale conoscenza.

Una possibile controreplica è che il compilatore dovrebbe essere più intelligente --- ma il programmatore saprà sempre cose che il compilatore non riesce a capire. Un altro suggerimento è questo: consentire al programmatore di comunicare tale conoscenza direttamente al compilatore. Questa è la direzione che esploriamo qui.

La mia domanda è, perché non possiamo rendere il compilatore più intelligente? Gli autori dicono che “ ma il programmatore saprà sempre cose che il compilatore non riesce a capire ”. Tuttavia, questo non è una risposta valida perché il compilatore può infatti capire che map f (map g xs) è equivalente a map (f . g) xs, ed ecco come:

map f (map g xs) 

1. map g xs unifica con map f [] = [].

   Quindi map g [] = [].

2. map f (map g []) = map f [].

   map f [] unifica con map f [] = [].

   Quindi map f (map g []) = [].

3. map g xs unifica con map f (x:xs) = f x : map f xs.

   Quindi map g (x:xs) = g x : map g xs.

4. map f (map g (x:xs)) = map f (g x : map g xs).

   map f (g x : map g xs) unifica con map f (x:xs) = f x : map f xs.

   Quindi map f (map g (x:xs)) = f (g x) : map f (map g xs).

Quindi ora abbiamo delle regole:

map f (map g [])  = [] 
map f (map g (x:xs)) = f (g x) : map f (map g xs) 

Come si può vedere f (g x) è solo (f . g) e map f (map g xs) viene chiamato in modo ricorsivo. Questa è esattamente la definizione di map (f . g) xs. L'algoritmo per questa conversione automatica sembra essere piuttosto semplice. Quindi, perché non implementare questo invece di regole di riscrittura?

Answer 1

L'inlining aggressivo può derivare molte delle uguaglianze per cui le regole di riscrittura sono a disposizione. Le differenze sono che l'inlining è "cieco", quindi non si sa in anticipo se il risultato sarà migliore o peggiore, o anche se terminerà.

Le regole di riscrittura, tuttavia, possono fare cose completamente non ovvie, basate su fatti di livello molto più elevato sul programma. Pensa a riscrivere le regole aggiungendo nuovi assiomi all'ottimizzatore. Aggiungendo questi si ha un set di regole più ricco da applicare, rendendo più facili da applicare le ottimizzazioni complicate.

Stream fusion, ad esempio, modifica la rappresentazione del tipo di dati. Questo non può essere espresso tramite l'inlining, in quanto comporta un cambio di tipo di rappresentazione (si rifà il problema di ottimizzazione in termini di ADT Stream). Facile da dichiarare nelle regole di riscrittura, impossibile con l'inlining da solo.

Answer 2

Qualcosa in quella direzione è stato esaminato in una tesi di laurea di Johannes Bader, uno dei miei studenti: Finding Equations in Functional Programs (PDF file).

In un certo senso è certamente possibile, ma

• è abbastanza difficile. Trovare tali equazioni è in un certo senso difficile come trovare prove in un proofer di teoremi, e
• non è spesso molto utile, perché tende a trovare equazioni che il programmatore scriverebbe raramente direttamente.

È tuttavia utile pulire dopo altre trasformazioni come l'inlining e varie forme di fusione.

Answer 3

Questo potrebbe essere considerato come un equilibrio tra il bilanciamento delle aspettative nel caso specifico e il bilanciamento nel caso generale. Questo equilibrio può generare situazioni divertenti in cui puoi sapere come fare qualcosa più velocemente, ma è meglio per la lingua in generale, se non lo fai.

Nel caso specifico di mappe nella struttura fornita, il computer potrebbe trovare ottimizzazioni. Tuttavia, che dire delle strutture correlate? Cosa succede se la funzione non è una mappa? Cosa succede se c'è un ulteriore livello di riferimento indiretto, come una funzione che restituisce la mappa. In questi casi, il compilatore non può ottimizzare facilmente. Questo è il problema generale.

Come se si fa ottimizzare il caso particolare, uno dei due risultati si verifica

• Nessuno si basa su di esso, perché non sono sicuro se è o no.In questo caso, articoli come quello che viene citato vengono scritti
• Le persone iniziano a fare affidamento su di esso, e ora ogni sviluppatore è costretto a ricordare "le mappe fatte in questa configurazione vengono convertite automaticamente nella versione veloce per me, ma se lo faccio non in questa configurazione. " Questo inizia a manipolare il modo in cui le persone usano la lingua e può ridurre la leggibilità!

Data la necessità per gli sviluppatori di pensare a tali ottimizzazioni nel caso generale, ci aspettiamo di vedere gli sviluppatori fare queste ottimizzazioni nel caso semplice , diminuendo la necessità di ottimizzare in primo luogo!

Ora, se si scopre che il caso particolare che è interessato rappresenta qualcosa di enorme come il 2% del codice base mondiale in Haskell, ci sarebbe un molto più forte argomento per applicare l'ottimizzazione del tuo caso speciale