[erlang-questions] Performance of the append/reverse idiom
Sat Oct 20 14:01:47 CEST 2007
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
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.
> On 7/16/07, Christopher Baus <> wrote:
>> 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
>> is complete. I assume this a O(n) operation. Is it common for
>> to be a bottleneck in many applications?
>> erlang-questions mailing list
> erlang-questions mailing list
• Cameron Kerr • ✉ •
• 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
More information about the erlang-questions