Poor compile time performance with deeply nested types

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:

module Main where
t :: ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T ( T )))))))))))))))))

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.

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 TypeSynonymInstance error limits the type synonym trick as a temporary workaround...

I have profiled purs compiling one of these programs, and have the profiterole output here.

Thanks for the report and investigation!

@natefaubion

@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 toks

which takes 10 seconds or so before producing any output.

@natefaubion

I just checked and @natefaubion's new parser does indeed fix this.

This 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)

Navigation Menu

Poor compile time performance with deeply nested types #3376

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Poor compile time performance with deeply nested types #3376

Description

Activity

jonathanlking commented on Jun 4, 2018

jonathanlking commented on Jun 4, 2018

jonathanlking commented on Jun 4, 2018

garyb commented on Jun 5, 2018

hdgarrood commented on Feb 14, 2019

hdgarrood commented on Feb 14, 2019

hdgarrood commented on Feb 14, 2019

hdgarrood commented on May 7, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions