#[deriving(PartialOrd)] is O(N^2) code size for N enum variants

[alexcrichton]

The program below generates a 259MB rlib, taking about two minutes to compile. Something pathological is going on here which shouldn't be going on.

#[deriving(PartialEq, PartialOrd)]
pub enum Key {
    Unknown                 ,
    Backspace               ,
    Tab                     ,
    Return                  ,
    Escape                  ,
    Space                   ,
    Exclaim                 ,
    Quotedbl                ,
    Hash                    ,
    Dollar                  ,
    Percent                 ,
    Ampersand               ,
    Quote                   ,
    LeftParen               ,
    RightParen              ,
    Asterisk                ,
    Plus                    ,
    Comma                   ,
    Minus                   ,
    Period                  ,
    Slash                   ,
    D0                      ,
    D1                      ,
    D2                      ,
    D3                      ,
    D4                      ,
    D5                      ,
    D6                      ,
    D7                      ,
    D8                      ,
    D9                      ,
    Colon                   ,
    Semicolon               ,
    Less                    ,
    Equals                  ,
    Greater                 ,
    Question                ,
    At                      ,
    LeftBracket             ,
    Backslash               ,
    RightBracket            ,
    Caret                   ,
    Underscore              ,
    Backquote               ,
    A                       ,
    B                       ,
    C                       ,
    D                       ,
    E                       ,
    F                       ,
    G                       ,
    H                       ,
    I                       ,
    J                       ,
    K                       ,
    L                       ,
    M                       ,
    N                       ,
    O                       ,
    P                       ,
    Q                       ,
    R                       ,
    S                       ,
    T                       ,
    U                       ,
    V                       ,
    W                       ,
    X                       ,
    Y                       ,
    Z                       ,
    Delete                  ,
    CapsLock                ,
    F1                      ,
    F2                      ,
    F3                      ,
    F4                      ,
    F5                      ,
    F6                      ,
    F7                      ,
    F8                      ,
    F9                      ,
    F10                     ,
    F11                     ,
    F12                     ,
    PrintScreen             ,
    ScrollLock              ,
    Pause                   ,
    Insert                  ,
    Home                    ,
    PageUp                  ,
    End                     ,
    PageDown                ,
    Right                   ,
    Left                    ,
    Down                    ,
    Up                      ,
    NumLockClear            ,
    NumPadDivide            ,
    NumPadMultiply          ,
    NumPadMinus             ,
    NumPadPlus              ,
    NumPadEnter             ,
    NumPad1                 ,
    NumPad2                 ,
    NumPad3                 ,
    NumPad4                 ,
    NumPad5                 ,
    NumPad6                 ,
    NumPad7                 ,
    NumPad8                 ,
    NumPad9                 ,
    NumPad0                 ,
    NumPadPeriod            ,
    Application             ,
    Power                   ,
    NumPadEquals            ,
    F13                     ,
    F14                     ,
    F15                     ,
    F16                     ,
    F17                     ,
    F18                     ,
    F19                     ,
    F20                     ,
    F21                     ,
    F22                     ,
    F23                     ,
    F24                     ,
    Execute                 ,
    Help                    ,
    Menu                    ,
    Select                  ,
    Stop                    ,
    Again                   ,
    Undo                    ,
    Cut                     ,
    Copy                    ,
    Paste                   ,
    Find                    ,
    Mute                    ,
    VolumeUp                ,
    VolumeDown              ,
    NumPadComma             ,
    NumPadEqualsAS400       ,
    AltErase                ,
    Sysreq                  ,
    Cancel                  ,
    Clear                   ,
    Prior                   ,
    Return2                 ,
    Separator               ,
    Out                     ,
    Oper                    ,
    ClearAgain              ,
    CrSel                   ,
    ExSel                   ,
    NumPad00                ,
    NumPad000               ,
    ThousandsSeparator      ,
    DecimalSeparator        ,
    CurrencyUnit            ,
    CurrencySubUnit         ,
    NumPadLeftParen         ,
    NumPadRightParen        ,
    NumPadLeftBrace         ,
    NumPadRightBrace        ,
    NumPadTab               ,
    NumPadBackspace         ,
    NumPadA                 ,
    NumPadB                 ,
    NumPadC                 ,
    NumPadD                 ,
    NumPadE                 ,
    NumPadF                 ,
    NumPadXor               ,
    NumPadPower             ,
    NumPadPercent           ,
    NumPadLess              ,
    NumPadGreater           ,
    NumPadAmpersand         ,
    NumPadDblAmpersand      ,
    NumPadVerticalBar       ,
    NumPadDblVerticalBar    ,
    NumPadColon             ,
    NumPadHash              ,
    NumPadSpace             ,
    NumPadAt                ,
    NumPadExclam            ,
    NumPadMemStore          ,
    NumPadMemRecall         ,
    NumPadMemClear          ,
    NumPadMemAdd            ,
    NumPadMemSubtract       ,
    NumPadMemMultiply       ,
    NumPadMemDivide         ,
    NumPadPlusMinus         ,
    NumPadCear              ,
    NumPadClearEntry        ,
    NumPadBinary            ,
    NumPadOctal             ,
    NumPadDecimal           ,
    NumPadHexadecimal       ,
    LCtrl                   ,
    LShift                  ,
    LAlt                    ,
    LGui                    ,
    RCtrl                   ,
    RShift                  ,
    RAlt                    ,
    RGui                    ,
    Mode                    ,
    AudioNext               ,
    AudioPrev               ,
    AudioStop               ,
    AudioPlay               ,
    AudioMute               ,
    MediaSelect             ,
    Www                     ,
    Mail                    ,
    Calculator              ,
    Computer                ,
    AcSearch                ,
    AcHome                  ,
    AcBack                  ,
    AcForward               ,
    AcStop                  ,
    AcRefresh               ,
    AcBookmarks             ,
    BrightnessDown          ,
    BrightnessUp            ,
    DisplaySwitch           ,
    KbdIllumToggle          ,
    KbdIllumDown            ,
    KbdIllumUp              ,
    Eject                   ,
    Sleep                   ,
}

cc #15346

[pnkfelix]

cc me

[alexcrichton]

Updated with a more accurate description

[alexcrichton]

As in, it appears that deriving(PartialOrd) is generating an absurd amount of code.

[alexcrichton]

Yes, --pretty expanded takes the source file from 7K to 11MB. That would help to explain the gargantuan size here. Additionally, each function is marked with #[inline] accounding for the absurd size of the metadata. Fun times!

[sfackler]

It could potentially be a regression from the partial_cmp implementation, since I touched the PartialOrd deriving logic.

[luqmana]

cc @cmr

[huonw]

Pretty sure this is my fault, sorry. :(

It might be worth deriving detecting C-like enums like this and just casting to an integer, rather than matching.

[sfackler]

@huonw any idea how long it's been like this? It could explain a blowup in the size of the rust-postgres binary that I've noticed but haven't bothered looking into.

[huonw]

It has been creating a huge match ever since I wrote the generalised deriving ages ago; but maybe partial_cmp is particularly bad for this? (I think it's somewhat unlikely that partial_cmp would be special, though.)

[pnkfelix]

@huonw yes on the way home I was also thinking that special case handling of C-like enums in the various deriving implementations could be warranted. Its not as nice as figuring out the source of this blowup (but who ever said we can't do both. :) )