Currently I'm working on a microprocessor that only has a small RAM capacity (128 MB). I'm running multiple threads of execution to analyze performance but the essence of the problem lies on storing large amounts of data (floats and integers) in dynamic space in order to reduce the possibility of data copy/allocation that data structures such as vectors tend to rely on in execution.
I decided to test some possible schemes on how to tackle this in CLion. I wrote the following code:
#include <cstdlib>
#include <cstdio>
int initial_capacity = 3;
int current_capacity = 3;
int current_count = 0;
int*** initializeArray(){
// initialize triple array space in memory
int*** arr;
/*
3 items -> 3 data sets -> each data set starts with 3 spaces
a "int arr[3][3][3]" but dynamically allocated
*/
arr = (int***) calloc(current_capacity, sizeof(int**));
for(int i = 0; i < current_capacity; i++){
arr[i] = (int**) calloc(current_capacity, sizeof(int*));
for(int j =0; j < current_capacity; j++){
arr[i][j] = (int*) calloc(current_capacity,sizeof(int));
}
}
return arr;
}
void resizeArray(int *** arr){
auto max = (double) current_capacity;
double percentage = current_count/max;
if(percentage >= 0.5){
for (int i = 0; i < initial_capacity; ++i) {
for (int j = 0; j < initial_capacity; ++j) {
current_capacity*=2;
arr[i][j] = (int*) realloc(arr[i][j],(current_capacity)*sizeof(int));
}
}
}
}
void deleteArrays(int *** arr){
for (int i = 0; i < initial_capacity; ++i) {
for (int j = 0; j < initial_capacity; ++j) {
for (int k = 0; k < current_count; ++k) {
arr[i][j][k] = NULL;
}
}
}
printf("Releasing allocated arrays 1\n");
for (int i = 0; i < initial_capacity; ++i) {
for (int j = 0; j < initial_capacity; ++j) {
arr[i][j] = (int*) realloc(arr[i][j],sizeof(int));
free(arr[i][j]);
}
}
printf("Releasing allocated arrays 2\n");
for (int i = 0; i < initial_capacity; ++i) {
free(arr[i]);
}
printf("Releasing allocated arrays 3\n");
free(arr);
}
void printArrays(int *** arr){
for (int i = 0; i < 3; ++i) {
printf("Array[%d]\n", i);
for (int j = 0; j < 3; ++j) {
printf("Array[%d][%d]\nElements: ", i, j);
for (int k = 0; k < current_count; ++k) {
printf(" %d", arr[i][j][k]);
}
printf("\n");
}
}
printf("\n");
}
int main() {
int *** generated= initializeArray();
int count = 0;
while (count < 21){
if(count % 3 == 0) printArrays(generated);
//verify
resizeArray(generated);
generated[0][0][current_count] = rand();
generated[0][1][current_count] = rand();
generated[0][2][current_count] = rand();
generated[1][0][current_count] = rand();
generated[1][1][current_count] = rand();
generated[1][2][current_count] = rand();
generated[2][0][current_count] = rand();
generated[2][1][current_count] = rand();
generated[2][2][current_count] = rand();
current_count++;
count++;
}
/* some operation with data collected */
deleteArrays(generated);
printf("Finished deleting dynamic arrays");
return 0;
}
I attempted to generate a triple array in order to keep storing the same amount of information in the last subset while it kept increasing in size and total amount. However, the delete procedure of the array in order to complete the dynamic aspect of the process always results in Process finished with exit code -1073740940 (0xC0000374) which is a heap corruption error. I'm not super familiar with this and any feedback on it would be helpful.
The routine resizeArray doubles current_capacity with current_capacity*=2; in each iteration of its inner loop. The first time it is called, this results in arr[0][0] being set to point to memory for 6 int, while the loops continue and ultimately leave current_capacity set to 1536. For the rest of program execution, resizeArray never allocates more memory, due to the fact that its threshold relative to current_capacity is never reached.
Meanwhile, the main routine continues writing more and more elements to generated[0][0], increasing current_count up to 20 and therefore writing beyond the bounds of the allocated memory.
This bug can be fixed by moving current_capacity*=2; out of the loops, to just inside the “then” block of if(percentage >= 0.5).
Also note that the technique of implementing multidimensional arrays as pointers-to-pointers or pointers-to-pointers-to-pointers is inefficient in time and space. “Pointer chasing” is bad for speculative execution of instructions by the processor. For fixed-size multidimensional arrays, this is not used in production-quality code. In this case where a variable last dimension is desired, the choice is a little less clear, but it still may be preferable to use one contiguous memory allocation and to use index arithmetic to calculate locations in the array rather than pointer lookups. (C makes this fairly simple with variable length arrays, although support for them is optional. C++ implementations may provide variable length arrays as an extension, but the necessary arithmetic is not hard and can be done with helper functions or classes.)