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

[Ulf Wiger]

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.

The module erl_eval.erl has some interesting message queue
gymnastics:

receive_clauses(Cs, Bs, Lf, Ef, Ms, RBs) ->
     receive
         Val ->
             case match_clause(Cs, [Val], Bs, Lf, Ef) of
                 {B, Bs1} ->
                     merge_queue(Ms),
                     exprs(B, Bs1, Lf, Ef, RBs);
                 nomatch ->
                     receive_clauses(Cs, Bs, Lf, Ef, [Val|Ms], RBs)
             end
     end.

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

recv_all(Xs) ->
     receive
         X -> recv_all([X|Xs])
     after 0 ->
             reverse(Xs)
     end.

send_all([X|Xs], Self) ->
     Self ! X,
     send_all(Xs, Self);
send_all([], _) -> true.


The case where the first message matches would be the
easy one, if it weren't for the fact that one also
needs to handle the case where the first message /doesn't/
match.

BR,
Ulf W
-- 
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com