0005562: Slow type-checking with -principal and mutually recursive object types

Notes
(0007201) frisch (developer) 2012-03-27 17:51 edited on: 2012-03-27 17:51	Note: we have a real piece of code which exhibits the same behavior.

(0007203) frisch (developer) 2012-03-27 18:44 edited on: 2012-03-27 18:46	All the time is spent in the unification, which keeps instantiating types. I've the feeling this is related to abbreviations. If we replace !Clflags.principal by false in Ctype.proper_abbrevs, then type-checking is immediate again.

(0007204) garrigue (manager) 2012-03-28 01:31	This is a well-known problem with -principal and mutually recursive classes. Basically, abbreviations ensure that recursive types expand to regular trees. However, in the case of recursive classes, this means moving from a graph to a regular tree, which is exponential. The problem is avoided by always expanding the same type constructor to the node when there are no type parameters. This is fine in the normal mode, but incorrect in principal mode, since it means that sharing is increased, while principality detection relies on unsharing. This is the main reason -principal is not enabled by default. Sorry to see that you hit this bad case. Note also that it is known that the situation is made worse by using module aliases.

Relationships