How to peak best allocation strategy

Question

I'm writing a program what reads data from stream (pipe or socket in my example) and put that data into array. The problem is what I can't know how much data I need to read from my stream and what's why I don't know how much memory I need to allocate for my array. If I know what, there is no need in this question. The only thing I know is what than some value (-1 for example) appears in stream what means end of stream. So the function what reads data from stream could look like this:

int next_value() {
    return (rand() % 100) - 1;
}

Code what work with this data looks like this:

int main()
{
    int len = 0;
    int *arr = NULL;
    int val, res = 0;

    srand(time(NULL));

    while ((val = next_value()) != -1) {
        if ((res = set_value_in_array(val, &arr, &len))) {
            perror("set_value_in_array");
            exit(EXIT_FAILURE);
        }
    }

    // uncomment next line if set_value_in_array_v2 or set_value_in_array_v3
    //realloc(arr, len * sizeof(*arr));
    free(arr);
    return 0;
}

I have three strategies of putting data into array with memory allocation routine for that array.

The easiest is to allocate (reallocate) memory for each new value what appears from next_value() like this:

// allocate new element in array for each call
int set_value_in_array_v1(int val, int **arr, int *len) {
    int *tmp;

    tmp = realloc(*arr, ((*len) + 1) * sizeof(**arr));
    if (tmp) {
        *arr = tmp;
    } else {
        return -1;
    }

    *((*arr) + (*len)) = val;
    (*len)++;

    return 0;
}

Easy, but I think that it's not ideal. I don't know how many values will be read from stream. The number of values could be in range from 0 to infinity. Another strategy is to allocate memory for more than one element. This will decrease number of calls to memory management unit. The code can look like this:

// allocate ELEMS_PER_ALLOC every time allocation needed
int set_value_in_array_v2(int val, int **arr, int *len) {
    #define ELEMS_PER_ALLOC 4 // how many elements allocate on next allocation
    int *tmp;

    if ((*len) % ELEMS_PER_ALLOC == 0) {
        tmp = realloc(*arr, ((*len) + ELEMS_PER_ALLOC) * sizeof(**arr));
        if (tmp) {
            *arr = tmp;
        } else {
            return -1;
        }
    }

    *((*arr) + (*len)) = val;
    (*len)++;

    return 0;
}

Much more better, but is it the best solution? What if I will allocate memory in geometric progression like this:

// allocate *len * FRAC_FOR_ALLOC each time allocation needed
int set_value_in_array_v3(int val, int **arr, int *len) {
    #define FRAC_FOR_ALLOC  3 // how many times increase number of allocated memory on next allocation
    static int allocated = 0; // i know this is bad to use static but it's for experiments only
    int *tmp;

    if (allocated == (*len)) {
        if (allocated == 0) {
            allocated = 1;
        }
        allocated *= FRAC_FOR_ALLOC;

        tmp = realloc(*arr, allocated * sizeof(**arr));
        if (tmp) {
            *arr = tmp;
        } else {
            return -1;
        }
    }

    *((*arr) + (*len)) = val;
    (*len)++;
    return 0;
}

The same way is used in .NET Framework List<T> data structure. This way has one big problem: it will allocate a lot of memory after 100 of elements and situations when there is no way to increase current chunk of memory will be more likely to appear.

In the other hand, set_value_in_array_v2 will call memory manager very often what is also not a good idea if there are many data in stream.

So my question is what is the best strategy of memory allocation in situations similar to mine? I can't find any answers for my question in Internet. Every link just show me the best practices for memory management API usage.

Thanks in advance.

Answer 1

This question was part of my bachelor's thesis, unfortunately it is in german.

I compared 3 allocation methods: fixed increase (your case 2), fixed factor (your case 3), and a dynamic factor.

The analysis in the other answers are quite good, but I want to add an important finding of my practical tests: The fixed step increase can use the most memory in runtime! (and is some orders of magnitude slower...)

Why? Suppose you have allocated space for 10 items. Then when adding the 11th item, the space should grow by 10. Now it might not be possible to simply increase the space adjacent to the first 10 items (because it is used otherwise). So fresh space for 20 items is allocated, the origninal 10 are copied, and the original space is freed. You have now allocated 30 items, when you can actually only use 20. This gets worse with every allocation.

My dynamic factor approach intendet to grow fast, as long as the steps are not too big, and later use smaller factors, so that the risk of getting out of memory is minimized. It is some kind of inverted sigmoid function.

The thesis can be found here: XML Toolbox for Matlab. Relevant chapters are 3.2 (implementation) and 5.3.2 (practical tests)

Answer 2

The number of reallocations if you are reallocating every time a new element is added is n. There is no worst case scenario for memory usage.

The number of reallocations if you are reallocating memory in multiples of 4 is nearly n/4. In the worst case scenario , you'll be wasting a constant 3 units of memory.

The number of reallocations required if you are reallocating the memory by a factor of k each time you run out of space is log n where the base of the logarithm is k. In the worst case scenario, you will have (1 - 1/k)*100% of memory being wasted. For k = 2, you'll have 50% of the allocated memory being unused. On average, you will have (1 - 1/k)*0.5*100% of your memory unused.

While reallocating memory using a geometric sequence, you will be guaranteed logarithmic time complexity. However, large factors of k will also put a limit on the maximum amount of memory you can allocate.

Suppose you could allocate just 1GB of memory for your requirement and you already storing 216MB. If you use a k factor of 20, your next reallocation would fail because you would demand more than 1GB of memory.

The larger your base is, the smaller the time complexity will be but it also increases the amount of memory going unused in the worst (and average) case and also caps the maximum memory to something lesser than what you could have actually used (this of course varies from situation to situation; if you had 1296MB of allocatable memory and your base was 6, the cap on the array size would be 1296MB as 1296 is a power of 6 assuming that you started off with memory which is a power of 6).

What you need depends on your situation. In most cases, you would have a rough estimate of your memory requirements. You can do the first optimization by setting up the initial memory to your estimate. You can keep doubling the memory thereon every time you run out of memory. After your stream is closed, you can reallocate the memory to match the exact size of your data (if you really really need to free the unused memory).