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

[Per Gustafsson]

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.
>
> On 16/07/2007, at 7:53 PM, Joe Armstrong wrote:
>
>   
lists:reverse is O(N), but it is implemented in C rather than in Erlang 
which makes it faster. The internal representation of lists is just 
linked cons cells where each cons cell takes up two words of heap space.

Per



>> Is reverse a bottleneck?
>>
>> Very rarely.
>>
>> The are some *extremely* rare cases where people write code to handle
>> both reversed
>> and non-reverse lists (I think the library routines for sort remember
>> if the current
>> list being sorted is in normal or reversed order) but this is only  
>> useful when
>> you're interested in making a tiny gain in efficiency (it also make  
>> the code
>> a  mess to read).
>>
>> The most common bottleneck are in the I/O system. Parsing inputs (in
>> any language)
>> is always a slow - other bottleneck are usually in the process
>> structure - using a centralized server that serializes everything can
>> make nasty bottlenecks.
>>
>> /Joe
>>
>>
>> On 7/16/07, Christopher Baus <christopher@REDACTED> wrote:
>>     
>>> Hi,
>>>
>>> I'm still going through Joe's book, but as a C/C++ hack, I can't help
>>> but have some reservations about performance.  One common idiom is to
>>> append to the front of a list and then reverse the list when the  
>>> append
>>> is complete.  I assume this a O(n) operation.  Is it common for  
>>> reverse
>>> to be a bottleneck in many applications?
>>>
>>> Thanks,
>>>
>>> Chris
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://www.erlang.org/mailman/listinfo/erlang-questions
>>>
>>>       
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>>     
>
>