Compiling `#[derive(Debug)] enum` + `dbg!` is quadratic with enum variants

[theemathas]

I tried compiling this code: lib.rs.zip

The code above was generated with the following python script:

print(
    """#[derive(Debug)]
pub enum Sprites {"""
)
for i in range(10000):
    print(f"    Sprite{i},")
print(
    """}
pub fn foo() {
   println!("{:?}", Sprites::Sprite1);
}"""
)

I then compiled the code with cargo build --release. It takes 21.00s to compile on my machine, which is rather slow. It would be nice if it compiled faster.

Note that reducing the number of variants from 10000 to 1000 makes the compilation take only 0.20s to compile on my machine. I suspect that something in the Debug trait impl is taking quadratic time, but only if you actually try to debug-print something.

This issue was discovered by tongke on the rust community discord.

Meta

rustc --version --verbose:

rustc 1.83.0 (90b35a623 2024-11-26)
binary: rustc
commit-hash: 90b35a6239c3d8bdabc530a6a0816f7ff89a0aaf
commit-date: 2024-11-26
host: aarch64-apple-darwin
release: 1.83.0
LLVM version: 19.1.1

[randyli]

I runned the compiling with -Z self-profile, and the result like this:

Item	Self time	% of total time
mir_borrowck	2.03s	58.174
check_match	340.29ms	9.772
run_linker	256.34ms	7.361

Is it a good idea to assign lable A-borrow-checker ?

[scottmcm]

The solution here would probably be to change the derive, like how PartialEq already special-cases field-less variants, not anything related to borrowcheck.

For example, it could have one arm for all the field-less variants that does a slice lookup using the discriminant.

(Or just tell people not to derive debug on enums like this...)

[hanna-kruppe]

For example, it could have one arm for all the field-less variants that does a slice lookup using the discriminant.

This could be a nice improvement for other reasons too. Considering compile time, code size, performance, binary size, and data cache footprint, I think the pareto-optimal way to implement “one of these N static strings, indexed by small dense integers” for all but the smallest N is probably something like this:

static START: [u16; MAX_INDEX + 1] = [0, … /* prefix sum of string lengths */];
static STRINGS: &str = "all strings concatenated";
// indices without associated string can be mapped to an empty string without extra code
fn get_str(i: usize) -> &str {
    let (start, end) = (START[i], START[i+1]);
    &STRINGS[usize::from(start)..usize::from(end)]
}

One non-obvious benefit of using indices into a single strong is that it reduces the number of relocations (an array of &strs not only takes more space but also has one pointer per string that needs relocation for position independent code).

I’ve written this code myself once for a fieldless enum with ca. 150 variants and it did generate a smaller wasm module. But it’s real chore to do manually and it’s rarely worth the complexity, especially for further optimizations like unchecked indexing and using u8 instead of u16 if possible. Having the compiler generate this kind of lookup table automatically for derive(Debug) could be a nice improvement even for modest number of variants.