The size of things

Ketil Z. Malde
14 Feb 2002 08:54:35 +0100


I'm building some stuff here that is basically a glorified and
specialized version of quicksort.  It is very quick, and works like a
charm for my purposes, except that it consumes way too much space,
about 100 bytes times the size of the input list.  Which means that,
for my data sets, the program exceeds available RAM and uses swap,
which in turn kills performance.

Is there any guideline how much space the various constructs use?
E.g. how much for cons cells (or whatever that make up lists), how
much for a data type with only nullary data constructors -- should I
use Word8s instead? -- how much for tuples, and so on.  I realize I
can (and I do somewhat) use profiling to determine heap use, but it'd
be nice to be able to do back-of-envelope calculations and have some
idea of what's the right approach. 

So, any pointers or thoughts?

If I haven't seen further, it is by standing in the footprints of giants