I spent a while pondering this, and the fact that I can manage lists of length
1000 with the default heap size of 100000 before I realised...
You're entirely correct, this does point to something ugly - the read function
Sometimes it seems like the Haskell committee added the Read class just to
guarantee that the ML/Lisp/C/Java zealots could easily confirm their impression
that Haskell really is a toy language unsuited for use in real applications.
Of read's many problems, the one you've hit upon is this:
read is not lazy
This isn't because of some minor coding error, it's because readsPrec
returns an empty list to indicate parse errors instead of just aborting.
It can't abort because of the backtracking and because Haskell doesn't
have any kind of exception handling.
Since read isn't lazy, it has to complete the parse (and confirm that there
are no others) before it can return any results.
But why does it take 500 cells per list element?
I haven't looked at this in detail but here's a few possibilities:
1) read lexes each token twice - once to find the end of the token
and a second time to figure out what the token is.
2) If you have a backtracking parser, you have to remember what to
backtrack to.
3) There's backtracking in the lexer too. A backtracking lexer!!!
What in the name of the wee man did they think they were doing?
4) Once we have the digit sequence, we use readDec to convert it to an Int.
I doubt this contributes to the enormous space usage but it would
definitely benefit from a bit of good old fashioned optimisation
(inlining, specialisation, strictness analysis, unboxing, etc).
Alastair
> Hugs 1.4, The Nottingham and Yale Haskell User's System. Version 970719.
>
> The input parser can't cope with long literate lists. With 337000 free
> heap cells, the parser cannot read a list of 795 1's of type Int or
> Integer, *sometimes* of type Double. Long lists of Bool or () are Ok.
>
> Doesn't seem like much, but it might point to something ugly.
>
> TripReport> :gc
> {{Gc:336528}}Garbage collection recovered 336528 cells
> TripReport> read (show (take 795 (repeat 1))) :: [Int]
> {{Gc:288538}}{{Gc:284944}}{{Gc:310438}}[1, 1, 1, 1, ...]
> (581471 reductions, 1014967 cells, 3 garbage collections)
> {{Gc:337317}}TripReport> :gc
> {{Gc:337319}}Garbage collection recovered 337319 cells
> TripReport> [1, 1, 1, 1, ... (795 of 'em)]
> {{Gc:19}}ERROR: Garbage collection fails to reclaim sufficient space
> TripReport>
>
> What's even stranger (to a layman, that is ;-) is that sometimes it
> only works the 3rd time!
>
> {{Gc:337038}}TripReport> :gc
> {{Gc:337038}}Garbage collection recovered 337038 cells
> TripReport> [1, 1, 1, 1, ...1] :: [Double]
> {{Gc:910}}ERROR: Garbage collection fails to reclaim sufficient space
> TripReport> [1, 1, 1, 1, ...] :: [Double]
> {{Gc:822}}ERROR: Garbage collection fails to reclaim sufficient space
> TripReport> [1, 1, 1, 1, ...] :: [Double]
> {{Gc:333316}}[1.0, 1.0, 1.0,...]
> (2755 reductions, 6325 cells)
> {{Gc:337038}}TripReport>
>
> --
> Fabrice Lavier <[EMAIL PROTECTED]>
>
