details: https://hg.nginx.org/nginx/rev/3038bd4d7816
branches:
changeset: 9167:3038bd4d7816
user: Maxim Dounin <mdounin@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

_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
https://mailman.nginx.org/mailman/listinfo/nginx-devel