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

[Nir Soffer]

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 at 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