Mercurial > hg > nginx

annotate src/core/ngx_queue.c @ 9167:3038bd4d7816

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
author Maxim Dounin <mdounin@mdounin.ru>
date Wed, 18 Oct 2023 04:30:11 +0300
parents d620f497c50f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
1
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
2 /*
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
3 * Copyright (C) Igor Sysoev
4412
d620f497c50f Copyright updated.
Maxim Konovalov <maxim@nginx.com>
parents: 2026
diff changeset
4 * Copyright (C) Nginx, Inc.
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
5 */
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
6
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
7
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
8 #include <ngx_config.h>
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
9 #include <ngx_core.h>
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
10
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
11
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
12 static void ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
13 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
14
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
15
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
16 /*
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
17 * find the middle queue element if the queue has odd number of elements
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
18 * or the first element of the queue's second part otherwise
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
19 */
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
20
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
21 ngx_queue_t *
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
22 ngx_queue_middle(ngx_queue_t *queue)
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
23 {
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
24 ngx_queue_t *middle, *next;
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
25
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
26 middle = ngx_queue_head(queue);
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
27
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
28 if (middle == ngx_queue_last(queue)) {
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
29 return middle;
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
30 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
31
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
32 next = ngx_queue_head(queue);
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
33
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
34 for ( ;; ) {
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
35 middle = ngx_queue_next(middle);
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
36
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
37 next = ngx_queue_next(next);
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
38
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
39 if (next == ngx_queue_last(queue)) {
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
40 return middle;
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
41 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
42
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
43 next = ngx_queue_next(next);
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
44
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
45 if (next == ngx_queue_last(queue)) {
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
46 return middle;
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
47 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
48 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
49 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
50
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
51
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
52 /* the stable merge sort */
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
53
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
54 void
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
55 ngx_queue_sort(ngx_queue_t *queue,
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
56 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
57 {
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
58 ngx_queue_t *q, tail;
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
59
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
60 q = ngx_queue_head(queue);
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
61
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
62 if (q == ngx_queue_last(queue)) {
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
63 return;
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
64 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
65
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
66 q = ngx_queue_middle(queue);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
67
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
68 ngx_queue_split(queue, q, &tail);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
69
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
70 ngx_queue_sort(queue, cmp);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
71 ngx_queue_sort(&tail, cmp);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
72
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
73 ngx_queue_merge(queue, &tail, cmp);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
74 }
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
75
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
76
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
77 static void
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
78 ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
79 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
80 {
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
81 ngx_queue_t *q1, *q2;
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
82
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
83 q1 = ngx_queue_head(queue);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
84 q2 = ngx_queue_head(tail);
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
85
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
86 for ( ;; ) {
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
87 if (q1 == ngx_queue_sentinel(queue)) {
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
88 ngx_queue_add(queue, tail);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
89 break;
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
90 }
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
91
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
92 if (q2 == ngx_queue_sentinel(tail)) {
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
93 break;
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
94 }
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
95
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
96 if (cmp(q1, q2) <= 0) {
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
97 q1 = ngx_queue_next(q1);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
98 continue;
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
99 }
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
100
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
101 ngx_queue_remove(q2);
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
102 ngx_queue_insert_before(q1, q2);
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
103
9167
3038bd4d7816 Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
104 q2 = ngx_queue_head(tail);
2026
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
105 }
72db8932f782 new ngx_queue functions
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
106 }