Optimized lists

Zoltan Peter Toth zoltan.peter.toth@REDACTED
Fri Mar 11 15:51:58 CET 2005


> Or is the idea that the emulator be changed to _only_ allow
> tail-size-in-every-element lists? 

Yes, that's the idea. Quite a change, I admit.

> The benefit is that length() becomes
> O(1). The cost is O(n) space for all lists and O(n) extra execution
> time for most string operations.

True, but for list BIFs the extra time would probably mean memcpy-ing a struct 
that's one word longer.
I don't have any profiling information about execution time
of BIFs, but I guess this would not be the dominant part on todays CPUs.
It won't be noticable if list operations concern only one or a few elements
(like prepending an element to the list).
If it becomes substantially slower, then probably we have such a long list
where it would be risky to call length().

The same for the O(n) space increase: if it really matters, then calling length() 
would be a real time problem.

Further on, this would allow to count the BIF reductions in a length-dependent
way, which requires to get the length in O(1) steps (or faster :)).


More information about the erlang-questions mailing list