Compiling large source files

[Simon Marlow]

On 04/08/2009 13:30, Serge D. Mechveliani wrote:
> On Tue, Aug 04, 2009 at 09:12:37AM +0100, Simon Marlow wrote:
>> I suggest not using Haskell for your list.  Put the data in a file and
>> read it at runtime, or put it in a static C array and link it in.
>>
>> On 03/08/2009 22:09, G?nther Schmidt wrote:
>>> Hi Thomas,
>>> yes, a source file with a single literal list with 85k elements.
>
>
> People,
> when a program only defines and returns a String constant of  n
> literals, how much memory needs ghc-6.10.4 to compile it ?
> O(n), or may be O(n^2), or ...

Certainly not O(n^2), we would class that as a bug.  I can imagine it 
might be worse than linear however, if not in memory at least in time.

Here's some very rough reasoning: GHC has to maintain various kinds of 
mappings to do its work.  A mapping from variables is O(logn) to look up 
in, and we have to do at least O(n) lookups since there are O(n) 
variables, so compilation will be O(nlogn).

We should remember that typechecking is worst-case exponential in space 
and time, though that is rarely an issue in practice.

String constants are a special case because they are stored internally 
as flat arrays of bytes, so you'll probably get closer to O(n) with a 
much better constant factor.

Cheers,
	Simon