Mercurial > hg > nginx
view src/core/ngx_array.h @ 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 | 65b895cd0dfa |
children |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #ifndef _NGX_ARRAY_H_INCLUDED_ #define _NGX_ARRAY_H_INCLUDED_ #include <ngx_config.h> #include <ngx_core.h> typedef struct { void *elts; ngx_uint_t nelts; size_t size; ngx_uint_t nalloc; ngx_pool_t *pool; } ngx_array_t; ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size); void ngx_array_destroy(ngx_array_t *a); void *ngx_array_push(ngx_array_t *a); void *ngx_array_push_n(ngx_array_t *a, ngx_uint_t n); static ngx_inline ngx_int_t ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size) { /* * set "array->nelts" before "array->elts", otherwise MSVC thinks * that "array->nelts" may be used without having been initialized */ array->nelts = 0; array->size = size; array->nalloc = n; array->pool = pool; array->elts = ngx_palloc(pool, n * size); if (array->elts == NULL) { return NGX_ERROR; } return NGX_OK; } #endif /* _NGX_ARRAY_H_INCLUDED_ */