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

1 files changed, 50 insertions, 4 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;