There are (at least) two important sources of quadratic code size in GHC core: (1) we have no ability to inspect or update part of a record (or indeed type class dictionary) without referring to every field in the record individually, and (2) it is difficult or impossible to control sharing at the type level. This lack of type level sharing means for example that a chain of n applications of the
<*> operator is
O(n^2) in size.
This does not matter for small chains and small types, but it can make compilation slow and memory hungry for large types. In this talk we will take a closer look at the various sources of quadratic core code size, and then introduce the
large-records library. This library makes it possible to define large records with an
O(n) core size, at the cost of using an untyped internal representation. We discuss how the library works and the API that users are provided for working with these records, including an generics interface; the latter is styled on
generics-sop but differs quite in a bit in the details to avoid all
O(n^2) pitfalls. For a module containing just a single record with 100 fields, using
large-records reduces the GHC core code size by more than two orders of magnitude.
Sun 22 AugDisplayed time zone: Seoul change
20:00 - 21:30
|Exact Print Annotations in GHC
|Avoiding quadratic GHC core code size
|Improvements to GHC's parallel garbage collector
Douglas Wilson Well Typed