|Anonymous | Login | Signup for a new account||2016-12-11 11:07 CET|
|Main | My View | View Issues | Change Log | Roadmap|
|View Issue Details|
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0004053||OCaml||OCaml general||public||2006-06-22 21:36||2011-12-12 02:14|
|Target Version||Fixed in Version||3.10.1|
|Summary||0004053: Quadratic compilation time with large variant types|
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!
|Tags||No tags attached.|
|Attached Files||gen.ml [^] (497 bytes) 2006-06-22 21:36 [Show Content]|
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...
I improved this in CVS branch 3.09.
Note however that the behaviour still looks quadratic for huge matches.
100: 0.11s 0.12s
250: 0.33s 0.59s
600: 2.05s 5.27s
1500: 14.4s 63s
The cause is clear enough: when typing pattern matching, one unifies incrementally with the argument type. Unification of variants starts by sorting label lists, which is O(n*log n). So the result shall be O(n*n*log n)...
Even keeping the list sorted (which creates other problems with polymorphism) would not be sufficient, as the merge_row_fields is still O(n), causing a O(n*n). The solution would be to use binary trees, but it requires changes all over the compiler :-(
edited on: 2007-07-10 01:25
Considerably improved performance in 3.10.1dev.
* no memory explosion
* compilation is about 4 times faster
But this is still O(n*n) :-(
Optimized (#t as x) patterns in branch release310.
No need to rebuild the type when we know it...
This wins a more than 4x speedup for simple dispatch functions with hundreds of constructors.
|Cannot do much more for it, and it seems fast enough now anyway.|
|2006-06-22 21:36||mottl||New Issue|
|2006-06-22 21:36||mottl||File Added: gen.ml|
|2006-06-23 00:25||mottl||Note Added: 0003692|
|2006-06-23 05:01||garrigue||Status||new => resolved|
|2006-06-23 05:01||garrigue||Resolution||open => suspended|
|2006-06-23 05:01||garrigue||Assigned To||=> garrigue|
|2006-06-23 05:01||garrigue||Note Added: 0003695|
|2006-06-23 05:09||garrigue||Status||resolved => confirmed|
|2007-06-08 10:05||garrigue||Note Added: 0004090|
|2007-07-10 01:25||garrigue||Note Edited: 0004090|
|2007-07-10 09:47||garrigue||Note Added: 0004099|
|2010-04-30 09:29||garrigue||Relationship added||related to 0004905|
|2011-12-12 02:14||garrigue||Note Added: 0006228|
|2011-12-12 02:14||garrigue||Status||confirmed => closed|
|2011-12-12 02:14||garrigue||Fixed in Version||=> 3.10.1|
|Copyright © 2000 - 2011 MantisBT Group|