Mercurial > hg > nginx

comparison 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
comparison
equal deleted inserted replaced
9166:533bc2336df4 9167:3038bd4d7816
5 */ 5 */
6 6
7 7
8 #include <ngx_config.h> 8 #include <ngx_config.h>
9 #include <ngx_core.h> 9 #include <ngx_core.h>
10
11
12 static void ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
13 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));
10 14
11 15
12 /* 16 /*
13 * find the middle queue element if the queue has odd number of elements 17 * find the middle queue element if the queue has odd number of elements
14 * or the first element of the queue's second part otherwise 18 * or the first element of the queue's second part otherwise
43 } 47 }
44 } 48 }
45 } 49 }
46 50
47 51
48 /* the stable insertion sort */ 52 /* the stable merge sort */
49 53
50 void 54 void
51 ngx_queue_sort(ngx_queue_t *queue, 55 ngx_queue_sort(ngx_queue_t *queue,
52 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) 56 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
53 { 57 {
54 ngx_queue_t *q, *prev, *next; 58 ngx_queue_t *q, tail;
55 59
56 q = ngx_queue_head(queue); 60 q = ngx_queue_head(queue);
57 61
58 if (q == ngx_queue_last(queue)) { 62 if (q == ngx_queue_last(queue)) {
59 return; 63 return;
60 } 64 }
61 65
62 for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { 66 q = ngx_queue_middle(queue);
63 67
64 prev = ngx_queue_prev(q); 68 ngx_queue_split(queue, q, &tail);
65 next = ngx_queue_next(q);
66 69
67 ngx_queue_remove(q); 70 ngx_queue_sort(queue, cmp);
71 ngx_queue_sort(&tail, cmp);
68 72
69 do { 73 ngx_queue_merge(queue, &tail, cmp);
70 if (cmp(prev, q) <= 0) { 74 }
71 break;
72 }
73 75
74 prev = ngx_queue_prev(prev);
75 76
76 } while (prev != ngx_queue_sentinel(queue)); 77 static void
78 ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
79 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
80 {
81 ngx_queue_t *q1, *q2;
77 82
78 ngx_queue_insert_after(prev, q); 83 q1 = ngx_queue_head(queue);
84 q2 = ngx_queue_head(tail);
85
86 for ( ;; ) {
87 if (q1 == ngx_queue_sentinel(queue)) {
88 ngx_queue_add(queue, tail);
89 break;
90 }
91
92 if (q2 == ngx_queue_sentinel(tail)) {
93 break;
94 }
95
96 if (cmp(q1, q2) <= 0) {
97 q1 = ngx_queue_next(q1);
98 continue;
99 }
100
101 ngx_queue_remove(q2);
102 ngx_queue_insert_before(q1, q2);
103
104 q2 = ngx_queue_head(tail);
79 } 105 }
80 } 106 }