Opened 4 years ago

Closed 4 years ago

#11991 closed bug (duplicate)

Generics deriving is quadratic

Reported by: nh2 Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.3
Keywords: Generics Cc: nh2
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by nh2)

I'm compiling some code with many sum type alternatives and it's absurdly slow.

{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics (Generic)

data D = D1 | D2 | ... | D400 deriving (Generic)

main = return ()

I did a little benchmark and it's actually precisely O(n²) in the number of alternatives.

Easy repro:

I assume that this is a bug and it should be linear.

Note that it is also quadratic in memory usage.

Change History (3)

comment:1 Changed 4 years ago by nh2

Keywords: Generics added

comment:2 Changed 4 years ago by nh2

Description: modified (diff)

comment:3 Changed 4 years ago by nh2

Resolution: duplicate
Status: newclosed

Looks like I just duplicated #5642.

Note: See TracTickets for help on using tickets.