Which order should allocated memory blocks be freed in?

user_45843 0
Viewed 382

Given something like:

char *a = malloc(m);
char *b = malloc(n);
char *c = malloc(o);

Once you have finished with the blocks of memory, this is correct:

free(a);
free(b);
free(c);

And so is this:

free(c);
free(b);
free(a);

Yet one or other order must be used, and it is more satisfying to have a basis for choosing one.

Is there any existing implementation on which it makes any difference to memory fragmentation, or to the speed at which the memory is freed and subsequent allocation requests satisfied? If so, which order is more efficient? Or is there any other basis for choosing an order?

malloc memory-management c c++
5 Answers

Without any known relationship between these blocks of memory, there is no basis for designating which deallocation order is correct. Just as there is no basis for deciding which allocation order is correct.

This is not a question that can be answered a priori. The only reason not to deallocate memory is if you're still using it, and one piece of memory could be "using" (ie: storing a pointer into) another. So without knowing anything about what is going on inside of that memory, there is no reason to pick any particular deallocation order.

user_7340690

Normally this should be irrelevant for most usecases. However, I once had a project, which was allocating an extremely high number of objects, and there it made a noticable performance difference. In this case, the second variant was much faster (from back to front), than deallocating in the same order as it was allocated.

In our scenario it took almost 4 minutes to deallocate from first to last, while it took only about a minute in the other direction.

But as always with performance, wether a change makes any difference should be measured on the target system.

user_22820110

All else equal, releasing resources is better done in the reverse order of acquisition. This "feels" more natural, and may actually be more efficient in some cases (including memory de/allocations) where the symmetry can help the manager of said resources reclaim them more orderly.

It is the same reason why for example C++ constructs elements of an array from beginning to end, but destructs them in reverse order (class.init.general/3):

When an array of class objects is initialized (either explicitly or implicitly) and the elements are initialized by constructor, the constructor shall be called for each element of the array, following the subscript order; see dcl.array.

[Note 1: Destructors for the array elements are called in reverse order of their construction. — end note]

user_55384200

I like to think of it like this, with scoping ifs

    char *a = malloc(m);
    if (a) {
        char *b = malloc(n);
        if (b) {
            char *c = malloc(o);
            if (c) {
                //...
                free(c);
            }
            free(b);
        }
        free(a);
    }

And now, remove the braces and ifs ... and you get your 2nd option.

user_253240

This is a low-level detail, subject to change when your build environment upgrades. As such, I would look to general principles instead of specific implementations. In this case, I would add a hypothesis to the general principles.

Hypothesis:
If the order of freeing memory makes a difference for performance, the build environment would prefer better performance for the general tendency of the language.

This is based on an assumption that the build environment values producing fast programs. Anyone who wants to dispute that should disregard this answer.

By "general tendency of the language", I am referring to the idea that the last thing constructed tends to be the first thing destroyed. For example, a derived class is constructed after its base is, but the derived class is destroyed before its base. Even within a class, members are destroyed in the reverse order of construction. Last constructed, first destroyed. If the members own dynamically allocated memory, then last allocated, first released (more or less).

This tendency does not guarantee that memory will be released in reverse order from acquisition. In fact, it's not hard to come up with counter-examples. However, it does mean that the reverse order seems more likely than any other order. There are very few guarantees when accounting for all the crazy things a programmer might do, but it seems reasonable to me that free would be optimized either in a symmetric manner (order does not matter) or geared towards this reverse order, if possible.

This is not a proof, nor is it an absolute rule. This is just playing the odds. If the above seems reasonable, I would suggest going with the tendency of the language initially. (Actually, I would suggest that memory be released in a destructor, which forces the order specified by the language.) If profiling indicates that this is a problem area, then more attention would be warranted. Until then, in the question's scenario, free(c) first to improve your odds.

user_98373010
Related