Reducción del consumo de memoria en librsvg, parte 3: espacio sobrante en las curvas de Bézier

Translations: en - Tags: gnome, librsvg, performance, rust

Llegó un bug con un SVG gigantesco de un mapa sacado de OpenStreetMap, y tiene unos 600,000 elementos. La mayoría son <path>, es decir, especificaciones de curvas de Bézier.

Un <path> puede verse así:

<path d="m 2239.05,1890.28 5.3,-1.81"/>

El atributo d contiene una lista de comandos para crear una curva, muy similares a los operadores de PostScript. Librsvg tiene esto para los comandos posibles:

pub enum PathCommand {
    MoveTo(f64, f64),
    LineTo(f64, f64),
    CurveTo(CubicBezierCurve),
    Arc(EllipticalArc),
    ClosePath,
}

Esos comandos se guardan en un arreglo, un Vec dentro de un PathBuilder:

pub struct PathBuilder {
    path_commands: Vec<PathCommand>,
}

Librsvg traduce cada uno de los comandos dentro del <path d="..."/> a un PathCommand y lo mete al Vec que trae el PathBuilder. Cuando termina, el PathBuilder se queda como la versión final del path.

Ahora bien, para que un Vec pueda crecer de forma eficiente sin importar cuántos elementos se le añadan, Rust hace que el Vec crezca por potencias de 2. Al añadir un elemento, si la capacidad del Vec ya está llena, se le hace un realloc() al bloque de memoria correspondiente para que tenga el doble de capacidad. Así se hacen sólo O(log₂n) llamadas a realloc(), donde n es el número de elementos totales.

Sin embargo, esto quiere decir que ya que terminamos de añadir elementos en el Vec, puede quedar algo de espacio libre: la capacidad es más grande que la longitud del arreglo. La invariante es que vec.capacity() >= vec.len().

Primero quise encoger los PathBuilder para que no tengan capacidad sobrante al final.

Primer paso: convertir a Box<[T]>

Un "boxed slice" es un arreglo contíguo en el heap, que no puede crecer ni encogerse. Es decir, no tiene capacidad sobrante, sólo longitud.

Vec tiene un método into_boxed_slice que hace exactamente eso: consume el vector y lo convierte en un "boxed slice" sin capacidad sobrante. En sus entrañas lo que hace es un realloc() del bloque de memoria que pertenecía al Vec para que sólo tenga espacio igual a su longitud.

Veamos los números que reporta Massif:

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 23 22,751,613,855    1,560,916,408    1,493,746,540    67,169,868            0
                                       ^^^^^^^^^^^^^
                                           antes

 30 22,796,106,012    1,553,581,072    1,329,943,324   223,637,748            0
                                       ^^^^^^^^^^^^^
                                          después

Es decir, pasamos de consumir 1,493,746,540 bytes en el heap a 1,329,943,324 bytes. Sólamente quitar la capacidad sobrante ahorra unos 159 MB para este archivo.

Segundo paso: quitarle trabajo al gestor de memoria

Sin embargo, en la columna de extra-heap de esa tabla sale un valor que no me gusta: quedan 223,637,748 bytes de metadatos de malloc() y sus amigos, más espacio en el heap que no se usa.

Me imagino que tantas llamadas a realloc() hacen que el heap quede fragmentado.

Sería bueno poder leer la mayoría de los <path d="..."/> a buffers temporales que no requieran tantas llamadas a realloc(), y que al final se copien a buffers de longitud exacta, sin capacidad sobrante.

Podemos hacer eso con el crate smallvec. Un SmallVec tiene el mismo API que Vec, pero puede guardar arreglos pequeños directamente en el stack, sin un bloque en el heap. Ya que llenamos la capacidad del arreglo, el bloque se "derrama" al heap automáticamente.

La mayoría de los atributos d en el archivote del bug tienen menos de 32 comandos. Es decir, si usamos lo siguiente:

pub struct PathBuilder {
    path_commands: SmallVec<[PathCommand; 32]>,
}

Estamos diciendo que se pueden meter hasta 32 elementos en el SmallVec sin que requieran un bloque extra en el heap; una vez sobrepasado este límite, funcionará como un Vec normal.

Al final seguimos haciéndole un into_boxed_slice para convertirlo en un bloque de memoria independiente y de tamaño exacto.

Esto reduce bastante el extra-heap:

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 33 24,139,598,653    1,416,831,176    1,329,943,212    86,887,964            0
                                                        ^^^^^^^^^^

También, los bytes totales se reducen de 1,553,581,072 a 1,416,831,176 — tenemos un heap más pequeño porque ya no le damos tanto trabajo al gestor de memoria, y usamos menos bloques temporales para leer los atributos d.

Hacer el código lindo

Puse lo siguiente:

/// Éste es mutable
pub struct PathBuilder {
    path_commands: SmallVec<[PathCommand; 32]>,
}

/// Éste es inmutable
pub struct Path {
    path_commands: Box<[PathCommand]>,
}

impl PathBuilder {
    /// Consume el PathBuilder y lo convierte en un Path inmutable.
    pub fn into_path(self) -> Path {
        Path {
            path_commands: self.path_commands.into_boxed_slice(),
        }
    }
}

Con eso, PathBuilder se vuelve una estructura temporal, que se convierte en un Path inmutable ya que terminamos de alimentarlo. Path contiene un "boxed slice" que tiene el tamaño exacto, sin capacidad sobrante.

Siguientes pasos

Todas las coordenadas en librsvg se representan con f64, números de punto flotante de doble precisión. La especificación de SVG/CSS indica que son suficientes los números de punto flotante de 32 bits, y que sólo se usen 64 bits para las transformaciones geométricas.

Me asusta un poco cambiar esto. Habría que ver con cuidado si cambian los resultados de la suite de pruebas de librsvg. Imagino que incluso los mapas muy grandes no llegan a sobrepasar la precisión de un f32 — es lo que usa OpenStreetMap, después de todo.

Referencias