[glib: 1/2] gsequence: make treap priorities more random to avoid worst-case scenarios

[Philip Withnall <pwithnall src gnome org>]

commit 59e5612339785938fe137bed17d84c0f2f3455bb
Author: Alexandr Miloslavskiy <alexandr miloslavskiy syntevo com>
Date:   Tue Aug 24 00:06:55 2021 +0300

    gsequence: make treap priorities more random to avoid worst-case scenarios
    
    Previously, priority was not randomly generated and was instead derived
    from `GSequenceNode*` pointer value.
    
    As a result, when a `GSequence` was freed and another was created, the
    nodes were returned to memory allocator in such order that allocating
    them again caused various performance problems in treap.
    
    To my understanding, the problem develops like this :
    1) Initially, memory allocator makes some nodes
    2) For each node, priority is derived from pointer alone.
       Due to the hash function, initially the priorities are reasonably
       randomly distributed.
    3) `GSequence` moves inserted nodes around to satisfy treap property.
       The priority for node must be >= than priorities of its children
    4) When `GSequence` is freed, it frees nodes in a new order.
       It finds root node and then recursively frees left/right children.
       Due to (3), hashes of freed nodes become partially ordered.
       Note that this doesn't depend on choice of hash function.
    5) Memory allocator will typically add freed chunks to free list.
       This means that it will reallocate nodes in same or inverse order.
    6) This results in order of hashes being more and more non-random.
    7) This order happens to be increasingly anti-optimal.
       That is, `GSequence` needs more `node_rotate` to maintain treap.
       This also causes the tree to become more and more unbalanced.
       The problem becomes worse with each iteration.
    
    The solution is to use additional noise to maintain reasonable
    randomness. This prevents "poisoning" the memory allocator.
    
    On top of that, this patch somehow decreases average tree's height,
    which is good because it speeds up various operations. I can't quite
    explain why the height decreases with new code, probably the properties
    of old hash function didn't quite match the needs of treap?
    
    My averaged results for tree height with different sequence lengths:
      Items | before|         after |
    --------+-------+---------------+
          2 |  2,69 |  2,67 -00,74% |
          4 |  3,71 |  3,80 +02,43% |
          8 |  5,30 |  5,34 +00,75% |
         16 |  7,45 |  7,22 -03,09% |
         32 | 10,05 |  9,38 -06,67% |
         64 | 12,97 | 11,72 -09,64% |
        128 | 16,01 | 14,20 -11,31% |
        256 | 19,11 | 16,77 -12,24% |
        512 | 22,03 | 19,39 -11,98% |
       1024 | 25,29 | 22,03 -12,89% |
       2048 | 28,43 | 24,82 -12,70% |
       4096 | 31,11 | 27,52 -11,54% |
       8192 | 34,31 | 30,30 -11,69% |
      16384 | 37,40 | 32,81 -12,27% |
      32768 | 40,40 | 35,84 -11,29% |
      65536 | 43,00 | 38,24 -11,07% |
     131072 | 45,50 | 40,83 -10,26% |
     262144 | 48,40 | 43,00 -11,16% |
     524288 | 52,40 | 46,80 -10,69% |
    
    The memory cost of the patch is zero on 64-bit, because the new field
    uses the alignment hole between two other fields.
    
    Note: priorities can sometimes have collisions. This is fine, because
    treap allows equal priorities, but these will gradually decrease
    performance. The hash function that was used previously has just one
    collision on 0xbfff7fff in 32-bit space, but such pointer will not
    occur because `g_slice_alloc()` always aligns to sizeof(void*).
    However, in 64-bit space the old hash function had collisions anyway,
    because it only uses lower 32 bits of pointer.
    
    Closes #2468

 glib/gsequence.c      | 54 +++++++++++++++++++++++++++++++++++++++++++++++----
 glib/tests/sequence.c | 13 ++++---------
 2 files changed, 54 insertions(+), 13 deletions(-)
---
diff --git a/glib/gsequence.c b/glib/gsequence.c
index 9d76dbb22..2b443fe5b 100644
--- a/glib/gsequence.c
+++ b/glib/gsequence.c
@@ -120,6 +120,7 @@ struct _GSequence
 struct _GSequenceNode
 {
   gint                  n_nodes;
+  guint32               priority;
   GSequenceNode *       parent;
   GSequenceNode *       left;
   GSequenceNode *       right;
@@ -1572,11 +1573,9 @@ g_sequence_swap (GSequenceIter *a,
  *
  *
  */
-static guint
-get_priority (GSequenceNode *node)
+static guint32
+hash_uint32 (guint32 key)
 {
-  guint key = GPOINTER_TO_UINT (node);
-
   /* This hash function is based on one found on Thomas Wang's
    * web page at
    *
@@ -1590,6 +1589,20 @@ get_priority (GSequenceNode *node)
   key = key + (key << 3) + (key << 11);
   key = key ^ (key >> 16);
 
+  return key;
+}
+
+static inline guint
+get_priority (GSequenceNode *node)
+{
+  return node->priority;
+}
+
+static guint
+make_priority (guint32 key)
+{
+  key = hash_uint32 (key);
+
   /* We rely on 0 being less than all other priorities */
   return key? key : 1;
 }
@@ -1608,7 +1621,40 @@ node_new (gpointer data)
 {
   GSequenceNode *node = g_slice_new0 (GSequenceNode);
 
+  /*
+   * Make a random number quickly. Some binary magic is used to avoid
+   * the costs of proper RNG, such as locking around global GRand.
+   *
+   * Using just the node pointer alone is not enough, because in this
+   * case freeing and re-allocating sequence causes node's priorities
+   * to no longer be random. This happens for two reasons:
+   * 1) Nodes are freed from the root and the treap's property is that
+   *    node's priority is >= than its children's priorities.
+   * 2) g_slice_new0() will reuse freed nodes in the order similar to
+   *    the order of freeing.
+   * As a result, there are severe problems where building the treap is
+   * much slower (100x and more after a few sequence new/free
+   * iterations) and treap becomes more like a list (tree height
+   * approaches tree's number of elements), which increases costs of
+   * using the built treap.
+   *
+   * Note that for performance reasons, counter completely ignores
+   * multi-threading issues. This is fine because it's merely a source
+   * of additional randomness. Even if it fails to ++ sometimes, this
+   * won't really matter for its goal.
+   *
+   * Note that 64-bit counter is used to avoid undefined behavior on
+   * overflow.
+   *
+   * See https://gitlab.gnome.org/GNOME/glib/-/issues/2468
+   */
+  static guint64 counter = 0;
+  guint32 hash_key = (guint32) GPOINTER_TO_UINT (node);
+  hash_key ^= (guint32) counter;
+  counter++;
+
   node->n_nodes = 1;
+  node->priority = make_priority (hash_key);
   node->data = data;
   node->left = NULL;
   node->right = NULL;
diff --git a/glib/tests/sequence.c b/glib/tests/sequence.c
index c2eba2c79..b52ca38fb 100644
--- a/glib/tests/sequence.c
+++ b/glib/tests/sequence.c
@@ -15,7 +15,8 @@ struct _GSequence
 
 struct _GSequenceNode
 {
-  guint                 n_nodes;
+  gint                  n_nodes;
+  guint32               priority;
   GSequenceNode *       parent;
   GSequenceNode *       left;
   GSequenceNode *       right;
@@ -25,15 +26,9 @@ struct _GSequenceNode
 static guint
 get_priority (GSequenceNode *node)
 {
-  guint key = GPOINTER_TO_UINT (node);
-
-  key = (key << 15) - key - 1;
-  key = key ^ (key >> 12);
-  key = key + (key << 2);
-  key = key ^ (key >> 4);
-  key = key + (key << 3) + (key << 11);
-  key = key ^ (key >> 16);
+  guint key = node->priority;
 
+  /* We rely on 0 being less than all other priorities */
   return key? key : 1;
 }