On 27/07/2010 01:54, John Meacham wrote:

For each type I can statically generate an "optimal" layout based on its structure. For instance, maybe benefits from two of these optimizations, first of all, nullary constructors (Nothing) need never appear in the heap, so they are given values that pack directly into a word, this happens for all nullay constructors in general. Then, since there is only one constructor left (Just) we can discard the tag field, because if something of type Maybe, is in WHNF, and is not Nothing then in must be a Just. so the Just is a single heap allocated word (which are packed end to end in a page with no overhead)

I am refining the optimization algorithm, on 64 bit machines I have another few bits to play with for instance that I can take advantage of.

A particularly nice case is that characters can be fully integreated into the word, so the entire space usage of

"Hello" is 10 words as lists benefit from the same packing benefits as Maybe.

I should point out that in GHC "Hello" requires 15 words: 3 for each list cell, and the Chars are free because they're statically allocated in the RTS. A Just requires 2 words (one more than JHC, I guess). Tantalisingly, it's almost possible to represent a Just with zero words - the pointer to the Just points directly to the element - but there's nowhere to put the tag bits for the element pointer (the tag bits are for the Just). A Nothing in GHC takes zero words, as do all nullary constructors. I wrote up a summary of the GHC heap representation on Stack Overflow recently: http://stackoverflow.com/questions/3254758/memory-footprint-of-haskell-data-... Cheers, Simon

compare this to 30 or so words used in a traditional "everything is on the heap and tagged" model.

The manual has a section describing the RTS, it doesn't describe the GC though, but talks about how I pack things in the pointers.

http://repetae.net/computer/jhc/manual.html#the-run-time-system

John