change growth factor of array
Vladimir Shebordaev
vshebordaev at mail.ru
Fri Oct 19 15:23:31 UTC 2012
Hi!
You might wish to try this patch if you do need really large arrays in nginx that would be fast and memory efficient on insertion at cost of rather slow read access.
--- /dev/null 2012-10-18 19:22:00.714822120 +0400
+++ src/core/ngx_vector.h 2012-07-13 05:57:58.000000000 +0400
@@ -0,0 +1,140 @@
+#ifndef _NGX_VECTOR_H_INCLUDED_
+#define _NGX_VECTOR_H_INCLUDED_
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+typedef struct ngx_vector_s ngx_vector_t;
+
+struct ngx_vector_s {
+ size_t size;
+ ngx_int_t last;
+ /* data blocks */
+ size_t d;
+ size_t db_size;
+ size_t d_free;
+ /* superblocks */
+ size_t s;
+ size_t sb_size;
+ size_t s_free;
+ /* index block */
+ void **index;
+ size_t ib_size;
+
+ ngx_pool_t *pool;
+};
+
+#ifdef __GNUC__
+#define ngx_clz(n) __builtin_clz(n)
+#else
+#error "You have to define ngx_clz() for your compiler"
+#endif
+
+static ngx_inline
+ngx_int_t ngx_vector_bound_check(const ngx_vector_t *vec, ngx_int_t idx)
+{
+ return idx > vec->last;
+}
+
+static ngx_inline
+void *__ngx_vector_locate(const ngx_vector_t *vec, size_t idx)
+{
+ ngx_uint_t k, msb, half, mask, b, e, p;
+
+ ++idx;
+ k = (NGX_PTR_SIZE << 3) - 1 - ngx_clz(idx);
+
+ msb = 1 << k;
+ half = (k + 1) >> 1;
+ mask = (1 << half) - 1;
+
+ p = mask + (1 << (k - half)) - 1;
+ b = (idx ^ msb) >> half;
+ e = idx & mask;
+
+ return (char *)vec->index[p + b] + e * vec->size;
+}
+
+static ngx_inline
+void *ngx_vector_read(const ngx_vector_t *vec, size_t idx)
+{
+ return ngx_vector_bound_check(vec, idx) ? NULL : __ngx_vector_locate(vec, idx);
+}
+
+static ngx_inline
+void *ngx_vector_write(const ngx_vector_t *vec, size_t idx, void *value)
+{
+ void *ret;
+
+ if (ngx_vector_bound_check(vec, idx))
+ return NULL;
+
+ ret = __ngx_vector_locate(vec, idx);
+ if (ret && value)
+ ngx_memcpy(ret, value, vec->size);
+
+ return ret;
+}
+
+extern ngx_int_t __ngx_vector_grow_by(ngx_vector_t *vec, size_t nelts);
+extern ngx_int_t __ngx_vector_alloc_block(ngx_vector_t *vec);
+
+static ngx_inline ngx_int_t
+ngx_vector_grow_by(ngx_vector_t *vec, size_t nelts)
+{
+ if (nelts <= vec->d_free) {
+ vec->d_free -= nelts;
+ vec->last += nelts;
+
+ return NGX_OK;
+ }
+
+ vec->last += vec->d_free;
+ nelts -= vec->d_free;
+
+ return __ngx_vector_grow_by(vec, nelts);
+}
+
+static ngx_inline ngx_int_t
+ngx_vector_grow(ngx_vector_t *vec)
+{
+ ngx_int_t ret;
+
+ ret = vec->d_free ? NGX_OK : __ngx_vector_alloc_block(vec);
+ if (ret != NGX_OK)
+ goto out;
+
+ vec->d_free--;
+ vec->last++;
+out:
+ return ret;
+}
+
+static ngx_inline size_t
+ngx_vector_size(ngx_vector_t *vec)
+{
+ return vec->last + 1;
+}
+
+static ngx_inline void *
+ngx_vector_push_back(ngx_vector_t *vec, void *value)
+{
+ void *ret;
+
+ if (ngx_vector_grow(vec) != NGX_OK) {
+ ret = NULL;
+ goto out;
+ }
+
+ ret = __ngx_vector_locate(vec, ngx_vector_size(vec) - 1);
+ if (ret && value)
+ ngx_memcpy(ret, value, vec->size);
+out:
+ return ret;
+}
+
+extern ngx_vector_t *ngx_vector_init(size_t size, ngx_pool_t *pool);
+extern void ngx_vector_destroy(ngx_vector_t *vec);
+
+#endif /* _NGX_VECTOR_H_INCLUDED_ */
+
--- /dev/null 2012-10-18 19:22:00.714822120 +0400
+++ src/core/ngx_vector.c 2012-07-13 05:36:28.000000000 +0400
@@ -0,0 +1,134 @@
+#include <ngx_vector.h>
+
+ngx_vector_t *
+ngx_vector_init(size_t size, ngx_pool_t *pool)
+{
+ ngx_vector_t *ret;
+
+ ret = NULL;
+
+ if (!pool)
+ goto out;
+
+ ret = ngx_palloc(pool, sizeof(ngx_vector_t));
+ if (!ret)
+ goto out;
+
+ ret->pool = pool;
+
+ ret->size = size;
+ ret->last = -1;
+
+ ret->index = ngx_palloc(pool, ngx_pagesize);
+ if (!ret->index)
+ goto out_free;
+
+ ngx_memzero(ret->index, ngx_pagesize);
+ ret->ib_size = ngx_pagesize / sizeof(ret->index[0]);
+
+ ret->d = 0;
+ ret->db_size = 1;
+ ret->d_free = 1;
+
+ ret->s = 0;
+ ret->sb_size = 1;
+ ret->s_free = 0;
+
+ ret->index[0] = ngx_palloc(pool, size);
+ if (!ret->index[0])
+ goto out_free_index;
+out:
+ return ret;
+
+out_free_index:
+ ngx_pfree(pool, ret->index);
+out_free:
+ ngx_pfree(pool, ret);
+ return NULL;
+}
+
+void
+ngx_vector_destroy(ngx_vector_t *vec)
+{
+ size_t i;
+
+ for (i = 0; i <= vec->d; i++)
+ ngx_pfree(vec->pool, (void *)vec->index[i]);
+
+ ngx_pfree(vec->pool, vec->index);
+ ngx_pfree(vec->pool, vec);
+}
+
+ngx_int_t
+__ngx_vector_grow_by(ngx_vector_t *vec, size_t nelts)
+{
+ ngx_int_t ret;
+
+ for(;;) {
+ ret = __ngx_vector_alloc_block(vec);
+ if (ret != NGX_OK)
+ goto out;
+
+ if (nelts < vec->d_free)
+ break;
+
+ nelts -= vec->db_size;
+ vec->last += vec->db_size;
+ }
+ vec->d_free -= nelts;
+ vec->last += nelts;
+
+ ret = NGX_OK;
+out:
+ return ret;
+}
+
+ngx_int_t
+__ngx_vector_alloc_block(ngx_vector_t *vec)
+{
+ ngx_int_t ret;
+
+ ret = NGX_ERROR;
+
+ if (!vec->s_free) {
+ vec->s++;
+
+ if (vec->s & 1)
+ vec->db_size *= 2;
+ else
+ vec->sb_size *= 2;
+
+ vec->s_free = vec->sb_size;
+ }
+
+ vec->d++;
+ vec->s_free--;
+
+ if (vec->d >= vec->ib_size) {
+ void **index;
+ size_t size;
+
+ size = 2 * vec->ib_size * sizeof(void *);
+ index = ngx_palloc(vec->pool, size);
+ if (!index)
+ goto out;
+
+ ngx_memzero(index, size);
+ ngx_memcpy(index, vec->index, vec->ib_size * sizeof(void *));
+ ngx_pfree(vec->pool, vec->index);
+
+ vec->index = index;
+ vec->ib_size *= 2;
+ }
+
+ vec->index[vec->d] = ngx_palloc(vec->pool, vec->db_size * vec->size);
+ if (!vec->index[vec->d])
+ goto out;
+
+ vec->d_free = vec->db_size;
+
+ ret = NGX_OK;
+out:
+ return ret;
+}
+
This code implements the algorithms described here
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9607>
They say about square root of array size .
It used to work for me a few months ago. Sure, it is possible to optimize read access code but the element size is known just at run-time, so it seems hard to be done without register parameters and inline assembler.
Hope it helps.
Regards,
Vladimir
Fri, 19 Oct 2012 20:06:15 +0800 от Simon Liu <simohayha.bobo at gmail.com>:
>
>In this document ( https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md ) , It is to suggest use factor 1.5 (when you'd push into
>a array without there being room) in dynamically-allocated arrays. the factor is 2 in array of Nginx, and so I think may be change factor to 1.5 is be better in Nginx's array.
>
>Thanks.
>
>
>
More information about the nginx-devel
mailing list