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/http/ngx_http_request.c | |
| parent | 284a0c73771e3a2c57af6e74d96d9a6878b2e7b4 (diff) | |
| download | nginx-c93cb45ae30760b7cd4ce2d9e053a36449d4e233.tar.gz nginx-c93cb45ae30760b7cd4ce2d9e053a36449d4e233.tar.bz2 | |
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 '')
0 files changed, 0 insertions, 0 deletions