derived Clone implementations for many-variant enums are unnecessarily large

589b4e3
Opened by Bobby Holley at 2023-10-08 20:47:33

The derived Clone implementations in Firefox weigh 192k [1], which is a lot.

Of that 192k, 79k of that is just for PropertyDeclaration::clone. PropertyDeclaration is a very large enum, but most of the variants are simple POD types. Ideally Rust would coalesce those together, and then generate special cases for the types that need it. Unfortunately, it appears that adding a single non-POD variant causes all the cases to be enumerated separately, as seen in the testcase at [2].

From IRC:

eddyb bholley: yeah I think this is a valid issue eddyb: if you do generate that sort of "(partial) identity match" it's unlikely to have anything else collapse it eddyb: LLVM might have a pass for switch-discriminant-dependent-values eddyb: but it probably has serious limitations in practice eddyb: bholley: but yeah this is one of those cases where not scattering in the first place is significantly easier than gathering later`

Ideally we'd do the same for PartialEq, since PropertyDeclaration::eq weighs another 61k.

[1] nm --print-size --size-sort --radix=d libxul.so | grep "..Clone" | grep -v Cloned | cut -d " " -f 2 | awk '{s+=$1} END {print s}' [2] https://play.rust-lang.org/?gist=0207af76d2e05acdbed913b7df96aa77&version=stable

  1. CC @dotdash @alexcrichton @Manishearth @eddyb @michaelwoerister

    Bobby Holley at 2018-01-27 02:22:01

  2. I was thinking about this earlier:

    The current Clone thing works at macro expansion time; which means that we don't know what is and isn't Copy. Except for types defined in other crates.

    One way to fix this would be to introduce fn clone<T>(x: T) to intrinsics and make Clone a lang item (it should be already, really, because Copy: Clone). This intrinsic is expanded during (post-monomorphization?) MIR/mir-trans or something where we have all the type info. This also lets us "poke through" nested enums if we really want to (may not be worth it).

    How high priority is this for Stylo? I could take a crack at it but it will take time. I'm also unsure if the Rust folks would want such a solution (imo this can be a speed win as well). @eddyb how well do you think this can work? Where do you think this should be introduced in the pipeline?

    Manish Goregaokar at 2018-01-27 02:39:59

  3. An alternate way of doing it is to continue generating the match, but in a later MIR pass collapse all the copy arms into a memcpy. The pass is triggered by tagging the generated impl, and runs before other MIR opts. May be fragile, but I think it should work.

    Needs to be post-monomorphization again but I think MIR is post-monomorphization anyway.

    Manish Goregaokar at 2018-01-27 02:53:39

  4. Wait, I thought this was about emtpy enum variants, not Copy vs not Copy. FWIW you don't need interaction with intrinsics and we already have shims in the compiler for clone (specifically closures), so those could be made to work on enums.

    And no, MIR is pre-monomorphization (it's what we run the MIR borrowck on, which limits its design).

    Collapsing correctly is harder than not generating the code in the first place.

    Eduard-Mihai Burtescu at 2018-01-27 09:45:57

  5. No, it's about enum variants that contain only POD.

    Can you point me to these shims? The reason I'm going through an intrinsic is that derive() is fundamentally an expansion step; we have to expand to something, even if it's a "fill this in later" placeholder intrinsic.

    Oh, also, if we do this we need to check for types where the clone impl is a copy (or is autogenerated), since clone impls for pod types can still do arbitrary things.

    Manish Goregaokar at 2018-01-27 09:53:46

  6. I just want to give a tip for a way to get clearer ASM/LLVM IR output on the playground, with no noise from formatting or main: (playground link)

    bluss at 2018-01-27 10:36:54

  7. Oh, btw this can't be done for partialeq. derive(Clone) is allowed to copy Copy things (even if Copy fields have a different Clone impl), but PartialEq doesn't work the same way. Comparing things like enums for example involves comparing specific bits (other bits may get reused).

    Manish Goregaokar at 2018-01-27 17:07:32

  8. Also note that memcmp (for PartialEq) would do the wrong thing on padding, unlike memcpy.

    Eduard-Mihai Burtescu at 2018-01-27 17:35:51

  9. @Manishearth I'm guessing this could end up saving ~100k in libxul, which is a reasonably big fish as far as these things go - even ignoring the impact on performance, build time, and everyone else in the ecosystem. If you can put in a week or so to make this work, I think that's very much worth doing from a Firefox perspective. If you think it's measured in months, we should evaluate the tradeoffs against your other priorities.

    I'm not particularly informed about this stuff, but it does seem to me like it would make sense to spit out a placeholder in the derive step, and then have the compiler generate the right thing post-monomorphization once it's clear which types are Copy.

    As for PartialEq, could we at least get the benefits here for Copy types of the same size?

    @bluss - Nice trick, that will save me time. Thanks!

    Bobby Holley at 2018-01-27 18:36:17

  10. If you think it's measured in months

    Only if it has to go through the RFC process, otherwise it's a few hours / days of hacking unless you're trying to implement an after-the-fact optimization.

    have the compiler generate the right thing post-monomorphization once it's clear which types are Copy.

    We already have something (used for Clone closures - @Manishearth is already looking into it) but it's pre-monomorphization - I hope you don't need this with type parameters. It'd be quite wasteful to have more than one MIR Clone::clone shim per type definition.

    As for PartialEq, could we at least get the benefits here for Copy types of the same size?

    No, if you have any padding bytes or any non-integer leaves, you can't use memcmp.

    Eduard-Mihai Burtescu at 2018-01-27 18:47:56

  11. @bholley yeah the impl work shouldn't take long. Pushing for it through the RFC process, as Eddy says, might.

    Post-monomorphization would be nice, but harder to achieve. Right now we directly hand off to LLVM during monomorphization so inserting more stuff there may not be great). All this means is that if you derive(Clone) a generic enum, variants containing generic types will be assumed to not be Copy, even if after substitution it turns out they aren't.

    This could affect us a bit; many of our generic enums are full of Copy types (usually Au) in computed mode. But I suspect it will still be worth it.

    Manish Goregaokar at 2018-01-28 01:24:50

  12. (Slightly off-topic for this issue: for other method like PropertyDeclaration::id I’ve been pondering whether we’d be better off making PropertyDeclaration a tagged union rather than a Rust enum. For Clone though that won’t help us much, unless maybe if we add Python/macro-level data for which properties’s values are known/supposed to be Copy.)

    Simon Sapin at 2018-01-28 01:54:30

  13. For generic enums, we again have a very important distinction, in whether the many-variant enums are generic over Copy types or just contain values of other generic types, instantiated at Copy types (the latter is much easier). Oh and if you're generic but always over Copy types, T: Copy bounds (or any other trait implying Copy) would also work (with a MIR shim at least).

    Eduard-Mihai Burtescu at 2018-01-28 10:21:42

  14. Some of the variants of PropertyDeclaration have fields that contains (concrete instantiations of) generic types, but it is not generic itself.

    Simon Sapin at 2018-01-28 10:38:54

  15. Yeah this is also enums with possibly-copy types in their generics. The main one that's problematic isn't of this type, but various generic property enums are. I think assuming all generics are !Copy is a good-enough solution for most of the problem though .

    Manish Goregaokar at 2018-01-28 11:25:08

  16. I think assuming all generics are !Copy is a good first step.

    You don't get a choice if you work at the MIR level - if a bound implies T: Copy, fields using T will appear copyable. It's more manual at the syntactical level, but we're not doing that, right?

    Eduard-Mihai Burtescu at 2018-01-28 11:28:47

  17. Yeah, I mistyped and edited that, meant to say "good enough solution for most of the problem"

    Manish Goregaokar at 2018-01-28 11:30:04

  18. There is a seemingly-working WIP at https://github.com/rust-lang/rust/pull/47867

    Manish Goregaokar at 2018-01-30 13:45:01