Quali sono le buone euristiche per le funzioni di inlining?

Question

Considerando che si sta tentando esclusivamente di ottimizzare per la velocità, quali sono le migliori euristiche per decidere se integrare o meno una funzione? Ovviamente la dimensione del codice dovrebbe essere importante, ma ci sono altri fattori tipicamente usati quando (per esempio) gcc o icc sta determinando se in linea una chiamata di funzione? C'è stato qualche lavoro accademico significativo nell'area?

Answer 1

Wikipedia ha afew paragrafi su questo, con alcuni link in fondo:

• Oltre alla dimensione della memoria e problemi di cache, another consideration is register pressure. Dal punto di vista del compilatore "le variabili aggiunte dalla procedura inline possono consumare registri aggiuntivi, e in un'area in cui la pressione del registro è già elevata, questo potrebbe forzare lo spargimento, che causa ulteriori accessi alla RAM."

Linguaggi con compilatori JIT e classe runtime loading hanno altre compromessi poiché i metodi virtuali non sono noti staticamente, ancora JIT può raccogliere runtime profiling informazioni, come la frequenza metodo di chiamata:

• Design, Implementation, and Evaluation of Optimizations in a Just-in-Time Compiler (per Java) parla dell'integrazione dei metodi statici e delle classi caricate dinamicamente e dei suoi miglioramenti sulle prestazioni.

• Practicing JUDO: Java Under Dynamic Optimizations rivendicazioni che la loro "politica inlining si basa sulla dimensione del codice e informazioni di profilatura. Se la frequenza di esecuzione di una voce metodo è sotto una certa soglia, il metodo è quindi non inlined perché è considerato come un metodo a freddo Per evitare l'esplosione del codice, non si incorpora un metodo con una dimensione bytecode di oltre 25 byte. Per evitare l'inline lungo una catena di chiamate profonde, l'inlining si interrompe quando la dimensione del byte byte accumulata lungo la catena di chiamate supera i 40 byte. " Sebbene abbiano informazioni di profilazione di runtime (frequenza di chiamata del metodo), sono ancora attenti a evitare di incorporare funzioni di grandi dimensioni o catene di funzioni per impedire che si verifichino.

A search on Google Scholar rivela una serie di documenti, come ad esempio

• The effect of code expanding optimizations on instruction cache design
• Function Inlining under Code Size Constraints for Embedded Processors

A search on Google Books rivela un certo numero di libri con le carte o capitoli sulla funzione inlining in vari contesti .

• The Compiler Design Handbook: Optimizations and Machine Code Generation ha un capitolo sulle tecniche Statisical e Machine Learning in Compiler design, con l'euristica per impostare vari parametri, profilazione dei risultati. Questo capitolo fa riferimento al Vaswani et al paper Microarchitecture Sensitive Empirical Models for Compiler Optimizations dove propongono "l'uso della modellazione empirica tecniche per la costruzione di modelli sensibili alla microarchitettura per le ottimizzazioni del compilatore".

• (Alcuni altri libri parlano di inling dal punto di vista del programmatore, come ad esempio C++ for Game Programmers, che parla dei pericoli di funzioni inline troppo spesso e le differenze tra inline e le macro. Compilatori spesso ignorano le richieste in linea del programmatore se in grado di determinare che avrebbero fatto più male che bene, questo può essere sovrascritto con le macro come ultima risorsa)

Answer 2

Una chiamata di funzione implica un codice aggiuntivo (il prologo della funzione, in cui è impostato il nuovo frame dello stack e l'epilogo della funzione, in cui è stato ripulito). Se il tuo compilatore vede che il codice della funzione è piccolo rispetto al prologo e all'epilogo, può decidere che non vale la pena effettuare una chiamata effettiva e in linea la funzione.

L'unico vantaggio che vedo di chiamare una funzione invece di inlining è relativo alla dimensione. Immagino che inlining una funzione quindi srotolare un ciclo può comportare un aumento significativo delle dimensioni.

Answer 3

per quanto ho visto, la dimensione della funzione è l'unico fattore di compilazione utilizzato per determinare in linea. Tuttavia, se si esegue l'ottimizzazione guidata del profilo (PGO), credo che il compilatore sia in grado di utilizzare altre variabili, come il numero di chiamate/il tempo di impostazione della chiamata.

Answer 4

In .NET è principalmente basato sulla dimensione. Misurare le dimensioni della funzione genitore e della funzione figlio in byte compilati. Quindi misurare le dimensioni della funzione combinata. Se la funzione combinata è più piccola, l'inlining è una buona idea.

La ragione di ciò è di rendere possibile inserire più codice nella cache della CPU il più possibile. Le carenze di cache sono molto più costose delle chiamate di funzione nelle moderne CPU.