From c93cb45ae30760b7cd4ce2d9e053a36449d4e233 Mon Sep 17 00:00:00 2001 From: Maxim Dounin Date: Wed, 18 Oct 2023 04:30:11 +0300 Subject: 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.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'src/core/ngx_queue.h') 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 -- cgit