Realloc Using Way too much Memory

Question

I have made a minimal-working example of how to add elements to an array with realloc. This will be expanded in a future program that has many more elements.

#include <stdio.h>//printf
#include <stdlib.h>//malloc, realloc

int main() {
//BEGIN REALLOCATE-ABLE ARRAY
    unsigned int *array, loop_variable;
    const unsigned int ORIGINAL_ARRAY_SIZE = 4, REALLOC_INDICES = 99;
    array = malloc(ORIGINAL_ARRAY_SIZE*sizeof(unsigned int));
    for (loop_variable = 0; loop_variable < ORIGINAL_ARRAY_SIZE; loop_variable++) {
        array[loop_variable] = loop_variable;
    }
//BEGIN REALLOCATION
    for (loop_variable = 1; loop_variable < REALLOC_INDICES; loop_variable++) {
        array = realloc(array,sizeof(unsigned int)*(ORIGINAL_ARRAY_SIZE+loop_variable));
        array[ORIGINAL_ARRAY_SIZE+loop_variable-1] = 2*(ORIGINAL_ARRAY_SIZE+loop_variable-1);
        printf("reallocate array[%d] = %d\n",ORIGINAL_ARRAY_SIZE+loop_variable-1,array[ORIGINAL_ARRAY_SIZE+loop_variable-1]);
    }
//BEGIN PRINTING ARRAY VALUES
    for (loop_variable = 0; loop_variable < ORIGINAL_ARRAY_SIZE+REALLOC_INDICES-1; loop_variable++) {
        printf("array[%d] = %d\n",loop_variable,array[loop_variable]);
    }
//BEGIN FREE ARRAY
    free(array); array = NULL;
    return 0;
}

This should compile on any computer with gcc or clang. I then run this program on valgrind to ensure there are no memory leaks, and I get this:

==10791== HEAP SUMMARY:
==10791==     in use at exit: 0 bytes in 0 blocks
==10791==   total heap usage: 99 allocs, 99 frees, 20,988 bytes allocated
==10791== 
==10791== All heap blocks were freed -- no leaks are possible
==10791== 
==10791== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
==10791== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

However, what troubles me is that I'm using 20,988 bytes for a 101-element array. The memory use grows exponentially as the array gets bigger, instead of linearly by 4 bytes/element.

If I'm understanding Valgrind's output correctly, this array should have 4*101 elements = 404 bytes memory size, but appears to use about 50 times as much memory as it should. This is a trivial problem for such a small program, but more meaningful programs will run out of memory on this computer.

My question: is this array really using 20,988 bytes, or is Valgrind double-counting the memory?

Is there a more memory-efficient way to do this? I can't understand other examples of realloc, though I have tried to follow them as closely as I can and make this question relevant to as many users as possible.

Answer 1

==10791==     in use at exit: 0 bytes in 0 blocks
==10791==   total heap usage: 99 allocs, 99 frees, 20,988 bytes allocated

is this array really using 20,988 bytes

No, it's using 0 bytes.

“allocated” obviously means “ever allocated”, including bytes that have been freed, since the amount of memory “still allocated” is zero (and another line tells you that).