Mercurial > hg > nginx
view src/core/ngx_spinlock.c @ 9167:3038bd4d7816
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
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Wed, 18 Oct 2023 04:30:11 +0300 |
parents | f737e406aa68 |
children |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #include <ngx_config.h> #include <ngx_core.h> void ngx_spinlock(ngx_atomic_t *lock, ngx_atomic_int_t value, ngx_uint_t spin) { #if (NGX_HAVE_ATOMIC_OPS) ngx_uint_t i, n; for ( ;; ) { if (*lock == 0 && ngx_atomic_cmp_set(lock, 0, value)) { return; } if (ngx_ncpu > 1) { for (n = 1; n < spin; n <<= 1) { for (i = 0; i < n; i++) { ngx_cpu_pause(); } if (*lock == 0 && ngx_atomic_cmp_set(lock, 0, value)) { return; } } } ngx_sched_yield(); } #else #if (NGX_THREADS) #error ngx_spinlock() or ngx_atomic_cmp_set() are not defined ! #endif #endif }