[erlang-questions] Erlang shows its slow face!

[Kostis Sagonas]

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.

>     This could be changed, and maybe some day it will change.
> 
> (2) Erlang is compiled incrementally to support hot loading and
>     (again in order to support hot loading) does not do much if any
>     cross-module inlining.
>     MLton is a whole-program optimising compiler, it can SML _are_
>     allowed to do cross-module inlining by the nature of the language.
> 
>     This *can't* be changed without making Erlang less useful for its job.    
> 
> Ah, but there's one more wrinkle!

Yes, there is that too in Erlang ;-)

>             SML/NJ  Erlang  SML/NJ     Smalltalk
> n=100 L= 34 s=0.004 e=0.020 s= 0.250   p1=0.016
> n=200 L= 86 s=0.028 e=0.130 s= 1.904   p1=0.109
> n=300 L=146 s=0.090 e=0.410 s= 6.567   p1=0.369
> n=400 L=210 s=0.213 e=0.980 s=15.581   p1=0.873
> n=500 L=274 s=0.415 e=1.900 s=30.218   p1=1.705 
> 
> (3) Erlang integer arithmetic is *not* limited to some ridiculous
>     size like 32 bits, it is _semantically_ unbounded integer
>     arithmetic, with a space-efficient representation and fast
>     calculation path for small integers.  To get something
>     comparable in SML, you have to use the type IntInf.int
>     instead of Int.int.  And when you do *that*, Erlang really
>     really shines.
> 
>     The difference here is that if you use int in C or Java or C#
>     or SML, then you'll find a positive integer n such that n+1 < 0.
>     That kind of nonsense simply doesn't happen in Erlang.
> 
>     It comes with a price, but the price of *not* using a Lispy
>     (or Smalltalky, or Erlangy) approach to integers is the price
>     of getting wrong answers without knowing.
> 
>     The Smalltalk column was done using my Smalltalk-via-C compiler.
>     It might be possible to go a factor of 2 faster using machine-
>     specific assembly code, but what we seem to be looking at in
>     the Erlang column really does seem to be no more than the
>     price of arithmetic that gives correct results.

Thanks for a nice post!

Kostis