Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
compiling large file hogs RAM and takes a long time.
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-06-08 (13:39)
From: Sam Steingold <sds@g...>
Subject: Re: compiling large file hogs RAM and takes a long time.
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:
>> 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.


Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla -