[nginx] Core: changed ngx_queue_sort() to use merge sort.

[Sergey Kandaurov]

details:   https://hg.nginx.org/nginx/rev/3038bd4d7816
branches:  
changeset: 9167:3038bd4d7816
user:      Maxim Dounin <mdounin at mdounin.ru>
date:      Wed Oct 18 04:30:11 2023 +0300
description:
Core: changed ngx_queue_sort() to use merge sort.

This improves nginx startup times significantly when using very large number
of locations due to computational complexity of the sorting algorithm being
used: insertion sort is O(n*n) on average, while merge sort is O(n*log(n)).
In particular, in a test configuration with 20k locations total startup
time is reduced from 8 seconds to 0.9 seconds.

Prodded by Yusuke Nojima,
https://mailman.nginx.org/pipermail/nginx-devel/2023-September/NUL3Y2FPPFSHMPTFTL65KXSXNTX3NQMK.html

diffstat:

 src/core/ngx_queue.c |  52 +++++++++++++++++++++++++++++++++++++++-------------
 src/core/ngx_queue.h |   3 +++
 2 files changed, 42 insertions(+), 13 deletions(-)

diffs (99 lines):

diff -r 533bc2336df4 -r 3038bd4d7816 src/core/ngx_queue.c
--- a/src/core/ngx_queue.c	Tue Oct 17 02:39:38 2023 +0300
+++ b/src/core/ngx_queue.c	Wed Oct 18 04:30:11 2023 +0300
@@ -9,6 +9,10 @@
 #include <ngx_core.h>
 
 
+static void ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
+    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));
+
+
 /*
  * find the middle queue element if the queue has odd number of elements
  * or the first element of the queue's second part otherwise
@@ -45,13 +49,13 @@ ngx_queue_middle(ngx_queue_t *queue)
 }
 
 
-/* the stable insertion sort */
+/* the stable merge sort */
 
 void
 ngx_queue_sort(ngx_queue_t *queue,
     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
 {
-    ngx_queue_t  *q, *prev, *next;
+    ngx_queue_t  *q, tail;
 
     q = ngx_queue_head(queue);
 
@@ -59,22 +63,44 @@ ngx_queue_sort(ngx_queue_t *queue,
         return;
     }
 
-    for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
+    q = ngx_queue_middle(queue);
+
+    ngx_queue_split(queue, q, &tail);
+
+    ngx_queue_sort(queue, cmp);
+    ngx_queue_sort(&tail, cmp);
+
+    ngx_queue_merge(queue, &tail, cmp);
+}
 
-        prev = ngx_queue_prev(q);
-        next = ngx_queue_next(q);
 
-        ngx_queue_remove(q);
+static void
+ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
+    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
+{
+    ngx_queue_t  *q1, *q2;
+
+    q1 = ngx_queue_head(queue);
+    q2 = ngx_queue_head(tail);
 
-        do {
-            if (cmp(prev, q) <= 0) {
-                break;
-            }
+    for ( ;; ) {
+        if (q1 == ngx_queue_sentinel(queue)) {
+            ngx_queue_add(queue, tail);
+            break;
+        }
+
+        if (q2 == ngx_queue_sentinel(tail)) {
+            break;
+        }
 
-            prev = ngx_queue_prev(prev);
+        if (cmp(q1, q2) <= 0) {
+            q1 = ngx_queue_next(q1);
+            continue;
+        }
 
-        } while (prev != ngx_queue_sentinel(queue));
+        ngx_queue_remove(q2);
+        ngx_queue_insert_before(q1, q2);
 
-        ngx_queue_insert_after(prev, q);
+        q2 = ngx_queue_head(tail);
     }
 }
diff -r 533bc2336df4 -r 3038bd4d7816 src/core/ngx_queue.h
--- a/src/core/ngx_queue.h	Tue Oct 17 02:39:38 2023 +0300
+++ b/src/core/ngx_queue.h	Wed Oct 18 04:30:11 2023 +0300
@@ -47,6 +47,9 @@ struct ngx_queue_s {
     (h)->prev = x
 
 
+#define ngx_queue_insert_before   ngx_queue_insert_tail
+
+
 #define ngx_queue_head(h)                                                     \
     (h)->next