diff options
| author | Maxim Dounin <mdounin@mdounin.ru> | 2023-10-18 04:30:11 +0300 |
|---|---|---|
| committer | Maxim Dounin <mdounin@mdounin.ru> | 2023-10-18 04:30:11 +0300 |
| commit | c93cb45ae30760b7cd4ce2d9e053a36449d4e233 (patch) | |
| tree | 6c902961f0bba9b219b4a939365cbc2393221a32 /src/core/ngx_queue.h | |
| parent | 284a0c73771e3a2c57af6e74d96d9a6878b2e7b4 (diff) | |
| download | nginx-c93cb45ae30760b7cd4ce2d9e053a36449d4e233.tar.gz nginx-c93cb45ae30760b7cd4ce2d9e053a36449d4e233.zip | |
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 (limited to 'src/core/ngx_queue.h')
| -rw-r--r-- | src/core/ngx_queue.h | 3 |
1 files changed, 3 insertions, 0 deletions
diff --git a/src/core/ngx_queue.h b/src/core/ngx_queue.h index 038bf1211..0f82f173e 100644 --- a/src/core/ngx_queue.h +++ b/src/core/ngx_queue.h @@ -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 |