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-types/3256825#3256825
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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
