aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/erl_db_catree.c141
-rw-r--r--erts/emulator/beam/erl_db_catree.h2
-rw-r--r--erts/emulator/beam/erl_process.h36
-rw-r--r--lib/stdlib/test/ets_SUITE.erl225
4 files changed, 331 insertions, 73 deletions
diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c
index e0d5e44f58..fed4b44a9b 100644
--- a/erts/emulator/beam/erl_db_catree.c
+++ b/erts/emulator/beam/erl_db_catree.c
@@ -166,8 +166,17 @@ static void split_catree(DbTableCATree *tb,
static void join_catree(DbTableCATree *tb,
DbTableCATreeNode *thiz,
DbTableCATreeNode *parent);
-
-
+static ERTS_INLINE
+int try_wlock_base_node(DbTableCATreeBaseNode *base_node);
+static ERTS_INLINE
+void wunlock_base_node(DbTableCATreeNode *base_node);
+static ERTS_INLINE
+void wlock_base_node_no_stats(DbTableCATreeNode *base_node);
+static ERTS_INLINE
+void wunlock_adapt_base_node(DbTableCATree* tb,
+ DbTableCATreeNode* node,
+ DbTableCATreeNode* parent,
+ int current_level);
/*
** External interface
*/
@@ -210,12 +219,16 @@ DbTableMethod db_catree =
* Constants
*/
-#define ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION 200
+#define ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION 250
#define ERL_DB_CATREE_LOCK_SUCCESS_CONTRIBUTION (-1)
+#define ERL_DB_CATREE_LOCK_GRAVITY_CONTRIBUTION (-500)
+#define ERL_DB_CATREE_LOCK_GRAVITY_PATTERN (0xFF800000)
#define ERL_DB_CATREE_LOCK_MORE_THAN_ONE_CONTRIBUTION (-10)
#define ERL_DB_CATREE_HIGH_CONTENTION_LIMIT 1000
#define ERL_DB_CATREE_LOW_CONTENTION_LIMIT (-1000)
-#define ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT 14
+#define ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT 16
+#define ERL_DB_CATREE_LOCK_LOW_NO_CONTRIBUTION_LIMIT (-20000)
+#define ERL_DB_CATREE_LOCK_HIGH_NO_CONTRIBUTION_LIMIT (20000)
/*
* Internal CA tree related helper functions and macros
@@ -245,6 +258,27 @@ DbTableMethod db_catree =
#define SET_LEFT_RELB(ca_tree_route_node, v) erts_atomic_set_relb(&(ca_tree_route_node->u.route.left), (erts_aint_t)(v));
#define SET_RIGHT_RELB(ca_tree_route_node, v) erts_atomic_set_relb(&(ca_tree_route_node->u.route.right), (erts_aint_t)(v));
+/* Change base node lock statistics */
+#define BASE_NODE_STAT_SET(NODE, VALUE) erts_atomic_set_nob(&(NODE)->u.base.lock_statistics, VALUE)
+#define BASE_NODE_STAT_READ(NODE) erts_atomic_read_nob(&(NODE)->u.base.lock_statistics)
+#define BASE_NODE_STAT_ADD(NODE, VALUE) \
+ do { \
+ Sint v = erts_atomic_read_nob(&((NODE)->u.base.lock_statistics)); \
+ ASSERT(VALUE > 0); \
+ if(v < ERL_DB_CATREE_LOCK_HIGH_NO_CONTRIBUTION_LIMIT) { \
+ erts_atomic_set_nob(&(NODE->u.base.lock_statistics), v + VALUE); \
+ } \
+ }while(0);
+#define BASE_NODE_STAT_SUB(NODE, VALUE) \
+ do { \
+ Sint v = erts_atomic_read_nob(&((NODE)->u.base.lock_statistics)); \
+ ASSERT(VALUE < 0); \
+ if(v > ERL_DB_CATREE_LOCK_LOW_NO_CONTRIBUTION_LIMIT) { \
+ erts_atomic_set_nob(&(NODE->u.base.lock_statistics), v + VALUE); \
+ } \
+ }while(0);
+
+
/* Compares a key to the key in a route node */
static ERTS_INLINE Sint cmp_key_route(Eterm key,
DbTableCATreeNode *obj)
@@ -653,10 +687,10 @@ static void dbg_provoke_random_splitjoin(DbTableCATree* tb,
switch (dbg_fastrand() % 8) {
case 1:
- base_node->u.base.lock_statistics = 1+ERL_DB_CATREE_HIGH_CONTENTION_LIMIT;
+ BASE_NODE_STAT_ADD(base_node, 1+ERL_DB_CATREE_HIGH_CONTENTION_LIMIT);
break;
case 2:
- base_node->u.base.lock_statistics = -1+ERL_DB_CATREE_LOW_CONTENTION_LIMIT;
+ BASE_NODE_STAT_SUB(base_node, -1+ERL_DB_CATREE_LOW_CONTENTION_LIMIT);
break;
}
}
@@ -664,6 +698,48 @@ static void dbg_provoke_random_splitjoin(DbTableCATree* tb,
# define dbg_provoke_random_splitjoin(T,N)
#endif /* PROVOKE_RANDOM_SPLIT_JOIN */
+static ERTS_NOINLINE
+void do_random_join(DbTableCATree* tb, Uint rand)
+{
+ DbTableCATreeNode* node = GET_ROOT_ACQB(tb);
+ DbTableCATreeNode* parent = NULL;
+ int level = 0;
+ Sint stat;
+ while (!node->is_base_node) {
+ parent = node;
+ if ((rand & (1 << level)) == 0) {
+ node = GET_LEFT_ACQB(node);
+ } else {
+ node = GET_RIGHT_ACQB(node);
+ }
+ level++;
+ }
+ BASE_NODE_STAT_SUB(node, ERL_DB_CATREE_LOCK_GRAVITY_CONTRIBUTION);
+ stat = BASE_NODE_STAT_READ(node);
+ if (stat >= ERL_DB_CATREE_LOW_CONTENTION_LIMIT &&
+ stat <= ERL_DB_CATREE_HIGH_CONTENTION_LIMIT) {
+ return; /* No adaptation */
+ }
+ if (parent != NULL && !try_wlock_base_node(&node->u.base)) {
+ if (!node->u.base.is_valid) {
+ wunlock_base_node(node);
+ return;
+ }
+ wunlock_adapt_base_node(tb, node, parent, level);
+ }
+}
+
+static ERTS_INLINE
+void do_random_join_with_low_probability(DbTableCATree* tb, Uint seed)
+{
+#ifndef ERTS_DB_CA_TREE_NO_RANDOM_JOIN_WITH_LOW_PROBABILITY
+ Uint32 rand = erts_sched_local_random(seed);
+ if (((rand & ERL_DB_CATREE_LOCK_GRAVITY_PATTERN)) == 0) {
+ do_random_join(tb, rand);
+ }
+#endif
+}
+
static ERTS_INLINE
int try_wlock_base_node(DbTableCATreeBaseNode *base_node)
{
@@ -691,9 +767,9 @@ void wlock_base_node(DbTableCATreeNode *base_node)
if (try_wlock_base_node(&base_node->u.base)) {
/* The lock is contended */
wlock_base_node_no_stats(base_node);
- base_node->u.base.lock_statistics += ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION;
+ BASE_NODE_STAT_ADD(base_node, ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION);
} else {
- base_node->u.base.lock_statistics += ERL_DB_CATREE_LOCK_SUCCESS_CONTRIBUTION;
+ BASE_NODE_STAT_SUB(base_node, ERL_DB_CATREE_LOCK_SUCCESS_CONTRIBUTION);
}
}
@@ -709,13 +785,14 @@ void wunlock_adapt_base_node(DbTableCATree* tb,
DbTableCATreeNode* parent,
int current_level)
{
+ Sint base_node_lock_stat = BASE_NODE_STAT_READ(node);
dbg_provoke_random_splitjoin(tb,node);
if ((!node->u.base.root && parent && !(tb->common.status
& DB_CATREE_FORCE_SPLIT))
- || node->u.base.lock_statistics < ERL_DB_CATREE_LOW_CONTENTION_LIMIT) {
+ || base_node_lock_stat < ERL_DB_CATREE_LOW_CONTENTION_LIMIT) {
join_catree(tb, node, parent);
}
- else if (node->u.base.lock_statistics > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT
+ else if (base_node_lock_stat > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT
&& current_level < ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT) {
split_catree(tb, node, parent);
}
@@ -728,11 +805,23 @@ static ERTS_INLINE
void rlock_base_node(DbTableCATreeNode *base_node)
{
ASSERT(base_node->is_base_node);
- erts_rwmtx_rlock(&base_node->u.base.lock);
+ if (EBUSY == erts_rwmtx_tryrlock(&base_node->u.base.lock)) {
+ /* The lock is contended */
+ BASE_NODE_STAT_ADD(base_node, ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION);
+ erts_rwmtx_rlock(&base_node->u.base.lock);
+ }
+}
+
+static ERTS_INLINE
+void runlock_base_node(DbTableCATreeNode *base_node, DbTableCATree* tb)
+{
+ ASSERT(base_node->is_base_node);
+ erts_rwmtx_runlock(&base_node->u.base.lock);
+ do_random_join_with_low_probability(tb, (Uint)base_node);
}
static ERTS_INLINE
-void runlock_base_node(DbTableCATreeNode *base_node)
+void runlock_base_node_no_rand(DbTableCATreeNode *base_node)
{
ASSERT(base_node->is_base_node);
erts_rwmtx_runlock(&base_node->u.base.lock);
@@ -814,7 +903,7 @@ void unlock_iter_base_node(CATreeRootIterator* iter)
{
ASSERT(iter->locked_bnode);
if (iter->read_only)
- runlock_base_node(iter->locked_bnode);
+ runlock_base_node(iter->locked_bnode, iter->tb);
else if (iter->locked_bnode->u.base.is_valid) {
wunlock_adapt_base_node(iter->tb, iter->locked_bnode,
iter->bnode_parent, iter->bnode_level);
@@ -874,7 +963,7 @@ DbTableCATreeNode* find_rlock_valid_base_node(DbTableCATree* tb, Eterm key)
rlock_base_node(base_node);
if (base_node->u.base.is_valid)
break;
- runlock_base_node(base_node);
+ runlock_base_node_no_rand(base_node);
}
return base_node;
}
@@ -923,8 +1012,8 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb,
"erl_db_catree_base_node",
NIL,
ERTS_LOCK_FLAGS_CATEGORY_DB);
- p->u.base.lock_statistics = ((tb->common.status & DB_CATREE_FORCE_SPLIT)
- ? INT_MAX : 0);
+ BASE_NODE_STAT_SET(p, ((tb->common.status & DB_CATREE_FORCE_SPLIT)
+ ? INT_MAX : 0));
p->u.base.is_valid = 1;
return p;
}
@@ -1094,7 +1183,7 @@ static void join_catree(DbTableCATree *tb,
ASSERT(thiz->is_base_node);
if (parent == NULL) {
- thiz->u.base.lock_statistics = 0;
+ BASE_NODE_STAT_SET(thiz, 0);
wunlock_base_node(thiz);
return;
}
@@ -1103,11 +1192,11 @@ static void join_catree(DbTableCATree *tb,
neighbor = leftmost_base_node(GET_RIGHT_ACQB(parent));
if (try_wlock_base_node(&neighbor->u.base)) {
/* Failed to acquire lock */
- thiz->u.base.lock_statistics = 0;
+ BASE_NODE_STAT_SET(thiz, 0);
wunlock_base_node(thiz);
return;
} else if (!neighbor->u.base.is_valid) {
- thiz->u.base.lock_statistics = 0;
+ BASE_NODE_STAT_SET(thiz, 0);
wunlock_base_node(thiz);
wunlock_base_node(neighbor);
return;
@@ -1153,11 +1242,11 @@ static void join_catree(DbTableCATree *tb,
neighbor = rightmost_base_node(GET_LEFT_ACQB(parent));
if (try_wlock_base_node(&neighbor->u.base)) {
/* Failed to acquire lock */
- thiz->u.base.lock_statistics = 0;
+ BASE_NODE_STAT_SET(thiz, 0);
wunlock_base_node(thiz);
return;
} else if (!neighbor->u.base.is_valid) {
- thiz->u.base.lock_statistics = 0;
+ BASE_NODE_STAT_SET(thiz, 0);
wunlock_base_node(thiz);
wunlock_base_node(neighbor);
return;
@@ -1241,7 +1330,7 @@ static void split_catree(DbTableCATree *tb,
if (less_than_two_elements(base->u.base.root)) {
if (!(tb->common.status & DB_CATREE_FORCE_SPLIT))
- base->u.base.lock_statistics = 0;
+ BASE_NODE_STAT_SET(base, 0);
wunlock_base_node(base);
return;
} else {
@@ -1521,7 +1610,7 @@ static int db_get_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
int result = db_get_tree_common(p, &tb->common,
node->u.base.root,
key, ret, NULL);
- runlock_base_node(node);
+ runlock_base_node(node, tb);
return result;
}
@@ -1804,7 +1893,7 @@ static int db_member_catree(DbTable *tbl, Eterm key, Eterm *ret)
int result = db_member_tree_common(&tb->common,
node->u.base.root,
key, ret, NULL);
- runlock_base_node(node);
+ runlock_base_node(node, tb);
return result;
}
@@ -1816,7 +1905,7 @@ static int db_get_element_catree(Process *p, DbTable *tbl,
int result = db_get_element_tree_common(p, &tb->common,
node->u.base.root,
key, ndex, ret, NULL);
- runlock_base_node(node);
+ runlock_base_node(node, tb);
return result;
}
@@ -2250,7 +2339,7 @@ void db_catree_force_split(DbTableCATree* tb, int on)
init_root_iterator(tb, &iter, 1);
root = catree_find_first_root(&iter);
do {
- iter.locked_bnode->u.base.lock_statistics = (on ? INT_MAX : 0);
+ BASE_NODE_STAT_SET(iter.locked_bnode, (on ? INT_MAX : 0));
root = catree_find_next_root(&iter, NULL);
} while (root);
destroy_root_iterator(&iter);
diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h
index cf3498dabb..c2c884eee3 100644
--- a/erts/emulator/beam/erl_db_catree.h
+++ b/erts/emulator/beam/erl_db_catree.h
@@ -42,7 +42,7 @@ typedef struct {
typedef struct {
erts_rwmtx_t lock; /* The lock for this base node */
- Sint lock_statistics;
+ erts_atomic_t lock_statistics;
int is_valid; /* If this base node is still valid */
TreeDbTerm *root; /* The root of the sequential tree */
ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */
diff --git a/erts/emulator/beam/erl_process.h b/erts/emulator/beam/erl_process.h
index bbf50b4189..0d6b512f78 100644
--- a/erts/emulator/beam/erl_process.h
+++ b/erts/emulator/beam/erl_process.h
@@ -2632,6 +2632,9 @@ void erts_notify_inc_runq(ErtsRunQueue *runq);
void erts_sched_finish_poke(ErtsSchedulerSleepInfo *, erts_aint32_t);
ERTS_GLB_INLINE void erts_sched_poke(ErtsSchedulerSleepInfo *ssi);
void erts_aux_thread_poke(void);
+ERTS_GLB_INLINE Uint32 erts_sched_local_random_hash_64_to_32_shift(Uint64 key);
+ERTS_GLB_INLINE Uint32 erts_sched_local_random(Uint additional_seed);
+
#if ERTS_GLB_INLINE_INCL_FUNC_DEF
@@ -2648,6 +2651,39 @@ erts_sched_poke(ErtsSchedulerSleepInfo *ssi)
}
+/*
+ * Source: https://gist.github.com/badboy/6267743
+ * http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
+ */
+ERTS_GLB_INLINE
+Uint32 erts_sched_local_random_hash_64_to_32_shift(Uint64 key)
+{
+ key = (~key) + (key << 18); /* key = (key << 18) - key - 1; */
+ key = key ^ (key >> 31);
+ key = (key + (key << 2)) + (key << 4);
+ key = key ^ (key >> 11);
+ key = key + (key << 6);
+ key = key ^ (key >> 22);
+ return (Uint32) key;
+}
+
+/*
+ * This function attempts to return a random number based on the state
+ * of the scheduler, the current process and the additional_seed
+ * parameter.
+ */
+ERTS_GLB_INLINE
+Uint32 erts_sched_local_random(Uint additional_seed)
+{
+ ErtsSchedulerData *esdp = erts_get_scheduler_data();
+ Uint64 seed =
+ additional_seed +
+ esdp->reductions +
+ esdp->current_process->fcalls +
+ (((Uint64)esdp->no) << 32);
+ return erts_sched_local_random_hash_64_to_32_shift(seed);
+}
+
#endif /* #if ERTS_GLB_INLINE_INCL_FUNC_DEF */
diff --git a/lib/stdlib/test/ets_SUITE.erl b/lib/stdlib/test/ets_SUITE.erl
index dd49288417..09238ae2b4 100644
--- a/lib/stdlib/test/ets_SUITE.erl
+++ b/lib/stdlib/test/ets_SUITE.erl
@@ -75,7 +75,8 @@
-export([throughput_benchmark/0,
throughput_benchmark/1,
test_throughput_benchmark/1,
- long_throughput_benchmark/1]).
+ long_throughput_benchmark/1,
+ lookup_catree_par_vs_seq_init_benchmark/0]).
-export([exit_large_table_owner/1,
exit_many_large_table_owner/1,
exit_many_tables_owner/1,
@@ -6728,6 +6729,14 @@ do_work(WorksDoneSoFar, Table, ProbHelpTab, Range, Operations) ->
end.
prefill_table(T, KeyRange, Num, ObjFun) ->
+ Parent = self(),
+ spawn_link(fun() ->
+ prefill_table_helper(T, KeyRange, Num, ObjFun),
+ Parent ! done
+ end),
+ receive done -> ok end.
+
+prefill_table_helper(T, KeyRange, Num, ObjFun) ->
Seed = rand:uniform(KeyRange),
%%io:format("prefill_table: Seed = ~p\n", [Seed]),
RState = unique_rand_start(KeyRange, Seed),
@@ -6740,11 +6749,77 @@ prefill_table_loop(T, RS0, N, ObjFun) ->
ets:insert(T, ObjFun(Key)),
prefill_table_loop(T, RS1, N-1, ObjFun).
+inserter_proc_starter(T, ToInsert, Parent) ->
+ receive
+ start -> ok
+ end,
+ inserter_proc(T, ToInsert, [], Parent, false).
+
+inserter_proc(T, [], Inserted, Parent, _) ->
+ inserter_proc(T, Inserted, [], Parent, true);
+inserter_proc(T, [I | ToInsert], Inserted, Parent, CanStop) ->
+ Stop =
+ case CanStop of
+ true ->
+ receive
+ stop -> Parent ! stopped
+ after 0 -> no_stop
+ end;
+ false -> no_stop
+ end,
+ case Stop of
+ no_stop ->
+ ets:insert(T, I),
+ inserter_proc(T, ToInsert, [I | Inserted], Parent, CanStop);
+ _ -> ok
+ end.
+
+prefill_table_parallel(T, KeyRange, Num, ObjFun) ->
+ Parent = self(),
+ spawn_link(fun() ->
+ prefill_table_parallel_helper(T, KeyRange, Num, ObjFun),
+ Parent ! done
+ end),
+ receive done -> ok end.
+
+prefill_table_parallel_helper(T, KeyRange, Num, ObjFun) ->
+ NrOfSchedulers = erlang:system_info(schedulers),
+ Seed = rand:uniform(KeyRange),
+ %%io:format("prefill_table: Seed = ~p\n", [Seed]),
+ RState = unique_rand_start(KeyRange, Seed),
+ InsertMap = prefill_insert_map_loop(T, RState, Num, ObjFun, #{}, NrOfSchedulers),
+ Self = self(),
+ Pids = [
+ begin
+ InserterFun =
+ fun() ->
+ inserter_proc_starter(T, ToInsert, Self)
+ end,
+ spawn_link(InserterFun)
+ end
+ || ToInsert <- maps:values(InsertMap)],
+ [Pid ! start || Pid <- Pids],
+ timer:sleep(1000),
+ [Pid ! stop || Pid <- Pids],
+ [receive stopped -> ok end || _Pid <- Pids].
+
+prefill_insert_map_loop(_, _, 0, _, InsertMap, _NrOfSchedulers) ->
+ InsertMap;
+prefill_insert_map_loop(T, RS0, N, ObjFun, InsertMap, NrOfSchedulers) ->
+ {Key, RS1} = unique_rand_next(RS0),
+ Sched = N rem NrOfSchedulers,
+ PrevInserts = maps:get(Sched, InsertMap, []),
+ NewPrevInserts = [ObjFun(Key) | PrevInserts],
+ NewInsertMap = maps:put(Sched, NewPrevInserts, InsertMap),
+ prefill_insert_map_loop(T, RS1, N-1, ObjFun, NewInsertMap, NrOfSchedulers).
+
-record(ets_throughput_bench_config,
{benchmark_duration_ms = 3000,
recover_time_ms = 1000,
thread_counts = not_set,
key_ranges = [1000000],
+ init_functions = [fun prefill_table/4],
+ nr_of_repeats = 1,
scenarios =
[
[
@@ -6838,7 +6913,7 @@ prefill_table_loop(T, RS0, N, ObjFun) ->
notify_res_fun = fun(_Name, _Throughput) -> ok end,
print_result_paths_fun =
fun(ResultPath, _LatestResultPath) ->
- Comment =
+ Comment =
io_lib:format("<a href=\"file:///~s\">Result visualization</a>",[ResultPath]),
{comment, Comment}
end
@@ -6848,7 +6923,7 @@ stdout_notify_res(ResultPath, LatestResultPath) ->
io:format("Result Location: /~s~n", [ResultPath]),
io:format("Latest Result Location: ~s~n", [LatestResultPath]).
-throughput_benchmark() ->
+throughput_benchmark() ->
throughput_benchmark(
#ets_throughput_bench_config{
print_result_paths_fun = fun stdout_notify_res/2}).
@@ -6856,9 +6931,11 @@ throughput_benchmark() ->
throughput_benchmark(
#ets_throughput_bench_config{
benchmark_duration_ms = BenchmarkDurationMs,
- recover_time_ms = RecoverTimeMs,
- thread_counts = ThreadCountsOpt,
- key_ranges = KeyRanges,
+ recover_time_ms = RecoverTimeMs,
+ thread_counts = ThreadCountsOpt,
+ key_ranges = KeyRanges,
+ init_functions = InitFuns,
+ nr_of_repeats = NrOfRepeats,
scenarios = Scenarios,
table_types = TableTypes,
etsmem_fun = ETSMemFun,
@@ -6872,21 +6949,21 @@ throughput_benchmark(
Start = rand:uniform(KeyRange),
Last =
lists:foldl(
- fun(_, Prev) ->
+ fun(_, Prev) ->
case Prev of
'$end_of_table'-> ok;
_ ->
try ets:next(T, Prev) of
Normal -> Normal
catch
- error:badarg ->
+ error:badarg ->
% sets (not ordered_sets) cannot handle when the argument
% to next is not in the set
rand:uniform(KeyRange)
end
end
end,
- Start,
+ Start,
lists:seq(1, SeqSize)),
case Last =:= -1 of
true -> io:format("Will never be printed");
@@ -6898,26 +6975,26 @@ throughput_benchmark(
Start = rand:uniform(KeyRange),
Last = Start + SeqSize,
case -1 =:= ets:select_count(T,
- ets:fun2ms(fun({X}) when X > Start andalso X =< Last -> true end)) of
+ ets:fun2ms(fun({X}) when X > Start andalso X =< Last -> true end)) of
true -> io:format("Will never be printed");
false -> ok
end
end,
%% Mapping benchmark operation names to their corresponding functions that do them
- Operations =
+ Operations =
#{insert =>
- fun(T,KeyRange) ->
+ fun(T,KeyRange) ->
Num = rand:uniform(KeyRange),
ets:insert(T, {Num})
end,
delete =>
- fun(T,KeyRange) ->
+ fun(T,KeyRange) ->
Num = rand:uniform(KeyRange),
ets:delete(T, Num)
end,
lookup =>
- fun(T,KeyRange) ->
+ fun(T,KeyRange) ->
Num = rand:uniform(KeyRange),
ets:lookup(T, Num)
end,
@@ -6928,8 +7005,8 @@ throughput_benchmark(
nextseq1000 =>
fun(T,KeyRange) -> NextSeqOp(T,KeyRange,1000) end,
selectAll =>
- fun(T,_KeyRange) ->
- case -1 =:= ets:select_count(T, ets:fun2ms(fun(_X) -> true end)) of
+ fun(T,_KeyRange) ->
+ case -1 =:= ets:select_count(T, ets:fun2ms(fun(_X) -> true end)) of
true -> io:format("Will never be printed");
false -> ok
end
@@ -6951,7 +7028,7 @@ throughput_benchmark(
NewCurrent = Current + OpPropability,
[{NewCurrent, OpName}| Calculate(Res, NewCurrent)]
end,
- RenderScenario =
+ RenderScenario =
fun R([], StringSoFar) ->
StringSoFar;
R([{Fraction, Operation}], StringSoFar) ->
@@ -6978,7 +7055,7 @@ throughput_benchmark(
false -> ok
end
end,
- DataHolder =
+ DataHolder =
fun DataHolderFun(Data)->
receive
{get_data, Pid} -> Pid ! {ets_bench_data, Data};
@@ -6992,18 +7069,21 @@ throughput_benchmark(
DataHolderPid ! io_lib:format(Str, List)
end,
GetData =
- fun () ->
+ fun () ->
DataHolderPid ! {get_data, self()},
receive {ets_bench_data, Data} -> Data end
end,
%% Function that runs a benchmark instance and returns the number
%% of operations that were performed
RunBenchmark =
- fun({NrOfProcs, TableConfig, Scenario, Range, Duration}) ->
+ fun({NrOfProcs, TableConfig, Scenario, Range, Duration, InitFun}) ->
ProbHelpTab = CalculateOpsProbHelpTab(Scenario, 0),
Table = ets:new(t, TableConfig),
Nobj = Range div 2,
- prefill_table(Table, Range, Nobj, fun(K) -> {K} end),
+ case InitFun of
+ not_set -> prefill_table(Table, Range, Nobj, fun(K) -> {K} end);
+ _ -> InitFun(Table, Range, Nobj, fun(K) -> {K} end)
+ end,
Nobj = ets:info(Table, size),
SafeFixTableIfRequired(Table, Scenario, true),
ParentPid = self(),
@@ -7016,12 +7096,14 @@ throughput_benchmark(
end,
ChildPids =
lists:map(fun(_N) ->spawn_link(Worker)end, lists:seq(1, NrOfProcs)),
+ erlang:garbage_collect(),
+ timer:sleep(RecoverTimeMs),
lists:foreach(fun(Pid) -> Pid ! start end, ChildPids),
timer:sleep(Duration),
lists:foreach(fun(Pid) -> Pid ! stop end, ChildPids),
TotalWorksDone = lists:foldl(
- fun(_, Sum) ->
- receive
+ fun(_, Sum) ->
+ receive
Count -> Sum + Count
end
end, 0, ChildPids),
@@ -7032,27 +7114,32 @@ throughput_benchmark(
RunBenchmarkInSepProcess =
fun(ParameterTuple) ->
P = self(),
- spawn_link(fun()-> P ! {bench_result, RunBenchmark(ParameterTuple)} end),
- Result = receive {bench_result, Res} -> Res end,
- timer:sleep(RecoverTimeMs),
- Result
+ Results =
+ [begin
+ spawn_link(fun()-> P ! {bench_result, RunBenchmark(ParameterTuple)} end),
+ receive {bench_result, Res} -> Res end
+ end || _ <- lists:seq(1, NrOfRepeats)],
+ lists:sum(Results) / NrOfRepeats
end,
RunBenchmarkAndReport =
fun(ThreadCount,
TableType,
Scenario,
KeyRange,
- Duration) ->
+ Duration,
+ InitFunName,
+ InitFun) ->
Result = RunBenchmarkInSepProcess({ThreadCount,
TableType,
Scenario,
KeyRange,
- Duration}),
+ Duration,
+ InitFun}),
Throughput = Result/(Duration/1000.0),
PrintData("; ~f",[Throughput]),
- Name = io_lib:format("Scenario: ~w, Key Range Size: ~w, "
+ Name = io_lib:format("Scenario: ~s, ~w, Key Range Size: ~w, "
"# of Processes: ~w, Table Type: ~w",
- [Scenario, KeyRange, ThreadCount, TableType]),
+ [InitFunName, Scenario, KeyRange, ThreadCount, TableType]),
NotifyResFun(Name, Throughput)
end,
ThreadCounts =
@@ -7087,17 +7174,29 @@ throughput_benchmark(
PrintData("$~n",[]),
lists:foreach(
fun(TableType) ->
- PrintData("~w ",[TableType]),
lists:foreach(
- fun(ThreadCount) ->
- RunBenchmarkAndReport(ThreadCount,
- TableType,
- Scenario,
- KeyRange,
- BenchmarkDurationMs)
+ fun(InitFunArg) ->
+ {InitFunName, InitFun} =
+ case InitFunArg of
+ {FunName, Fun} -> {FunName, Fun};
+ Fun -> {"", Fun}
+ end,
+ PrintData("~s,~w ",[InitFunName,TableType]),
+ lists:foreach(
+ fun(ThreadCount) ->
+ RunBenchmarkAndReport(ThreadCount,
+ TableType,
+ Scenario,
+ KeyRange,
+ BenchmarkDurationMs,
+ InitFunName,
+ InitFun)
+ end,
+ ThreadCounts),
+ PrintData("$~n",[])
end,
- ThreadCounts),
- PrintData("$~n",[])
+ InitFuns)
+
end,
TableTypes)
end,
@@ -7121,7 +7220,7 @@ throughput_benchmark(
test_throughput_benchmark(Config) when is_list(Config) ->
throughput_benchmark(
#ets_throughput_bench_config{
- benchmark_duration_ms = 100,
+ benchmark_duration_ms = 100,
recover_time_ms = 0,
thread_counts = [1, erlang:system_info(schedulers)],
key_ranges = [50000],
@@ -7136,7 +7235,7 @@ long_throughput_benchmark(Config) when is_list(Config) ->
recover_time_ms = 1000,
thread_counts = [1, N div 2, N],
key_ranges = [1000000],
- scenarios =
+ scenarios =
[
[
{0.5, insert},
@@ -7171,15 +7270,15 @@ long_throughput_benchmark(Config) when is_list(Config) ->
{0.01, partial_select1000}
]
],
- table_types =
+ table_types =
[
[ordered_set, public, {write_concurrency, true}, {read_concurrency, true}],
[set, public, {write_concurrency, true}, {read_concurrency, true}]
],
etsmem_fun = fun etsmem/0,
verify_etsmem_fun = fun verify_etsmem/1,
- notify_res_fun =
- fun(Name, Throughput) ->
+ notify_res_fun =
+ fun(Name, Throughput) ->
SummaryTable =
proplists:get_value(ets_benchmark_result_summary_tab, Config),
AddToSummaryCounter =
@@ -7209,13 +7308,47 @@ long_throughput_benchmark(Config) when is_list(Config) ->
total_throughput_ordered_set)
end,
ct_event:notify(
- #event{name = benchmark_data,
+ #event{name = benchmark_data,
data = [{suite,"ets_bench"},
{name, Name},
{value,Throughput}]})
end
}).
+%% This function compares the lookup operation's performance for
+%% ordered_set ETS tables with and without write_concurrency enabled
+%% when the data structures have been populated in parallel and
+%% sequentially.
+%%
+%% The main purpose of this function is to check that the
+%% implementation of ordered_set with write_concurrency (CA tree)
+%% adapts its structure to contention even when only lookup operations
+%% are used.
+lookup_catree_par_vs_seq_init_benchmark() ->
+ N = erlang:system_info(schedulers),
+ throughput_benchmark(
+ #ets_throughput_bench_config{
+ benchmark_duration_ms = 600000,
+ recover_time_ms = 1000,
+ thread_counts = [1, N div 2, N],
+ key_ranges = [1000000],
+ init_functions = [{"seq_init", fun prefill_table/4},
+ {"par_init", fun prefill_table_parallel/4}],
+ nr_of_repeats = 1,
+ scenarios =
+ [
+ [
+ {1.0, lookup}
+ ]
+ ],
+ table_types =
+ [
+ [ordered_set, public, {write_concurrency, true}],
+ [ordered_set, public]
+ ],
+ print_result_paths_fun = fun stdout_notify_res/2
+ }).
+
add_lists(L1,L2) ->
add_lists(L1,L2,[]).
add_lists([],[],Acc) ->
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-04 17:56:30 +0000