[erlang-questions] cost of operations in ordered_set tables

Hynek Vychodil <>
Mon Jun 16 16:55:22 CEST 2008


On Mon, Jun 16, 2008 at 4:42 PM, Hynek Vychodil <>
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 <
> > 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
>> > 
>> > http://www.erlang.org/mailman/listinfo/erlang-questions
>> >
>>
>> _______________________________________________
>> erlang-questions mailing list
>> 
>> 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.html>


More information about the erlang-questions mailing list