Optimized lists

Richard Carlsson <>
Mon Mar 14 07:41:18 CET 2005


Richard A. O'Keefe wrote:
> (1) The Warren Abstract Machine stores list pairs in 2 words.  I don't
>     know what BEAM uses.  Probably 3 words.  The change would thus
>     add 33% to the size of every list.

The BEAM uses 2 words per cons cell, so it would be a 50% addition,
which of course would make it even more horrific.

Folks, the whole reason that lists are as efficient as they are,
is that the implementation is dead simple. Adding words to the
representation, or having different kinds of lists under the hood
(forcing a runtime test for each access to a cons cell to see what
kind it really is) generally kills performance.

	/Richard



More information about the erlang-questions mailing list