Let's continue with the enormous SVG from the last time, a map extracted from OpenStreetMap.
According to Massif, peak memory consumption for that file occurs at the following point during the execution of rsvg-convert. I pasted only the part that refers to Bézier paths:
--------------------------------------------------------------------------------
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)
Line 1 has the totals, and we see that at that point the program uses 1,329,943,212 bytes on the heap.
Lines 3 and 5 give us a hint that into_path is being called; this is
the function that converts a temporary/mutable PathBuilder into a
permanent/immutable Path.
Lines 2 and 4 indicate that the arrays of PathCommand, which are
inside those immutable Paths, use 24.88% + 3.60% = 28.48% of the
program's memory; between both they use
352,523,448 + 50,990,328 = 403,513,776 bytes.
That is about 400 MB of PathCommand. Let's see what's going on.
What is in a PathCommand?
A Path is a list of commands similar to PostScript, which get used
in SVG to draw Bézier paths. It is a flat array of PathCommand:
pub struct Path {
path_commands: Box<[PathCommand]>,
}
pub enum PathCommand {
MoveTo(f64, f64),
LineTo(f64, f64),
CurveTo(CubicBezierCurve),
Arc(EllipticalArc),
ClosePath,
}
Let's see the variants of PathCommand:
MoveTo: 2 double-precision floating-point numbers.LineTo: same.CurveTo: 6 double-precision floating-point numbers.EllipticalArc: 7 double-precision floating-point numbers, plus 2 flags (see below).ClosePath: no extra data.
These variants vary a lot in terms of size, and each element of the
Path.path_commands array occupies the maximum of their sizes
(i.e. sizeof::<EllipticalArc>).
A more compact representation
Ideally, each command in the array would only occupy as much space as it needs.
We can represent a Path in a different way, as two separate arrays:
- A very compact array of commands without coordinates.
- An array with coordinates only.
That is, the following:
pub struct Path {
commands: Box<[PackedCommand]>,
coords: Box<[f64]>,
}
The coords array is obvious; it is just a flat array with all the
coordinates in the Path in the order in which they appear.
And the commands array?
PackedCommand
We saw above that the biggest variant in PathCommand is
Arc(EllipticalArc). Let's look inside it:
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),
}
There are 7 f64 floating-point numbers there. The other two fields,
large_arc and sweep, are effectively booleans (they are just enums
with two variants, with pretty names instead of just true and
false).
Thus, we have 7 doubles and two flags. Between the two flags there are 4 possibilities.
Since no other PathCommand variant has flags, we can have the
following enum, which fits in a single byte:
#[repr(u8)]
enum PackedCommand {
MoveTo,
LineTo,
CurveTo,
ArcSmallNegative,
ArcSmallPositive,
ArcLargeNegative,
ArcLargePositive,
ClosePath,
}
That is, simple values for MoveTo/etc. and four special values for
the different types of Arc.
Packing a PathCommand into a PackedCommand
In order to pack the array of PathCommand, we must first know how
many coordinates each of its variants will produce:
impl PathCommand {
fn num_coordinates(&self) -> usize {
match *self {
PathCommand::MoveTo(..) => 2,
PathCommand::LineTo(..) => 2,
PathCommand::CurveTo(_) => 6,
PathCommand::Arc(_) => 7,
PathCommand::ClosePath => 0,
}
}
}
Then, we need to convert each PathCommand into a PackedCommand and
write its coordinates into an array:
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. for the other simple commands
PathCommand::Arc(ref a) => a.to_packed_and_coords(coords),
}
}
}
Let's look at that to_packed_and_coords more closely:
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,
}
}
}
Creating the compact Path
Let's look at PathBuilder::into_path line by line:
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());
First we compute the total number of coordinates using fold; we ask
each command cmd its num_coordinates() and add it into the acc
accumulator.
Now we know how much memory to allocate:
let mut packed_commands = Vec::with_capacity(num_commands);
let mut coords = vec![0.0; num_coords];
We use Vec::with_capacity to allocate exactly as much memory as we will
need for the packed_commands; adding elements will not need a
realloc(), since we already know how many elements we will have.
We use the vec! macro to create an array of 0.0 repeated
num_coords times; that macro uses with_capacity internally. That is the
array we will use to store the coordinates for all the commands.
let mut coords_slice = coords.as_mut_slice();
We get a mutable slice out of the whole array of coordinates.
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..];
}
For each command, we see how many coordinates it will generate and we
put that number in n. We get a mutable sub-slice from
coords_slice with only that number of elements, and pass it to
to_packed for each command.
At the end of each iteration we move the mutable slice to where the next command's coordinates will go.
Path {
commands: packed_commands.into_boxed_slice(),
coords: coords.into_boxed_slice(),
}
}
At the end, we create the final and immutable Path by converting
each array into_boxed_slice like the last time. That way each of
the two arrays, the one with PackedCommands and the one with
coordinates, occupy the minimum space they need.
An iterator for Path
This is all very well, but we also want it to be easy to iterate on
that compact representation; the PathCommand enums from the
beginning are very convenient to use and that's what the rest of the
code already uses. Let's make an iterator that unpacks what is inside
a Path and produces a PathCommand for each element.
pub struct PathIter<'a> {
commands: slice::Iter<'a, PackedCommand>,
coords: &'a [f64],
}
We need an iterator over the array of PackedCommand so we can visit
each command. However, to get elements of coords, I am going to
use a slice of f64 instead of an iterator.
Let's look at the implementation of the iterator:
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
}
}
}
Since we want each iteration to produce a PathCommand, we declare it
as having the associated type Item = PathCommand.
If the self.commands iterator has another element, it means there is
another PackedCommand available.
We call PathCommand::from_packed with the self.coords slice to
unpack a command and its coordinates. We see how many coordinates the
command consumed and re-slice self.coords according to the number of
commands, so that it now points to the coordinates for the next
command.
We return Some(cmd) if there was an element, or None if the
iterator is empty.
The implementation of from_packed is obvious and I'll just paste a
bit from it:
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. for the other variants in PackedCommand
PackedCommand::ArcSmallNegative => PathCommand::Arc(EllipticalArc::from_coords(
LargeArc(false),
Sweep::Negative,
coords,
)),
PackedCommand::ArcSmallPositive => // etc.
PackedCommand::ArcLargeNegative => // etc.
PackedCommand::ArcLargePositive => // etc.
}
}
}
Results
Before the changes (this is the same Massif heading as above):
--------------------------------------------------------------------------------
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
^^^^^^^^^^^^^
boo
After:
--------------------------------------------------------------------------------
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 yeah
We went from using 1,329,943,212 bytes down to 1,023,147,907 bytes, that is, we knocked it down by 300 MB.
However, that is for the whole program. Above we saw that Path data
occupies 403,513,776 bytes; how about now?
->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)
Perfect. We went from occupying 403,513,776 bytes to just
81,525,328 bytes. Instead of Path data amounting to 28.48% of the
heap, it is just 7.45%.
I think we can stop worrying about Path data for now. I like how
this turned out without having to use unsafe.