Medir y razonar: la memoria real de una tabla

Las cuatro lecciones anteriores describen una máquina: dos estructuras bajo una cabecera, una regla que reparte claves, un algoritmo que redimensiona y una representación que desde 5.5 gasta nueve bytes donde antes gastaba dieciséis. Saber cómo funciona esa máquina no sirve de nada si no puedes usarla para responder preguntas concretas sobre tu programa. Cuánto ocupan de verdad mis quinientas mil entidades. Por qué el recolector se dispara justo en ese bucle. Si convierto estos registros en vectores paralelos, cuánto gano. La diferencia entre saber teoría de tablas y saber programar con tablas está en poder contestar esas preguntas dos veces: primero con un cálculo en una servilleta y después con una medición que lo confirme.

Contar bytes con el recolector

Lua no tiene introspección de memoria por objeto, pero sí tiene un total global. collectgarbage("count") devuelve los kilobytes en uso por el estado de Lua, con parte fraccionaria. Desde 5.4 devuelve un único valor; el segundo resultado que existía en 5.3 desapareció.

Medir con él es fácil de hacer mal. Hay tres formas de engañarse: no recolectar antes, con lo que mides basura de otro; no recolectar después, con lo que no ves lo que ya se ha liberado; y dejar que el objeto medido muera antes de la segunda lectura, con lo que mides cero.

local function medir(constructor)
  collectgarbage("collect")
  collectgarbage("collect")            -- dos pasadas: finalizadores y ciclos
  local antes = collectgarbage("count")
  local objeto = constructor()
  collectgarbage("collect")
  local despues = collectgarbage("count")
  local bytes = (despues - antes) * 1024
  return bytes, objeto                 -- devolver el objeto lo mantiene vivo
end

local bytes, t = medir(function()
  local t = table.create(1000000)
  for i = 1, 1000000 do t[i] = i end
  return t
end)
print(string.format("%.1f MB, %.2f bytes por elemento",
                    bytes / 2^20, bytes / #t))

Dos advertencias sobre el alcance de la cifra. La primera es que collectgarbage("count") solo contabiliza la memoria que gestiona el asignador de Lua: no ve la memoria que un userdata haya reservado por su cuenta con malloc, ni las cadenas externas que 5.5 permite referenciar sin copiarlas. La segunda es que la memoria residente del proceso siempre será mayor que este número, porque el asignador del sistema tiene su propia fragmentación y sus propios bloques. Para comparar dos diseños de datos, la cifra de Lua es la correcta; para saber cuánta RAM pide tu programa, mide el proceso.

Estimar a mano antes de medir

Con los datos de las lecciones anteriores se construye una estimación que en la práctica acierta con un error de pocos puntos porcentuales.

flowchart TD
T[Coste de una tabla] --> H[Cabecera fija de unos 56 bytes]
T --> A[Parte array]
T --> N[Parte hash]
A --> A1[9 bytes por hueco en 5.5 y 16 en 5.4]
A --> A2[Ocupacion garantizada por encima de la mitad]
N --> N1[24 bytes por nodo]
N --> N2[Tamano redondeado a la potencia de dos superior]

La cabecera ocupa del orden de cincuenta y seis bytes en una máquina de 64 bits: los dos campos comunes del recolector, los dos bytes de control, el tamaño del vector y cinco punteros. Cada hueco de la parte array cuesta nueve bytes en 5.5. Cada entrada de la parte hash cuesta un nodo de veinticuatro bytes, pero el vector de nodos se redondea a la potencia de dos siguiente, de modo que el coste real por entrada oscila entre veinticuatro y cuarenta y ocho bytes según lo desafortunado que sea el número de claves.

-- Un millon de enteros como secuencia densa, en 5.5
-- 56 + 1000000 * 9  =  ~8,6 MB

-- Los mismos valores con claves dispersas, en la parte hash
-- 56 + 1048576 * 24 =  ~24 MB   (casi el triple)

-- Un millon de puntos como tabla por registro
-- contenedor:  1000000 * 9                     =  ~8,6 MB
-- cada punto:  56 de cabecera + 4 nodos * 24   =  152 bytes
-- total:       ~152 MB, mas la presion sobre el recolector

-- Los mismos puntos como tres vectores paralelos
-- 3 * (56 + 1000000 * 9)                       =  ~26 MB

Para aplicar la fórmula a una tabla real hace falta saber cuántas de sus claves son enteros densos desde uno y cuántas no. Eso sí se puede contar desde Lua, aunque el resultado sea una aproximación: no revela el tamaño interno de las partes, solo el de los datos que las justifican.

local function perfil(t)
  local densas, resto, maxima = 0, 0, 0
  for k in pairs(t) do
    if math.type(k) == "integer" and k >= 1 then
      densas = densas + 1
      if k > maxima then maxima = k end
    else
      resto = resto + 1
    end
  end
  -- Si densas y maxima coinciden, las claves enteras forman una
  -- secuencia perfecta y con casi total seguridad viven en el vector.
  return densas, resto, maxima, densas == maxima
end

La cuarta salida es la más informativa. Cuando densas y maxima divergen mucho, tienes claves enteras que el algoritmo de redimensionado no pudo justificar en el vector y que están pagando veinticuatro bytes por cabeza en la dispersión. Ese cociente entre el número de claves enteras y la mayor de ellas es, en la práctica, el mejor indicador de una tabla mal diseñada.

Ese último par de cifras es el resultado más importante del nivel entero. Pasar de un millón de tablas pequeñas a tres tablas grandes divide la memoria por seis, y además reduce el número de objetos que el recolector tiene que visitar de un millón y uno a cuatro. El coste es de expresividad: puntos[i].x se convierte en xs[i], y pierdes la capacidad de pasar un punto como un solo valor. Es un intercambio real, no una obviedad, y solo lo puedes evaluar si sabes cuánto vale cada lado.

Los patrones que hacen que una tabla se comporte mal

Antes de los que necesitan explicación larga, hay uno que se resuelve con una frase y que se ve constantemente en código real: usar una tabla como conjunto de banderas booleanas indexado por enteros pequeños. Si tus índices llegan a cien mil, estás gastando novecientos kilobytes para almacenar cien mil bits de información, un factor setenta y dos de desperdicio. Cuando el volumen justifica el esfuerzo, empaquetar esas banderas en enteros con los operadores de bits reduce el coste a doce kilobytes y además convierte la consulta en una operación aritmética sin acceso a memoria adicional.

Hay dos patrones más que merecen explicación en lugar de tarjeta. El primero es la creación de tablas efímeras dentro de un bucle caliente: devolver {x, y} desde una función llamada un millón de veces genera un millón de cabeceras y un millón de vectores diminutos que el recolector tendrá que perseguir. La alternativa clásica es que el llamante aporte el buffer y la función lo rellene, o que la función devuelva valores múltiples, que en Lua no cuestan ninguna reserva.

-- Antes: una tabla nueva por iteracion, un millon de veces.
local function normalizar(x, y)
  return { x = x / 10, y = y / 10 }
end

-- Despues: valores multiples, cero reservas.
local function normalizar(x, y)
  return x / 10, y / 10
end

-- O bien, cuando el resultado tiene que viajar como una unidad:
local function normalizar(x, y, destino)
  destino.x = x / 10
  destino.y = y / 10
  return destino
end

El segundo es la tabla que se usa como conjunto de cadenas. Cada clave distinta obliga a crear un objeto cadena interno si no existía, y ese objeto se mantiene vivo mientras la tabla lo referencie. Un conjunto de un millón de cadenas cortas no cuesta veinticuatro megabytes de nodos: cuesta eso más un millón de objetos cadena, cada uno con su cabecera y su contenido. Cuando el conjunto solo sirve para comprobar pertenencia y las cadenas vienen de un vocabulario cerrado, sustituirlas por índices enteros cambia el orden de magnitud del coste.