ETS ordered_set: Improvements to the CA tree implementation

This commit only affects the implementation of ETS `ordered_set`
tables with the `write_concurrency` option enabled. Such tables are
implemented with a data structure that is called the contention
adapting search tree (CA tree). This commit introduces the following
changes:

* This commit causes a join to be triggered in one randomly selected
  base node in about one of 1000 read unlock calls for base node
  locks. No such joins happened before this commit. Before this
  commit, operations that only acquired looks in read-mode never
  triggered any contention adaptation. Therefore, the CA tree could
  get stuck in a sub-optimal state in certain scenarios. This could
  happen, for example, when a CA tree is first populated with parallel
  inserts (which will cause splits of base nodes) and then only
  read-only operations are applied to the data structure. Benchmark
  results from the
  `ets_SUITE:lookup_catree_par_vs_seq_init_benchmark/0` benchmark
  function (which is included in this commit) shows that this change
  can improve the throughput of the CA tree in the scenario described
  above.

* Read-only operations will now also increase values of statistics
  counters when they detect that they need to wait for other
  operations. Only write operation changed statistics counters before
  this commit. This improves the statistics that the adaptation
  heuristics is based on.

* Additionally, this commit adds an upper and lower limit to the
  contention statistics variables in the base nodes. Such limits did
  not exist before this commit. This should, for example, make the CA
  tree more responsive to contention after long periods of low
  contention.

1 files changed, 36 insertions, 0 deletions

diff --git a/erts/emulator/beam/erl_process.h b/erts/emulator/beam/erl_process.h
index 9ccdd9df82..3f3c7de64d 100644
--- a/erts/emulator/beam/erl_process.h
+++ b/erts/emulator/beam/erl_process.h
@@ -2634,6 +2634,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
 
@@ -2650,6 +2653,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 */