Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005562OCamlOCaml typingpublic2012-03-27 17:492012-03-29 09:46
Reporterfrisch 
Assigned Togarrigue 
PrioritynormalSeverityminorReproducibilityhave not tried
StatusresolvedResolutionnot fixable 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0005562: Slow type-checking with -principal and mutually recursive object types
DescriptionThe attached file takes 12s to compile with "ocamlc.opt -principal" and no measurable time without -principal.
TagsNo tags attached.
Attached Files? file icon slow.ml [^] (1,230 bytes) 2012-03-27 17:49 [Show Content]
? file icon slow_2.ml [^] (574 bytes) 2012-03-28 09:39 [Show Content]
? file icon slow_3.ml [^] (538 bytes) 2012-03-28 09:45 [Show Content]

- Relationships

-  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.

- Issue History
Date Modified Username Field Change
2012-03-27 17:49 frisch New Issue
2012-03-27 17:49 frisch Status new => assigned
2012-03-27 17:49 frisch Assigned To => garrigue
2012-03-27 17:49 frisch File Added: slow.ml
2012-03-27 17:51 frisch Note Added: 0007201
2012-03-27 17:51 frisch Note Edited: 0007201 View Revisions
2012-03-27 18:44 frisch Note Added: 0007203
2012-03-27 18:46 frisch Note Edited: 0007203 View Revisions
2012-03-28 01:31 garrigue Note Added: 0007204
2012-03-28 01:31 garrigue Status assigned => resolved
2012-03-28 01:31 garrigue Resolution open => not fixable
2012-03-28 09:39 frisch File Added: slow_2.ml
2012-03-28 09:45 frisch File Added: slow_3.ml


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker