# HG changeset patch # User Yusuke Nojima <noj...@ynojima.com> # Date 1679555707 -32400 # Thu Mar 23 16:15:07 2023 +0900 # Node ID 6aac98fb135e47ca9cf7ad7d780cf4a10e9aa55c # Parent 8771d35d55d0a2b1cefaab04401d6f837f5a05a2 Improve performance when starting nginx with a lot of locations
Our team has a configuration file with a very large number of locations, and we found that starting nginx with this file takes an unacceptable amount of time. After investigating the issue, we discovered that the root cause of the long startup time is the sorting of the location list. Currently, the sorting algorithm used in nginx is insertion sort, which requires O(n^2) time for n locations. We have modified the sorting algorithm to use merge sort instead, which has a time complexity of O(n log n). We have tested the modified code using micro-benchmarks and confirmed that the new algorithm improves nginx startup time significantly (shown below). We believe that this change would be valuable for other users who are experiencing similar issues. Table: nginx startup time in seconds n current patched 2000 0.033 0.018 4000 0.047 0.028 6000 0.062 0.038 8000 0.079 0.050 10000 0.091 0.065 12000 0.367 0.081 14000 0.683 0.086 16000 0.899 0.097 18000 1.145 0.110 20000 1.449 0.122 22000 1.650 0.137 24000 2.155 0.151 26000 3.096 0.155 28000 3.711 0.168 30000 3.539 0.184 32000 3.980 0.193 34000 4.543 0.208 36000 4.349 0.217 38000 5.021 0.229 40000 4.918 0.245 42000 4.835 0.256 44000 5.159 0.262 46000 5.802 0.331 48000 6.205 0.295 50000 5.701 0.308 52000 5.992 0.335 54000 6.561 0.323 56000 6.856 0.333 58000 6.515 0.347 60000 7.051 0.359 62000 6.956 0.377 64000 7.376 0.376 66000 7.506 0.404 68000 7.292 0.407 70000 7.422 0.461 72000 10.090 0.443 74000 18.505 0.463 76000 11.857 0.462 78000 9.752 0.470 80000 12.485 0.481 82000 11.027 0.498 84000 9.804 0.523 86000 8.482 0.515 88000 9.838 0.560 90000 12.341 0.546 92000 13.881 0.648 94000 8.309 0.635 96000 8.854 0.650 98000 12.871 0.674 100000 8.261 0.698 diff -r 8771d35d55d0 -r 6aac98fb135e src/core/ngx_queue.c --- a/src/core/ngx_queue.c Fri Mar 10 07:43:50 2023 +0300 +++ b/src/core/ngx_queue.c Thu Mar 23 16:15:07 2023 +0900 @@ -45,36 +45,103 @@ } -/* the stable insertion sort */ +/* merge queue2 into queue1. queue2 becomes empty after merge. */ + +static void +ngx_queue_merge(ngx_queue_t *queue1, ngx_queue_t *queue2, + ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) +{ + ngx_queue_t *p1, *p2; + + p1 = ngx_queue_head(queue1); + p2 = ngx_queue_head(queue2); + + while (p1 != ngx_queue_sentinel(queue1) + && p2 != ngx_queue_sentinel(queue2)) { + + if (cmp(p1, p2) > 0) { + ngx_queue_t *next, *prev; + + next = ngx_queue_next(p2); + ngx_queue_remove(p2); + prev = ngx_queue_prev(p1); + ngx_queue_insert_after(prev, p2); + p2 = next; + } else { + p1 = ngx_queue_next(p1); + } + } + if (p2 != ngx_queue_sentinel(queue2)) { + ngx_queue_add(queue1, queue2); + ngx_queue_init(queue2); + } +} + + +/* move all elements from src to dest. dest should be empty before call. */ + +static void +ngx_queue_move(ngx_queue_t *dest, ngx_queue_t *src) +{ + *dest = *src; + ngx_queue_init(src); + + if (dest->next == src) { + dest->next = dest; + } else { + dest->next->prev = dest; + } + if (dest->prev == src) { + dest->prev = dest; + } else { + dest->prev->next = dest; + } +} + + +/* the stable merge sort */ void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) { - ngx_queue_t *q, *prev, *next; + ngx_queue_t merged[64], *p, *last; - q = ngx_queue_head(queue); - - if (q == ngx_queue_last(queue)) { + if (ngx_queue_head(queue) == ngx_queue_last(queue)) { return; } - for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { + last = merged; - prev = ngx_queue_prev(q); - next = ngx_queue_next(q); + while (!ngx_queue_empty(queue)) { + /* + * Loop invariant: + * merged[i] must have exactly 0 or 2^i elements in sorted order. + * For each iteration, we take one element from the given queue and + * insert it into merged without violating the invariant condition. + */ - ngx_queue_remove(q); + ngx_queue_t carry, *h; + + h = ngx_queue_head(queue); + ngx_queue_remove(h); + ngx_queue_init(&carry); + ngx_queue_insert_head(&carry, h); - do { - if (cmp(prev, q) <= 0) { - break; - } + for (p = merged; p != last && !ngx_queue_empty(p); p++) { + ngx_queue_merge(p, &carry, cmp); + ngx_queue_move(&carry, p); + } + if (p == last) { + ngx_queue_init(last); + last++; + } + ngx_queue_move(p, &carry); + } - prev = ngx_queue_prev(prev); - - } while (prev != ngx_queue_sentinel(queue)); - - ngx_queue_insert_after(prev, q); + /* Merge all queues into one queue */ + for (p = merged + 1; p != last; p++) { + ngx_queue_merge(p, p-1, cmp); } + ngx_queue_move(queue, last-1); } _______________________________________________ nginx-devel mailing list nginx-devel@nginx.org https://mailman.nginx.org/mailman/listinfo/nginx-devel