[erlang-questions] cost of operations in ordered_set tables
Hynek Vychodil
vychodil.hynek@REDACTED
Mon Jun 16 16:55:22 CEST 2008
On Mon, Jun 16, 2008 at 4:42 PM, Hynek Vychodil <vychodil.hynek@REDACTED>
wrote:
> I have tried primitive benchmark:
>
> -module(ets_bench).
>
> -export([start/2, insert/2]).
>
> start(N, Type) ->
> S = self(),
> Sub = spawn_link( fun() ->
> ok = io:format("| ~15w ", [Type]),
> Tab = ets:new(a, [Type, private]),
> insert(Tab, N),
> ets:delete_all_objects(Tab),
> {InsertTime, ok} = timer:tc(?MODULE, insert, [Tab, N]),
> ok = io:format("| ~10g ", [InsertTime/N]),
> ok = io:format("| ~10g ", [ets:info(Tab, memory)/N]),
> Counter = fun(_,Acc) -> Acc+1 end,
> {CountTime, N} = timer:tc(ets, foldl, [Counter, 0, Tab]),
> ok = io:format("| ~10g |~n", [CountTime/N]),
> S ! {self(), ok}
> end ),
> receive
> {Sub, ok} -> ok
> after (N div 10) + 1 -> exit(timeout)
> end.
>
> insert(_Tab, 0) -> ok;
> insert(Tab, N) -> ets:insert(Tab, {N}), insert(Tab, N-1).
>
> And I can see little bit unexpected result:
>
> > lists:foreach(fun(N) -> io:format("N: ~10w~n| ~15s | ~10s | ~10s | ~10s
> |~n", [N, "Type", "Insert[us]", "Size[B]", "Select[us]"]),
> lists:foreach(fun(T) -> ets_bench:start(N, T) end, [set, ordered_set, bag,
> duplicate_bag]) end, [100, 1000, 10000, 100000, 1000000, 10000000]).
> N: 100
> | Type | Insert[us] | Size[B] | Select[us] |
> | set | 1.56000 | 11.8800 | 2.37000 |
> | ordered_set | 1.70000 | 10.8100 | 2.30000 |
> | bag | 1.54000 | 11.8800 | 2.28000 |
> | duplicate_bag | 1.55000 | 11.8800 | 2.29000 |
> N: 1000
> | Type | Insert[us] | Size[B] | Select[us] |
> | set | 1.53600 | 9.28800 | 2.12400 |
> | ordered_set | 1.88800 | 10.0810 | 2.08700 |
> | bag | 1.53700 | 9.28800 | 2.12100 |
> | duplicate_bag | 1.53600 | 9.28800 | 2.11500 |
> N: 10000
> | Type | Insert[us] | Size[B] | Select[us] |
> | set | 1.75870 | 9.18230 | 2.12930 |
> | ordered_set | 1.95290 | 10.0081 | 2.11430 |
> | bag | 1.79200 | 9.18230 | 2.15800 |
> | duplicate_bag | 1.81070 | 9.18230 | 2.17460 |
> N: 100000
> | Type | Insert[us] | Size[B] | Select[us] |
> | set | 2.01674 | 9.14623 | 2.26671 |
> | ordered_set | 1.97474 | 10.0008 | 2.03010 |
> | bag | 1.99262 | 9.14623 | 2.19376 |
> | duplicate_bag | 1.98019 | 9.14623 | 2.19390 |
> N: 1000000
> | Type | Insert[us] | Size[B] | Select[us] |
> | set | 2.89089 | 9.14377 | 2.25434 |
> | ordered_set | 2.14992 | 10.0001 | 2.06282 |
> | bag | 2.88939 | 9.14377 | 2.26617 |
> | duplicate_bag | 2.90703 | 9.14377 | 2.27656 |
Sorry, I mashed result for 10 millions, result is:
N: 10000000
| Type | Insert[us] | Size[B] | Select[us] |
| set | 3.36146 | 9.14344 | 2.35820 |
| ordered_set | 2.35257 | 10.0000 | 2.10989 |
| bag | 3.36846 | 9.14344 | 2.40425 |
| duplicate_bag | 3.36811 | 9.14344 | 2.40532 |
Another result with different CPU performance settings:
N: 100
| Type | Insert[us] | Size[B] | Select[us] |
| set | 0.520000 | 11.8800 | 0.820000 |
| ordered_set | 0.570000 | 10.8100 | 0.790000 |
| bag | 0.510000 | 11.8800 | 0.770000 |
| duplicate_bag | 0.520000 | 11.8800 | 0.780000 |
N: 1000
| Type | Insert[us] | Size[B] | Select[us] |
| set | 0.514000 | 9.28800 | 0.698000 |
| ordered_set | 0.578000 | 10.0810 | 0.692000 |
| bag | 0.513000 | 9.28800 | 0.734000 |
| duplicate_bag | 0.515000 | 9.28800 | 0.705000 |
N: 10000
| Type | Insert[us] | Size[B] | Select[us] |
| set | 0.590200 | 9.18230 | 0.710100 |
| ordered_set | 0.645100 | 10.0081 | 0.758000 |
| bag | 0.638600 | 9.18230 | 0.753200 |
| duplicate_bag | 0.960300 | 9.18230 | 0.839500 |
N: 100000
| Type | Insert[us] | Size[B] | Select[us] |
| set | 0.702480 | 9.14623 | 0.763710 |
| ordered_set | 0.657220 | 10.0008 | 0.736930 |
| bag | 0.696980 | 9.14623 | 0.764570 |
| duplicate_bag | 0.733030 | 9.14623 | 0.762530 |
N: 1000000
| Type | Insert[us] | Size[B] | Select[us] |
| set | 1.30601 | 9.14377 | 0.805855 |
| ordered_set | 0.745067 | 10.0001 | 0.699019 |
| bag | 1.32297 | 9.14377 | 0.827663 |
| duplicate_bag | 1.30111 | 9.14377 | 0.818840 |
N: 10000000
| Type | Insert[us] | Size[B] | Select[us] |
| set | 1.59831 | 9.14344 | 0.833202 |
| ordered_set | 0.796910 | 10.0000 | 0.698836 |
| bag | 1.60898 | 9.14344 | 0.844491 |
| duplicate_bag | 1.59895 | 9.14344 | 0.847049 |
Original purpose of those tests was compare ets to MySQL engine and ets is
less than 10 times slower than MySQL core engine. This is not as bad as I
expect.
> ok
>
> I have expected that ordered_set goes worse and worse in compare to other
> types. Is it caused by ordered insert and using foldl instead lookup?
>
>
> On Mon, Jun 16, 2008 at 1:59 PM, Sverker Eriksson <
> sverker@REDACTED> wrote:
>
>> Hi
>>
>> Ets ordered_set's are AVL-trees. The cost for insert() and delete() are
>> thus O(log n).
>>
>> /Sverker, Erlang/OTP Ericsson
>>
>>
>> Yariv Sadan wrote:
>> > Hi,
>> >
>> > What are the costs of insert() and delete() in ordered_set ets tables?
>> > Are they O(log n)? Also, what kind of tree is used to store the keys?
>> > Is it a balanced tree (e.g. red-black tree)?
>> >
>> > Thanks,
>> > Yariv
>> > _______________________________________________
>> > erlang-questions mailing list
>> > erlang-questions@REDACTED
>> > http://www.erlang.org/mailman/listinfo/erlang-questions
>> >
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>>
>
>
>
> --
> --Hynek (Pichi) Vychodil
--
--Hynek (Pichi) Vychodil
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080616/1e06bc11/attachment.htm>
More information about the erlang-questions
mailing list