Repository navigation
Poor compile time performance with deeply nested types #3376
Description
Activity
If you rewrite a nested type using type synonyms there is no performance degradation - so it looks like it's definitely an issue with the parser!
module Main where type T1 = T type T2 = (T1 T) type T3 = (T2 T) type T4 = (T3 T) type T5 = (T4 T) type T6 = (T5 T) type T7 = (T6 T) type T8 = (T7 T) type T9 = (T8 T) type T10 = (T9 T) type T11 = (T10 T) type T12 = (T11 T) type T13 = (T12 T) type T14 = (T13 T) type T15 = (T14 T) type T16 = (T15 T) type T17 = (T16 T) type T18 = (T17 T) type T19 = (T18 T) type T20 = (T19 T) t :: T20
So unfortunately the
TypeSynonymInstanceerror limits the type synonym trick as a temporary workaround...I have profiled
purscompiling one of these programs, and have the profiterole output here.Thanks for the report and investigation!
@natefaubion Your new parser would fix this, presumably?
Yep, this is indeed a problem with
parseType. Another repro, this time in the repl:$ stack repl purescript:lib > Right toks = Language.PureScript.lex "" "T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T )))))))))))))" > runTokenParser "" parseType tokswhich takes 10 seconds or so before producing any output.
I just checked and @natefaubion's new parser does indeed fix this.
Reacted by Jonathan King, Liam Goodacre and Colin WahlThis doesn't seem worth the effort of putting together a test for so I think we can close it. (come to think of it, at some point I suppose we will probably want to add performance regression tests for the compiler as a whole)
Reacted by Jonathan King
I am working on a project where I represent large amounts of data at the type level using
RowLists and noticed terrible (super-exponential) asymptotic compile time performance with respect the the number of elements in the list. It isn’t noticable for fewer than 8 elements, but takes ~30 minutes for a 15 element list.Initially I thought it was an unavoidable issue with constraint solving, however after further experimentation I found that I could reproduce the slowdown with this following (invalid) program:
This takes ~15 seconds on my laptop to get an error message.
(I have experience this behaviour on both versions 0.11.6 and 0.12.0)
I haven't yet investigated any further, but I'm guessing it's an issue with the parser/AST representation.
I've written a script that generates programs with increasingly nested types and plotted a graph displaying the results:
I would be happy to work on a fix, however I am very busy until the start of July.