]> git.kaiwu.me - nginx.git/commit
Core: changed ngx_queue_sort() to use merge sort.
authorMaxim Dounin <mdounin@mdounin.ru>
Wed, 18 Oct 2023 01:30:11 +0000 (04:30 +0300)
committerMaxim Dounin <mdounin@mdounin.ru>
Wed, 18 Oct 2023 01:30:11 +0000 (04:30 +0300)
commitc93cb45ae30760b7cd4ce2d9e053a36449d4e233
tree6c902961f0bba9b219b4a939365cbc2393221a32
parent284a0c73771e3a2c57af6e74d96d9a6878b2e7b4
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
src/core/ngx_queue.c
src/core/ngx_queue.h