Reducir el tamaño del código en librsvg mediante eliminar un tipo genérico

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

El otro día alguien mencionó a cargo-bloat y recordé que he querido medir cuánto código binario ocupan las funciones con genéricos que se usan en librsvg, para ver si se puede mejorar algo por ahí.

Cargo-bloat puede dar una medida burda del tamaño de código binario para cada uno de los huacales (crates) que hay en un ejecutable de Rust ya compilado, y también una vista más detallada del código que se genera para cada función. Necesita una salida de tipo [bin]; si sólo tienes un [lib] no va a hacer nada. Corrí cargo-bloat en el binario de rsvg-convert.

$ cargo bloat --release --crates
    Finished release [optimized] target(s) in 0.23s
    Analyzing target/release/rsvg-bench

 File  .text     Size Crate
10.0%  38.7%   1.0MiB librsvg
 4.8%  18.8% 505.5KiB std
 2.5%   9.8% 262.8KiB clap
 1.8%   7.1% 191.3KiB regex
 ... lines omitted ...
25.8% 100.0%   2.6MiB .text section size, the file size is 10.2MiB

Note: numbers above are a result of guesswork. They are not 100% correct and never will be.

La salida de arriba es para cargo bloat --release --crates. La opción --release es para generar un ejecutable optimizado, y --crates le dice a cargo-bloat que sólo pinte un resumen de los tamaños de los crates. Los valores no son completamente exactos porque, por ejemplo, las funciones en línea (inline) pueden afectar a quienes las llaman desde otro crate. Sin embargo, esto es un buen comienzo para darse una idea del tamaño de las cosas.

En este caso, el código binario de librsvg es de más o menos 1.0 MB.

Ahora, vamos a buscar qué funciones con genéricos podríamos condensar. Cuando cargo-bloat se corre sin la opción --crates, te da el tamaño de funciones individuales en el código. Después de experimentar un poco, llegué a cargo bloat --release -n 0 --filter librsvg. La opción -n 0 le dice a cargo-bloat que pinte todas las funciones, no sólo las N más grandes en términos de código binario. La opción --filter librsvg es para que sólo pinte las funciones en ese crate, y que omita las de std, regex, etc.

$ cargo bloat --release -n 0 --filter librsvg

File .text    Size   Crate Name
0.0%  0.0%  1.2KiB librsvg librsvg::element::ElementInner<T>::new
0.0%  0.0%  1.2KiB librsvg librsvg::element::ElementInner<T>::new
0.0%  0.0%  1.2KiB librsvg librsvg::element::ElementInner<T>::new
... output omitted ...
0.0%  0.0%    825B librsvg librsvg::element::ElementInner<T>::set_style_attribute
0.0%  0.0%    825B librsvg librsvg::element::ElementInner<T>::set_style_attribute
0.0%  0.0%    825B librsvg librsvg::element::ElementInner<T>::set_style_attribute
... output omitted ...
0.0%  0.0%    358B librsvg librsvg::element::ElementInner<T>::get_cond
0.0%  0.0%    358B librsvg librsvg::element::ElementInner<T>::get_cond
0.0%  0.0%    358B librsvg librsvg::element::ElementInner<T>::get_cond
... etc ...

Después de mirar un rato esa salida, encontré las funciones "duplicadas" que quería observar. Lo que pasa aquí es que ElementInner<T> es un tipo con genéricos, y rustc produce una copia de cada uno de sus métodos para cada instancia del tipo. Así, hay una copia de cada método para ElementInner<Circle>, otra copia para ElementInner<Rect>, y así sucesivamente para todos los tipos de elementos que hay en SVG.

Vamos a ver cómo está el código que produce eso; está en una parte de librsvg que no se ha limpiado mucho después del port inicial de C a Rust.

El código inicial

Librsvg procesa el XML en un documento SVG y construye algo que parece un árbol DOM. Para representar el árbol usamos el crate rctree; tiene nodos con conteo de referencias y funciones como first_child o next_sibling. Los nodos pueden representar elementos en el XML, o contenido de texto adentro de las etiquetas de XML. Aquí sólo nos interesan los elementos.

Imagínate un elemento así:

<path d="M0,0 L10,10 L0,10 Z" fill="black"/>

Vamos a ver cómo se representa eso en librsvg. Dentro de cada nodo con cuenta de referencias en un rctree, librsvg guarda una enum NodeData que puede diferenciar entre elementos y contenido de texto:

enum NodeData {
    Element(Element),
    Text(Chars),
}

Luego, Element es una enum que distingue entre todos los elementos que librsvg soporta como parte del espacio de nombres svg:

enum Element {
    Circle(Box<ElementInner<Circle>>),
    Ellipse(Box<ElementInner<Ellipse>>),
    Path(Box<ElementInner<Path>>),
    // ... se omiten más o menos 50 adicionales ...
}

Dentro de cada una de esas variantes de la enum hay un ElementInner<T>, una struct con un parámetro de tipo genérico. ElementInner guarda los datos de un elemento en el DOM:

struct ElementInner<T: ElementTrait> {
    element_name: QualName,
    attributes: Attributes,
    // ... se omiten otros campos
    element_impl: T,
}

Para el elemento <path> que puse arriba, esta estructura contendría lo siguiente:

  • element_name: un nombre path con un espacio de nombres svg.
  • attributes: un arreglo de parejas (nombre, valor), en este caso (d, "M0,0 L10,10 L0,10 Z"), (fill, "black").
  • element_impl: Un tipo concreto, en este caso Path.

Los detalles del tipo Path no importan mucho aquí; es sólo la representación interna de las curvas de Bézier.

struct Path {
    path: Rc<SvgPath>,
}

Vamos a ver cómo está dispuesto todo esto en la memoria.

Disposición inicial de la memoria

Aquí se ilustra cómo se organizan los tipos anteriores en la memoria, en términos de bloques reservados en la pila. Vamos a ignorar el rctree:Node que envuelve a un NodeData.

La enum NodeData, y ElementInner<T> (descripción en el texto)

Hay un bloque reservado para la enum NodeData, y ese bloque contiene el discriminante de la enum y el Element que está inmerso como parte de una de sus variantes. Luego, la enum Element también tiene su propio discriminante y espacio para un Box (i.e. un puntero), pues cada una de las variantes de Element tan sólo guarda un box.

Ese box apunta a un bloque reservado para un ElementInner<T>, que a su vez contiene un struct Path.

Es incómodo que los campos que contienen cosas específicas de XML, como el nombre de un elemento y sus atributos, están en ElementInner<T> y no en Element. Más aún, ElementInner<T> tiene un montón de métodos:

impl<T: ElementTrait> ElementInner<T> {
    fn new(...) -> ElementInner<T> {
        // mucho código para el constructor
    }

    fn element_name(&self) -> &QualName {
        ...
    }

    fn get_attributes(&self) -> &Attributes {
        ...
    }

    // Un montón de métodos adicionales
}

Sin embargo, ¡ninguno de esos métodos usa el campo element_impl: T! Es decir, todos los métodos hacen cosas comunes a los elementos de XML, pero el único que lidia con el campo element_impl es el método ::draw() — y lo único que hace es delegar la llamada al tipo concreto que está en el element_impl.

Eliminar ese tipo con genéricos

Entonces, vamos a cambiar de orden las cosas. Hice esto:

  • Cambiar la enum Element para que sea struct Element, con campos comunes de los elementos de XML.

  • Ese struct tiene un campo Element.element_data...

  • ... que es de tipo ElementData, una enum que sabe de todos los tipos de elementos para SVG.

Nos quedan tipos sin parámetros genéricos:

struct Element {
    element_name: QualName,
    attributes: Attributes,
    // ... se omiten otros campos
    element_data: ElementData,
}

enum ElementData {
    Circle(Box<Circle>),
    Ellipse(Box<Ellipse>),
    Path(Box<Path>),
    // ...
}

Después de esos cambios, así queda la disposición en memoria:

Enum NodeData enum con boxes, Element, y ElementData (descripción en el texto)

Esto tiene un bloque reservado adicional, pero vamos a ver cómo cambió el tamaño del código binario.

Tamaño del código binario

Queremos saber el tamaño de la sección .text del ejecutable en formato ELF; es la sección donde se guarda el código de máquina:

# viejo
$ objdump --section-headers ./target/release/rsvg-bench
Idx Name          Size      VMA               LMA               File off  Algn
 15 .text         0029fa17  000000000008a060  000000000008a060  0008a060  2**4
(2750999 bytes)

# nuevo
Idx Name          Size      VMA               LMA               File off  Algn
 15 .text         00271ff7  000000000008b060  000000000008b060  0008b060  2**4
(2564087 bytes)

El código nuevo es 186912 bytes más pequeño. No es la gran cosa, pero cargo-bloat ya no muestra funciones duplicadas o monomorfizadas sin sentido.

Versión vieja:

$ cargo bloat --release --crates
 File  .text     Size Crate
10.0%  38.7%   1.0MiB librsvg
# lines omitted
25.8% 100.0%   2.6MiB .text section size, the file size is 10.2MiB

Versión nueva:

$ cargo bloat --release --crates
 File  .text     Size Crate
 9.2%  37.5% 939.5KiB librsvg
24.6% 100.0%   2.4MiB .text section size, the file size is 10.0MiB

El tener menos código de máquina debe ayudar un poco a mantener la proximidad en el cache, pero las funciones involucradas no están en el "camino caliente" del código. Prácticamente todo el tiempo de ejecución de librsvg se va en Cairo para el renderizado y en Pixman para la composición.

Despachado dinámico

Todos los tipos concretos para los elementos (Circle, ClipPath, etc.) implementan un ElementTrait, que tiene métodos como draw(), aunque esto no se ve en el código de arriba. Esto es lo más conviente para librsvg; usar Box<ElementTrait> para eliminar la información de tipos concretos sería un poco incómodo ahí.

Al final de cuentas el código necesita encontrar la tabla de métodos virtuales del ElementTrait que corresponde a cada una de las variantes de ElementData:

let dato: &dyn ElementTrait = match self {
    ElementData::Circle(d) =>   &**d,
    ElementData::ClipPath(d) => &**d,
    ElementData::Ellipse(d) =>  &**d,
    // ...
};

dato.algún_método_del_trait(...);

Ese &**d horrible es para llegar al &dyn ElementTrait que se implementa por cada variante. Debe poderse hacer menos feo cuando se estabilicen los patrones para boxes en el compilador de Rust.

Esta no es la única forma de hacer las cosas. Para librsvg es útil poder saber el tipo concreto de cada elemento, es decir, tener una enum con todos los tipos de elementos conocidos. Algún código de otro tipo podría ser feliz con la eliminación de tipo que ocurre al poner un Box<AlgúnTrait>. Si ese código necesita recuperar el tipo concreto de lo que se guarda en el box, se puede usar algo como downcast-rs.

De hecho cambió el consumo de memoria

Tal vez hayas notado en los diagramas anteriores que el NodeData original no tenía sus variantes dentro de Boxes, pero ahora sí los tiene.

Versión vieja:

enum NodeData {
    Element(Element),
    Text(Chars),
}

Versión nueva:

enum NodeData {
    Element(Box<Element>),
    Text(Box<Chars>),
}

Una cosa de la que no me di cuenta durante la primera ronda de optimización de memoria es que la variante NodeData::Text(Chars) no está en un Box. Es decir, el tamaño de la enum NodeData es igual al tamaño del mayor de Element y Chars, más el espacio para el discriminante de la enum. Quería hacer que ambas variantes ocuparan el mismo espacio, y al meterlas en Boxes cada una ocupa sólo el espacio de un puntero.

Medí el consumo de memoria en la pila de un SVG razonablemente grande:

Mapa de carreteras de la India, de Wikimedia Commons

Usé la heramienta Massif de Valgrind para medir el consumo máximo de memoria durante la etapa de cargar el SVG:

valgrind --tool=massif --massif-out-file=massif.out ./target/release/rsvg-bench --num-load 1 --num-render 0 India_roadway_map.svg
ms_print massif.out

Lo primero que muestra ms_print es un resumen del consumo de memoria a lo largo de la ejecución del programa, y un listado de las "fotos instantáneas" que le tomó a la memoria en la pila. Esto es un extracto de la salida de la versión nueva del código, donde la foto 36 es la que tiene el consumo máximo de memoria:

MB
14.22^                                                                      : 
     |                                                @#::::::::::::::::::::: 
     |                                              @@@#:      :::: :: ::: :: 
     |                                            @@@@@#:      :::: :: ::: :: 
     |                                          @@@ @@@#:      :::: :: ::: :: 
     |                                        @@@ @ @@@#:      :::: :: ::: :: 
     |                                       @@@@ @ @@@#:      :::: :: ::: :: 
     |                                    @@@@@@@ @ @@@#:      :::: :: ::: :: 
     |                                  @@@@ @@@@ @ @@@#:      :::: :: ::: :: 
     |                                 @@ @@ @@@@ @ @@@#:      :::: :: ::: :::
     |                               @@@@ @@ @@@@ @ @@@#:      :::: :: ::: :::
     |                              @@ @@ @@ @@@@ @ @@@#:      :::: :: ::: :::
     |                             @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: :::
     |                          @@@@@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: :::
     |                        :@@@ @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: ::@
     |                     @@@:@@@ @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: ::@
     |                 @@@@@ @:@@@ @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: ::@
     |              :::@ @ @ @:@@@ @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: ::@
     |            :@:: @ @ @ @:@@@ @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: ::@
     |     @@@@::::@:: @ @ @ @:@@@ @@@ @@ @@ @@@@ @ @@@#:      :::: :: ::: ::@
   0 +----------------------------------------------------------------------->Mi
     0                                                                   380.9

Number of snapshots: 51
 Detailed snapshots: [3, 4, 5, 9, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 (peak), 50]

Como sólo estamos midiendo el consumo de memoria durante la carga, no el renderizado, la gráfica nos muestra cómo el consumo de memoria sube poco a poco hasta llegar al máximo cuando todo el SVG ya está cargado, y luego se mantiene más o menos constante mientras librsvg hace la cascada de CSS.

La versión de librsvg sin cambios muestra esto (observa cómo la foto de massif número 39 es la que tiene el mayor consumo de memoria):

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 39    277,635,004       15,090,640       14,174,848       915,792            0

Es decir, 15,090,640 bytes.

Después de hacer los cambios a la disposición en memoria, obtenemos esto:

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 36    276,041,810       14,845,456       13,935,702       909,754            0

Es decir, después de los cambios, el consumo máximo de memoria ya que todo el archivo SVG está cargado es de 14,845,456 bytes. Los cambios anteriores no sólo redujeron el tamaño del código binario, sino también el consumo de memoria en la pila. ¡Lindo!

Medidas de tiempo real

Ese archivo no es gigantesco — digamos, 15 MB al cargarse — entonces lo que hayamos ganado en cuanto a consumo de memoria, no es gran cosa. Sin embargo, es bonito saber que el tamaño del código binario puede reducirse, pero de todas formas no era un problema para librsvg.

Tomé varias medidas del tiempo que tardan las versiones vieja y nueva para cargar y renderizar el mismo archivo, pero no hubo diferencias significativas. Esto es porque aunque podamos tener mejor proximidad en el cache y todo eso, el tiempo de renderizado es mucho mayor que el tiempo empleado en el código que maneja los elementos. Es decir, Cairo consume la mayor parte del tiempo de ejecución de rsvg-convert, y librsvg por sí solo usa muy poquito de ese tiempo.

Conclusión

Al menos en este caso, es factible reducir la cantidad de código binario que se emitía para los tipos genéricos, pues aquí no los necesitábamos. El código en la sección .text del archivo ELF se redujo por 186912 bytes, de 2.6 MB en total.

Para el código que necesita tipos genéricos, uno puede tomar otras estrategias para reducir la cantidad de código compilado. Por ejemplo, una función que toma argumentos de tipo AsRef<Path> puede primero tomar una referencia al &Path, y luego pasarla a otra función que haga el trabajo real. Un ejemplo de la biblioteca estándar:

impl PathBuf {
    pub fn push<P: AsRef<Path>>(&mut self, path: P) {
        self._push(path.as_ref())
    }

    fn _push(&mut self, path: &Path) {
        // mucho código aquí
    }
}

La función push se va a monomorfizar en funcioncitas muy pequeñas que sólo llaman a _push después de convertir lo que les pasaste a una referencia &Path, pero la función grande _push sólo se emite compilada una vez.

Existe el crate momo, que permite hacer cosas similares de forma automática. No la he usado, entonces no tengo comentarios al respecto.

Puedes ver los parches para librsvg en el merge request.