[Libguestfs] [PATCH nbdkit 2/4] common/urils/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. NBDKIT_BENCH=1 ./test-vector bench_reserve: 1000000 appends in 0.004496 s bench_append: 1000000 appends in 0.004180 s This can make a difference in code appending millions of items. Ported from libnbd: https://listman.redhat.com/archives/libguestfs/2021-October/msg00306.html --- 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 00cd2546..7df17e1b 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; } -- 2.31.1