[erlang-questions] Erlang shows its slow face!

[Richard O'Keefe]

On 17/11/2010, at 4:23 AM, Anders Nygren wrote:

> On Tue, Nov 16, 2010 at 8:20 AM, Kostis Sagonas <kostis@REDACTED> wrote:
>> Richard O'Keefe wrote:
>>> 
>>> ... SNIP
>>> 
>>> The time for p0 was 420 milliseconds in Erlang.
>>> On the same machine, the same function, the time was
>>> 91 milliseconds in SML/NJ.
>>>            SML/NJ  MLton   Erlang
>>> n=100 L= 34 s=0.004 m=0.004 e=0.020
>>> n=200 L= 86 s=0.028 m=0.027 e=0.130
>>> n=300 L=146 s=0.090 m=0.086 e=0.410
>>> n=400 L=210 s=0.213 m=0.202 e=0.980
>>> n=500 L=274 s=0.415 m=0.394 e=1.900
>>> 
>>> We see that Erlang is about 5 times slower than SML.
>> 
>> Is Erlang running native code here?
>> (Because both SML/NJ and MLton are.)
>> 
>>> Here's the SML code.
>>> 
>>> ...  What's more, SML is
>>> strongly typed, and the Dialyzer should be able to handle this,
>>> so the compiler *knows* it is dealing with integers.
>> 
>> Let's leave dialyzer out of this discussion -- it is a type analyzer
>> alright, but the types it infers are not necessarily usable for optimization
>> purposes (I can possibly elaborate in some other mail).
>> 
>> Can you post p0 to see whether the compiler can infer whether the program
>> deals with integers or not?
>> 
>> 
>>> There are two basic issues here:
>>> (1) The Erlang compiler doesn't really handle list comprehension as
>>>    native loops; it compiles list comprehensions to recursive
>>>    functions.  lists:seq(1, N) is not special syntax -- unlike Haskell --
>>>    and almost surely builds an actual list.
>> 
>> Yes.  This is an issue.  Actually, it's more general: in my experience most
>> Erlang programmers do not understand the difference between list
>> comprehensions and lists:foreach/2. Many of them find list comprehension
>> notation so nice that they often use it in places where building the list is
>> not only is not their intention but is completely unnecessary.
>> The compiler is not sufficiently clever to perform deforestation and avoid
>> construction of intermediate lists.
> 
> 
> Maybe You are talking about some special case here that I missed but the
> "Efficiency Guide" ch 5.2, in the documentation says
> "In R12B, if the result of the list comprehension will obviously not
> be used, a list will not be constructed."

We are talking about completely different lists.

What I'm talking about is that

	R = [f(X) || X <- lists:seq(1, N)]

will construct lists:seq(1, N), even though it doesn't need to.

You are talking about the fact that

	_ = [g(Y) || Y <- L]

won't construct a list of g results.  But that is not at all relevant
to the problem at hand, where the list of triples obviously *WILL* be
used, so the comprehension *MUST* construct it.  That's fine, that's
what we want.

Compare this with Haskell, where for
	[(a,b,c) | a <- [1..n], b <- [1..n], c <- [1..n],
		   a+b+c <= n, a^2 + b^2 == c^2]
some compilers *won't* construct the lists [1..n].