Mercurial > hg > nginx
comparison src/core/ngx_queue.c @ 9167:3038bd4d7816
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 } |