Re: [Libguestfs] [PATCH libnbd 2/7] common/utils/vector.c: Optimize vector append

Minimize reallocs by growing the backing array by factor of 1.5. Testing show that now append() is fast without calling reserve() upfront, simplifying code using vector. $ ./test-vector | grep bench bench_reserve: 1000000 appends in 0.003997 s bench_append: 1000000 appends in 0.003869 s In practice, this can make "nbdinfo --map" 10 milliseconds faster when running with image that have 500,000 extents. Signed-off-by: Nir Soffer <nsoffer(a)redhat.com&gt; --- common/utils/vector.c | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) diff --git a/common/utils/vector.c b/common/utils/vector.c index 00cd254..7df17e1 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -41,11 +41,21 @@ int generic_vector_reserve (struct generic_vector *v, size_t n, size_t itemsize) { void *newptr; + size_t reqalloc, newalloc; - newptr = realloc (v->ptr, (n + v->alloc) * itemsize); + reqalloc = v->alloc + n; + if (reqalloc < v->alloc) + return -1; /* overflow */

+ newalloc = (v->alloc * 3 + 1) / 2; + + if (newalloc < reqalloc) + newalloc = reqalloc; + + newptr = realloc (v->ptr, newalloc * itemsize); if (newptr == NULL) return -1; v->ptr = newptr; - v->alloc += n; + v->alloc = newalloc; return 0; }