[Libguestfs] [PATCH libnbd v2 3/8] 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>
---
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;
}
--
2.31.1