¿Por qué esta optimización de Lua hack mejoraría el rendimiento?

Question

Estoy buscando un código de script document that describes various techniques to improve performance of Lua, y estoy sorprendido de que tales trucos sean necesarios. (Aunque estoy citando a Lua, he visto hacks similares en Javascript).

Por qué se requeriría esta optimización:

Por ejemplo, el código

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

se ejecuta un 30% más lento que éste:

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

Son re -declaring sin función localmente.

¿Por qué sería útil? Es el trabajo del compilador hacer eso de todos modos. ¿Por qué el programador tiene que hacer el trabajo del compilador?

He visto cosas similares en Javascript; y obviamente debe haber una muy buena razón por la cual el compilador de interpretación no está haciendo su trabajo. ¿Qué es?

---

Lo veo repetidamente en el entorno de Lua en el que me estoy metiendo; personas redeclasando variables como locales:

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 

¿Qué está pasando aquí que la gente tiene que hacer el trabajo del compilador? ¿El compilador está confundido por cómo encontrar format? ¿Por qué es este un problema que un programador tiene que tratar? ¿Por qué no se habría solucionado esto en 1993?

---

También parecen haber golpeado una paradoja lógica:

1. optimización no debe hacerse sin perfilar
2. Lua no tiene capacidad para ser perfilado
3. Lua no debe ser optimizado

Answer 1

¿Por qué sería útil? Es el trabajo del compilador hacer eso de todos modos. ¿Por qué el programador tiene que hacer el trabajo del compilador?

Lua es un lenguaje dinámico. Los compiladores pueden razonar mucho en lenguajes estáticos, como extraer expresiones constantes del ciclo. En los lenguajes dinámicos, la situación es un poco diferente.

La estructura de datos principal de Lua (y también la única) es la tabla. math también es solo una tabla, aunque aquí se usa como espacio de nombre. Nadie puede impedirte que modifiques la función math.sin en algún punto del ciclo (incluso pensé que sería algo imprudente de hacer), y el compilador no puede saberlo al compilar el código. Por lo tanto, el compilador hace exactamente lo que le indica que haga: en cada iteración del ciclo, busque la función sin en la tabla math y llámela.

Ahora, si USTED sabe que no va a modificar math.sin (es decir, va a llamar a la misma función), puede guardarlo en una variable local fuera del ciclo. Como no hay búsquedas en la tabla, el código resultante es más rápido.

La situación es un poco diferente con LuaJIT - que utiliza el rastreo y un poco de magia avanzada para ver lo que su código está haciendo en tiempo de ejecución, por lo que en realidad puede optimizar el bucle moviendo la expresión fuera del bucle, y otra optimizaciones, aparte de compilarlo en código automático, volviéndolo loco rápidamente.

En cuanto a las 'variables de redeclaración como locales', muchas veces cuando se define un módulo, se desea trabajar con la función original. Al acceder a pairs, max o cualquier cosa utilizando sus variables globales, nadie puede asegurarle que será la misma función en cada llamada. Por ejemplo, stdlib redefine muchas funciones globales.

Al crear una variable local con el mismo nombre que el global, esencialmente almacena la función en una variable local y porque las variables locales (que tienen un alcance léxico, lo que significa que son visibles en el ámbito actual y cualquier ámbito anidado también) tienen prioridad antes que los globales, asegúrese de llamar siempre a la misma función. Si alguien modifica el global más tarde, no afectará su módulo. Sin mencionar que también es más rápido, porque los globales se buscan en una tabla global (_G).

actualización: acabo de leer Lua Performance Tips por Roberto Ierusalimschy, uno de los autores de Lua, y explica casi todo lo que necesita saber acerca de Lua, el rendimiento y la optimización. OMI las reglas más importantes son:

Regla # 1: no lo hacen.

Regla # 2: No lo hagas todavía. (Sólo para expertos)

Answer 2

Mi hipótesis es que en la versión optimizada, porque la referencia a la función se almacena en un local variable, un cruce de árbol no tiene que hacerse en cada iteración del bucle for (para buscar en math.sin).

No estoy seguro acerca de las referencias locales establecidas para los nombres de las funciones, pero supongo que se necesita algún tipo de búsqueda de espacio de nombres global si no se encuentra una local.

Por otra parte, podría estar fuera de lugar;)

Editar: También supongo que el compilador Lua es tonto (que es una suposición general para mí acerca de los compiladores de todos modos;))

Answer 3

Guardando funciones en las variables locales elimina la indexación de la tabla para buscar la tecla de función en cada iteración del ciclo, las matemáticas son obvias, ya que necesita buscar el hash en la tabla Math, las demás no, están indexadas en _G (tabla global), que ahora es _ENV (tabla de entorno) a partir de 5.2.

Además, uno debería ser capaz de crear perfiles de lua utilizando su API de enlaces de depuración, o usando los depuradores de lua que se encuentran.

Answer 4

La razón por la que no se hace por defecto, no lo sé. Sin embargo, el motivo por el cual es más rápido es porque los locales se escriben en un registro, mientras que un término global significa buscarlo en una tabla (_G), que se sabe que es algo más lento.

En cuanto a la visibilidad (como con la función de formato): Un local oscurece el global. Por lo tanto, si declara una función local con el mismo nombre que global, se usará el local siempre que esté dentro del alcance. Si desea usar la función global en su lugar, use _G.function.

Si realmente quiere rápida Lua, podría intentar LuaJIT

Answer 5

lo veo repetidamente en el entorno de Lua estoy jugando en; personas que redecilan variables como locales:

Hacer eso de forma predeterminada es completamente incorrecto.

Podría decirse que es útil el uso de referencias locales en lugar de la Tabla accede cuando se utiliza más de una función y otra vez, como el interior de su ejemplo de bucle:

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

bucles Sin embargo, fuera de, la sobrecarga de la adición de una mesa el acceso es completamente insignificante.

¿Qué está pasando aquí que la gente tiene que hacer el trabajo del compilador?

Porque las dos muestras de código que hizo anteriormente no significan exactamente lo mismo.

No es que la función pueda cambiar mientras mi función se está ejecutando.

Lua es un lenguaje muy dinámico, y no se puede hacer que los mismos supuestos que en otros lenguajes más restrictivas, como C. La función puede cambio, mientras que el bucle se está ejecutando. Dada la naturaleza dinámica del lenguaje, el compilador no puede suponer que la función no cambiará. O al menos no sin un análisis complejo de su código y sus ramificaciones.

El truco es que, incluso si sus dos piezas de código parecen equivalentes, en Lua no lo son. En el primero, explícitamente le dice que "obtenga la función pecado dentro de la tabla matemática en cada iteración". En el segundo, está utilizando una sola referencia a la misma función una y otra vez.

Considera:

-- 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

Esto no es sólo un error/característica del Lua, muchos idiomas incluyendo JavaC y llevará a cabo más rápido si accede a los valores locales en lugar de los valores fuera de alcance, como por ejemplo de una clase o matriz

En C++ por ejemplo, es más rápido acceder a un miembro local de lo que sería acceder a miembros variables de alguna clase.

Este contaría con 10.000 más rápido:

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

que:

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

La razón Lua propugna como valores globales dentro de una tabla se debe a que permite al programador para guardar y cambiar el entorno global rápidamente simplemente cambiando la tabla que _G hace referencia. Estoy de acuerdo en que sería bueno tener algún 'azúcar sintético' que tratara la tabla global _G como un caso especial; reescribiéndolos todos como variables locales en el alcance del archivo (o algo similar), por supuesto que no hay nada que nos impida hacer esto nosotros mismos; tal vez una función optGlobalEnv (...) que 'localiza' la tabla _G y sus miembros/valores al 'alcance del archivo' usando unpack() o algo así.