Merge branch 'kjell/stdlib/ets_ordered_set_slow_react/OTP-15906' into maint

* kjell/stdlib/ets_ordered_set_slow_react/OTP-15906:
  ETS ordered_set: Improvements to the CA tree implementation

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) ->