rsys

commit b0974b36ea707018c1e0570c5c0af58bd7ecb88a
parent 024e645eef0e17c0e6cc9420ac01934b713c3dd2
Author: vaplv <vaplv@free.fr>
Date:   Tue, 14 May 2019 11:23:46 +0200

Update the dynamic array allocation policies

Previously the resize function strictly allocates the submitted size if
there is no sufficient space. This exhibits strong performance issues
when resize was used in a "push_back" manner to allocate only one more
element at the end of the vector.

Now, if the submitted size is less than the current capacity, the resize
function keeps the current allocated space. If it is less than the
current size * 2, then the resize function reserves a new memory space
of size*2 entries. Finally, if the submitted size is greater than the
current size*2, then the function reserves strictly the given size.

The push back function continues to allocate 2 times the capacity of the
dynamic array if there is no sufficient space. However, note that the
reserved size is no more necessarily a power of two.

Finally the copy function reserves the maximum size between the
destination and the source. Anyway, if the destination has a capacity
that is greater than the size to reserve, the copy function use the same
memory space.

Diffstat:
M
src/dynamic_array.h
 | 
26
++++++++++++++++++++------
M
src/test_dynamic_array.c
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 74 insertions(+), 6 deletions(-)
diff --git a/src/dynamic_array.h b/src/dynamic_array.h
@@ -191,13 +191,21 @@ DARRAY_FUNC__(reserve)(struct DARRAY_TYPE__* darray, const size_t sz)
 static INLINE res_T
 DARRAY_FUNC__(resize)(struct DARRAY_TYPE__* darray, const size_t sz)
 {
+  size_t sz_adjusted;
   size_t i;
   res_T res;
   ASSERT(darray);
 
-  res = DARRAY_FUNC__(reserve)(darray, sz);
-  if(res != RES_OK)
-    return res;
+  if(sz < darray->capacity) {
+    sz_adjusted = sz;
+  } else if (sz < darray->size*2) {
+    sz_adjusted = darray->size*2;
+  } else {
+    sz_adjusted = sz;
+  }
+
+  res = DARRAY_FUNC__(reserve)(darray, sz_adjusted);
+  if(res != RES_OK) return res;
 
   if(sz < darray->size) {
     FOR_EACH(i, sz, darray->size)
@@ -220,7 +228,10 @@ DARRAY_FUNC__(push_back)
   res_T res;
   ASSERT(darray && data);
 
-  sz_adjusted = round_up_pow2(darray->size + 1);
+  sz_adjusted = darray->size + 1;
+  if(sz_adjusted > darray->capacity) {
+    sz_adjusted = MMAX(darray->capacity*2, 1);
+  }
   res = DARRAY_FUNC__(reserve)(darray, sz_adjusted);
   if(res != RES_OK) return res;
   dst = darray->data + darray->size;
@@ -272,7 +283,7 @@ static INLINE res_T
 DARRAY_FUNC__(copy)(struct DARRAY_TYPE__* dst, const struct DARRAY_TYPE__* src)
 {
   DARRAY_DATA const* src_data = NULL;
-  size_t i, src_sz;
+  size_t i, src_sz, dst_sz, sz_adjusted;
   res_T res;
   ASSERT(dst && src);
 
@@ -281,7 +292,10 @@ DARRAY_FUNC__(copy)(struct DARRAY_TYPE__* dst, const struct DARRAY_TYPE__* src)
 
   DARRAY_FUNC__(clear)(dst);
   src_sz = DARRAY_FUNC__(size_get)(src);
-  res = DARRAY_FUNC__(reserve)(dst, src_sz);
+  dst_sz = DARRAY_FUNC__(size_get)(dst);
+
+  sz_adjusted = MMAX(src_sz, dst_sz);
+  res = DARRAY_FUNC__(reserve)(dst, sz_adjusted);
   if(res != RES_OK) return res;
 
   src_data = DARRAY_FUNC__(cdata_get)(src);
diff --git a/src/test_dynamic_array.c b/src/test_dynamic_array.c
@@ -366,10 +366,12 @@ static void
 test_allocation_policy(struct mem_allocator* allocator)
 {
   struct darray_int integers;
+  struct darray_int integers2;
   const int* mem;
   int i;
 
   darray_int_init(allocator, &integers);
+  darray_int_init(allocator, &integers2);
   CHK(darray_int_capacity(&integers) == 0);
 
   CHK(darray_int_reserve(&integers, 33) == RES_OK);
@@ -436,7 +438,59 @@ test_allocation_policy(struct mem_allocator* allocator)
   CHK(darray_int_capacity(&integers) == 64);
   CHK(darray_int_size_get(&integers) == 33);
 
+  darray_int_purge(&integers);
+  CHK(darray_int_capacity(&integers) == 0);
+  CHK(darray_int_size_get(&integers) == 0);
+  CHK(darray_int_cdata_get(&integers) == NULL);
+
+  CHK(darray_int_resize(&integers, 10) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 10);
+  CHK(darray_int_size_get(&integers) == 10);
+
+  CHK(darray_int_push_back(&integers, &i) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 20);
+  CHK(darray_int_size_get(&integers) == 11);
+
+  CHK(darray_int_push_back(&integers, &i) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 20);
+  CHK(darray_int_size_get(&integers) == 12);
+
+  CHK(darray_int_resize(&integers, 17) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 20);
+  CHK(darray_int_size_get(&integers) == 17);
+
+  CHK(darray_int_resize(&integers, 24) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 34);
+  CHK(darray_int_size_get(&integers) == 24);
+
+  CHK(darray_int_resize(&integers, 41) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 48);
+  CHK(darray_int_size_get(&integers) == 41);
+
+  CHK(darray_int_reserve(&integers, 30) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 48);
+  CHK(darray_int_size_get(&integers) == 41);
+
+  CHK(darray_int_reserve(&integers, 49) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 49);
+  CHK(darray_int_size_get(&integers) == 41);
+
+  CHK(darray_int_resize(&integers2, 42) == RES_OK);
+  CHK(darray_int_copy(&integers, &integers2) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 49);
+  CHK(darray_int_size_get(&integers) == 42);
+
+  CHK(darray_int_copy(&integers2, &integers) == RES_OK);
+  CHK(darray_int_capacity(&integers2) == 42);
+  CHK(darray_int_size_get(&integers2) == 42);
+
+  CHK(darray_int_reserve(&integers2, 70) == RES_OK);
+  CHK(darray_int_copy(&integers, &integers2) == RES_OK);
+  CHK(darray_int_capacity(&integers) == 49);
+  CHK(darray_int_size_get(&integers) == 42);
+
   darray_int_release(&integers);
+  darray_int_release(&integers2);
 }
 
 int