[erlang-questions] Performance of the append/reverse idiom
Sat Oct 20 14:36:27 CEST 2007
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.
>> 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
More information about the erlang-questions