Welcome! Log In Create A New Profile

Advanced

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

Yusuke Nojima
September 22, 2023 03:00AM
# HG changeset patch
# User Yusuke Nojima <nojima@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);
}
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
https://mailman.nginx.org/mailman/listinfo/nginx-devel
Subject Author Views Posted

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

Yusuke Nojima 351 September 22, 2023 03:00AM

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

Maxim Dounin 79 September 29, 2023 11:40PM

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

Yusuke Nojima 61 October 04, 2023 09:52PM

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

Илья Шипицин 79 October 05, 2023 02:18AM

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

Yusuke Nojima 71 October 05, 2023 10:40PM

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

Maxim Dounin 59 October 10, 2023 06:58PM

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

Yusuke Nojima 63 October 11, 2023 06:34AM

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

Sergey Kandaurov 58 October 17, 2023 07:26AM

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

Maxim Dounin 82 October 17, 2023 10:04PM



Sorry, you do not have permission to post/reply in this forum.

Online Users

Guests: 121
Record Number of Users: 8 on April 13, 2023
Record Number of Guests: 421 on December 02, 2018
Powered by nginx      Powered by FreeBSD      PHP Powered      Powered by MariaDB      ipv6 ready