[erlang-questions] receive _ -> ok end is exponential in queue length?!!

[Richard Carlsson]

Matthew Sackman wrote:
> [begin [ self() ! a || _ <- lists:seq(1,N) ],
>        S = now(),
>        [ receive _ -> ok end || _ <- lists:seq(1,N) ],
>        io:format("~w~n", [timer:now_diff(now(), S) / N])
>  end || N <- [1,10,100,1000,10000]].
> 13.0
> 3.0
> 11.91
> 221.703
> 3421.773
> 
> I'm willing to believe I'm being staggaringly dumb here, but why on
> earth isn't this constant? We're just removing from the head of the
> message queue. The above is direct in the erlang shell.

It seems that since the interpreter (erl_eval) must simulate the
pattern matching over the mailbox, it must extract messages
unconditionally from the head of the mailbox, one at a time,
try to match them, and put them aside for later if they don't
match. When a matching message is found, or a timeout occurs,
it must restore the mailbox as it is supposed to look, by putting
the extracted messages back _before_ any messages still left in
the real queue. The only way it can do that is by extracting all
of the remaining messages as well, and then send the whole lot
back to itself (hoping that no further messages arrive while it
is doing this).

This tends to work in a shell process with little traffic and
a generally small mailbox, but obviously doesn't scale.

The quick fix would be to change the following in erl_eval:

 merge_queue(Ms) ->
    send_all(recv_all(Ms), self()).

to

 merge_queue([]) -> true;
 merge_queue(Ms) -> ...

which at least avoids unnecessary work when no messages have
been extracted which need to be put back.

    /Richard