[PATCH] Improve performance when starting nginx with a lot of locations

[Yusuke Nojima]

# HG changeset patch
# User Yusuke Nojima <nojima at ynojima.com>
# Date 1679555707 -32400
#      Thu Mar 23 16:15:07 2023 +0900
# Node ID 6aac98fb135e47ca9cf7ad7d780cf4a10e9aa55c
# Parent  8771d35d55d0a2b1cefaab04401d6f837f5a05a2
Improve performance when starting nginx with a lot of locations

Our team has a configuration file with a very large number of
locations, and we found that starting nginx with this file takes an
unacceptable amount of time. After investigating the issue, we
discovered that the root cause of the long startup time is the sorting
of the location list.

Currently, the sorting algorithm used in nginx is insertion sort,
which requires O(n^2) time for n locations. We have modified the
sorting algorithm to use merge sort instead, which has a time
complexity of O(n log n).

We have tested the modified code using micro-benchmarks and confirmed
that the new algorithm improves nginx startup time significantly
(shown below). We believe that this change would be valuable for other
users who are experiencing similar issues.


Table: nginx startup time in seconds

n current patched
2000 0.033 0.018
4000 0.047 0.028
6000 0.062 0.038
8000 0.079 0.050
10000 0.091 0.065
12000 0.367 0.081
14000 0.683 0.086
16000 0.899 0.097
18000 1.145 0.110
20000 1.449 0.122
22000 1.650 0.137
24000 2.155 0.151
26000 3.096 0.155
28000 3.711 0.168
30000 3.539 0.184
32000 3.980 0.193
34000 4.543 0.208
36000 4.349 0.217
38000 5.021 0.229
40000 4.918 0.245
42000 4.835 0.256
44000 5.159 0.262
46000 5.802 0.331
48000 6.205 0.295
50000 5.701 0.308
52000 5.992 0.335
54000 6.561 0.323
56000 6.856 0.333
58000 6.515 0.347
60000 7.051 0.359
62000 6.956 0.377
64000 7.376 0.376
66000 7.506 0.404
68000 7.292 0.407
70000 7.422 0.461
72000 10.090 0.443
74000 18.505 0.463
76000 11.857 0.462
78000 9.752 0.470
80000 12.485 0.481
82000 11.027 0.498
84000 9.804 0.523
86000 8.482 0.515
88000 9.838 0.560
90000 12.341 0.546
92000 13.881 0.648
94000 8.309 0.635
96000 8.854 0.650
98000 12.871 0.674
100000 8.261 0.698

diff -r 8771d35d55d0 -r 6aac98fb135e src/core/ngx_queue.c
--- a/src/core/ngx_queue.c Fri Mar 10 07:43:50 2023 +0300
+++ b/src/core/ngx_queue.c Thu Mar 23 16:15:07 2023 +0900
@@ -45,36 +45,103 @@
 }


-/* the stable insertion sort */
+/* merge queue2 into queue1. queue2 becomes empty after merge. */
+
+static void
+ngx_queue_merge(ngx_queue_t *queue1, ngx_queue_t *queue2,
+    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
+{
+    ngx_queue_t *p1, *p2;
+
+    p1 = ngx_queue_head(queue1);
+    p2 = ngx_queue_head(queue2);
+
+    while (p1 != ngx_queue_sentinel(queue1)
+        && p2 != ngx_queue_sentinel(queue2)) {
+
+        if (cmp(p1, p2) > 0) {
+            ngx_queue_t *next, *prev;
+
+            next = ngx_queue_next(p2);
+            ngx_queue_remove(p2);
+            prev = ngx_queue_prev(p1);
+            ngx_queue_insert_after(prev, p2);
+            p2 = next;
+        } else {
+            p1 = ngx_queue_next(p1);
+        }
+    }
+    if (p2 != ngx_queue_sentinel(queue2)) {
+        ngx_queue_add(queue1, queue2);
+        ngx_queue_init(queue2);
+    }
+}
+
+
+/* move all elements from src to dest. dest should be empty before call. */
+
+static void
+ngx_queue_move(ngx_queue_t *dest, ngx_queue_t *src)
+{
+    *dest = *src;
+    ngx_queue_init(src);
+
+    if (dest->next == src) {
+        dest->next = dest;
+    } else {
+        dest->next->prev = dest;
+    }
+    if (dest->prev == src) {
+        dest->prev = dest;
+    } else {
+        dest->prev->next = dest;
+    }
+}
+
+
+/* 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 merged[64], *p, *last;

-    q = ngx_queue_head(queue);
-
-    if (q == ngx_queue_last(queue)) {
+    if (ngx_queue_head(queue) == ngx_queue_last(queue)) {
         return;
     }

-    for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
+    last = merged;

-        prev = ngx_queue_prev(q);
-        next = ngx_queue_next(q);
+    while (!ngx_queue_empty(queue)) {
+        /*
+         * Loop invariant:
+         *   merged[i] must have exactly 0 or 2^i elements in sorted order.
+         * For each iteration, we take one element from the given queue and
+         * insert it into merged without violating the invariant condition.
+         */

-        ngx_queue_remove(q);
+        ngx_queue_t carry, *h;
+
+        h = ngx_queue_head(queue);
+        ngx_queue_remove(h);
+        ngx_queue_init(&carry);
+        ngx_queue_insert_head(&carry, h);

-        do {
-            if (cmp(prev, q) <= 0) {
-                break;
-            }
+        for (p = merged; p != last && !ngx_queue_empty(p); p++) {
+            ngx_queue_merge(p, &carry, cmp);
+            ngx_queue_move(&carry, p);
+        }
+        if (p == last) {
+            ngx_queue_init(last);
+            last++;
+        }
+        ngx_queue_move(p, &carry);
+    }

-            prev = ngx_queue_prev(prev);
-
-        } while (prev != ngx_queue_sentinel(queue));
-
-        ngx_queue_insert_after(prev, q);
+    /* Merge all queues into one queue */
+    for (p = merged + 1; p != last; p++) {
+        ngx_queue_merge(p, p-1, cmp);
     }
+    ngx_queue_move(queue, last-1);
 }