Zoltan Peter Toth
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