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
Quadratic compilation time with large variant types #4053
Comments
Comment author: @mmottl For those of you who cannot wait for a fix, here is a somewhat kludgy workaround: Split up the type into smaller types, and combine the small ones at the end. Though it may still take about two minutes to compile a type + some functions on it with around three thousand constructors, that's still better than waiting for the heat death of the universe... |
Comment author: @garrigue I improved this in CVS branch 3.09. |
Comment author: @garrigue Considerably improved performance in 3.10.1dev.
But this is still O(n*n) :-( |
Comment author: @garrigue Optimized (#t as x) patterns in branch release310. |
Comment author: @garrigue Cannot do much more for it, and it seems fast enough now anyway. |
Original bug ID: 4053
Reporter: @mmottl
Assigned to: @garrigue
Status: closed (set by @garrigue on 2011-12-12T01:14:00Z)
Resolution: suspended
Priority: normal
Severity: major
Version: 3.09.2
Fixed in version: 3.10.1
Category: ~DO NOT USE (was: OCaml general)
Related to: #4905
Monitored by: letaris @mmottl
Bug description
Hi,
the attached file (gen.ml) generates timings for increasing sizes of variant types (test takes a couple of seconds). The results, which can be viewed with "xgraph", demonstrate quadratic time complexity of compilation.
Looking at callgraphs produced by oprofile, it becomes obvious that a large amount of CPU-time is spent in comparison of values, and these comparisons are almost exclusively called from "List.assoc". This seems to indicate that the datastructures used in the compiler may not scale well on large type definitions. I'm pretty sure that this could be reduced to O(n * log(n)) behaviour with more appropriate datastructures for representing mappings than lists.
We are automatically generating very large type definitions with up to several thousand constructors. The resulting compilation time for these files is just way too long for practical use. We'd therefore be grateful if this problem could be fixed in the next release. Thanks a lot!
File attachments
The text was updated successfully, but these errors were encountered: