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 |<br>N: 1000000<br>| Type | Insert[us] | Size[B] | Select[us] |<br>| set | 2.89800 | 9.14377 | 2.26243 |<br>| ordered_set | 2.17359 | 10.0001 | 2.04451 |<br>
| bag | 2.89416 | 9.14377 | 2.26667 |<br>| duplicate_bag | 2.89497 | 9.14377 | 2.28294 |<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?<br>
<br><div class="gmail_quote">On Mon, Jun 16, 2008 at 1:59 PM, Sverker Eriksson <<a href="mailto:sverker@erix.ericsson.se">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 class="Wj3C7c"><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">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">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>-- <br>--Hynek (Pichi) Vychodil