Iteration over lists

Bjorn Gustavsson bjorn@REDACTED
Fri Mar 17 14:10:13 CET 2006


Which release of Erlang/OTP did you benchmark?

Your numbers might be correct if you benchmarked an old release
of Erlang/OTP. If you benchmarked R10B, they don't make sense.
Did you start each new test in a newly spawned Erlang process?
How did you measure the time?

Emil Öberg (LN/EAB) <emil.oberg@REDACTED> writes:

>  That's a strange statement. There's nothing 'fair' when choosing implementation. 

It is unfair if they don't produce the same result.

>  Of course I implement recursive functions as tail recursion if possible, with reverse() if the order of the list is important.

The compiler has no way of knowing whether it is OK for a list comprehension
to return the list in reverse order.

>  The thing is that by using map or list comprehension you provide more information that the compiler could use to optimize the code (you know that you are iterating elements in a list). 

No. The compiler can know in both cases that the user INTENDED the input to be
a list, but that does not help. At run-time the function or list comprehension
can still be passed something that is not a list, so all the run-time tests
must still be there.

> I was also informed that map() is implemented in a beam, not in erts, so this explains why it is slower. But still there is list comprehension.

See my comments above, and my numbers.

> Since tail recursion is so much faster, why isn't list comprehension implemented as such, and why isn't map()?

Because the list would be in the wrong order, and as my benchmark showed,
for lists of 6000 elements running R10B on Solari8/Sparc workstation, a list
comprehension is slightly faster than a tail-recursion followed by a reverse.

> As it is now I will have to recommend designers not to use map() and absolutely not list comprehension on large lists.

If you use an old Erlang/OTP, that is a good recommendation. If you use R10B,
my benchmark showed that list comprehensions are faster than the lists:map/2.

Feel free to run my benchmark yourself if you don't trust my results.

/Bjorn

-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB



More information about the erlang-questions mailing list