[erlang-questions] Performance of the append/reverse idiom

[Richard Carlsson]

Cameron Kerr wrote:
> So what is the time complexity of reverse/1? I know that Erlang  
> intercepts calls to lists:reverse/1 to make performance a lot better.  
> Given the description, I get the impression that it might be O(1),  
> and so internally there might be some doubly-linked list sort of  
> thing going on.
> 
> What is the internal representation of a list such that it makes it  
> much cheaper?
> 
> PS. Please CC in any responses, I don't regularly follow this list.

There is no magic here. Reverse is an O(n) operation; it's just that
the built-in version (written in C) has a smaller constant factor than
a version implemented in Erlang.

Anyhow, doing a reverse at the end of an operation to get the elements
in the right order is not really a problem, if you consider that since
it is O(n), this just means a fairly small constant cost per element.
(The cost includes the additional memory allocation and higher pressure
on the garbage collector.) You have to consider that the alternative
is to rewrite the algorithm to produce the result in the right order
directly, and (assuming there are no destructive operations), no matter
what you do, this will also have its additional costs per element.

The right thing to do is to stop worrying and learn to love reverse!
It will let you write the main algorithm in a clearer way, which will
typically turn out to be more efficient, even if you have to include a
call to reverse at the end.

    /Richard