Optimized lists

[Zoltan Peter Toth]

Matthias Lang wrote:
> Zoltan Peter Toth writes:
>
>  > Idea:
>  > Store in each list element the length of the remaining part of the
> list.
> [...]
>
>  > How feasible this would be to implement ?
>
> Pretty straightforward:
...
> I'm not sure many people will use it, given that it imposes even more
> space overhead than lists already have.
> 
> Implementing it inside the runtime would be possible too, with likely
> space and performance gains. I'm sure a bunch of people would
> implement it right away, if only the Erlang source code wasn't kept a
> closely guarded secret.

Hi Matthias,

The Erlang solution is really pretty straightforward, and may be an option
for new code that uses only the new list structure.
But it would not solve the problem when we get a long conventional list that
we don't want to handle and want to check its size with length().
Further on, transforming to/from conventional list would also be O(n).
Therefore I propose a change to the implementation of the Erlang list construct 
in the emulator.

(Afaik, currently the head structures are linked into a list and each of them has 
a pointer to the next head and the actual list element.
What I propose is to include a length field into the head structure. So it would
not consume too much extra memory I believe.)

Cheers,
	Zoltan