receive _ -> ok end is exponential in queue length?!!

Matthew Sackman matthew@REDACTED
Fri Jul 10 15:54:45 CEST 2009


[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.

If I put it into a module, add 1e5 and 1e6 then I get:

1> test:test().
1.0
0.1
0.06
0.114
0.1554
0.36398
0.358997

Which looks rather more sensible. So why is it so much slower doing it
direct in the shell? It's not just a case of it looking like compiler
optimisations (which you'd expect to produce a linear factor speedup),
it's more that it looks like the shell is doing the wrong algorithm
(like removing from the end of the queue instead of the head?!).

Matthew


More information about the erlang-questions mailing list