Skip to content

Yoyo Code
MatyΓ‘Ε‘ Racek's blog


Compile time improvements for derive(Debug)

Recently, I've helped to optimize compiler performance on derive(Debug) implementation. This ended being a bit of a rabbit hole, and some of the issues we encountered and tricks we used might be useful to know for Rust developers in general, so I decided to summarize it here.

It all started a while ago with #133945, where @themathas reported that deriving Debug on large enums is slow, and it has quadratic complexity with the number of variants.

This is not exactly surprising, let's see why. The debug impl is fairly straightforward:

std::fmt::write_str(formatter, match (value) {
    Sprites::Sprite1 => "Sprite1",
    Sprites::Sprite2 => "Sprite2",
    // ...
})

There are two main problems with this - match checking and borrow checking.

Match checking algorithm checks whether all cases of match statement are covered and useful. Usefulness is only needed for warnings, but they are both done in the same pass. This algorithm in general is NP-complete, because you can reduce checking of match (boolean, boolean, boolean, ..) to SAT, but this case specifically is "just" quadratic. Roughly speaking because every match arm gets compared to every previous match arm (which is quadratic) and the enum is simple, so there's no complicated pattern deconstruction logic.

Borrow checking is superlinear as well, but it's a bit more tricky to analyze, because the algorithm does more things. Nevertheless, one simple example is that for each function, it creates some matrices with dimensions that correspond to number of locals times the number of statements. This seems fine, because there are no local variables in this function, but this also applies to temporary locals that the compiler generates automatically. It turns out that for every string literal in the match arm, the compiler creates a new temp local for storing it, before it is copied into the local that holds the final value. Also, strings are references, which means that they participate in borrow checking, though I believe static strings are eliminated early in the computation.

Other problems include binary size bloat and relocation costs from having a lot of small strings. Those sizes also influence metadata and query cache size.

Using concatenated string for C-like enums πŸ”—

The initial solution proposed in the issue was to avoid the match altogether, concatenate all variant names into a single string and index into it using the enum's discriminant, mapped to the name index. Something like:

let names = "Sprite1Sprite2...";
let indexes = [0, 7, ...];
let variant_name = names[indexes[discriminant]..indexes[discriminant + 1]];
std::fmt::write_str(formatter, variant_name)

This was implemented by @makai410 in #155452, but the initial implementation did compile slower in many cases. In fact, two previous attempts were closed before for the same reason.

I met @makai410 on Rust All Hands, we talked about the PR, and I gave him some suggestions to try out. The problem was that this solution ended up introducing more code constructs that have to get through the compiler machinery. For example, indexing desugars to Index::index call, which is a generic function on a trait, so the compiler has to invoke a bunch of trait solver machinery to type check it and generate the code.

The solution is to mimic what we already do for other Debug derives - move all common code into a new, non-generic helper function in std, and generate only a single call with arguments containing the variant names, indexes, and discriminant.

The other problem was that this optimization has larger fixed cost than the original version, so it's better to apply it to larger enums only.

With that, @makai410 wrote a tool to figure out the threshold and landed the PR which finally showed the improvement.

Bitflags regression πŸ”—

Unfortunately, the PR had to be reverted a few weeks later because beta crater run uncovered a regression in bitflags, which is a crate that assigns new discriminants to enum values and derives some helper code for it. The problem is that the Debug code indexed into the list of names with an index derived from discriminant_value, so the discriminants used in the derive macro are no longer valid once the bitflags macro changes them later. This makes its Debug impl output nonsense or panic.

This in an instance of one of the most annoying (and potentially unsound) issues with macros: #148423. This problem has been dubbed a TOCTOU problem for macros - procedural macros can change or even completely discard the original code they operate on, so depending on how you order attribute macros, some macros might generate code based on input that is later changed.

This was already predicted by @themathas on the original PR, but somehow slipped through the cracks, probably because the main point about unsoundness was addressed, and the discriminant issue was either forgotten or not deemed problematic (btw. you can't imagine the terror when a compiler developer gets a notification from @themathas, it usually means you broke something real bad).

In cases involving macros, it's sometimes difficult to tell what behavior is considered stable and something people can rely on. There's not really a specific description of what people can expect from derive(Debug) if their macro also messes around with the original item definition later. We could as well say that this is a user error and something bitflags shouldn't do, but Rust tries to avoid breaking the ecosystem unless it has a very good reason, so for a non-critical issue like this, it's better to just revert.

Landing the optimization again πŸ”—

I decided to reland the optimization without using discriminant_value in #162535. This took a lot of experimentation and changing the strategy. Since we can't use discriminant_value, we have to reintroduce the match statement to produce a variant index. This way, we don't save on match checking, but we still save on borrow checking, because the match only assigns a number and not a string.

If you diff the generated MIR for match that produces either VariantName => 2 or VariantName => "VariantName" arms, there's actually quite a large difference. In both cases, there's a basic block for each arm, but the integer one contains only 2 statements, while the string ones contains 5. On top of that, the integer one use the same temporary local for all arms, while the string one uses a new local for each. For large matches, this difference can drastically change memory usage and borrow checking cost.

That said, using the match makes the optimization potential much smaller, so I had to find more ways to reduce the cost of the derive to show the improvement. The big change in strategy was to avoid generating the array of indexes. If we concatenate the names with a known delimiter (space), we don't have to track those to figure out name lengths. We can generate an index of where the variant name starts, forward that to the helper function in std, and let that function figure it out by looking for the next space. Doing this means we can avoid generating AST, HIR, and MIR for the list of integer constants. Those can add up, partially because they often correspond to some individually heap allocated nodes. (e.g. Box<Expr> in AST or Box<ConstOperand<'tcx>> in MIR).

The result looks something like this:

formatter.debug_c_like_enum_write_str(
    "Sprite1 Sprite ...",
    match self {
        Sprites::Sprite1 => 0usize,
        Sprites::Sprite2 => 8usize,
        ...
    }
)

Changing it like this also allowed us to lower the threshold and apply this optimization to more enums - even those with explicit discriminates.

Even with those changes, the impact was not very clear in our benchmarks. In these cases, we usually add a new benchmark to make sure this is tracked somewhere, otherwise we might accidentally revert it at some point and cause a silent compiler performance regression.

In #2617, I proposed to add a new benchmark specifically targeting the reproducer from the original issue. In the end, we decided to just add derive(Debug) to existing stress test in #2618. With that in the suite, the PR finally showed clear 10% compile time and 90% memory usage reduction on the stress test.

Binary size regression on MSP430 πŸ”—

Unfortunately, this is not the end, because this PR caused a regression as well. This time, it was a binary size regression reported in #165189, notably important for embedded targets.

The problem here is fairly subtle. Let's look at the implementation of debug_c_like_enum_write_str:

fn debug_c_like_enum_write_str(&mut self, names: &str, start_index: usize) -> Result {
    self.write_str(names[start_index..].split(' ').next().unwrap())
}

The new strategy uses .split(' ') to find the end of the variant name. This is a fairly heavy iterator, because it pulls in a lot UTF-8 handling. Another problem is even less obvious - indexing into a string needs UTF-8 handling as well. Indexing itself is still fine, because it just needs to check for codepoint which is fairly simple, but std tries to be helpful if you index incorrectly, and it generates a really nice error which tells you exactly what is the problem, and this pulls in a lot of strings and formatting machinery (see slice_error_fail_rt).

Curiously, the reproducer program doesn't even contain debug formatting, so this impact is a bit unexpected. The bloat is pulled in through Result::unwrap, because it formats the error into the panic message, and this error is often an enum with derive(Debug). Those embedded targets use unwrap for functions that access peripherals, because once those fail, there's often nothing reasonable to do in the program.

We ended up fixing this by using custom split_str_by_space routine which avoids UTF-8 handling (variant names are ascii), and used .get().unwrap() instead of indexing to avoid slice_error_fail_rt call. This was all done with the help of @Jules-Bertholet in #165140, together with more cleanups and binary size improvements in those derive macros.

Using a single string for structs as well πŸ”—

Before we found the regression above, I figured we can use the string concatenation strategy in other Debug derives. As I hinted earlier, derives for structs and enums were already optimized into a single function call before (mostly by @nnethercote in #98190). The base version passes an array of field names and an array of field values (as &[dyn Debug]) into the helper function in std. We also have specialized variants for structs up to 5 fields which don't use the array to avoid its compile time costs.

Since we already use a list of names, we can change that to a single concatenated string as well, and let the std helper split it in the common code. I implemented this in #164726, which improved compile time in many cases, notably for crates with larger structs, like ripgrep.

Once we merged this, we could clean up some of the duplicated code and unify code paths for tuples and structs, which I did in #165140. This coincided with the binary size regression from above so we put those fixes there as well, as it was easier to fix when all the code paths were united. This also reduced compile time and binary size of eza.

Future work πŸ”—

I think we can still push this optimization a bit further to cover more complex enums. Those currently use the concatenated string strategy only for individual variants, because those are processed the same way as structs.

Of course, we should also adress the match checking cost. We can maybe do something wacky in the derive, but I think the proper way to fix it is just optimizing the algorithm, because it really doesn't have to be quadratic in this case. That's easier said than done because the algorithm is quite complex, but it should be doable.

Takeaways πŸ”—

It's a bit of a mess, isn't it? I think this whole effort is once again a reminder why I think that procedural macros are not really a good abstraction. What's really absurd in this case is that derive(Debug) is implemented in the compiler, operates directly on the AST, and yet, it still has to resort to weird hacks like this to avoid pitfalls and compile time cost.

In principle, the compiler already knows the enum's correct discriminant and the fastest way to make the derive for a specific struct, but the derive happens too early in the pipeline, where none of this is figured out yet, and can be changed by later passes. This is why I'm really glad we're currently experimenting with reflection, because that's just much better fit for many use cases served by derives today.


btw. if you want to support my work on the compiler, you can sponsor me on GitHub.