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

[Cameron Kerr]

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:

> 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

-- 
• Cameron Kerr  • ✉ ckerr@REDACTED •
 •
• Telecommunications Teaching Fellow & SysAdmin •
• ✎ http://humbledown.org/blog/ • ✆ New: 027 7175 244 •

"Technological advances are not made by sadomasochistic, cultic, tool- 
worshipping pain freaks." – http://freeshells.ch/~revence/myths.txt