Reducción del consumo de memoria en librsvg, parte 4: representación compacta para las curvas de Bézier

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

Sigamos con el SVG gigantesco de la vez anterior, un mapa sacado de OpenStreetMap.

Según Massif, el máximo de consumo de memoria ocurre en el siguiente punto de la ejecución de rsvg-convert. Dejé sólo la parte que se refiere a las curvas de Bézier:

    --------------------------------------------------------------------------------
      n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
    --------------------------------------------------------------------------------
1    33 24,139,598,653    1,416,831,176    1,329,943,212    86,887,964            0
2   ->24.88% (352,523,448B) 0x4A2727E: alloc (alloc.rs:84)
    | ->24.88% (352,523,448B) 0x4A2727E: alloc (alloc.rs:172)
    |   ->24.88% (352,523,448B) 0x4A2727E: allocate_in<rsvg_internals::path_builder::PathCommand,alloc::alloc::Global> (raw_vec.rs:98)
    |     ->24.88% (352,523,448B) 0x4A2727E: with_capacity<rsvg_internals::path_builder::PathCommand> (raw_vec.rs:167)
    |       ->24.88% (352,523,448B) 0x4A2727E: with_capacity<rsvg_internals::path_builder::PathCommand> (vec.rs:358)
    |         ->24.88% (352,523,448B) 0x4A2727E: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T,I>>::from_iter (vec.rs:1992)
    |           ->24.88% (352,523,448B) 0x49D212C: from_iter<rsvg_internals::path_builder::PathCommand,smallvec::IntoIter<[rsvg_internals::path_builder::PathCommand; 32]>> (vec.rs:1901)
    |             ->24.88% (352,523,448B) 0x49D212C: collect<smallvec::IntoIter<[rsvg_internals::path_builder::PathCommand; 32]>,alloc::vec::Vec<rsvg_internals::path_builder::PathCommand>> (iterator.rs:1493)
    |               ->24.88% (352,523,448B) 0x49D212C: into_vec<[rsvg_internals::path_builder::PathCommand; 32]> (lib.rs:893)
    |                 ->24.88% (352,523,448B) 0x49D212C: smallvec::SmallVec<A>::into_boxed_slice (lib.rs:902)
3   |                   ->24.88% (352,523,016B) 0x4A0394C: into_path (path_builder.rs:320)
    |
4   ->03.60% (50,990,328B) 0x4A242F0: realloc (alloc.rs:128)
    | ->03.60% (50,990,328B) 0x4A242F0: realloc (alloc.rs:187)
    |   ->03.60% (50,990,328B) 0x4A242F0: shrink_to_fit<rsvg_internals::path_builder::PathCommand,alloc::alloc::Global> (raw_vec.rs:633)
    |     ->03.60% (50,990,328B) 0x4A242F0: shrink_to_fit<rsvg_internals::path_builder::PathCommand> (vec.rs:623)
    |       ->03.60% (50,990,328B) 0x4A242F0: alloc::vec::Vec<T>::into_boxed_slice (vec.rs:679)
    |         ->03.60% (50,990,328B) 0x49D2136: smallvec::SmallVec<A>::into_boxed_slice (lib.rs:902)
5   |           ->03.60% (50,990,328B) 0x4A0394C: into_path (path_builder.rs:320)

En la línea 1 están los totales, donde se ve que en ese punto el programa usa 1,329,943,212 bytes en el heap.

Las líneas 3 y 5 nos dan una pista de que se está llamando a into_path; esa es la función que convierte un PathBuilder temporal/mutable en un Path permanente/inmutable.

Las líneas 2 y 4 indican que los arreglos de PathCommand, adentro de esos Path inmutables, ocupan 24.88% + 3.60% = 28.48% de la memoria total; entre los dos dan un total de 352,523,448 + 50,990,328 = 403,513,776 bytes.

Es decir, unos 400 MB de PathCommand. Veamos qué está pasando.

¿Qué hay en un PathCommand?

Un Path es una lista de comandos similares a los de PostScript, que se usan en SVG para dibujar curvas de Bézier. Es un arreglo plano de PathCommand:

pub struct Path {
    path_commands: Box<[PathCommand]>,
}

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

Veamos las variantes de PathCommand:

  • MoveTo: 2 flotantes de doble precisión.
  • LineTo: igual.
  • CurveTo: 6 flotantes de doble precisión.
  • EllipticalArc: 7 flotantes de doble precisión, más 2 banderas (ver abajo).
  • ClosePath: sin datos extra.

Es decir, varían mucho de tamaño entre sí, y cada elemento del arreglo Path.path_commands ocupa el máximo del espacio de todos (i.e. sizeof::<EllipticalArc>).

Una representación más compacta

De forma ideal, cada comando en el arreglo ocuparía sólo el espacio que necesita.

Podemos representar un Path de otra forma, como dos arreglos separados:

  • Un arreglo de comandos muy compacto, sin coordenadas.
  • Un arreglo sólo de coordenadas.

Es decir, lo siguiente:

pub struct Path {
    commands: Box<[PackedCommand]>,
    coords: Box<[f64]>,
}

El arreglo coords es obvio; es sólo un arreglo plano con todas las coordenadas del Path en el orden en que aparecen.

¿Y el otro arreglo commands?

PackedCommand

Arriba vimos que la variante más grande de un PathCommand es Arc(EllipticalArc). Ahora veamos qué hay ahí:

pub struct EllipticalArc {
    pub r: (f64, f64),
    pub x_axis_rotation: f64,
    pub large_arc: LargeArc,
    pub sweep: Sweep,
    pub from: (f64, f64),
    pub to: (f64, f64),
}

Entre todos los f64 son 7 números de punto flotante. Los otros dos campos, large_arc y sweep, son en efecto booleanos (son sólo enumeraciones con dos variantes, con nombres bonitos en vez de true y false).

Entonces tenemos 7 flotantes de doble precisión y dos banderas. Entre las dos banderas hay 4 posibilidades.

Como ninguna otra variante de PathCommand tiene banderas, podemos tener el siguiente enum, que cabe en un byte:

#[repr(u8)]
enum PackedCommand {
    MoveTo,
    LineTo,
    CurveTo,
    ArcSmallNegative,
    ArcSmallPositive,
    ArcLargeNegative,
    ArcLargePositive,
    ClosePath,
}

Es decir, valores simples para MoveTo/etc. y cuatro valores especiales para los diferentes tipos de Arc.

Empacar un PathCommand en un PackedCommand

Para empacar el arreglo de PathCommand, primero necesitamos saber cuántas coordenadas va a requerir cada una de sus variantes:

impl PathCommand {
    fn num_coordinates(&self) -> usize {
        match *self {
            PathCommand::MoveTo(..) => 2,
            PathCommand::LineTo(..) => 2,
            PathCommand::CurveTo(_) => 6,
            PathCommand::Arc(_) => 7,
            PathCommand::ClosePath => 0,
        }
    }
}

Además, necesitamos convertir cada PathCommand a un PackedCommand y escribir sus coordenadas en otro arreglo:

impl PathCommand {
    fn to_packed(&self, coords: &mut [f64]) -> PackedCommand {
        match *self {
            PathCommand::MoveTo(x, y) => {
                coords[0] = x;
                coords[1] = y;
                PackedCommand::MoveTo
            }

            // etc. para los demás comandos simples

            PathCommand::Arc(ref a) => a.to_packed_and_coords(coords),
        }
    }
}

Veamos ese to_packed_and_coords más de cerca:

impl EllipticalArc {
    fn to_packed_and_coords(&self, coords: &mut [f64]) -> PackedCommand {
        coords[0] = self.r.0;
        coords[1] = self.r.1;
        coords[2] = self.x_axis_rotation;
        coords[3] = self.from.0;
        coords[4] = self.from.1;
        coords[5] = self.to.0;
        coords[6] = self.to.1;

        match (self.large_arc, self.sweep) {
            (LargeArc(false), Sweep::Negative) => PackedCommand::ArcSmallNegative,
            (LargeArc(false), Sweep::Positive) => PackedCommand::ArcSmallPositive,
            (LargeArc(true), Sweep::Negative) => PackedCommand::ArcLargeNegative,
            (LargeArc(true), Sweep::Positive) => PackedCommand::ArcLargePositive,
        }
    }
}

Crear el Path compacto

Veamos línea por línea cómo quedó PathBuilder::into_path:

impl PathBuilder {
    pub fn into_path(self) -> Path {
        let num_commands = self.path_commands.len();
        let num_coords = self
            .path_commands
            .iter()
            .fold(0, |acc, cmd| acc + cmd.num_coordinates());

Primero calculamos el número de coordenadas totales usando fold; para cada comando cmd le pedimos su num_coordinates() y lo sumamos al acumulador acc.

Ahora ya sabemos cuánta memoria pedir:

        let mut packed_commands = Vec::with_capacity(num_commands);
        let mut coords = vec![0.0; num_coords];

Usamos Vec::with_capacity para pedir un bloque de tamaño exacto para los packed_commands; a ese no habrá que hacerle realloc() porque ya sabemos cuántos elementos va a tener.

Usamos el macro vec! para crear un arreglo de 0.0 repetido num_coords veces; el macro usa with_capacity en sus entrañas. En ese arreglo vamos meter las coordenadas para todos los comandos.

        let mut coords_slice = coords.as_mut_slice();

Sacamos un slice mutable del arreglo de coordenadas completo.

        for c in self.path_commands {
            let n = c.num_coordinates();
            packed_commands.push(c.to_packed(coords_slice.get_mut(0..n).unwrap()));
            coords_slice = &mut coords_slice[n..];
        }

Para cada commando, vemos cuántas coordenadas va a generar y ponemos ese número en n. Sacamos una sub-rebanada mutable de coords_slice sólo con ese número de elementos y se lo pasamos al método to_packed de cada comando.

Al final de la iteración recorremos la rebanada mutable a donde irán coordenadas del comando siguiente.

        Path {
            commands: packed_commands.into_boxed_slice(),
            coords: coords.into_boxed_slice(),
        }
    }

Por último, creamos el Path final e inmutable, convirtiendo cada arreglo en into_boxed_slice como la vez pasada. Así cada uno de los dos arreglos, el de PackedCommand y el de coordenadas, ocupan el espacio mínimo.

Un iterador para Path

Ahora bien, queremos que sea fácil de iterar sobre esa representación compacta; los PathCommand del principio son muy cómodos de usar y es lo que usa el resto del código. Vamos a hacer un iterador que des-empaque lo que hay dentro de Path, y que para cada elemento regrese un PathCommand.

pub struct PathIter<'a> {
    commands: slice::Iter<'a, PackedCommand>,
    coords: &'a [f64],
}

Necesitamos un iterador sobre el arreglo de PackedCommand, para visitar cada comando. Pero para ir sacando elementos de los coords, voy a usar un slice de f64 en vez de un iterador.

Veamos la implementación del iterador:

impl<'a> Iterator for PathIter<'a> {
    type Item = PathCommand;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(cmd) = self.commands.next() {
            let cmd = PathCommand::from_packed(cmd, self.coords);
            let num_coords = cmd.num_coordinates();
            self.coords = &self.coords[num_coords..];
            Some(cmd)
        } else {
            None
        }
    }
}

Como queremos que el iterador regrese un PathCommand, lo declaramos como el tipo asociado type Item =  PathCommand.

Si el iterador self.commands tiene otro elemento, quiere decir que sí hay un PackedCommand adicional.

Llamamos a PathCommand::from_packed con el slice self.coords para des-empacar un comando y sus coordenadas. Vemos cuántas coordenadas consumió y re-rebanamos self.coords según este número, para que ahora apunte a las coordenadas del comando siguiente.

Regresamos Some(cmd) si hubo un elemento, o None si ya se vació el iterador.

La implementación de from_packed es obvia y nada más voy a poner un pedazo:

impl PathCommand {
    fn from_packed(packed: &PackedCommand, coords: &[f64]) -> PathCommand {
        match *packed {
            PackedCommand::MoveTo => {
                let x = coords[0];
                let y = coords[1];
                PathCommand::MoveTo(x, y)
            }

            // etc. para las demás variantes de PackedCommand

            PackedCommand::ArcSmallNegative => PathCommand::Arc(EllipticalArc::from_coords(
                LargeArc(false),
                Sweep::Negative,
                coords,
            )),

            PackedCommand::ArcSmallPositive => // etc.

            PackedCommand::ArcLargeNegative => // etc.

            PackedCommand::ArcLargePositive => // etc.
        }
    }
}

Resultados

Antes (el mismo encabezado de la salida de Massif que puse arriba):

--------------------------------------------------------------------------------
  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
                                       ^^^^^^^^^^^^^
                                           búúú

Después:

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 28 26,611,886,993    1,093,747,888    1,023,147,907    70,599,981            0
                                       ^^^^^^^^^^^^^
                                           oh sí

Pasamos de ocupar 1,329,943,212 bytes a 1,023,147,907 bytes, es decir, le tumbamos unos 300 MB.

Pero eso es para todo el programa. Arriba vimos que los datos de los Path ocupaban 403,513,776 bytes; ¿y ahora?

->07.45% (81,525,328B) 0x4A34C6F: alloc (alloc.rs:84)
| ->07.45% (81,525,328B) 0x4A34C6F: alloc (alloc.rs:172)
|   ->07.45% (81,525,328B) 0x4A34C6F: allocate_in<f64,alloc::alloc::Global> (raw_vec.rs:98)
|     ->07.45% (81,525,328B) 0x4A34C6F: with_capacity<f64> (raw_vec.rs:167)
|       ->07.45% (81,525,328B) 0x4A34C6F: with_capacity<f64> (vec.rs:358)
|         ->07.45% (81,525,328B) 0x4A34C6F: rsvg_internals::path_builder::PathBuilder::into_path (path_builder.rs:486)

Perfecto. Pasamos de ocupar 403,513,776 bytes a sólo 81,525,328 bytes. En vez de que los datos de los Path sean el 28.48% de la memoria, ahora sólo son 7.45%.

Podemos dejar de preocuparnos por los Path por ahora. Me gusta que esto fue posible sin usar unsafe.

Referencias