[erlang-questions] Fastest pseudo-random number-generator: erlang:statistics(io) ?
Thijs
that using erlang:now() is quite slow: it requires a system call. I
decided to test some alternatives. My requirements are: speed, speed,
speed :) I will use it in a server that is quite busy, so I figured I
could use various system metrics to generate random numbers. I use
these pseudo-random numbers to do load-balancing, log requests at
random etc.
benchmark results :
erlang:now() 288.090
erlang:statistics(io) 2.730.853
erlang:statistics(wall_clock) 280.396
erlang:statistics(runtime) 510.765
erlang:statistics(reductions) 471.688
erlang:statistics(context_switches) 493.851
random:uniform() 870.261
This test is spawning 100 concurrent processes, each executing 10000
calls to each function. Two notes:
1. Note that you can only use this function if your server is actually
performing (lots) of IO
2. random:uniform() needs to be seeded for real use (each process
starts the same), I didn't do that.
Based on these tests, erlang:statistics(io) is the clear winner. I
will use it now for picking random elements from lists and replacing
pg2:get_closest_pid(Name).
Does anyone have any faster suggestions than erlang:statistics(io) ?
________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org
Dave Smith
> benchmark results :
>
> erlang:now() 288.090
> erlang:statistics(io) 2.730.853
> erlang:statistics(wall_clock) 280.396
> erlang:statistics(runtime) 510.765
> erlang:statistics(reductions) 471.688
> erlang:statistics(context_switches) 493.851
> random:uniform() 870.261
Off the top of my head, I have to wonder if using statistics(io) is
going to yield sufficient pseudo-randomness for load distribution
purposes. If you consider that most IO is likely to be a block size
modulo 8 (for efficiency) it seems like you might get a skewed
distribution. A simpler (and perhaps faster) approach would be to just
maintain a counter that gets atomically incremented on each call -- a
port driver or ETS table would suffice and have similar amounts of
contention as the call to statistics.
My $0.02...and you know how weak the dollar has been these days. :)
D.
Thijs
> Off the top of my head, I have to wonder if using statistics(io) is
> going to yield sufficient pseudo-randomness for load distribution
> purposes. If you consider that most IO is likely to be a block size
> modulo 8 (for efficiency) it seems like you might get a skewed
> distribution. A simpler (and perhaps faster) approach would be to just
> maintain a counter that gets atomically incremented on each call -- a
> port driver or ETS table would suffice and have similar amounts of
> contention as the call to statistics.
Maintaining a counter in ETS would be (much) slower, so that is
unfortunately no option for me. I have tried some simple randomness
tests for this io-function in the running server and the distribution
looks sufficiently random. I have many processes sending and receiving
data (via ports), so that shouldn't be a problem. Someone else told me
that erlang:now() blocks the scheduler shortly, so that is something I
definitely want to avoid.
Gleb Peregud
> that erlang:now() blocks the scheduler shortly, so that is something I
> definitely want to avoid.
Yes, since erlang:now() is guaranteed to return ascending numbers on
each call regardless of number of cores VM is running one. It has to
do some synchronization to meet this requirement.
Zoltan Lajos Kis
How about process_info(self(), reductions). ?
Regards,
Zoltan.
Jayson Vantuyl
This has the added bonus that phash2/2 (not hash or phash, but phash2) has a range argument, so you wouldn't have to scale the number down to list size. It also wouldn't be a problem on a system doing very little I/O, as long as it has done some IO. Of course, you could always toss a counter from the process dictionary (and maybe the PID) into a tuple with it, and poof "unique hash". I haven't benchmarked it, but I'd imagine it shouldn't be too much slower, right?
For that matter, what about erlang:process_info(self(),reductions)? Maybe it would be faster since it's only process-local data?
--
Jayson Vantuyl
kag...@souja.net
Thijs
> Is it too slow to run the result through erlang:phash/2?
I tested it, erlang:phash2(erlang:statistics(io), 10) it still is
fast, but significantly slower than without. You are right that it
immediately scales the result, so i tested with scaling the
erlang:statistics(io) as well. I think the randomness (for my case)
will not improve a lot, but I will keep this function in mind.
On Nov 25, 12:10 am, "Zoltan Lajos Kis" <ki...@tmit.bme.hu> wrote:
> How about process_info(self(), reductions). ?
This one is also very fast (only a bit slower than statistics(io)),
but I am concerned about the randomness of this function (at least in
my case). I have many short-lived processes and it's likely that the
number of reductions for each process might be quite similar if they
follow similar code paths?
new benchmark results:
erlang_now req/sec 296667.7
stats_io req/sec 2638898.4
stats_wall_clock req/sec 289306.0
stats_runtime req/sec 522258.4
stats_reductions req/sec 484499.9
stats_cont_switch req/sec 491190.3
random_uniform req/sec 1109517.1
process_info_reduc req/sec 2410724.8
phash2_io req/sec 1773493.0
stats_io_scaled req/sec 2357073.0
tested like this:
---------------------------
test_random_speed(ParCount, SeqCount) ->
FunErlangNow = fun() -> erlang:now() end,
FunIO = fun() -> erlang:statistics(io) end,
FunWallClock = fun() -> erlang:statistics(wall_clock) end,
FunRuntime = fun() -> erlang:statistics(runtime) end,
FunReductions = fun() -> erlang:statistics(reductions) end,
FunContextSwitches = fun() -> erlang:statistics(context_switches)
end,
FunRandomUniform = fun() -> random:uniform() end,
FunProcessInfoRed = fun() -> erlang:process_info(self(), reductions)
end,
FunPhashIO = fun() -> erlang:phash2(erlang:statistics(io), 10) end,
FunIOScaled = fun() ->
{{input, Input}, {output, Output}} = erlang:statistics(io),
(Input+Output) rem 10
end,
test_fun_x_times_parallel(erlang_now, FunErlangNow, ParCount,
SeqCount),
test_fun_x_times_parallel(stats_io, FunIO, ParCount, SeqCount),
test_fun_x_times_parallel(stats_wall_clock, FunWallClock, ParCount,
SeqCount),
test_fun_x_times_parallel(stats_runtime, FunRuntime, ParCount,
SeqCount),
test_fun_x_times_parallel(stats_reductions, FunReductions, ParCount,
SeqCount),
test_fun_x_times_parallel(stats_cont_switch, FunContextSwitches,
ParCount, SeqCount),
test_fun_x_times_parallel(random_uniform, FunRandomUniform, ParCount,
SeqCount),
test_fun_x_times_parallel(process_info_reduc, FunProcessInfoRed,
ParCount, SeqCount),
test_fun_x_times_parallel(phash2_io, FunPhashIO, ParCount, SeqCount),
test_fun_x_times_parallel(stats_io_scaled, FunIOScaled, ParCount,
SeqCount),
ok.
test_fun_x_times_parallel(Name, Fun, ParCount, SeqCount) ->
Tick = now(),
app_util:pmap(
fun(_) ->
lists:foreach(fun(_) ->
Fun()
end,
lists:seq(1, SeqCount))
end,
lists:seq(1, ParCount),
[],
250000),
Tock = now(),
AvgTime = timer:now_diff(Tock, Tick)/1000,
Speed = ParCount*SeqCount*1000/AvgTime,
io:format("~20w req/sec ~10.1f ~n", [Name, Speed]),
Speed.
pmap(Fun, List, Nodes, Timeout) ->
SpawnFun =
case length(Nodes) of
0 ->
fun spawn/1;
Length ->
NextNode = fun() -> lists:nth(random:uniform(Length), Nodes) end,
fun(F) -> spawn(NextNode(), F) end
end,
Parent = self(),
Pids =
[
SpawnFun(fun() -> Parent ! {self(), (catch Fun(Elem))} end)
|| Elem <- List
],
[
receive
{Pid, Val} -> Val
after Timeout ->
exit(timeout)
end
|| Pid <- Pids
].
Thijs
to generate random numbers and timestamps, much faster than the Erlang
alternatives!
The speed is about 1/2 to 1/3 of statistics(io), but still much faster
than erlang:now().
I simply used time(0) for the nif_now() and gettimeofday(&tv, NULL)
for the nif_random() functions.
nif's are a great addition to the language!
Kenji Rikitake
Or probably in NIF?
SIMD-oriented Fast Mersenne Twister (SFMT)
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
(C code available)
Kenji Rikitake
In the message <af660f57-3816-44fd...@y32g2000prd.googlegroups.com>
dated Tue, Nov 24, 2009 at 06:59:45AM -0800,
Thijs <thijst...@gmail.com> writes:
> Today I needed a faster alternative for erlang:now(). It turns out
> that using erlang:now() is quite slow: it requires a system call. I
> decided to test some alternatives. My requirements are: speed, speed,
> speed :) I will use it in a server that is quite busy, so I figured I
> could use various system metrics to generate random numbers. I use
> these pseudo-random numbers to do load-balancing, log requests at
> random etc.
(rest snapped)