Perché l'ottimizzazione dell'Lua ha migliorato le prestazioni?

Question

Sto esaminando un codice di script document that describes various techniques to improve performance of Lua e sono scioccato dal fatto che sarebbero necessari trucchi del genere. (Anche se sto citando Lua, ho visto simili hack in Javascript). Perché sarebbe necessario

questa ottimizzazione:

Per esempio, il codice

for i = 1, 1000000 do 
    local x = math.sin(i) 
end 

gestisce il 30% più lento di questo:

local sin = math.sin 
for i = 1, 1000000 do 
    local x = sin(i) 
end 

Sono re -declarare la funzione sin localmente.

Perché questo sarebbe utile? È compito del compilatore farlo comunque. Perché il programmatore deve eseguire il lavoro del compilatore?

Ho visto cose simili in Javascript; e così ovviamente ci deve essere un buon motivo per cui il compilatore di interpretazioni non sta facendo il suo lavoro. Che cos'è?

---

Lo vedo ripetutamente nell'ambiente Lua in cui sto giocando; persone redeclaring variabili come locali:

local strfind = strfind 
local strlen = strlen 
local gsub = gsub 
local pairs = pairs 
local ipairs = ipairs 
local type = type 
local tinsert = tinsert 
local tremove = tremove 
local unpack = unpack 
local max = max 
local min = min 
local floor = floor 
local ceil = ceil 
local loadstring = loadstring 
local tostring = tostring 
local setmetatable = setmetatable 
local getmetatable = getmetatable 
local format = format 
local sin = math.sin 

Che cosa sta succedendo qui che le persone devono fare il lavoro del compilatore? Il compilatore è confuso da come trovare format? Perché questo è un problema che un programmatore deve affrontare? Perché questo non sarebbe stato curato nel 1993?

---

Mi sembra anche di aver colpito un paradosso logico:

1. ottimizzazione non dovrebbe essere fatto senza profilatura
2. Lua non ha possibilità di essere profilato
3. Lua non deve essere ottimizzato

Answer 1

perché questo sarebbe utile? È compito del compilatore farlo comunque. Perché il programmatore deve eseguire il lavoro del compilatore?

Lua è un linguaggio dinamico. I compilatori possono fare molti ragionamenti in linguaggi statici, come estrarre le espressioni costanti dal ciclo. Nelle lingue dinamiche, la situazione è leggermente diversa.

La struttura dati principale di Lua (e anche solo) è la tabella. math è anche solo una tabella, anche se qui è usato come spazio dei nomi. Nessuno può impedirti di modificare la funzione math.sin da qualche parte nel ciclo (anche se pensavo che sarebbe stata una cosa poco sagge da fare), e il compilatore non può saperlo durante la compilazione del codice. Pertanto, il compilatore fa esattamente ciò che gli si impone di fare: in ogni iterazione del ciclo, cercare la funzione sin nella tabella math e chiamarla.

Ora, se si sa che non si ha intenzione di modificare math.sin (vale a dire che si sta per chiamare la stessa funzione), è possibile salvarlo in una variabile locale al di fuori del ciclo. Perché non ci sono ricerche di tabelle, il codice risultante è più veloce.

La situazione è un po 'diverso con LuaJIT - usa tracciamento e qualche magia avanzata per vedere che cosa il vostro codice sta facendo in runtime, in modo che possa realmente di ottimizzare il ciclo spostando l'espressione al di fuori del ciclo, e gli altri ottimizzazioni, oltre a compilarlo effettivamente al codice macchina, rendendolo follemente veloce.

Per quanto riguarda la "ridichiarazione delle variabili come locale", molte volte quando si definisce un modulo, si desidera lavorare con la funzione originale. Quando si accede a pairs, max oa qualcosa che utilizza le loro variabili globali, nessuno può assicurare che sarà la stessa funzione per ogni chiamata. Ad esempio, stdlib ridefinisce molte funzioni globali.

Creando una variabile locale con lo stesso nome del globale, si memorizza essenzialmente la funzione in una variabile locale, e poiché le variabili locali (che sono lessicalmente con scope, ovvero sono visibili nell'ambito corrente e anche in tutti gli ambiti annidati) avere la precedenza sulle globali, assicurati di chiamare sempre la stessa funzione. Qualcuno dovrebbe modificare il globale in un secondo momento, non influenzerà il tuo modulo. Per non dire che è anche più veloce, perché i globals sono cercati in una tabella globale (_G).

Aggiornamento: Ho appena letto Lua Performance Tips di Roberto Ierusalimschy, uno degli autori Lua, e spiega praticamente tutto quello che c'è da sapere su Lua, le prestazioni e l'ottimizzazione. IMO le regole più importanti sono:

Regola # 1: non lo fanno.

Regola # 2: Non farlo ancora. (Solo per esperti)

Answer 2

La mia ipotesi è che nella versione ottimizzata, perché il riferimento alla funzione è memorizzato in un locale variabile, non è necessario eseguire un tree traversal ad ogni iterazione del ciclo for (per la ricerca su math.sin).

Non sono sicuro dei riferimenti locali impostati sui nomi di funzione, ma suppongo che sia necessaria una sorta di ricerca dello spazio dei nomi globale se non viene trovato uno locale.

Poi di nuovo, potrebbe essere lontano di base;)

Edit: Suppongo inoltre che il compilatore Lua è muto (che è un presupposto generale per me su compilatori comunque;))

Answer 3

funzioni Memorizzazione nelle variabili locali rimuove l'indicizzazione della tabella per cercare la chiave di funzione ogni iterazione del ciclo, quelle matematiche sono ovvie, poiché ha bisogno di cercare l'hash nella tabella Math, le altre no, sono indicizzate nello _G (tabella globale), che ora è _ENV (tabella dell'ambiente) a partire dal 5.2.

Inoltre, si dovrebbe essere in grado di profilare lua usando la sua API di debug hooks, o usando i debugger lua in giro.

Answer 4

Il motivo per cui non è stato eseguito per impostazione predefinita, non lo so. Perché è più veloce, tuttavia, è perché i locali vengono scritti in un registro, mentre un globale significa cercarlo in una tabella (_G), che è noto per essere un po 'più lento.

Come per la visibilità (come con la funzione di formato): Un locale oscura il globale. Quindi, se dichiari una funzione locale con lo stesso nome di una globale, il locale verrà usato fino a quando è nella portata. Se si desidera utilizzare la funzione globale, utilizzare _G.function.

Se si vuole veramente veloce Lua, si potrebbe provare LuaJIT

Answer 5

vedo ripetutamente nell'ambiente Lua sto trafficando in; persone redeclaring variabili come locale:

Fare ciò per impostazione predefinita è semplicemente sbagliato.

È probabilmente utile utilizzare riferimenti locali invece di tavolo accede quando una funzione viene usato ripetutamente, come all'interno tuo esempio ciclo:

local sin = math.sin 
for i = 1, 1000000 do 
    local x = sin(i) 
end 

loop Tuttavia, al di fuori, il sovraccarico di aggiungere una tabella l'accesso è completamente trascurabile.

Cosa sta succedendo qui che le persone devono fare il lavoro del compilatore?

Poiché i due esempi di codice che hai fatto in precedenza non significano esattamente la stessa cosa.

Non è come la funzione può cambiare mentre la mia funzione è in esecuzione.

Lua è un linguaggio molto dinamica, e non si possono fare le stesse ipotesi che in altre lingue più restrittive, come C. La funzione può cambiamento, mentre il ciclo è in esecuzione. Data la natura dinamica della lingua, il compilatore non può assumere che la funzione non cambierà. O almeno non senza un'analisi complessa del tuo codice e delle sue ramificazioni.

Il trucco è che, anche se i due pezzi di codice sguardo equivalente, in Lua non lo sono. Sul primo si sta esplicitamente dicendo di "ottenere la funzione sin all'interno della tabella matematica su ogni iterazione". Sul secondo si sta usando un singolo riferimento alla stessa funzione ancora e ancora.

Considerate questo:

-- The first 500000 will be sines, the rest will be cosines 
for i = 1, 1000000 do 
    local x = math.sin(i) 
    if i==500000 then math.sin = math.cos end 
end 

-- All will be sines, even if math.sin is changed 
local sin = math.sin 
for i = 1, 1000000 do 
    local x = sin(i) 
    if i==500000 then math.sin = math.cos end 
end 

Answer 6

Questo non è solo un bug/caratteristica di Lua, molte lingue tra cui Java e C si esibiranno più velocemente se si accede valori locali, invece di valori fuori portata, come ad esempio da una classe o un array.

In C++ ad esempio, è più veloce accedere a un membro locale piuttosto che accedere ai membri variabili di alcune classi.

Ciò contare fino a 10.000 più veloce:

for(int i = 0; i < 10000, i++) 
{ 
} 

di:

for(myClass.i = 0; myClass.i < 10000; myClass.i++) 
{ 
} 

La ragione Lua detiene valori globali all'interno di una tabella è perché permette al programmatore di salvare e cambiare l'ambiente globale in fretta semplicemente cambiando la tabella che fa riferimento a _G. Sono d'accordo che sarebbe bello avere un po 'di zucchero sintetico che ha trattato il tavolo globale _G come un caso speciale; riscrivendoli tutti come variabili locali nell'ambito del file (o qualcosa di simile), ovviamente non c'è nulla che ci impedisca di farlo da soli; forse una funzione optGlobalEnv (...) che 'localizza' la tabella _G ed è membri/valori per 'scope del file' usando unpack() o qualcosa del genere.