Opened 5 years ago

Last modified 2 years ago

#9557 new bug

Deriving instances is slow

Reported by: Feuerbach Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.8.3
Keywords: deriving-perf Cc: slyfox, jstolarek, edsko, gidyn, hvr, erikd, RyanGlScott, michalt
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #8731 #10858 Differential Rev(s):
Wiki Page:

Description

Let's take this file (from haskell-src-exts) and build it with -O0. On my machine it takes 55s.

If we remove deriving of all classes except Functor (which is the only one used by the module itself), the time will drop down to 4s.

Different classes vary in their compile-time cost, but there's no single culprit. Among the costly ones are Generic, Data, Show, Ord.

haskell-src-exts users are very annoyed by its long compile time, about 10 minutes, especially because we don't compile with -O0 by default. It would be nice to get this fixed.

Change History (24)

comment:1 Changed 5 years ago by slyfox

Cc: slyfox added

comment:2 Changed 5 years ago by jstolarek

Cc: jan.stolarek@… added

comment:3 Changed 5 years ago by carter

Resolution: duplicate
Status: newclosed

I think this is likely a dupe of #8731

This is a problem that impacts many many projects directly and indirectly (and epecshows up when folks )

I'm marking it as a duplicate for now.

comment:4 Changed 5 years ago by Feuerbach

carter: why do you think they are the same?

There, the reason is the large number of field selectors.

Here, I was able to check that removing some of the class derivations reduces the compile time significantly.

I'm not convinced that fixing that issue will necessarily fix this one; they may (or may not) be inefficiencies in different parts of code.

comment:5 Changed 5 years ago by Feuerbach

Resolution: duplicate
Status: closednew

comment:6 Changed 5 years ago by rwbarton

Deriving a lot of instances for a lot of large types generates a lot of code. Language.Haskell.Exts.Annotated.Syntax desugared to a program with 126,396 terms and took 24.2 seconds to build (with -O0). By comparison, the longest (in terms of lines, roughly 2100) module Language.Haskell.Exts.Annotated.ExactPrint desugared to a program with only 12,181 terms and it took 2.7 seconds to build. So, I don't think there is anything wrong with the speed of deriving instances specifically.

Now, it's possible that instance deriving could be made to generate smaller code than it currently does for some particular classes... but I didn't notice anything amiss scanning through the generated instances for Decl (with -dsuppress-all -ddump-deriv -ddump-to-file). So, I don't really think deriving is to blame here.

comment:7 Changed 5 years ago by simonpj

It undoubtedly is a bit unexpected if simply adding deriving( Show ) or whatever, which seems such a little thing, generates seriously large amounts of object code.

If someone feels able to investigate I would suggest:

  • Find out if any particular class is to blame. How much of the code is generated by which classes?
  • Study the generated code to see if it could be abstracted, so that instead of lots of code, there were calls to some suitable shared functions.

Obviously there is a performance/code-size issue to worry about, but my guess is that while Eq and Ord might be performance-critical, Read and Show are not.

But it would require some thoughtful investigation.

Simon

comment:8 Changed 5 years ago by rwbarton

I performed the following list of modifications to the program and recorded the size in terms after desugaring after each step:

stepprogram size (terms)
original 126396
remove everything but data decls 122877
remove deriving Generic 106339
remove deriving Data 78544
remove deriving Traversable 70886
remove deriving Foldable 59332
remove deriving Functor 55041
remove deriving Show 42848
remove deriving Ord 11044
remove deriving Eq 2244
remove deriving Typeable 1140

So, the cost of each class is

classterms
Ord 31804
Data 27795
Generic 16538
Show 12193
Foldable 11554
Eq 8800
Traversable 7658
Functor 4291
Typeable 1104

So no individual class is adding a particularly egregious amount of code.

comment:9 Changed 5 years ago by nomeata

For those who want to play around with the module: You can fetch it from http://hackage.haskell.org/package/haskell-src-exts-1.16.0/src/src/Language/Haskell/Exts/Annotated/Syntax.hs and it is has no dependencies inside haskell-src-exts, so you can just download and compile it in isolation.

comment:10 Changed 5 years ago by nomeata

Study the generated code to see if it could be abstracted, so that instead of lots of code, there were calls to some suitable shared functions.

Looking at the Ord code (which seems to be the largest):

  • It seems that it could be made much smaller using <> (which is EQ <> x = x and y <> _ = y otherwise) instead of nested case expressions. I guess there would be a performance hit, though.
  • Do we really have to provide separate definitions for compare and < and <= and > and >=? Maybe using the default implementation for all methods but compare is good enough, and could bring code size down considerably.

Overreaching spontaneous idea: Add a method generalCompare :: r -> r -> r -> a -> a -> r to the Ord class. Implement that in deriving clauses, and have the default implementations use that. (e.g. (<) = generalCompare True False False). Should be faster than using compare + pattern matching. OTOH. all constructors of Comparing are static values, so there is probably not much to win here.

comment:11 Changed 5 years ago by nomeata

Obviously, people have considered my second suggest before, see Note [Do not rely on compare] in ghc/compiler/typecheck/TcGenDeriv.lhs#L300...

comment:12 Changed 5 years ago by Feuerbach

Is there an easy way to check what exactly takes up the time: generating the ast, renaming/typechecking it, generating the output code? Or do I have to compile ghc with profiling for that?

comment:13 Changed 5 years ago by gidyn

Cc: gideon@… added

comment:14 Changed 5 years ago by edsko

Cc: edsko added

comment:15 Changed 4 years ago by gidyn

Cc: gideon@… removed

comment:16 Changed 4 years ago by gidyn

Cc: gidyn added

comment:17 Changed 4 years ago by thomie

Type of failure: None/UnknownCompile-time performance bug

comment:18 Changed 4 years ago by nomeata

See #10858 for some ideas around the specific case of the Ord instance.

comment:19 Changed 4 years ago by jstolarek

Cc: jstolarek added; jan.stolarek@… removed

comment:20 Changed 4 years ago by hvr

Cc: hvr added

comment:21 Changed 4 years ago by ezyang

Keywords: deriving-perf added

comment:22 Changed 3 years ago by erikd

Cc: erikd added

comment:23 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added

comment:24 Changed 2 years ago by michalt

Cc: michalt added
Note: See TracTickets for help on using tickets.