-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

skaller wrote:
> On Fri, 2007-06-08 at 10:02 +0900, Jacques Garrigue wrote:
>>> Any chance there is some quadratic code in polymorphic variant type
>>> processing?!
>> There is, and this is a known problem:
>>   http://caml.inria.fr/mantis/view.php?id=4053
>>
>> I'm sorry, but I don't see any easy way out.
>> At least on the basic time complexity.
> 
> You mention in the ticket there is a hard way out .. using
> binary trees; hard because it would require changes everywhere
> in the compiler. Is this actually enough? Seems to reduce
> 
> 	O(n * n * log n)
> 
> to 
> 
> 	O( n * log n * log n)
> 
> which is still pretty bad.. is that right?

for n=16,000 you have log n~14, i.e., a factor of 1,000.
even allowing for an unfavorable constant, the factor of 100 would be a
huge win.
I think going from n*n*log to n*log*log would be a worthy project.

Sam.


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGaVv+Pp1Qsf2qnMcRAkKzAJ4lWTSha/aF/3Uhr9+2E6C3nIGwpACgio0q
Z0Yb0Aru1bbV0vzwt/1eMXM=
=8UNH
-----END PGP SIGNATURE-----