<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