0004053: Quadratic compilation time with large variant types

(0003692)
mottl (reporter)
2006-06-23 00:25

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

(0003695)
garrigue (manager)
2006-06-23 05:01

I improved this in CVS branch 3.09.
Note however that the behaviour still looks quadratic for huge matches.
new old
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 :-(

(0004090)
garrigue (manager)
2007-06-08 10:05
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) :-(

(0004099)
garrigue (manager)
2007-07-10 09:47

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.

(0006228)
garrigue (manager)
2011-12-12 02:14

Cannot do much more for it, and it seems fast enough now anyway.

Issue History
Date Modified	Username	Field	Change
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

Notes
(0003692) mottl (reporter) 2006-06-23 00:25	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...

(0003695) garrigue (manager) 2006-06-23 05:01	I improved this in CVS branch 3.09. Note however that the behaviour still looks quadratic for huge matches. new old 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(nlog n). So the result shall be O(nnlog 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(nn). The solution would be to use binary trees, but it requires changes all over the compiler :-(

(0004090) garrigue (manager) 2007-06-08 10:05 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) :-(

(0004099) garrigue (manager) 2007-07-10 09:47	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.

(0006228) garrigue (manager) 2011-12-12 02:14	Cannot do much more for it, and it seems fast enough now anyway.