From 89133a5589c32529bb33d53de0ae0f0c687ace9c Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 22 Oct 2018 22:35:02 +0200 Subject: stdlib: Remove doc note about multi key performance limit --- lib/stdlib/doc/src/ets.xml | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/doc/src/ets.xml b/lib/stdlib/doc/src/ets.xml index 57a19ef2ca..0179090878 100644 --- a/lib/stdlib/doc/src/ets.xml +++ b/lib/stdlib/doc/src/ets.xml @@ -1140,16 +1140,11 @@ ets:select(Table, MatchSpec), set, bag and duplicate_bag. For ordered_set the memory overhead depends on the number of inserted objects and the amount of actual detected - concurrency. The memory overhead can be especially large when both - options are combined.

+ concurrency in runtime. The memory overhead can be especially + large when both options are combined.

Prior to stdlib-3.7 (OTP-22.0) write_concurrency had no effect on ordered_set.

-

The current implementation of write_concurrency for - ordered_set does only improve explicit single key - operations. Mixing single key operations with operations - potentially accessing multiple keys may even yield worse - performance with write_concurrency on ordered_set.

 -- cgit v1.2.3 From 375a1f5c29fd2d3b537e117149e78b0ac61e263f Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 16 Oct 2018 20:04:33 +0200 Subject: erts: Implement ets:info(T, stats) for catrees {RouteNodes, BaseNodes, MaxRouteTreeDepth} --- lib/stdlib/doc/src/ets.xml | 5 ++--- lib/stdlib/test/ets_SUITE.erl | 6 +++--- 2 files changed, 5 insertions(+), 6 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/doc/src/ets.xml b/lib/stdlib/doc/src/ets.xml index 0179090878..611b176613 100644 --- a/lib/stdlib/doc/src/ets.xml +++ b/lib/stdlib/doc/src/ets.xml @@ -611,9 +611,8 @@ Error: fun containing local Erlang function calls

Item=stats, Value=tuple()

-

Returns internal statistics about set, bag, and - duplicate_bag tables on an internal format used by OTP - test suites. Not for production use.

 +

Returns internal statistics about tables on an internal format + used by OTP test suites. Not for production use.

diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index 2c0692855f..da4933064c 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -796,10 +796,10 @@ t_delete_all_objects(Config) when is_list(Config) -> get_kept_objects(T) -> case ets:info(T,stats) of - false -> - 0; {_,_,_,_,_,_,KO} -> - KO + KO; + _ -> + 0 end. t_delete_all_objects_do(Opts) -> -- cgit v1.2.3 From 32fc84630bdb499ca0eabb6b1de8a03b1d9aa321 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 16 Oct 2018 20:19:31 +0200 Subject: stdlib: Optimize ets_SUITE:stimulate_contention with ets_force_split --- lib/stdlib/test/ets_SUITE.erl | 78 +++++++++++++++++++------------------------ 1 file changed, 34 insertions(+), 44 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index da4933064c..5352524ee2 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -7373,53 +7373,43 @@ ets_new(Name, Opts) -> EtsNewHelper(Opts) end. -% This function do the following to the input ETS table: -% 1. Perform a number of concurrent insert operations -% 2. Remove all inserted items -% % The purpose of this function is to stimulate fine grained locking in % tables of types ordered_set with the write_concurrency options -% turned on. Such tables are implemented as CA trees* and thus -% activates fine grained locking only when lock contention is -% detected. -% -% A Contention Adapting Approach to Concurrent Ordered Sets -% Journal of Parallel and Distributed Computing, 2018 -% Kjell Winblad and Konstantinos Sagonas -% https://doi.org/10.1016/j.jpdc.2017.11.007 -stimulate_contention(T) -> - NrOfSchedulers = erlang:system_info(schedulers), - ParentPid = self(), - KeyRange = 100000, - ChildPids = - lists:map(fun(_N) -> - spawn(fun() -> - receive start -> ok end, - stimulate_contention_do_inserts(T, KeyRange, 0), - ParentPid ! done - end) - end, lists:seq(1, NrOfSchedulers)), - lists:foreach(fun(Pid) -> Pid ! start end, ChildPids), - timer:sleep(100), - lists:foreach(fun(Pid) -> Pid ! stop end, ChildPids), - lists:foreach(fun(_P) -> receive done -> ok end end, ChildPids), - lists:foreach(fun(N) -> ets:delete(T, N) end, lists:seq(0, KeyRange)). - - - -stimulate_contention_do_inserts(T, KeyRange, 0) -> - OpsBetweenStopCheck = 10000, - receive - stop -> ok - after - 0 -> stimulate_contention_do_inserts(T, KeyRange, OpsBetweenStopCheck) - end; -stimulate_contention_do_inserts(T, KeyRange, OpsToNextStopCheck) -> - R = trunc(KeyRange * rand:uniform()), - ets:insert(T,{R,R,R}), - stimulate_contention_do_inserts(T, KeyRange, OpsToNextStopCheck - 1). - +% turned on. The erts_debug feature 'ets_force_split' is used to easier +% generate a routing tree with fine grained locking without having to +% provoke lots of actual lock contentions. +stimulate_contention(Tid) -> + T = case Tid of + A when is_atom(A) -> ets:whereis(A); + _ -> Tid + end, + erts_debug:set_internal_state(ets_force_split, {T, true}), + KeyRange = 1000*1000, + Num = 50, + Seed = rand:uniform(KeyRange), + %%io:format("prefill_table: Seed = ~p\n", [Seed]), + RState = unique_rand_start(KeyRange, Seed), + stim_inserter_loop(T, RState, Num), + Num = ets:info(T, size), + erts_debug:set_internal_state(ets_force_split, {T, false}), + Stats1 = ets:info(T,stats), + ets:match_delete(T, {'$1','$1','$1'}), + case ets:info(T,stats) of + Stats1 -> + io:format("stimulated ordered_set: ~p\n", [Stats1]); + Stats2 -> + io:format("Houston, we got a testability problem.\n" + "Someone seems to have implemented join-on-delete\n" + "~p =/= ~p\n", [Stats1, Stats2]), + ct:fail("Join on delete?") + end. +stim_inserter_loop(_, _, 0) -> + ok; +stim_inserter_loop(T, RS0, N) -> + {Key, RS1} = unique_rand_next(RS0), + ets:insert(T, {Key, Key, Key}), + stim_inserter_loop(T, RS1, N-1). do_tc(Do, Report) -> T1 = erlang:monotonic_time(), -- cgit v1.2.3 From 77d3d262c5e7d784204a6d91b79ed2f46b4013ad Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 18 Oct 2018 11:29:06 +0200 Subject: erts: Do contention adaptions during (updating) iterations Once an iteration key has been found, never fall back to first/last key in next/prev tree as trees may split or join under our feet. I.e we must always use previous key when searching for the next key. --- lib/stdlib/test/ets_SUITE.erl | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index 5352524ee2..de7c647610 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -6017,7 +6017,9 @@ smp_select_replace_do(Opts) -> 1 -> Cnt0+1; 0 -> ets:insert_new(T, {CounterId, 0}), - Cnt0 + Cnt0; + _ -> + erlang:display("Nooooo!") end, receive stop -> [end_of_work | Cnt1] -- cgit v1.2.3 From 822b60430eeae0ae32aca52019762566fec1acce Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 19 Oct 2018 20:08:22 +0200 Subject: erts: Provoke random catree split/join for DEBUG emulator --- lib/stdlib/test/ets_SUITE.erl | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index de7c647610..367c7533b4 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -7394,16 +7394,14 @@ stimulate_contention(Tid) -> stim_inserter_loop(T, RState, Num), Num = ets:info(T, size), erts_debug:set_internal_state(ets_force_split, {T, false}), - Stats1 = ets:info(T,stats), ets:match_delete(T, {'$1','$1','$1'}), case ets:info(T,stats) of - Stats1 -> - io:format("stimulated ordered_set: ~p\n", [Stats1]); - Stats2 -> + {0, _, _} -> io:format("Houston, we got a testability problem.\n" - "Someone seems to have implemented join-on-delete\n" - "~p =/= ~p\n", [Stats1, Stats2]), - ct:fail("Join on delete?") + "Someone seems to have implemented join-on-delete\n", []), + ct:fail("Join on delete?"); + Stats -> + io:format("stimulated ordered_set: ~p\n", [Stats]) end. stim_inserter_loop(_, _, 0) -> -- cgit v1.2.3 From c6af9cd30c151baaa0afb929ce6a0292607db86c Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 23 Oct 2018 16:56:03 +0200 Subject: stdlib: Add runtime dependency to erts --- lib/stdlib/src/stdlib.app.src | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/src/stdlib.app.src b/lib/stdlib/src/stdlib.app.src index cd09872b87..9cd425db9a 100644 --- a/lib/stdlib/src/stdlib.app.src +++ b/lib/stdlib/src/stdlib.app.src @@ -108,7 +108,7 @@ dets]}, {applications, [kernel]}, {env, []}, - {runtime_dependencies, ["sasl-3.0","kernel-6.0","erts-10.0","crypto-3.3", + {runtime_dependencies, ["sasl-3.0","kernel-6.0","erts-@OTP-15128@","crypto-3.3", "compiler-5.0"]} ]}. -- cgit v1.2.3 From 13214aae3697d27d27d5c628997fd4a92b497f89 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 25 Oct 2018 13:35:12 +0200 Subject: erts: Join empty base nodes in catree The original implementation did not do this due to fear of bad performance. But we think the negative effect of "leaking" empty base nodes is more important to fix. To get the bad performance a special kind of access patterns is needed where base nodes are frequently emptied and then repopulated soon again. ets_SUITE:throughput_benchmark for example did not show any negative effect from this commit at all. --- lib/stdlib/test/ets_SUITE.erl | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index 367c7533b4..74a4f47fa9 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -7393,13 +7393,14 @@ stimulate_contention(Tid) -> RState = unique_rand_start(KeyRange, Seed), stim_inserter_loop(T, RState, Num), Num = ets:info(T, size), - erts_debug:set_internal_state(ets_force_split, {T, false}), ets:match_delete(T, {'$1','$1','$1'}), + 0 = ets:info(T, size), + erts_debug:set_internal_state(ets_force_split, {T, false}), case ets:info(T,stats) of {0, _, _} -> - io:format("Houston, we got a testability problem.\n" - "Someone seems to have implemented join-on-delete\n", []), - ct:fail("Join on delete?"); + io:format("No routing nodes in table?\n" + "Debug feature 'ets_force_split' does not seem to work.\n", []), + ct:fail("No ets_force_split?"); Stats -> io:format("stimulated ordered_set: ~p\n", [Stats]) end. -- cgit v1.2.3 From b97be434476fc65620b2969a4f549a343e300dda Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 26 Oct 2018 19:31:48 +0200 Subject: stdlib: Improve stim_cat_ord_set in ets_SUITE to generate a routing tree with keys that fit each test case. --- lib/stdlib/test/ets_SUITE.erl | 311 +++++++++++++++++++++++------------------- 1 file changed, 170 insertions(+), 141 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index 74a4f47fa9..daea9bccf5 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -803,8 +803,9 @@ get_kept_objects(T) -> end. t_delete_all_objects_do(Opts) -> - T=ets_new(x,Opts), - filltabint(T,4000), + KeyRange = 4000, + T=ets_new(x, Opts, KeyRange), + filltabint(T,KeyRange), O=ets:first(T), ets:next(T,O), ets:safe_fixtable(T,true), @@ -813,13 +814,13 @@ t_delete_all_objects_do(Opts) -> 0 = ets:info(T,size), case ets:info(T,type) of ordered_set -> ok; - _ -> 4000 = get_kept_objects(T) + _ -> KeyRange = get_kept_objects(T) end, ets:safe_fixtable(T,false), 0 = ets:info(T,size), 0 = get_kept_objects(T), - filltabint(T,4000), - 4000 = ets:info(T,size), + filltabint(T, KeyRange), + KeyRange = ets:info(T,size), true = ets:delete_all_objects(T), 0 = ets:info(T,size), ets:delete(T), @@ -3104,18 +3105,18 @@ setbag(Config) when is_list(Config) -> %% Test case to check proper return values for illegal ets_new() calls. badnew(Config) when is_list(Config) -> EtsMem = etsmem(), - {'EXIT',{badarg,_}} = (catch ets_new(12,[])), - {'EXIT',{badarg,_}} = (catch ets_new({a,b},[])), - {'EXIT',{badarg,_}} = (catch ets_new(name,[foo])), - {'EXIT',{badarg,_}} = (catch ets_new(name,{bag})), - {'EXIT',{badarg,_}} = (catch ets_new(name,bag)), + {'EXIT',{badarg,_}} = (catch ets:new(12,[])), + {'EXIT',{badarg,_}} = (catch ets:new({a,b},[])), + {'EXIT',{badarg,_}} = (catch ets:new(name,[foo])), + {'EXIT',{badarg,_}} = (catch ets:new(name,{bag})), + {'EXIT',{badarg,_}} = (catch ets:new(name,bag)), verify_etsmem(EtsMem). %% OTP-2314. Test case to check that a non-proper list does not %% crash the emulator. verybadnew(Config) when is_list(Config) -> EtsMem = etsmem(), - {'EXIT',{badarg,_}} = (catch ets_new(verybad,[set|protected])), + {'EXIT',{badarg,_}} = (catch ets:new(verybad,[set|protected])), verify_etsmem(EtsMem). %% Small check to see if named tables work. @@ -3464,9 +3465,11 @@ delete_tab_do(Opts) -> %% Check that ets:delete/1 works and that other processes can run. delete_large_tab(Config) when is_list(Config) -> ct:timetrap({minutes,60}), %% valgrind needs a lot - Data = [{erlang:phash2(I, 16#ffffff),I} || I <- lists:seq(1, 200000)], + KeyRange = 16#ffffff, + Data = [{erlang:phash2(I, KeyRange),I} || I <- lists:seq(1, 200000)], EtsMem = etsmem(), - repeat_for_opts(fun(Opts) -> delete_large_tab_do(Opts,Data) end), + repeat_for_opts(fun(Opts) -> delete_large_tab_do(key_range(Opts,KeyRange), + Data) end), verify_etsmem(EtsMem). delete_large_tab_do(Opts,Data) -> @@ -3542,9 +3545,13 @@ delete_large_tab_2(Name, Flags, Data, Fix) -> %% Delete a large name table and try to create a new table with %% the same name in another process. delete_large_named_table(Config) when is_list(Config) -> - Data = [{erlang:phash2(I, 16#ffffff),I} || I <- lists:seq(1, 200000)], + KeyRange = 16#ffffff, + Data = [{erlang:phash2(I, KeyRange),I} || I <- lists:seq(1, 200000)], EtsMem = etsmem(), - repeat_for_opts(fun(Opts) -> delete_large_named_table_do(Opts,Data) end), + repeat_for_opts(fun(Opts) -> + delete_large_named_table_do(key_range(Opts,KeyRange), + Data) + end), verify_etsmem(EtsMem), ok. @@ -3585,8 +3592,12 @@ delete_large_named_table_2(Name, Flags, Data, Fix) -> %% Delete a large table, and kill the process during the delete. evil_delete(Config) when is_list(Config) -> - Data = [{I,I*I} || I <- lists:seq(1, 100000)], - repeat_for_opts(fun(Opts) -> evil_delete_do(Opts,Data) end). + KeyRange = 100000, + Data = [{I,I*I} || I <- lists:seq(1, KeyRange)], + repeat_for_opts(fun(Opts) -> + evil_delete_do(key_range(Opts,KeyRange), + Data) + end). evil_delete_do(Opts,Data) -> EtsMem = etsmem(), @@ -4154,19 +4165,12 @@ match_object2(Config) when is_list(Config) -> match_object2_do(Opts) -> EtsMem = etsmem(), - Tab = ets_new(foo, [bag, {keypos, 2} | Opts]), - fill_tab2(Tab, 0, 13005), % match_db_object does 1000 + KeyRange = 13005, + Tab = ets_new(foo, [{keypos, 2} | Opts], KeyRange), + fill_tab2(Tab, 0, KeyRange), % match_db_object does 1000 % elements per pass, might % change in the future. - case catch ets:match_object(Tab, {hej, '$1'}) of - {'EXIT', _} -> - ets:delete(Tab), - ct:fail("match_object EXIT:ed"); - [] -> - io:format("Nothing matched."); - List -> - io:format("Matched:~p~n",[List]) - end, + [] = ets:match_object(Tab, {hej, '$1'}), ets:delete(Tab), verify_etsmem(EtsMem). @@ -4411,10 +4415,11 @@ tab2file2(Config) when is_list(Config) -> tab2file2_do(Opts, Config) -> EtsMem = etsmem(), - Tab = ets_new(ets_SUITE_foo_tab, [named_table, private, - {keypos, 2} | Opts]), + KeyRange = 10000, + Tab = ets_new(ets_SUITE_foo_tab, [named_table, private, {keypos, 2} | Opts], + KeyRange), FName = filename:join([proplists:get_value(priv_dir, Config),"tab2file2_case"]), - ok = fill_tab2(Tab, 0, 10000), % Fill up the table (grucho mucho!) + ok = fill_tab2(Tab, 0, KeyRange), % Fill up the table (grucho mucho!) Len = length(ets:tab2list(Tab)), Mem = ets:info(Tab, memory), Type = ets:info(Tab, type), @@ -4473,8 +4478,9 @@ tabfile_ext1(Config) when is_list(Config) -> tabfile_ext1_do(Opts,Config) -> FName = filename:join([proplists:get_value(priv_dir, Config),"nisse.dat"]), FName2 = filename:join([proplists:get_value(priv_dir, Config),"countflip.dat"]), - L = lists:seq(1,10), - T = ets_new(x,Opts), + KeyRange = 10, + L = lists:seq(1,KeyRange), + T = ets_new(x,Opts,KeyRange), Name = make_ref(), [ets:insert(T,{X,integer_to_list(X)}) || X <- L], ok = ets:tab2file(T,FName,[{extended_info,[object_count]}]), @@ -4511,8 +4517,9 @@ tabfile_ext2(Config) when is_list(Config) -> tabfile_ext2_do(Opts,Config) -> FName = filename:join([proplists:get_value(priv_dir, Config),"olle.dat"]), FName2 = filename:join([proplists:get_value(priv_dir, Config),"bitflip.dat"]), - L = lists:seq(1,10), - T = ets_new(x,Opts), + KeyRange = 10, + L = lists:seq(1, KeyRange), + T = ets_new(x, Opts, KeyRange), Name = make_ref(), [ets:insert(T,{X,integer_to_list(X)}) || X <- L], ok = ets:tab2file(T,FName,[{extended_info,[md5sum]}]), @@ -4681,9 +4688,10 @@ heavy_lookup(Config) when is_list(Config) -> heavy_lookup_do(Opts) -> EtsMem = etsmem(), - Tab = ets_new(foobar_table, [{keypos, 2} | Opts]), - ok = fill_tab2(Tab, 0, 7000), - _ = [do_lookup(Tab, 6999) || _ <- lists:seq(1, 50)], + KeyRange = 7000, + Tab = ets_new(foobar_table, [{keypos, 2} | Opts], KeyRange), + ok = fill_tab2(Tab, 0, KeyRange), + _ = [do_lookup(Tab, KeyRange-1) || _ <- lists:seq(1, 50)], true = ets:delete(Tab), verify_etsmem(EtsMem). @@ -4704,11 +4712,12 @@ heavy_lookup_element(Config) when is_list(Config) -> heavy_lookup_element_do(Opts) -> EtsMem = etsmem(), - Tab = ets_new(foobar_table, [{keypos, 2} | Opts]), - ok = fill_tab2(Tab, 0, 7000), + KeyRange = 7000, + Tab = ets_new(foobar_table, [{keypos, 2} | Opts], KeyRange), + ok = fill_tab2(Tab, 0, KeyRange), %% lookup ALL elements 50 times Laps = 50 div syrup_factor(), - _ = [do_lookup_element(Tab, 6999, 1) || _ <- lists:seq(1, Laps)], + _ = [do_lookup_element(Tab, KeyRange-1, 1) || _ <- lists:seq(1, Laps)], true = ets:delete(Tab), verify_etsmem(EtsMem). @@ -4731,11 +4740,11 @@ heavy_concurrent(Config) when is_list(Config) -> repeat_for_opts_all_set_table_types(fun do_heavy_concurrent/1). do_heavy_concurrent(Opts) -> - Size = 10000, + KeyRange = 10000, Laps = 10000 div syrup_factor(), EtsMem = etsmem(), - Tab = ets_new(blupp, [public, {keypos, 2} | Opts]), - ok = fill_tab2(Tab, 0, Size), + Tab = ets_new(blupp, [public, {keypos, 2} | Opts], KeyRange), + ok = fill_tab2(Tab, 0, KeyRange), Procs = lists:map( fun (N) -> my_spawn_link( @@ -5014,6 +5023,7 @@ filltabint(Tab,0) -> filltabint(Tab,N) -> ets:insert(Tab,{N,integer_to_list(N)}), filltabint(Tab,N-1). + filltabint2(Tab,0) -> Tab; filltabint2(Tab,N) -> @@ -5230,8 +5240,9 @@ gen_dets_filename(Config,N) -> otp_6842_select_1000(Config) when is_list(Config) -> repeat_for_opts_all_ord_set_table_types( fun(Opts) -> - Tab = ets_new(xxx,Opts), - [ets:insert(Tab,{X,X}) || X <- lists:seq(1,10000)], + KeyRange = 10000, + Tab = ets_new(xxx, Opts, KeyRange), + [ets:insert(Tab,{X,X}) || X <- lists:seq(1,KeyRange)], AllTrue = lists:duplicate(10,true), AllTrue = [ length( @@ -5420,7 +5431,7 @@ grow_shrink(Config) when is_list(Config) -> fun(Opts) -> EtsMem = etsmem(), - Set = ets_new(a, Opts), + Set = ets_new(a, Opts, 5000), grow_shrink_0(0, 3071, 3000, 5000, Set), ets:delete(Set), @@ -5449,14 +5460,13 @@ grow_shrink_3(N, ShrinkTo, T) -> true = ets:delete(T, N), grow_shrink_3(N-1, ShrinkTo, T). -%% Grow a table that still contains pseudo-deleted objects. +%% Grow a hash table that still contains pseudo-deleted objects. grow_pseudo_deleted(Config) when is_list(Config) -> only_if_smp(fun() -> grow_pseudo_deleted_do() end). grow_pseudo_deleted_do() -> lists:foreach(fun(Type) -> grow_pseudo_deleted_do(Type) end, - [set,cat_ord_set,stim_cat_ord_set, - ordered_set,bag,duplicate_bag]). + [set,bag,duplicate_bag]). grow_pseudo_deleted_do(Type) -> process_flag(scheduler,1), @@ -5471,12 +5481,7 @@ grow_pseudo_deleted_do(Type) -> [true]}]), Left = Mult*(Mod-1), Left = ets:info(T,size), - case Type of - cat_ord_set -> ok; - stim_cat_ord_set -> ok; - ordered_set -> ok; - _ -> Mult = get_kept_objects(T) - end, + Mult = get_kept_objects(T), filltabstr(T,Mult), my_spawn_opt( fun() -> @@ -5508,14 +5513,13 @@ grow_pseudo_deleted_do(Type) -> ets:delete(T), process_flag(scheduler,0). -%% Shrink a table that still contains pseudo-deleted objects. +%% Shrink a hash table that still contains pseudo-deleted objects. shrink_pseudo_deleted(Config) when is_list(Config) -> only_if_smp(fun()->shrink_pseudo_deleted_do() end). shrink_pseudo_deleted_do() -> lists:foreach(fun(Type) -> shrink_pseudo_deleted_do(Type) end, - [set,cat_ord_set,stim_cat_ord_set, - ordered_set,bag,duplicate_bag]). + [set,bag,duplicate_bag]). shrink_pseudo_deleted_do(Type) -> process_flag(scheduler,1), @@ -5529,12 +5533,7 @@ shrink_pseudo_deleted_do(Type) -> [{'>', '$1', Half}], [true]}]), Half = ets:info(T,size), - case Type of - cat_ord_set -> ok; - stim_cat_ord_set -> ok; - ordered_set -> ok; - _ -> Half = get_kept_objects(T) - end, + Half = get_kept_objects(T), my_spawn_opt( fun()-> true = ets:info(T,fixed), Self ! start, @@ -5638,9 +5637,11 @@ smp_insert(Config) when is_list(Config) -> [[set,ordered_set,stim_cat_ord_set]]). smp_insert_do(Opts) -> - ets_new(smp_insert,[named_table,public,{write_concurrency,true}|Opts]), + KeyRange = 10000, + ets_new(smp_insert,[named_table,public,{write_concurrency,true}|Opts], + KeyRange), InitF = fun(_) -> ok end, - ExecF = fun(_) -> true = ets:insert(smp_insert,{rand:uniform(10000)}) + ExecF = fun(_) -> true = ets:insert(smp_insert,{rand:uniform(KeyRange)}) end, FiniF = fun(_) -> ok end, run_smp_workers(InitF,ExecF,FiniF,100000), @@ -5649,41 +5650,36 @@ smp_insert_do(Opts) -> %% Concurrent deletes on same fixated table. smp_fixed_delete(Config) when is_list(Config) -> - only_if_smp(fun()-> - repeat_for_opts(fun smp_fixed_delete_do/1, - [[set,ordered_set,stim_cat_ord_set]]) - end). - -smp_fixed_delete_do(Opts) -> - begin - T = ets_new(foo,[public,{write_concurrency,true}|Opts]), - %%Mem = ets:info(T,memory), - NumOfObjs = 100000, - filltabint(T,NumOfObjs), - ets:safe_fixtable(T,true), - Buckets = num_of_buckets(T), - InitF = fun([ProcN,NumOfProcs|_]) -> {ProcN,NumOfProcs} end, - ExecF = fun({Key,_}) when Key > NumOfObjs -> - [end_of_work]; - ({Key,Increment}) -> - true = ets:delete(T,Key), - {Key+Increment,Increment} - end, - FiniF = fun(_) -> ok end, - run_sched_workers(InitF,ExecF,FiniF,NumOfObjs), - 0 = ets:info(T,size), - true = ets:info(T,fixed), - Buckets = num_of_buckets(T), - case ets:info(T,type) of - set -> NumOfObjs = get_kept_objects(T); - _ -> ok - end, - ets:safe_fixtable(T,false), - %% Will fail as unfix does not shrink the table: - %%Mem = ets:info(T,memory), - %%verify_table_load(T), - ets:delete(T) - end. + only_if_smp(fun() -> smp_fixed_delete_do() end). + +smp_fixed_delete_do() -> + T = ets_new(foo,[public,{write_concurrency,true}]), + %%Mem = ets:info(T,memory), + NumOfObjs = 100000, + filltabint(T,NumOfObjs), + ets:safe_fixtable(T,true), + Buckets = num_of_buckets(T), + InitF = fun([ProcN,NumOfProcs|_]) -> {ProcN,NumOfProcs} end, + ExecF = fun({Key,_}) when Key > NumOfObjs -> + [end_of_work]; + ({Key,Increment}) -> + true = ets:delete(T,Key), + {Key+Increment,Increment} + end, + FiniF = fun(_) -> ok end, + run_sched_workers(InitF,ExecF,FiniF,NumOfObjs), + 0 = ets:info(T,size), + true = ets:info(T,fixed), + Buckets = num_of_buckets(T), + case ets:info(T,type) of + set -> NumOfObjs = get_kept_objects(T); + _ -> ok + end, + ets:safe_fixtable(T,false), + %% Will fail as unfix does not shrink the table: + %%Mem = ets:info(T,memory), + %%verify_table_load(T), + ets:delete(T). %% ERL-720 %% Provoke race between ets:delete and table unfix (by select_count) @@ -5928,8 +5924,10 @@ verify_table_load(T) -> otp_8732(Config) when is_list(Config) -> repeat_for_all_ord_set_table_types( fun(Opts) -> - Tab = ets_new(noname,Opts), - filltabstr(Tab,999), + KeyRange = 999, + KeyFun = fun(K) -> integer_to_list(K) end, + Tab = ets_new(noname,Opts, KeyRange, KeyFun), + filltabstr(Tab, KeyRange), ets:insert(Tab,{[],"nasty NIL object"}), [] = ets:match(Tab,{'_',nomatch}) %% Will hang if bug not fixed end), @@ -5939,11 +5937,14 @@ otp_8732(Config) when is_list(Config) -> %% Run concurrent select_delete (and inserts) on same table. smp_select_delete(Config) when is_list(Config) -> repeat_for_opts(fun smp_select_delete_do/1, - [[set,ordered_set,stim_cat_ord_set], read_concurrency, compressed]). + [[set,ordered_set,stim_cat_ord_set], + read_concurrency, compressed]). smp_select_delete_do(Opts) -> + KeyRange = 10000, begin % indentation - T = ets_new(smp_select_delete,[named_table,public,{write_concurrency,true}|Opts]), + T = ets_new(smp_select_delete,[named_table,public,{write_concurrency,true}|Opts], + KeyRange), Mod = 17, Zeros = erlang:make_tuple(Mod,0), InitF = fun(_) -> Zeros end, @@ -5960,7 +5961,7 @@ smp_select_delete_do(Opts) -> element(Eq+1,Diffs0) - Deleted), Diffs1; _ -> - Key = rand:uniform(10000), + Key = rand:uniform(KeyRange), Eq = Key rem Mod, case ets:insert_new(T,{Key,Key}) of true -> @@ -6004,12 +6005,13 @@ smp_select_replace(Config) when is_list(Config) -> [[set,ordered_set,stim_cat_ord_set,duplicate_bag]]). smp_select_replace_do(Opts) -> + KeyRange = 20, T = ets_new(smp_select_replace, - [public, {write_concurrency, true} | Opts]), - ObjCount = 20, + [public, {write_concurrency, true} | Opts], + KeyRange), InitF = fun (_) -> 0 end, ExecF = fun (Cnt0) -> - CounterId = rand:uniform(ObjCount), + CounterId = rand:uniform(KeyRange), Match = [{{'$1', '$2'}, [{'=:=', '$1', CounterId}], [{{'$1', {'+', '$2', 1}}}]}], @@ -6017,9 +6019,7 @@ smp_select_replace_do(Opts) -> 1 -> Cnt0+1; 0 -> ets:insert_new(T, {CounterId, 0}), - Cnt0; - _ -> - erlang:display("Nooooo!") + Cnt0 end, receive stop -> [end_of_work | Cnt1] @@ -6035,7 +6035,7 @@ smp_select_replace_do(Opts) -> FinalCounts = ets:select(T, [{{'_', '$1'}, [], ['$1']}]), Total = lists:sum(FinalCounts), Total = lists:sum(Results), - ObjCount = ets:select_delete(T, [{{'_', '_'}, [], [true]}]), + KeyRange = ets:select_delete(T, [{{'_', '_'}, [], [true]}]), 0 = ets:info(T, size), true = ets:delete(T), ok. @@ -7326,20 +7326,46 @@ is_redundant_opts_combo(Opts) -> lists:member(private, Opts) orelse lists:member(protected, Opts)). -ets_new(Name, Opts) -> - ReplaceStimOrdSetHelper = - fun (MOpts) -> - lists:map(fun (I) -> - case I of - stim_cat_ord_set -> ordered_set; - cat_ord_set -> ordered_set; - _ -> I - end - end, MOpts) - end, +%% Add fake table option with info about key range. +%% Will be consumed by ets_new and used for stim_cat_ord_set. +key_range(Opts, KeyRange) -> + [{key_range, KeyRange} | Opts]. + +key_range_fun(Opts, KeyRange, KeyFun) -> + [{key_range, KeyRange}, {key_fun, KeyFun} | Opts]. + +ets_new(Name, Opts0) -> + {KeyRange, Opts1} = case lists:keytake(key_range, 1, Opts0) of + {value, {key_range, KR}, Rest1} -> + {KR, Rest1}; + false -> + {1000*1000, Opts0} + end, + ets_new(Name, Opts1, KeyRange). + +ets_new(Name, Opts1, KeyRange) -> + {KeyFun, Opts2} = case lists:keytake(key_fun, 1, Opts1) of + {value, {key_fun, KF}, Rest2} -> + {KF, Rest2}; + false -> + {fun id/1, Opts1} + end, + ets_new(Name, Opts2, KeyRange, KeyFun). + +ets_new(Name, Opts0, KeyRange, KeyFun) -> + {CATree, Stimulate, RevOpts} = + lists:foldl(fun(cat_ord_set, {false, false, Lacc}) -> + {true, false, [ordered_set | Lacc]}; + (stim_cat_ord_set, {false, false, Lacc}) -> + {true, true, [ordered_set | Lacc]}; + (Other, {CAT, STIM, Lacc}) -> + {CAT, STIM, [Other | Lacc]} + end, + {false, false, []}, + Opts0), + Opts = lists:reverse(RevOpts), EtsNewHelper = - fun (MOpts) -> - UseOpts = ReplaceStimOrdSetHelper(MOpts), + fun (UseOpts) -> case get(ets_new_opts) of UseOpts -> silence; %% suppress identical table opts spam @@ -7349,8 +7375,7 @@ ets_new(Name, Opts) -> end, ets:new(Name, UseOpts) end, - case (lists:member(stim_cat_ord_set, Opts) or - lists:member(cat_ord_set, Opts)) andalso + case CATree andalso (not lists:member({write_concurrency, false}, Opts)) andalso (not lists:member(private, Opts)) andalso (not lists:member(protected, Opts)) of @@ -7366,9 +7391,9 @@ ets_new(Name, Opts) -> false -> [public|NewOpts1] end, T = EtsNewHelper(NewOpts2), - case lists:member(stim_cat_ord_set, Opts) of - true -> stimulate_contention(T); - false -> ok + case Stimulate of + false -> ok; + true -> stimulate_contention(T, KeyRange, KeyFun) end, T; false -> @@ -7380,18 +7405,20 @@ ets_new(Name, Opts) -> % turned on. The erts_debug feature 'ets_force_split' is used to easier % generate a routing tree with fine grained locking without having to % provoke lots of actual lock contentions. -stimulate_contention(Tid) -> +stimulate_contention(Tid, KeyRange, KeyFun) -> T = case Tid of A when is_atom(A) -> ets:whereis(A); _ -> Tid end, erts_debug:set_internal_state(ets_force_split, {T, true}), - KeyRange = 1000*1000, - Num = 50, + Num = case KeyRange > 50 of + true -> 50; + false -> KeyRange + end, Seed = rand:uniform(KeyRange), %%io:format("prefill_table: Seed = ~p\n", [Seed]), RState = unique_rand_start(KeyRange, Seed), - stim_inserter_loop(T, RState, Num), + stim_inserter_loop(T, RState, Num, KeyFun), Num = ets:info(T, size), ets:match_delete(T, {'$1','$1','$1'}), 0 = ets:info(T, size), @@ -7405,12 +7432,13 @@ stimulate_contention(Tid) -> io:format("stimulated ordered_set: ~p\n", [Stats]) end. -stim_inserter_loop(_, _, 0) -> +stim_inserter_loop(_, _, 0, _) -> ok; -stim_inserter_loop(T, RS0, N) -> - {Key, RS1} = unique_rand_next(RS0), +stim_inserter_loop(T, RS0, N, KeyFun) -> + {K, RS1} = unique_rand_next(RS0), + Key = KeyFun(K), ets:insert(T, {Key, Key, Key}), - stim_inserter_loop(T, RS1, N-1). + stim_inserter_loop(T, RS1, N-1, KeyFun). do_tc(Do, Report) -> T1 = erlang:monotonic_time(), @@ -7469,4 +7497,5 @@ dquad(Prime, X, Seed) -> %% Primes where P rem 4 == 3. primes_3mod4() -> [103, 211, 503, 1019, 2003, 5003, 10007, 20011, 50023, - 100003, 200003, 500083, 1000003, 2000003]. + 100003, 200003, 500083, 1000003, 2000003, 5000011, + 10000019, 20000003, 50000047, 100000007]. -- cgit v1.2.3 From cc18836780d7d047bf53b1ff8d94a6b31b58f98a Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 26 Oct 2018 19:34:12 +0200 Subject: stdlib: Add ets_SUITE:smp_ordered_iteration to provoke iteration over a moving ordered_set with write_concurrency and make sure we hit all "stable" keys. --- lib/stdlib/test/ets_SUITE.erl | 138 +++++++++++++++++++++++++++++++++++++++--- 1 file changed, 129 insertions(+), 9 deletions(-) (limited to 'lib/stdlib') diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl index daea9bccf5..e49181b12f 100644 --- a/lib/stdlib/test/ets_SUITE.erl +++ b/lib/stdlib/test/ets_SUITE.erl @@ -66,6 +66,7 @@ meta_lookup_named_read/1, meta_lookup_named_write/1, meta_newdel_unnamed/1, meta_newdel_named/1]). -export([smp_insert/1, smp_fixed_delete/1, smp_unfix_fix/1, smp_select_delete/1, + smp_ordered_iteration/1, smp_select_replace/1, otp_8166/1, otp_8732/1, delete_unfix_race/1]). -export([throughput_benchmark/0, test_throughput_benchmark/1]). -export([exit_large_table_owner/1, @@ -133,7 +134,8 @@ all() -> otp_5340, otp_6338, otp_6842_select_1000, otp_7665, otp_8732, meta_wb, grow_shrink, grow_pseudo_deleted, shrink_pseudo_deleted, {group, meta_smp}, smp_insert, - smp_fixed_delete, smp_unfix_fix, smp_select_replace, + smp_fixed_delete, smp_unfix_fix, smp_select_replace, + smp_ordered_iteration, smp_select_delete, otp_8166, exit_large_table_owner, exit_many_large_table_owner, exit_many_tables_owner, exit_many_many_tables_owner, write_concurrency, heir, @@ -6040,6 +6042,123 @@ smp_select_replace_do(Opts) -> true = ets:delete(T), ok. +%% Iterate ordered_set with write_concurrency +%% and make sure we hit all "stable" long lived keys +%% while "volatile" objects are randomly inserted and deleted. +smp_ordered_iteration(Config) when is_list(Config) -> + repeat_for_opts(fun smp_ordered_iteration_do/1, + [[cat_ord_set,stim_cat_ord_set]]). + + +smp_ordered_iteration_do(Opts) -> + KeyRange = 1000, + KeyFun = fun(K, Type) -> + {K div 10, K rem 10, Type} + end, + StimKeyFun = fun(K) -> + KeyFun(K, element(rand:uniform(3), + {stable, other, volatile})) + end, + T = ets_new(smp_ordered_iteration, [public, {write_concurrency,true} | Opts], + KeyRange, StimKeyFun), + NStable = KeyRange div 4, + prefill_table(T, KeyRange, NStable, fun(K) -> {KeyFun(K, stable), 0} end), + NStable = ets:info(T, size), + NVolatile = KeyRange div 2, + prefill_table(T, KeyRange, NVolatile, fun(K) -> {KeyFun(K, volatile), 0} end), + + InitF = fun (_) -> #{} end, + ExecF = fun (Counters) -> + K = rand:uniform(KeyRange), + Key = KeyFun(K, volatile), + Acc = case rand:uniform(22) of + R when R =< 10 -> + ets:insert(T, {Key}), + incr_counter(insert, Counters); + R when R =< 15 -> + ets:delete(T, Key), + incr_counter(delete, Counters); + R when R =< 19 -> + %% Delete bound key + ets:select_delete(T, [{{Key, '_'}, [], [true]}]), + incr_counter(select_delete_bk, Counters); + R when R =< 20 -> + %% Delete partially bound key + ets:select_delete(T, [{{{K div 10, '_', volatile}, '_'}, [], [true]}]), + incr_counter(select_delete_pbk, Counters); + R when R =< 21 -> + %% Replace bound key + ets:select_replace(T, [{{Key, '$1'}, [], + [{{{const,Key}, {'+','$1',1}}}]}]), + incr_counter(select_replace_bk, Counters); + _ -> + %% Replace partially bound key + ets:select_replace(T, [{{{K div 10, '_', volatile}, '$1'}, [], + [{{{element,1,'$_'}, {'+','$1',1}}}]}]), + incr_counter(select_replace_pbk, Counters) + end, + receive stop -> + [end_of_work | Acc] + after 0 -> + Acc + end + end, + FiniF = fun (Acc) -> Acc end, + Pids = run_sched_workers(InitF, ExecF, FiniF, infinite), + timer:send_after(1000, stop), + Rounds = fun Loop(N) -> + NStable = ets:select_count(T, [{{{'_', '_', stable}, '_'}, [], [true]}]), + NStable = count_stable(T, next, ets:first(T), 0), + NStable = count_stable(T, prev, ets:last(T), 0), + NStable = length(ets:select(T, [{{{'_', '_', stable}, '_'}, [], [true]}])), + NStable = length(ets:select_reverse(T, [{{{'_', '_', stable}, '_'}, [], [true]}])), + NStable = ets_select_chunks_count(T, [{{{'_', '_', stable}, '_'}, [], [true]}], + rand:uniform(5)), + receive stop -> N + after 0 -> Loop(N+1) + end + end (1), + [P ! stop || P <- Pids], + Results = wait_pids(Pids), + io:format("Ops = ~p\n", [maps_sum(Results)]), + io:format("Diff = ~p\n", [ets:info(T,size) - NStable - NVolatile]), + io:format("Stats = ~p\n", [ets:info(T,stats)]), + io:format("Rounds = ~p\n", [Rounds]), + true = ets:delete(T), + ok. + +incr_counter(Name, Counters) -> + Counters#{Name => maps:get(Name, Counters, 0) + 1}. + +count_stable(T, Next, {_, _, stable}=Key, N) -> + count_stable(T, Next, ets:Next(T, Key), N+1); +count_stable(T, Next, {_, _, volatile}=Key, N) -> + count_stable(T, Next, ets:Next(T, Key), N); +count_stable(_, _, '$end_of_table', N) -> + N. + +ets_select_chunks_count(T, MS, Chunk) -> + ets_select_chunks_count(ets:select(T, MS, Chunk), 0). + +ets_select_chunks_count('$end_of_table', N) -> + N; +ets_select_chunks_count({List, Continuation}, N) -> + ets_select_chunks_count(ets:select(Continuation), + length(List) + N). + +maps_sum([Ma | Tail]) when is_map(Ma) -> + maps_sum([lists:sort(maps:to_list(Ma)) | Tail]); +maps_sum([La, Mb | Tail]) -> + Lab = lists:zipwith(fun({K,Va}, {K,Vb}) -> {K,Va+Vb} end, + La, + lists:sort(maps:to_list(Mb))), + maps_sum([Lab | Tail]); +maps_sum([L]) -> + L. + + + + %% Test different types. types(Config) when is_list(Config) -> init_externals(), @@ -6309,19 +6428,18 @@ do_work(WorksDoneSoFar, Table, ProbHelpTab, Range, Operations) -> do_work(WorksDoneSoFar + 1, Table, ProbHelpTab, Range, Operations) end. -prefill_table(T, KeyRange, Num) -> +prefill_table(T, KeyRange, Num, ObjFun) -> Seed = rand:uniform(KeyRange), %%io:format("prefill_table: Seed = ~p\n", [Seed]), RState = unique_rand_start(KeyRange, Seed), - prefill_table_loop(T, RState, Num), - Num = ets:info(T, size). + prefill_table_loop(T, RState, Num, ObjFun). -prefill_table_loop(_, _, 0) -> +prefill_table_loop(_, _, 0, _) -> ok; -prefill_table_loop(T, RS0, N) -> +prefill_table_loop(T, RS0, N, ObjFun) -> {Key, RS1} = unique_rand_next(RS0), - ets:insert(T, {Key}), - prefill_table_loop(T, RS1, N-1). + ets:insert(T, ObjFun(Key)), + prefill_table_loop(T, RS1, N-1, ObjFun). throughput_benchmark() -> throughput_benchmark(false, not_set, not_set). @@ -6447,7 +6565,9 @@ throughput_benchmark(TestMode, BenchmarkRunMs, RecoverTimeMs) -> Range, Duration, RecoverTime) -> ProbHelpTab = CalculateOpsProbHelpTab(Scenario, 0), Table = ets:new(t, TableConfig), - prefill_table(Table, Range, Range div 2), + Nobj = Range div 2, + prefill_table(Table, Range, Nobj, fun(K) -> {K} end), + Nobj = ets:info(Table, size), SafeFixTableIfRequired(Table, Scenario, true), ParentPid = self(), ChildPids = -- cgit v1.2.3