Currently, I'm experiencing what I would call "strange behaviour":
I've got a data-type
data Fraction = Fraction Int Int
to hold rational numbers (maybe there's already some built-in type for this in Haskell,
http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Ratio.html
This list has up to 3 million elements. If I do
main = print $ length $ points
main = print $ length $ map (\(x, _) -> x == Fraction 1 2) points
main = print $ length $ reverse points
However, trying to do
import List main = print $ length $ sort points
makes memory usage go up and the program does not finish in 15m, also spending most time waiting for swapped out memory. What am I doing wrong, why is sort this expensive in this case? I would assume that computing and holding the whole list does not take too much memory, given its size and data type; doing the very same calculation in C should be straight forward. And sort should be O(n * log n) for time and also not much more expensive in memory, right?
Not having looked at your code, I think you are benefiting from fusion/deforestation in the first three main functions. In this case, although you may appear to be evaluating the entire list, in fact the list elements can be discarded as they are generated, so functions like length and reverse can run using constant space, rather than O(n) space. The sort function, however, requires that the entire list is retained, hence greater memory usage. I also think you are optimistic in the memory requirements of your 3 million element list. A list of Ints will take a lot more than 4 bytes per element (on 32-bit machines) because there's overhead for the list pointers, plus possibly the boxes for the Ints themselves. I think there are 3 machine words for each list entry (pointer to this element, pointer to next element, info-table pointer), and 2 words for each Int, but I'm just guessing: http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObje cts You might get some mileage by suggesting to GHC that your Fraction type is strict e.g.
data Fraction = Fraction !Int !Int
which might persuade it to unbox the Ints, giving some space savings. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************