Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Slow type-checking with -principal and mutually recursive object types #5562

Closed
vicuna opened this issue Mar 27, 2012 · 3 comments
Closed

Slow type-checking with -principal and mutually recursive object types #5562

vicuna opened this issue Mar 27, 2012 · 3 comments
Assignees

Comments

@vicuna
Copy link

vicuna commented Mar 27, 2012

Original bug ID: 5562
Reporter: @alainfrisch
Assigned to: @garrigue
Status: closed (set by @xavierleroy on 2015-12-11T18:04:25Z)
Resolution: not fixable
Priority: normal
Severity: minor
Category: typing
Monitored by: @jmeber

Bug description

The attached file takes 12s to compile with "ocamlc.opt -principal" and no measurable time without -principal.

File attachments

@vicuna
Copy link
Author

vicuna commented Mar 27, 2012

Comment author: @alainfrisch

Note: we have a real piece of code which exhibits the same behavior.

@vicuna
Copy link
Author

vicuna commented Mar 27, 2012

Comment author: @alainfrisch

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.

@vicuna
Copy link
Author

vicuna commented Mar 27, 2012

Comment author: @garrigue

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants