The size of things

Simon Marlow simonmar@microsoft.com
Fri, 15 Feb 2002 09:44:27 -0000


> "Simon Marlow" <simonmar@microsoft.com> writes:
>=20
> > You can save storage by using strict constructor fields and using
> > the -funbox-strict-fields flag.  eg.=20
>=20
> This would be switched on automatically with -O, no?

Actually no... but perhaps it's time to turn it on.  The reason it's not =
on by default is that there are cases where it can make performance =
*worse* - storing the value unboxed occasionally requires us to =
reconstruct the boxed version eg. for passing to a polymorphic function =
or storing in an ordinary list.

> > 	data FloatList =3D FloatNil | FloatCons !Float FloatList
>=20
> ..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,
> right?=20

Yes, spot on.

> > requires 3 words for each float in the list, because its actual
> > representation is=20
>=20
> > 	data FloatList =3D FloatNil | FloatCons Float# FloatList
>=20
> I'm going to sketch my data structure, and try to reason a bit about
> it.  Let's see
>=20
> I have an (Array Int Foo), where Foo is a set of nullary constructors
> (in other words, cheap?).  I have a list of Bar =3D Bar (Array Int =
Foo)
> Int (where the array is the same for all elements), and construct a
> list of tuples (Int, Bar).=20
>=20
> 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?

It already costs one word per element (think of nullary constructors as =
free - we only have one copy of each nullary constructor which everybody =
points to).

If the array is the same for each element, why store it in the list at =
all? =20

> 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).

Yes.

> 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).=20
>=20
> Summing up, the array is 3n, the first list is (3+3+2)n =3D 7n, and =
the
> second list is (3+3+2)n =3D 7n, for a grand total of 17n, or =
multiplied
> with four to get the bytes, 68n bytes.
>=20
> This isn't too far from what I observe, so I hope my analysis is
> somewhat correct. :-)

Yes, sounds right.

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

I don't think it'll make a difference.

> For the list of Bar's, I can strictify the Ints to save 2 words.  But
> if I defined=20
>=20
>         data BarList =3D Bar (Array Int Foo) !Int (BarList) |BarNil,=20
>=20
> I should be able to get away with 4 words per Bar, shouldn't I
> (disregarding the actual array, which is shared anyway)?
>=20
> And for the tuple-list, I could do
>=20
>         data TupleList =3D Tuple !Int Bar TupleList | TupleNil
>=20
> and get 4n, which is equally good.
>=20
> ---
>=20
> This is assuming the compiler doesn't do any of this on its own...

The compiler won't do any of this on its own.  Remember that you can't =
pass a BarList to standard list functions like length, for example, =
because the types (and representations) are different.  The compiler =
won't make data constructor fieds strict - except in simple cases it =
would need a sophisticated whole-program analysis to ensure that adding =
the annotation wouldn't change the behaviour of the program, and AFAIK =
no-one has attempted this.

Cheers,
	Simon