performance - ¿Qué puedo hacer para aumentar el rendimiento de un programa Lua?

optimization

Question

Hice una pregunta sobre la actuación de Lua, y una de las respuestas solicitadas:

¿Has estudiado consejos generales para mantener alto el rendimiento de Lua? es decir, conocer la creación de tablas y, en su lugar, reutilizar una tabla antes que crear una nueva, el uso de "impresión local = imprimir" y así evitar los accesos globales.

Esta es una pregunta ligeramente diferente de Lua Patterns, Tips and Tricks porque me gustaría obtener respuestas que afecten específicamente el rendimiento y (si es posible) una explicación de por qué se ve afectado el rendimiento.

Un consejo por respuesta sería ideal.

Answer 1

Mantenga las tablas cortas, cuanto más grande sea la tabla, mayor será el tiempo de búsqueda. Y en la misma línea iterar sobre tablas indexadas numéricamente (= matrices) es más rápido que las tablas basadas en claves (por lo tanto, ipairs es más rápido que los pares)

Answer 2

Si su programa de lua es demasiado lento, utilice el generador de perfiles de Lua y limpie las cosas costosas o migre a C. Pero si no está esperando allí, su tiempo se desperdicia.

La primera ley de optimización: no.

Me encantaría ver un problema en el que pueda elegir entre ipairs y pares y pueda medir el efecto de la diferencia.

La única pieza fácil de fruta que está a la altura es recordar el uso de variables locales dentro de cada módulo. En general no vale la pena hacer cosas como

local strfind = string.find

a menos que pueda encontrar una medida que le indique lo contrario.

Answer 3

• Haciendo las funciones más usadas locales
• Hacer buen uso de las tablas como HashSets
• Disminuir la creación de tabla mediante reutilización
• ¡Usando luajit!

Answer 4

En respuesta a algunas de las otras respuestas y comentarios:

Es cierto que, como programador, generalmente debe evitar una optimización prematura. Pero . Esto no es tan cierto para los lenguajes de scripting donde el compilador no optimiza mucho - o en absoluto.

Entonces, cada vez que escribes algo en Lua, y eso se ejecuta muy a menudo, se ejecuta en un entorno de tiempo crítico o puede funcionar por un tiempo, es bueno saber qué cosas evitar (y evitarlas).

Esta es una colección de lo que descubrí con el tiempo. Algo de lo que descubrí en la red, pero siendo de naturaleza sospechosa cuando se trata de interwebs , lo probé yo mismo. Además, he leído el documento de rendimiento de Lua en Lua.org.

Alguna referencia:

• Consejos de rendimiento Lua
• Consejos de optimización de Lua-users.org

Evita los globales

Este es uno de los consejos más comunes, pero afirmarlo una vez más no puede doler.

Los Globales se almacenan en una tabla hash por su nombre. Acceder a ellos significa que debe acceder a un índice de tabla. Si bien Lua tiene una buena implementación de hashtable, aún es mucho más lenta que acceder a una variable local. Si tiene que usar valores globales, asigne su valor a una variable local, esto es más rápido en el segundo acceso variable.

do
  x = gFoo + gFoo;
end
do -- this actually performs better.
  local lFoo = gFoo;
  x = lFoo + lFoo;
end

(No es que las pruebas simples puedan arrojar resultados diferentes, por ejemplo, local x; for i=1, 1000 do x=i; end aquí el encabezado de bucle for toma realmente más tiempo que el cuerpo del bucle, por lo que los resultados del perfil podrían distorsionarse).

Evitar la creación de cadenas

Lua aplica todos los hilos en la creación, esto hace que la comparación y su uso en tablas sea muy rápido y reduce el uso de memoria ya que todas las cadenas se almacenan internamente una sola vez. Pero hace que la creación de cuerdas sea más costosa.

Una opción popular para evitar la creación excesiva de cadenas es usar tablas. Por ejemplo, si tiene que ensamblar una cadena larga, cree una tabla, coloque las cadenas individuales allí y luego use table.concat para unirlo una vez

-- do NOT do something like this
local ret = "";
for i=1, C do
  ret = ret..foo();
end

Si foo() devolvería solo el carácter A , este bucle crearía una serie de cadenas como "" , "A" , "AA" , "AAA" , etc. Cada cadena sería hash y residiría en la memoria hasta que finalizara la aplicación. - ¿ves el problema aquí?

-- this is a lot faster
local ret = {};
for i=1, C do
  ret[#ret+1] = foo();
end
ret = table.concat(ret);

Este método no crea cadenas en absoluto durante el ciclo, la cadena se crea en la función foo y solo las referencias se copian en la tabla. Después, concat crea una segunda cadena "AAAAAA..." (dependiendo de cuán grande es C ). Tenga en cuenta que puede usar i lugar de #ret+1 pero a menudo no tiene un bucle tan útil y no tendrá una variable de iterador que pueda usar.

Otro truco que encontré en lua-users.org es usar gsub si tienes que analizar una cadena

some_string:gsub(".", function(m)
  return "A";
end);

Esto parece extraño al principio, el beneficio es que gsub crea una cadena "a la vez" en C, que solo es hash después de que se devuelve a lua cuando gsub regresa. Esto evita la creación de tablas, pero posiblemente tenga más sobrecarga de funciones (no si llama a foo() todos modos, pero si foo() es realmente una expresión)

Evite los gastos generales

Utilice construcciones de lenguaje en lugar de funciones cuando sea posible

función ipairs

Al iterar una tabla, la carga de la función de ipairs no justifica su uso. Para iterar una tabla, en su lugar use

for k=1, #tbl do local v = tbl[k];

Hace exactamente lo mismo sin la sobrecarga de llamada de función (los pares realmente devuelven otra función que luego se llama para cada elemento de la tabla, mientras que #tbl solo se evalúa una vez). Es mucho más rápido, incluso si necesita el valor. Y si no lo haces ...

Nota para Lua 5.2 : En 5.2, puede definir un campo __ipairs en la metatabla, lo que hace que las ipairs útiles en algunos casos. Sin embargo, Lua 5.2 también hace que el campo __len trabaje para las tablas, por lo que aún puede preferir el código anterior para ipairs ya que entonces el __len __len solo se llama una vez, mientras que para las ipairs se obtiene una llamada de función adicional por iteración.

funciones table.insert , table.remove

Los usos simples de table.insert y table.remove se pueden reemplazar utilizando el operador # lugar. Básicamente esto es para operaciones push y pop simples. Aquí hay unos ejemplos:

table.insert(foo, bar);
-- does the same as
foo[#foo+1] = bar;

local x = table.remove(foo);
-- does the same as
local x = foo[#foo];
foo[#foo] = nil;

Para los cambios (por ejemplo, table.remove(foo, 1) ), y si terminar con una tabla dispersa no es deseable, por supuesto, es mejor usar las funciones de la tabla.

Use tablas para SQL-IN por igual

Puede - o no - tener decisiones en su código como las siguientes

if a == "C" or a == "D" or a == "E" or a == "F" then
   ...
end

Ahora bien, este es un caso perfectamente válido, sin embargo (a partir de mis propias pruebas) comenzando con 4 comparaciones y excluyendo la generación de tablas, esto es realmente más rápido:

local compares = { C = true, D = true, E = true, F = true };
if compares[a] then
   ...
end

Y dado que las tablas hash tienen un tiempo de búsqueda constante, la ganancia de rendimiento aumenta con cada comparación adicional. Por otro lado, si coinciden una o dos comparaciones "la mayoría de las veces", es posible que sea mejor con la forma booleana o una combinación.

Evite la creación frecuente de tablas

Esto se analiza a fondo en Lua Performance Tips . Básicamente, el problema es que Lua asigna su mesa a pedido y hacerlo de esta manera llevará más tiempo que limpiar su contenido y llenarlo nuevamente.

Sin embargo, esto es un problema, ya que Lua no proporciona un método para eliminar todos los elementos de una tabla, y los pairs() no son la bestia de rendimiento en sí misma. Aún no he hecho ninguna prueba de rendimiento sobre este problema.

Si puede, defina una función C que borre una tabla, esta debería ser una buena solución para la reutilización de tablas.

Evita hacer lo mismo una y otra vez

Este es el mayor problema, creo. Si bien un compilador en un lenguaje no interpretado puede optimizar fácilmente una gran cantidad de redundancias, Lua no lo hará.

Memoize

Usando tablas esto se puede hacer bastante fácilmente en Lua. Para las funciones de un solo argumento, puede incluso reemplazarlas con una tabla y un __index metamethod. Aunque esto destruye la transparencia, el rendimiento es mejor en los valores almacenados en caché debido a una llamada de función menos.

Aquí hay una implementación de memoialización para un argumento único que usa una metatabla. (Importante: esta variante no admite un argumento de valor nulo, pero es bastante rápido para los valores existentes).

function tmemoize(func)
    return setmetatable({}, {
        __index = function(self, k)
            local v = func(k);
            self[k] = v
            return v;
        end
    });
end
-- usage (does not support nil values!)
local mf = tmemoize(myfunc);
local v  = mf[x];

En realidad podría modificar este patrón para múltiples valores de entrada

Aplicación parcial

La idea es similar a la memorización, que consiste en "caché" de resultados. Pero aquí, en lugar de almacenar en caché los resultados de la función, almacenaría en caché los valores intermedios poniendo su cálculo en una función de constructor que defina la función de cálculo en su bloque. En realidad, simplemente lo llamaría uso inteligente de cierres.

-- Normal function
function foo(a, b, x)
    return cheaper_expression(expensive_expression(a,b), x);
end
-- foo(a,b,x1);
-- foo(a,b,x2);
-- ...

-- Partial application
function foo(a, b)
    local C = expensive_expression(a,b);
    return function(x)
        return cheaper_expression(C, x);
    end
end
-- local f = foo(a,b);
-- f(x1);
-- f(x2);
-- ...

De esta manera, es posible crear fácilmente funciones flexibles que almacenan algunos de sus trabajos sin demasiado impacto en el flujo del programa.

Una variante extrema de esto sería Currying , pero en realidad es más una manera de imitar la programación funcional que cualquier otra cosa.

Aquí hay un ejemplo más extenso ("mundo real") con algunas omisiones de código; de lo contrario, ocuparía fácilmente toda la página aquí (es decir, get_color_values realiza una gran cantidad de comprobaciones de valor y reconoce que acepta valores mixtos)

function LinearColorBlender(col_from, col_to)
    local cfr, cfg, cfb, cfa = get_color_values(col_from);
    local ctr, ctg, ctb, cta = get_color_values(col_to);
    local cdr, cdg, cdb, cda = ctr-cfr, ctg-cfg, ctb-cfb, cta-cfa;
    if not cfr or not ctr then
        error("One of given arguments is not a color.");
    end

    return function(pos)
        if type(pos) ~= "number" then
            error("arg1 (pos) must be in range 0..1");
        end
        if pos < 0 then pos = 0; end;
        if pos > 1 then pos = 1; end;
        return cfr + cdr*pos, cfg + cdg*pos, cfb + cdb*pos, cfa + cda*pos;
    end
end
-- Call 
local blender = LinearColorBlender({1,1,1,1},{0,0,0,1});
object:SetColor(blender(0.1));
object:SetColor(blender(0.3));
object:SetColor(blender(0.7));

Puede ver que una vez que se creó la licuadora, la función solo tiene que comprobar la cordura de un solo valor en lugar de hasta ocho. Incluso extraje el cálculo de la diferencia, aunque probablemente no mejore mucho, espero que muestre lo que este patrón intenta lograr.

Answer 5

También se debe señalar que el uso de campos de matriz a partir de tablas es mucho más rápido que el uso de tablas con cualquier tipo de clave. Sucede (casi) que todas las implementaciones de Lua (incluido LuaJ) almacenan una llamada "parte de matriz" dentro de las tablas, a la que acceden los campos de la matriz de tablas, y no almacena la clave de campo ni la busca;).

Incluso puede imitar aspectos estáticos de otros lenguajes como struct , class C ++ / Java, etc. Los locales y matrices son suficientes.