Memory Allocation/Deallocation

Memory Allocation/Deallocation?

The Memory Model

The C++ standard has a memory model. It attempts to model the memory in a computer system in a generic way. The standard defines that a byte is a storage unit in the memory model and that memory is made up of bytes (§1.7):

The fundamental storage unit in the C++ memory model is the byte. [...] The memory available to a C++ program consists of one or more sequences of contiguous bytes.

The Object Model

The standard always provides an object model. This specifies that an object is a region of storage (so it is made up of bytes and resides in memory) (§1.8):

The constructs in a C++ program create, destroy, refer to, access, and manipulate objects. An object is a region of storage.

So there we go. Memory is where objects are stored. To store an object in memory, the required region of storage must be allocated.

Allocation and Deallocation Functions

The standard provides two implicitly declared global scope allocation functions:

void* operator new(std::size_t);
void* operator new[](std::size_t);

How these are implemented is not the standard's concern. All that matters is that they should return a pointer to some region of storage with the number of bytes corresponding to the argument passed (§3.7.4.1):

The allocation function attempts to allocate the requested amount of storage. If it is successful, it shall return the address of the start of a block of storage whose length in bytes shall be at least as large as the requested size. There are no constraints on the contents of the allocated storage on return from the allocation function.

It also defines two corresponding deallocation functions:

void operator delete(void*);
void operator delete[](void*);

Which are defined to deallocate storage that has previously been allocated (§3.7.4.2):

If the argument given to a deallocation function in the standard library is a pointer that is not the null pointer value (4.10), the deallocation function shall deallocate the storage referenced by the pointer, rendering invalid all pointers referring to any part of the deallocated storage.

new and delete

Typically, you should not need to use the allocation and deallocation functions directly because they only give you uninitialised memory. Instead, in C++ you should be using new and delete to dynamically allocate objects. A new-expression obtains storage for the requested type by using one of the above allocation functions and then initialises that object in some way. For example new int() will allocate space for an int object and then initialise it to 0. See §5.3.4:

A new-expression obtains storage for the object by calling an allocation function (3.7.4.1).

[...]

A new-expression that creates an object of type T initializes that object [...]

In the opposite direction, delete will call the destructor of an object (if any) and then deallocate the storage (§5.3.5):

If the value of the operand of the delete-expression is not a null pointer value, the delete-expression will invoke the destructor (if any) for the object or the elements of the array being deleted.

[...]

If the value of the operand of the delete-expression is not a null pointer value, the delete-expression will call a deallocation function (3.7.4.2).

Other Allocations

However, these are not the only ways that storage is allocated or deallocated. Many constructs of the language implicitly require allocation of storage. For example, giving an object definition, like int a;, also requires storage (§7):

A definition causes the appropriate amount of storage to be reserved and any appropriate initialization (8.5) to be done.

C standard library: malloc and free

In addition, the <cstdlib> header brings in the contents of the stdlib.h C standard library, which includes the malloc and free functions. They are also defined, by the C standard, to allocate and deallocate memory, much like the allocation and deallocation functions defined by the C++ standard. Here's the definition of malloc (C99 §7.20.3.3):

void *malloc(size_t size);
Description
The malloc function allocates space for an object whose size is specified by size and
whose value is indeterminate.

Returns
The malloc function returns either a null pointer or a pointer to the allocated space.

And the definition of free (C99 §7.20.3.2):

void free(void *ptr);
Description
The free function causes the space pointed to by ptr to be deallocated, that is, made
available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if the argument does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to free or realloc,
the behavior is undefined.

However, there's never a good excuse to be using malloc and free in C++. As described before, C++ has its own alternatives.

---

Answers to Questions

So to answer your questions directly:

1. Where is the "memory" that is being allocated?

   The C++ standard doesn't care. It simply says that the program has some memory which is made up of bytes. This memory can be allocated.

2. What is this "memory"? Space in an array? Or something else?

   As far as the standard is concerned, the memory is just a sequence of bytes. This is purposefully very generic, as the standard only tries to model typical computer systems. You can, for the most part, think of it as a model of the RAM of your computer.

3. What happens exactly when this "memory" gets allocated?

   Allocating memory makes some region of storage available for use by the program. Objects are initialized in allocated memory. All you need to know is that you can allocate memory. The actual allocation of physical memory to your process tends to be done by the operating system.

4. What happens exactly when the memory gets deallocated?

   Deallocating some previously allocated memory causes that memory to be unavailable to the program. It becomes deallocated storage.

5. It would also really help me if someone could answer what malloc does in these C++ lines:

   char* x; 
   x = (char*) malloc (8);
   

   Here, malloc is simply allocating 8 bytes of memory. The pointer it returns is being cast to a char* and stored in x.

Memory allocation/deallocation when working with C# and C++ unmanaged

It's really simple!

1. Depends
2. Depends

Eh, Sorry about that.

1. Under typical conditions, C# will keep track of the memory and get rid of it any time after it's no longer used on the C# side. It has no way of tracking references on the C++ side, so one common mistake in interop is that the memory is deallocated before the unmanaged side is done with it (resulting in loads of FUN). This only applies for cases where the memory is directly referenced, not when its copied (the typical case being a byte[] that's pinned for the duration of the unmanaged call). Don't use automatic marshalling when the life-time of the object/pointer being passed to unmanaged code is supposed to be longer than the run of the invoked method.
2. Under typical conditions, C# has no way of tracking memory allocations in the C++ code, so you can't rely on automatic memory management. There are exceptions (e.g. some COM scenarios), but you'll almost always need to manage the memory manually. This usually means sending the pointer back to the C++ code to do the deallocation, unless it used a global allocator of some kind (e.g. CoMemoryInitialize). Remember that in the unmanaged world, there is no one memory manager that you can safely invoke to dispose of memory; you don't really have the necessary information anyway.

This only applies to pointers, of course. Passing integers is perfectly fine, and using automatic marshalling usually means the marshaller takes care of most of the subtleties (though still only in the simplest case, so be careful). Unmanaged code is unmanaged - you need to understand perfectly how the memory is allocated, and how, when and who is responsible for cleaning up the memory.

Memory Allocation/Deallocation Bottleneck?

It's significant, especially as fragmentation grows and the allocator has to hunt harder across larger heaps for the contiguous regions you request. Most performance-sensitive applications typically write their own fixed-size block allocators (eg, they ask the OS for memory 16MB at a time and then parcel it out in fixed blocks of 4kb, 16kb, etc) to avoid this issue.

In games I've seen calls to malloc()/free() consume as much as 15% of the CPU (in poorly written products), or with carefully written and optimized block allocators, as little as 5%. Given that a game has to have a consistent throughput of sixty hertz, having it stall for 500ms while a garbage collector runs occasionally isn't practical.

Dynamic memory allocation/deallocation in MIPS asembly

However, I do not understand how it is possible to deallocate memory back to the heap.

MARS/SPIM do not allow for returning memory back to the heap, AFAIK.  Even if they did allow the negative value sbrk like unix does, that only supports returning the most recently allocated (by sbrk) item — and this is different from client expectations that any heap item can be freed.

So, the only thing you can do is provide an intermediate allocator, that keeps track of free'd space, and prefers freed space (e.g. over increasing the heap space with sbrk) for new allocations when possible.

Second, I am unsure how to save dynamic variables by the user.

This is program responsibility — and by that I mean the test program or user program, not the library that implements malloc and free.  I presume there will be some test program.  That program will invoke your malloc & free implementations and probably will only pass the test by allocating & freeing lots of memory, but staying within the 4k limit of maximum memory.

To succeed in this task, the code must allocate and deallocate memory upon request. If some of the requests cannot be handled, exception handling must activate to resolve the issue.

I have trouble imagining what this means.  Obviously, we can terminate the program when a request for memory is made that cannot be satisfied (i.e. out of memory), but this text suggests that exception handling of some sort can resolve the issue.

Does Ada deallocate memory automatically under some circumstances?

As outlined in Memory Management with Ada 2012, cited here, a local variable is typically allocated on a stack; its memory is automatically released when the variable's scope exits. In contrast, a dynamic a variable is typically allocated on a heap; its memory is allocated using new, and its memory must be reclaimed, usually:

• Explicitly, e.g. using an instance of Unchecked_Deallocation.

• Implicitly, e.g. using a controlled type derived from Finalization; as noted here, when the scope of a controlled instance exits, automatic finalization calls Finalize, which reclaims storage in a manner suitable to the type's design.

The children of Ada.Containers use controlled types internally to encapsulate access values and manage memory automatically. For reference, compare your compiler's implementation of a particular container to the corresponding functional container cited here.

Ada offers a variety of ways to manage memory, summarized on slide 28 in the author's order of preferability:

1. Stack-based.
2. Container-based.
3. Finalization-based.
4. Subpool-based.
5. Manual allocate/deallocate.

In the particular case of Main, the program allocates storage for 16 instances of Integer. As noted on slide 12, "A compiler may reclaim allocated memory when the corresponding access type goes out of scope." For example, a recent version of the GNAT reference manual indicates that the following storage management implementation advice is followed:

A storage pool for an anonymous access type should be created at the point of an allocator for the type, and be reclaimed when the designated object becomes inaccessible.

Absent such an indication, the storage is not required to be reclaimed. It is typically reclaimed by the host operating system when the program exits.

Why deallocating heap memory is much slower than allocating it?

I had much the same idea as @Basile: I wondered whether your base assumption was actually (even close to) correct. Since you tagged the question C++, I wrote a quick benchmark in C++ instead.

#include <vector>
#include <iostream>
#include <numeric>
#include <chrono>
#include <iomanip>
#include <locale>

int main() {
    std::cout.imbue(std::locale(""));

    using namespace std::chrono;
    using factor = microseconds;

    auto const size = 2000;

    std::vector<int *> allocs(size);

    auto start = high_resolution_clock::now();

    for (int i = 0; i < size; i++)
        allocs[i] = new int[size];

    auto stop = high_resolution_clock::now();
    auto alloc_time = duration_cast<factor>(stop - start).count();

    start = high_resolution_clock::now();

    for (int i = 0; i < size; i++)
        delete[] allocs[i];

    stop = high_resolution_clock::now();

    auto del_time = duration_cast<factor>(stop - start).count();

    std::cout << std::left << std::setw(20) << "alloc time: " << alloc_time << " uS\n";
    std::cout << std::left << std::setw(20) << "del time: " << del_time << " uS\n";
}

I also used VC++ on Windows instead of gcc on Linux. The result wasn't much different though: freeing the memory took substantially less time than allocating it did. Here are the results from three successive runs.

alloc time:         2,381 uS
del time:           1,429 uS

alloc time:         2,764 uS
del time:           1,592 uS

alloc time:         2,492 uS
del time:           1,442 uS

I'd warn, however, allocation and freeing is handled (primarily) by the standard library, so this could be different between one standard library and another (even when using the same compiler). I'd also note that it wouldn't surprise me if this were to change somewhat in multi-threaded code. Although it's not actually correct, there appear to be a few authors who are under the mis-apprehension that freeing in a multithreaded environment requires locking a heap for exclusive access. This can be avoided, but the means to do so isn't necessarily immediately obvious.

Memory allocation and deallocation in separate module

There is no memory leak in the code. It is impossible to make a memory leak with allocatable entities in Fortran. Only pointer can cause a memory leak.

With allocatable if something is going out of scope, it is deallocated automatically.

Your main array is a module variable so it is never going out of scope (it is save implicitly by Fortran 2008 rules). So if you don't deallocate it yourself, it will remain allocated and then deleted by the operating system on the program termination. But that is not normally considered to be a memory leak. It is not really harmful, because there is no way to make some forgotten copies of the array in memory.

The individual components my_size could go out of scope, when deallocating the large array dS_sn. In that case they are deallocated automatically by Fortran rules. You don't have to deallocate them one by one.

So you do not really have to do

Do k = 1 , Br_nn_mre

   Deallocate(dS_sn(k)%my_size)

End do

Doing just

Deallocate(dS_sn)

is perfectly correct.

---

Related Topics