Mercurial > hg > nginx
comparison src/core/ngx_queue.h @ 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 |
|---|---|
| 43 #define ngx_queue_insert_tail(h, x) \ | 43 #define ngx_queue_insert_tail(h, x) \ |
| 44 (x)->prev = (h)->prev; \ | 44 (x)->prev = (h)->prev; \ |
| 45 (x)->prev->next = x; \ | 45 (x)->prev->next = x; \ |
| 46 (x)->next = h; \ | 46 (x)->next = h; \ |
| 47 (h)->prev = x | 47 (h)->prev = x |
| 48 | |
| 49 | |
| 50 #define ngx_queue_insert_before ngx_queue_insert_tail | |
| 48 | 51 |
| 49 | 52 |
| 50 #define ngx_queue_head(h) \ | 53 #define ngx_queue_head(h) \ |
| 51 (h)->next | 54 (h)->next |
| 52 | 55 |