<br><br><div class="gmail_quote">On Mon, Jun 16, 2008 at 4:42 PM, Hynek Vychodil <<a href="mailto:vychodil.hynek@gmail.com">vychodil.hynek@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I have tried primitive benchmark:<br><br>-module(ets_bench).<br><br>-export([start/2, insert/2]).<br><br>start(N, Type) -><br>    S = self(),<br>    Sub = spawn_link( fun() -><br>            ok = io:format("| ~15w ", [Type]),<br>

            Tab = ets:new(a, [Type, private]),<br>            insert(Tab, N),<br>            ets:delete_all_objects(Tab),<br>            {InsertTime, ok} = timer:tc(?MODULE, insert, [Tab, N]),<br>            ok = io:format("| ~10g ", [InsertTime/N]),<br>

            ok = io:format("| ~10g ", [ets:info(Tab, memory)/N]),<br>            Counter = fun(_,Acc) -> Acc+1 end,<br>            {CountTime, N} = timer:tc(ets, foldl, [Counter, 0, Tab]),<br>            ok = io:format("| ~10g |~n", [CountTime/N]),<br>

            S ! {self(), ok}<br>        end ),<br>    receive<br>        {Sub, ok} -> ok<br>        after (N div 10) + 1 -> exit(timeout)<br>    end.<br><br>insert(_Tab, 0) -> ok;<br>insert(Tab, N) -> ets:insert(Tab, {N}), insert(Tab, N-1).<br>

<br>And I can see little bit unexpected result:<br><br>> 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]).<br>

N:        100<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    1.56000 |    11.8800 |    2.37000 |<br>|     ordered_set |    1.70000 |    10.8100 |    2.30000 |<br>|             bag |    1.54000 |    11.8800 |    2.28000 |<br>

|   duplicate_bag |    1.55000 |    11.8800 |    2.29000 |<br>N:       1000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    1.53600 |    9.28800 |    2.12400 |<br>|     ordered_set |    1.88800 |    10.0810 |    2.08700 |<br>

|             bag |    1.53700 |    9.28800 |    2.12100 |<br>|   duplicate_bag |    1.53600 |    9.28800 |    2.11500 |<br>N:      10000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    1.75870 |    9.18230 |    2.12930 |<br>

|     ordered_set |    1.95290 |    10.0081 |    2.11430 |<br>|             bag |    1.79200 |    9.18230 |    2.15800 |<br>|   duplicate_bag |    1.81070 |    9.18230 |    2.17460 |<br>N:     100000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>

|             set |    2.01674 |    9.14623 |    2.26671 |<br>|     ordered_set |    1.97474 |    10.0008 |    2.03010 |<br>|             bag |    1.99262 |    9.14623 |    2.19376 |<br>|   duplicate_bag |    1.98019 |    9.14623 |    2.19390 |<br>

N:    1000000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    2.89089 |    9.14377 |    2.25434 |<br>|     ordered_set |    2.14992 |    10.0001 |    2.06282 |<br>|             bag |    2.88939 |    9.14377 |    2.26617 |<br>

|   duplicate_bag |    2.90703 |    9.14377 |    2.27656 |</blockquote><div><br>Sorry, I mashed result for 10 millions, result is:<br> N:   10000000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    3.36146 |    9.14344 |    2.35820 |<br>
|     ordered_set |    2.35257 |    10.0000 |    2.10989 |<br>|             bag |    3.36846 |    9.14344 |    2.40425 |<br>|   duplicate_bag |    3.36811 |    9.14344 |    2.40532 |<br><br>Another result with different CPU performance settings:<br>
<br>N:        100<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |   0.520000 |    11.8800 |   0.820000 |<br>|     ordered_set |   0.570000 |    10.8100 |   0.790000 |<br>|             bag |   0.510000 |    11.8800 |   0.770000 |<br>
|   duplicate_bag |   0.520000 |    11.8800 |   0.780000 |<br>N:       1000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |   0.514000 |    9.28800 |   0.698000 |<br>|     ordered_set |   0.578000 |    10.0810 |   0.692000 |<br>
|             bag |   0.513000 |    9.28800 |   0.734000 |<br>|   duplicate_bag |   0.515000 |    9.28800 |   0.705000 |<br>N:      10000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |   0.590200 |    9.18230 |   0.710100 |<br>
|     ordered_set |   0.645100 |    10.0081 |   0.758000 |<br>|             bag |   0.638600 |    9.18230 |   0.753200 |<br>|   duplicate_bag |   0.960300 |    9.18230 |   0.839500 |<br>N:     100000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>
|             set |   0.702480 |    9.14623 |   0.763710 |<br>|     ordered_set |   0.657220 |    10.0008 |   0.736930 |<br>|             bag |   0.696980 |    9.14623 |   0.764570 |<br>|   duplicate_bag |   0.733030 |    9.14623 |   0.762530 |<br>
N:    1000000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    1.30601 |    9.14377 |   0.805855 |<br>|     ordered_set |   0.745067 |    10.0001 |   0.699019 |<br>|             bag |    1.32297 |    9.14377 |   0.827663 |<br>
|   duplicate_bag |    1.30111 |    9.14377 |   0.818840 |<br>N:   10000000<br>|            Type | Insert[us] |    Size[B] | Select[us] |<br>|             set |    1.59831 |    9.14344 |   0.833202 |<br>|     ordered_set |   0.796910 |    10.0000 |   0.698836 |<br>
|             bag |    1.60898 |    9.14344 |   0.844491 |<br>|   duplicate_bag |    1.59895 |    9.14344 |   0.847049 |<br><br>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.<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>ok<br><br>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?<div>
<div></div><div class="Wj3C7c"><br>
<br><div class="gmail_quote">On Mon, Jun 16, 2008 at 1:59 PM, Sverker Eriksson <<a href="mailto:sverker@erix.ericsson.se" target="_blank">sverker@erix.ericsson.se</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Hi<br>
<br>
Ets ordered_set's are AVL-trees. The cost for insert() and delete() are<br>
thus O(log n).<br>
<br>
/Sverker, Erlang/OTP Ericsson<br>
<div><div></div><div><br>
<br>
Yariv Sadan wrote:<br>
> Hi,<br>
><br>
> What are the costs of insert() and delete() in ordered_set ets tables?<br>
> Are they O(log n)? Also, what kind of tree is used to store the keys?<br>
> Is it a balanced tree (e.g. red-black tree)?<br>
><br>
> Thanks,<br>
> Yariv<br>
> _______________________________________________<br>
> erlang-questions mailing list<br>
> <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
> <a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br>
><br>
<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br>
</div></div></blockquote></div><br><br clear="all"><br></div></div><font color="#888888">-- <br>--Hynek (Pichi) Vychodil
</font></blockquote></div><br><br clear="all"><br>-- <br>--Hynek (Pichi) Vychodil