[erlang-questions] cost of operations in ordered_set tables

[Hynek Vychodil]

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 |
N:    1000000
|            Type | Insert[us] |    Size[B] | Select[us] |
|             set |    2.89800 |    9.14377 |    2.26243 |
|     ordered_set |    2.17359 |    10.0001 |    2.04451 |
|             bag |    2.89416 |    9.14377 |    2.26667 |
|   duplicate_bag |    2.89497 |    9.14377 |    2.28294 |
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080616/e7642e5b/attachment.htm>