rsys

commit 09c677e26fede0741f13a4c589a0da887a9ee459
parent 92c2d902582f97b08062c5eaae5d089a3fd595e8
Author: vaplv <vaplv@free.fr>
Date:   Tue, 14 May 2019 11:46:13 +0200

Merge branch 'release_0.8.1'

Diffstat:
M
README.md
 | 
6
++++++
M
cmake/CMakeLists.txt
 | 
2
+-
M
src/dynamic_array.h
 | 
26
++++++++++++++++++++------
M
src/test_dynamic_array.c
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 81 insertions(+), 7 deletions(-)
diff --git a/README.md b/README.md
@@ -17,6 +17,12 @@ project can be now edited, built, tested and installed as any CMake project.
 
 ## Release notes
 
+### Version 0.8.1
+
+- Fix the allocation policy of the dynamic array that exhibited strong
+  performance issues when the `resize` function was used in a `push_back`
+  manner, i.e. to allocate a new entry at the end of the dynamic array.
+
 ### Version 0.8
 
 - Update the allocation policy of the dynamic arrays: the `reserve` and
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -39,7 +39,7 @@ include(rcmake)
 ################################################################################
 set(VERSION_MAJOR 0)
 set(VERSION_MINOR 8)
-set(VERSION_PATCH 0)
+set(VERSION_PATCH 1)
 set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
 
 set(RSYS_FILES_SRC
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