(Blog post/Video) Avoiding quadratic core code size

Posted on August 20, 2021 (last updated 2021-10-20)

I’ve thought, written and spoken quite a lot about this topic:

Blog post: Avoiding quadratic core code size with large records

A module that contains nothing but the definition of a single record with 100 fields and some type class instances, using ghc’s standard representation for records, along with the code generated by the RecordDotPreprocessor plugin and the Generic instance generated by generics-sop, results in a core representation of a whopping 450,000 terms/types/coercions, takes 3 seconds to compile, and requires 500M of RAM to compile. With the large-records library, we get a module with essentially the same functionality, but with a core size of a mere 14,000 terms/types/coercions, which compiles within 1 second and requires roughly 100M of RAM. In this blog post we describe why this simple module generates so much code, and how the large-records library manages to reduce this by more than an order of magnitude.

Read more at well-typed.com

Blog post: Induction without core-size blow-up (a.k.a. Large records: anonymous edition)

An important factor affecting compilation speed and memory requirements is the size of the core code generated by ghc from Haskell source modules. Thus, if compilation time is an issue, this is something we should be conscious of and optimize for. In [part 1][part1] of this blog post we took an in-depth look at why certain Haskell constructs lead to quadratic blow-up in the generated ghc core code, and how the [large-records][lr-hackage] library avoids these problems. Indeed, the large-records library provides support for records, including support for generic programming, with a guarantee that the generated core is never more than O(n) in the number of record fields.

The approach described there does however not directly apply to the case of anonymous records. This is the topic we will tackle in this part 2. Unfortunately, it seems that for anonymous records the best we can hope for is O(n log n), and even to achieve that we need to explore some dark corners of ghc. We have not attempted to write a new anynomous records library, but instead consider the problems in isolation; on the other hand, the solutions we propose should be applicable in other contexts as well. Apart from section “Putting it all together”, the rest of this blog post can be understood without having read part 1.

Read more at well-typed.com

Presentations (videos)