Reducing code size in librsvg by removing an unnecessary generic struct

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

Someone mentioned cargo-bloat the other day and it reminded me that I have been wanting to measure the code size for generic functions in librsvg, and see if there are improvements to be made.

Cargo-bloat can give you a rough estimate of the code size for each Rust crate in a compiled binary, and also a more detailed view of the amount of code generated for individual functions. It needs a [bin] target to work on; if you have just a [lib], it will not do anything. So, for librsvg's purposes, I ran cargo-bloat on the rsvg-convert binary.

$ 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.

The output above is for cargo bloat --release --crates. The --release option is to generate an optimized binary, and --crates tells cargo-bloat to just print a summary of crate sizes. The numbers are not completely accurate since, for example, inlined functions may affect callers of a particular crate. Still, this is good enough to start getting an idea of the sizes of things.

In this case, the librsvg crate's code is about 1.0 MB.

Now, let's find what generic functions we may be able to condense. When cargo-bloat is run without --crates, it prints the size of individual functions. After some experimentation, I ended up with cargo bloat --release -n 0 --filter librsvg. The -n 0 option tells cargo-bloat to print all functions, not just the top N biggest ones, and --filter librsvg is to make it print functions only in that crate, not for example in std or regex.

$ 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 ...

After looking a bit at the output, I found the "duplicated" functions I wanted to find. What is happening here is that ElementInner<T> is a type with generics, and rustc is generating one copy of each of its methods for every type instance. So, there is one copy of each method for ElementInner<Circle>, one for ElementInner<Rect>, and so on for all the SVG element types.

The code around that is a bit convoluted; it's in a part of the library that hasn't gotten much cleanup after the C to Rust port and initial refactoring. Let's see what it is like.

The initial code

Librsvg parses the XML in an SVG document and builds something that resembles a DOM tree. The tree itself uses the rctree crate; it has reference-counted nodes and functions like first_child or next_sibling. Nodes can represent XML elements, or character content inside XML tags. Here we are interested in elements only.

Consider an element like this:

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

Let's look at how librsvg represents that. Inside each reference-counted node in an rctree, librsvg keeps a NodeData enum that can differentiate between elements and character content:

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

Then, Element is an enum that can distinguish between all the elements in the svg namespace that librsvg supports:

enum Element {
    Circle(Box<ElementInner<Circle>>),
    Ellipse(Box<ElementInner<Ellipse>>),
    Path(Box<ElementInner<Path>>),
    // ... about 50 others omitted ...
}

Inside each of those enum's variants there is an ElementInner<T>, a struct with a generic type parameter. ElementInner holds the data for the DOM-like element:

struct ElementInner<T: ElementTrait> {
    element_name: QualName,
    attributes: Attributes,
    // ... other fields omitted
    element_impl: T,
}

For the <path> element above, this struct would contain the following:

  • element_name: a qualified name path with an svg namespace.
  • attributes: an array of (name, value) pairs, in this case (d, "M0,0 L10,10 L0,10 Z"), (fill, "black").
  • element_impl: A concrete type, Path in this case.

The specifics of the Path type are not terribly interesting here; it's just the internal representation for Bézier paths.

struct Path {
    path: Rc<SvgPath>,
}

Let's look at the details of the memory layout for all of this.

Initial memory layout

Here is how the enums and structs above are laid out in memory, in terms of allocations, without taking into account the rctree:Node that wraps a NodeData.

NodeData enum, and ElementInner<T> (description in text)

There is one allocated block for the NodeData enum, and that block holds the enum's discriminant and the embedded Element enum. In turn, the Element enum has its own discriminant and space for a Box (i.e. a pointer), since each of its variants just holds a single box.

That box points to an allocation for an ElementInner<T>, which itself contains a Path struct.

It is awkward that the fields to hold XML-isms like an element's name and its attributes are in ElementInner<T>, not in Element. But more importantly, ElementInner<T> has a little bunch of methods:

impl<T: ElementTrait> ElementInner<T> {
    fn new(...) -> ElementInner<T> {
        // lots of construction
    }

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

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

    // A bunch of other methods
}

However, none but one of these methods actually use the element_impl: T field! That is, all of them do things that are common to all element types. The only method that really deals with the element_impl field is the ::draw() method, and the only thing it does is to delegate down to the concrete type's implementation of ::draw().

Removing that generic type

So, let's shuffle things around. I did this:

  • Turn enum Element into a struct Element, with the fields common to all element types.

  • Have an Element.element_data field...

  • ... that is of type ElementData, an enum that actually knows about all supported element types.

There are no types with generics in here:

struct Element {
    element_name: QualName,
    attributes: Attributes,
    // ... other fields omitted
    element_data: ElementData,
}

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

Now the memory layout looks like this:

NodeData enum with boxes, Element, and ElementData (description in text)

One extra allocation, but let's see if this changes the code size.

Code size

We want to know the size of the .text section in the ELF file.

# old
$ 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)

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

The new code is is 186912 bytes smaller. Not earth-shattering, but cargo-bloat no longer shows duplicated functions which have no reason to be monomorphized, since they don't touch the varying data.

old:

$ 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

new:

$ 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

Less code should help a bit with cache locality, but the functions involved are not in hot loops. Practically all of librsvg's time is spent in Cairo for rasterization, and Pixman for compositing.

Dynamic dispatch

All the concrete types (Circle, ClipPath, etc.) implement ElementTrait, which has things like a draw() method, although that is not visible in the types above. This is what is most convenient for librsvg; using Box<ElementTrait> for type erasure would be a little awkward there — we used it a long time ago, but not anymore.

Eventually the code needs to find the ElementTrait vtable that corresponds to each of ElementData's variants:

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

data.some_method_in_the_trait(...);

The ugly &**d is to arrive at the &dyn ElementTrait that each variant implements. It will get less ugly when pattern matching for boxes gets stabilized in the Rust compiler.

This is not the only way of doing things. For librsvg it is convenient to actually know the type of an element, that is, to keep an enum of the known element types. Other kinds of code may be perfectly happy with the type erasure that happens when you have a Box<SomeTrait>. If that code needs to go back to the concrete type, an alternative is to use something like the downcast-rs crate, which lets you recover the concrete type inside the box.

Heap usage actually changed

You may notice in the diagrams below that the original NodeData didn't box its variants, but now it does.

Old:

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

New:

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

One thing I didn't notice during the first round of memory reduction is that the NodeData::Text(Chars) variant is not boxed. That is, the size of NodeData enum is the size of the biggest of Element and Chars, plus space for the enum's discriminant. I wanted to make both variants the same size, and by boxing them they occupy only a pointer each.

I measured heap usage for a reasonably large SVG:

India Roadway Map, from Wikimedia Commons

I used Valgrind's Massif to measure peak memory consumption during loading:

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

The first thing that ms_print shows is an overview of the program's memory usage over time, and the list of snapshots it created. The following is an extract of its output for the new version of the code, where snapshot 36 is the one with peak memory usage:

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]

Since we are just measuring memory consumption during loading, the chart shows that memory usage climbs steadily until it peaks when the complete SVG is loaded, and then it stays more or less constant while librsvg does the initial CSS cascade.

The version of librsvg without changes shows this (note how the massif snapshot with peak usage is number 39 in this one):

--------------------------------------------------------------------------------
  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

That is, 15,090,640 bytes.

And after making the changes in memory layout, we get this:

--------------------------------------------------------------------------------
  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

I.e. after the changes, the peak usage of heap memory when the whole file is loaded is 14,845,456 bytes. So the changes above not only reduced the code size, but also slightly lowered memory consumption at runtime. Nice!

Wall-clock performance

This file is not huge — say, 15 MB when loaded — so whatever we gained in memory consumption is a negligible win. It's nice to know that code size can be reduced, but it is not a problem for librsvg either way.

I did several measurements of the time used by the old and new versions to render the same file, and there was no significant difference. This is because although we may get better cache locality and everything, the time spent executing the element-related code is much smaller than the rendering code. That is, Cairo takes up most of the runtime of rsvg-convert, and librsvg itself takes relatively little of it.

Conclusion

At least for this case, it was feasible to reduce the amount of code emitted for generics, since this is a case where we definitely didn't need generics! The code size in the ELF file's .text section shrank by 186912 bytes, out of 2.6 MB.

For code that does need generics, one can take different approaches. For example, a function that take arguments of type AsRef<Path> can first actually obtain the &Path, and then pass that to a function that does the real work. For example, from the standard library:

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

    fn _push(&mut self, path: &Path) {
        // lots of code here
    }
}

The push function will be monomorphized into very tiny functions that call _push after converting what you passed to a &Path reference, but the big _push function is only emitted once.

There is also the momo crate, which helps doing similar things automatically. I have not used it yet, so I can't comment further on it.

You can see the patches for librsvg in the merge request.