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
_______________________________________________
Libguestfs mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/libguestfs
