Improving the compilation speed of TH generated parsing code from mkYesodData

[TeofilC]

A while ago, I looked into the performance of compiling the code generated by mkYesodData. While the TH generation runs quite quickly, the compilation of the generated code is slow.

In particular, the generated route parsing code creates a giant case statement with a lot of view patterns. I'm suspicious that a lot the slowness comes from this. I remember finding some evidence that this was the case, but I can't remember precisely.
Case staments on strings/text values are also O(n), so this is also likely generating suboptimal code (especially if you have lots of routes).

I don't use yesod anymore, so I probably won't look into this any further any time soon.
But this might a good avenue to investigate for someone hitting bad compile times.

Perhaps it would be generating something like a trie (although handling capture parsing might be annoying, and require turning things into Any) or just parser combinators.

I recall the other generated code also being suboptimal, but the parsing code seemed especially bad.

[parsonsmatt]

Hmm, I wonder if very large sum types have similar issues as very large records. I can imagine a huge case expression taking a while to compile.

Shrinking Route site into smaller chunks with nested routes should help significantly, especially with the work in #1880 to allow compiling these in separate modules. This shrinks the case expressions and pattern matches, which should take care of most of the issues.

I would be surprised if ViewPatterns or matching on string literals is particularly slow. If you can recall anything you saw that indicated that to be a problem I'd be very interested in seeing it.

The match with string literals is unfortunately not optimal, particularly if you have non-nested routes which inspect the first fragment many times. If you do, like,

mkYesod "App" [parseRoutes|

/organizations/ OrganizationIndexR GET POST
/organizations/#{OrganizationId} OrganizationR GET POST
/organizations/#{OrganizationId}/edit EditOrganizationR GET POST
/organizations/#{OrganizationId}/users/ OrganizationUserIndexR GET POST
/organizations/#{OrganizationId}/users/#UserId OrganizationUserR GET POST
|]

Then you will repeat the comparison for organizations each time.

A trie based structure would be significantly better for runtime route parsing.

[TeofilC]

Hmm, I wonder if very large sum types have similar issues as very large records. I can imagine a huge case expression taking a while to compile.

Yeah I think that's quite likely.

It's a bit frustrating, since I think having a huge sum type is completely superfluous here. The only time I have ever seen these be pattern matched on is in the yesod TH generated code.

Shrinking Route site into smaller chunks with nested routes should help significantly

Yeah that's a good point. What I was seeing was code that was superlinear to compile in the amount of routes. But if you can get the routes in a file down to a reasonable level, then you side-step the problem.

If you can recall anything you saw that indicated that to be a problem I'd be very interested in seeing it.

I remember that I looked at -ddump-timings, -dth-dec-file, -ddump-simpl and maybe the -ddump-simpl-iterations one.

The main thing I noticed was that you get this huge case statement.

There were lots of little things like using ViewPatterns that could've just been replaced by what they would desugar or simplify to. Another example is that it generates some code that looks like field_name record_value where record_value is known at compile time, so we could have just directly emitted the identifier the field pointed to, which then led to a lot of CSE.

I think the main thing I saw was that the ddump-timings indicated that a lot of time was spent in typechecking/desugarring, and that seemed a bit strange, especially since we don't have any complex type level code here. Although I'm not sure if I'm remembering this correctly.
I remember my theory being that the huge case statement was triggering something super-linear in some case statement logic in the typechecker.

Really all of this code would benefit a lot IMO from someone to go through it, understand it and simplify it.
I was going to try to improve some of these things, but then ran out of steam since there's no clear semantics for these things and a lot of the internals are exposed, so everything would be potentially a breaking change.

[jezen]

Potentially similar issues:

• mkMessage generates poor code #1545
• mkMessage eats 30 GB of memory during compile #1487
• Foundation is giving OOM errors with 120 routes, 45 tables and around 250 I18N messages #1651