[erlang-bugs] Inserting new keys into maps is very slow (R17rc1)

[McDowell, Edward D.]

maps:put/3 in R17rc1 on Windows (64 bit) runs slowly when a
large number of randomly generated keys are inserted into a
map.  The following table shows that the time to insert n
keys grows quadratically, so the time to insert a single key
grows linearly.  Note that performance is greatly improved
by using a dict (from stdlib).

Number    Insert into map   Insert into dict
of keys   (milliseconds)    (milliseconds)
10000           969                16
20000          4031                62
40000         15937               172
80000         63734               453

The following code was used for these tests.  The dict
tests used the same code with dict:new/0 and dict:store/3
replacing maps:new/0 and maps:put/3, respectively.

-module(testmap).
-export([start/1]).

loop(Map, 0) -> Map;
loop(Map, Times) ->
    Key = random:uniform(999999),
    loop(maps:put(Key, true, Map), Times - 1).

start(NumKeys) ->
    {A, B, C} = now(),
    random:seed(A, B, C),
    Before = (1000000 * A + B) * 1000 + C div 1000,
    loop(maps:new(), NumKeys),
    {E, F, G} = now(),
    After = (1000000 * E + F) * 1000 + G div 1000,
    io:format("Elapsed time: ~w milliseconds.~n",
      [After - Before]).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-bugs/attachments/20140206/cd8819ec/attachment.htm>