The size of things

Ketil Z. Malde
15 Feb 2002 08:41:25 +0100

"Simon Marlow" <> writes:

> You can save storage by using strict constructor fields and using
> the -funbox-strict-fields flag.  eg. 

This would be switched on automatically with -O, no?

> 	data FloatList = FloatNil | FloatCons !Float FloatList

..while without strictness, the compiler wouldn't be able to unbox it,
and then we'd have three words per cons, *plus* two words per Float,

> requires 3 words for each float in the list, because its actual
> representation is 

> 	data FloatList = FloatNil | FloatCons Float# FloatList

I'm going to sketch my data structure, and try to reason a bit about
it.  Let's see

I have an (Array Int Foo), where Foo is a set of nullary constructors
(in other words, cheap?).  I have a list of Bar = Bar (Array Int Foo)
Int (where the array is the same for all elements), and construct a
list of tuples (Int, Bar). 

So the array shouldn't be too costly, I think - but perhaps an UArray
would reduce cost from three words to one word per element?

The list of Bars should require three words per cons cell, and three
words for each Bar, and then two words for the Ints (which could be
saved by an exclamation mark).

The list of tuples should again cost three words per cons, three per
tuple, plus two words per Int (with the Bars already existing and only
moved around). 

Summing up, the array is 3n, the first list is (3+3+2)n = 7n, and the
second list is (3+3+2)n = 7n, for a grand total of 17n, or multiplied
with four to get the bytes, 68n bytes.

This isn't too far from what I observe, so I hope my analysis is
somewhat correct. :-)


Now for improvement upon it:  I'll try to use an UArray, and see if
that reduces the array size somewhat.

For the list of Bar's, I can strictify the Ints to save 2 words.  But
if I defined 

        data BarList = Bar (Array Int Foo) !Int (BarList) |BarNil, 

I should be able to get away with 4 words per Bar, shouldn't I
(disregarding the actual array, which is shared anyway)?

And for the tuple-list, I could do

        data TupleList = Tuple !Int Bar TupleList | TupleNil

and get 4n, which is equally good.


This is assuming the compiler doesn't do any of this on its own...

> Does that help?

As usual, your postings are enlightening.  I haven't gotten around to
try things out yet, so I don't know how it turns out in practice.

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