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.