Difference between revisions of "Memory Management"

From D Wiki
Jump to: navigation, search
(Finished migrating from dlang.org)
(Deprecation of scope as a type constraint has been resolved)
 
(39 intermediate revisions by 7 users not shown)
Line 1: Line 1:
Most non-trivial programs needs to allocate and free memory. Memory management techniques become more and more important as programs increase in complexity, size, and performance. D offers many options for managing memory.
+
Most non-trivial programs needs to allocate and free memory. Memory management techniques become more and more important as programs increase in complexity, size, and performance.
 +
 
 +
== Built-in types that allocate GC memory ==
 +
 
 +
D has built-in types that may be difficult to use without the GC: exceptions, strings, dynamic arrays, associative arrays, and delegate closures. See [http://dlang.org/builtin.html D Builtin Rationale].
 +
 
 +
== Options for managing memory ==
  
 
The three primary methods for allocating memory in D are:
 
The three primary methods for allocating memory in D are:
Line 9: Line 15:
 
The techniques for using them, as well as some advanced alternatives are:
 
The techniques for using them, as well as some advanced alternatives are:
  
== Strings (and Array) Copy-on-Write ==
+
=== Strings (and Array) Copy-on-Write ===
 
Consider the case of passing an array to a function, possibly modifying the contents of the array, and returning the modified array. As the contents of an array are accessed through a reference, a crucial issue is who owns the contents of the array? For example, a function to convert an array of characters to upper case:  
 
Consider the case of passing an array to a function, possibly modifying the contents of the array, and returning the modified array. As the contents of an array are accessed through a reference, a crucial issue is who owns the contents of the array? For example, a function to convert an array of characters to upper case:  
 
<syntaxhighlight lang="D">
 
<syntaxhighlight lang="D">
Line 60: Line 66:
 
Copy-on-write is the protocol implemented by array processing functions in the D Phobos runtime library.
 
Copy-on-write is the protocol implemented by array processing functions in the D Phobos runtime library.
  
== Real Time ==
+
=== Real Time ===
Real time programming means that a program must be able to guarantee a maximum latency, or time to complete an operation. With most memory allocation schemes, including malloc/free and garbage collection, the latency is theoretically not bound. The most reliable way to guarantee latency is to preallocate all data that will be needed by the time critical portion. If no calls to allocate memory are done, the GC will not run and so will not cause the maximum latency to be exceeded.  
+
Real-time programming means that a program must be able to guarantee a maximum latency, or time to complete an operation. With most memory allocation schemes, including malloc/free and garbage collection, the latency is theoretically not bound. The most reliable way to guarantee latency is to preallocate all data that will be needed by the time critical portion. If no calls to allocate memory are done, the GC will not run and so will not cause the maximum latency to be exceeded.
 +
 
 +
It is possible to create a real-time thread by [http://dlang.org/phobos/core_thread.html#.thread_detachThis detaching it from the runtime], marking the thread function <code>@nogc</code>, and ensuring the real-time thread does not hold any GC roots.  GC objects can still be used in the real-time thread, but they must be referenced from other threads to prevent them from being collected.
  
== Smooth Operation ==
+
=== Smooth Operation ===
 
Related to real time programming is the need for a program to operate smoothly, without arbitrary pauses while the garbage collector stops everything to run a collection. An example of such a program would be an interactive shooter type game. Having the game play pause erratically, while not fatal to the program, can be annoying to the user.
 
Related to real time programming is the need for a program to operate smoothly, without arbitrary pauses while the garbage collector stops everything to run a collection. An example of such a program would be an interactive shooter type game. Having the game play pause erratically, while not fatal to the program, can be annoying to the user.
  
Line 70: Line 78:
 
* Preallocate all data needed before the part of the code that needs to be smooth is run.
 
* Preallocate all data needed before the part of the code that needs to be smooth is run.
 
* Manually run a GC collection cycle at points in program execution where it is already paused. An example of such a place would be where the program has just displayed a prompt for user input and the user has not responded yet. This reduces the odds that a collection cycle will be needed during the smooth code.
 
* Manually run a GC collection cycle at points in program execution where it is already paused. An example of such a place would be where the program has just displayed a prompt for user input and the user has not responded yet. This reduces the odds that a collection cycle will be needed during the smooth code.
* Call std.gc.disable() before the smooth code is run, and std.gc.enable() afterwards. This will cause the GC to favor allocating more memory instead of running a collection pass.
+
* Call [http://dlang.org/phobos/core_memory.html#.GC.disable core.memory.GC.disable()] before the smooth code is run, and [http://dlang.org/phobos/core_memory.html#.GC.enable core.memory.GC.enable()] afterwards. This will cause the GC to favor allocating more memory instead of running a collection pass.
  
== Free Lists ==
+
=== Free Lists ===
 
Free lists are a great way to accelerate access to a frequently allocated and discarded type. The idea is simple - instead of deallocating an object when done with it, put it on a free list. When allocating, pull one off the free list first.  
 
Free lists are a great way to accelerate access to a frequently allocated and discarded type. The idea is simple - instead of deallocating an object when done with it, put it on a free list. When allocating, pull one off the free list first.  
  
Line 116: Line 124:
 
* It is not necessary to practice RAII with this, since if any objects are not passed to deallocate() when done, because of a thrown exception, they'll eventually get picked up by the GC anyway.
 
* It is not necessary to practice RAII with this, since if any objects are not passed to deallocate() when done, because of a thrown exception, they'll eventually get picked up by the GC anyway.
  
== Reference Counting ==
+
=== Reference Counting ===
 
The idea behind reference counting is to include a count field in the object. Increment it for each additional reference to it, and decrement it whenever a reference to it ceases. When the count hits 0, the object can be deleted.
 
The idea behind reference counting is to include a count field in the object. Increment it for each additional reference to it, and decrement it whenever a reference to it ceases. When the count hits 0, the object can be deleted.
  
D doesn't provide any automated support for reference counting, it will have to be done explicitly.
+
D does not provide automated support for reference counting.
 +
 
 +
[http://dlang.org/phobos/std_typecons.html#.RefCounted RefCounted] provides limited support for reference counting; not for class types. Unlike [http://en.cppreference.com/w/cpp/memory/shared_ptr C++ shared_ptr], it does not support multi-threading, weak pointers, or destructors. (See [http://forum.dlang.org/post/cakobtxrmvrpqhswmfsy@forum.dlang.org this forum thread].)
  
 
[[COM_Programming | Win32 COM programming]] uses the members AddRef() and Release() to maintain the reference counts.
 
[[COM_Programming | Win32 COM programming]] uses the members AddRef() and Release() to maintain the reference counts.
  
== Explicit Class Instance Allocation ==
+
=== Explicit Class Instance Allocation ===
'''Note:''' [http://dlang.org/class.html#allocators Class allocators] and [http://dlang.org/class.html#deallocators deallocators] are deprecated in D2.
+
'''Note:''' [http://dlang.org/class.html#allocators Class allocators] and [http://dlang.org/class.html#deallocators deallocators] are deprecated in D2, but the following example provides an alternative.
  
D provides a means of creating custom allocators and deallocators for class instances. Normally, these would be allocated on the garbage collected heap, and deallocated when the collector decides to run. For specialized purposes, this can be handled by creating NewDeclarations and DeleteDeclarations. For example, to allocate using the C runtime library's <code>malloc</code> and <code>free</code>:
+
D provides a means of creating custom allocators and deallocators for class instances. Normally, these would be allocated on the garbage collected heap, and deallocated when the collector decides to run. For specialized purposes, this can be handled by creating New Declarations (<code>heapAllocate</code> in the example below) and Delete Declarations(<code>heapDeallocate</code> in the example below). For example, to allocate using the C runtime library's <code>malloc</code> and <code>free</code>:
  
 
<syntaxhighlight lang="D">
 
<syntaxhighlight lang="D">
import std.c.stdlib;
+
import std.stdio;
import core.exception;
+
import core.memory : GC;
+
class TestClass
 
+
{
class Foo
+
    int x;
 +
   
 +
    this(int x)
 +
    {
 +
        writeln("TestClass's constructor called");
 +
        this.x = x;
 +
    }
 +
   
 +
    ~this()
 +
    {
 +
        writeln("TestClass's destructor called");
 +
    }
 +
}     
 +
 +
T heapAllocate(T, Args...) (Args args)
 
{
 
{
     new(size_t sz)
+
     import std.conv : emplace;
 +
    import core.stdc.stdlib : malloc;
 +
    import core.memory : GC;
 +
   
 +
    // get class size of class instance in bytes
 +
    auto size = __traits(classInstanceSize, T);
 +
   
 +
    // allocate memory for the object
 +
    auto memory = malloc(size)[0..size];
 +
    if(!memory)
 
     {
 
     {
         void* p;
+
         import core.exception : onOutOfMemoryError;
 +
        onOutOfMemoryError();
 +
    }                   
 +
   
 +
    writeln("Memory allocated");
  
        p = std.c.stdlib.malloc(sz);
+
    // notify garbage collector that it should scan this memory
 +
    GC.addRange(memory.ptr, size);
 +
   
 +
    // call T's constructor and emplace instance on
 +
    // newly allocated memory
 +
    return emplace!(T, Args)(memory, args);                                   
 +
}
 +
 +
void heapDeallocate(T)(T obj)
 +
{
 +
    import core.stdc.stdlib : free;
 +
    import core.memory : GC;
 +
   
 +
    // calls obj's destructor
 +
    destroy(obj);  
  
        if (!p)
+
    // garbage collector should no longer scan this memory
            throw new OutOfMemoryError();
+
    GC.removeRange(cast(void*)obj);
 
+
   
        GC.addRange(p, sz);
+
    // free memory occupied by object
        return p;
+
    free(cast(void*)obj);
     }
+
   
 
+
    writeln("Memory deallocated");
     delete(void* p)
+
}
 +
     
 +
void main()
 +
{
 +
     // allocate new instance of TestClass on the heap
 +
    auto test = heapAllocate!TestClass(42);
 +
     scope(exit)
 
     {
 
     {
         if (p)
+
         heapDeallocate(test);  
        {
 
            GC.removeRange(p);
 
            std.c.stdlib.free(p);
 
        }
 
 
     }
 
     }
 +
   
 +
    writefln("test.x = %s", test.x);
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
The critical features of new() are:
 
  
* new() does not have a return type specified, but it is defined to be void*. new() must return a void*.
+
Output:
* If new() cannot allocate memory, it must not return null, but must throw an exception.
+
<pre>
* The pointer returned from new() must be to memory aligned to the default alignment. This is 8 on win32 systems.
+
Memory allocated
* The size parameter is needed in case the allocator is called from a class derived from Foo and is a larger size than Foo.
+
TestClass's constructor called  
* A null is not returned if storage cannot be allocated. Instead, an exception is thrown. Which exception gets thrown is up to the programmer, in this case, OutOfMemory() is.
+
test.x = 42
* When scanning memory for root pointers into the garbage collected heap, the static data segment and the stack are scanned automatically. The C heap is not. Therefore, if Foo or any class derived from Foo using the allocator contains any references to data allocated by the garbage collector, the GC needs to be notified. This is done with the std.gc.addRange() method.
+
TestClass's destructor called
* No initialization of the memory is necessary, as code is automatically inserted after the call to new() to set the class instance members to their defaults and then the constructor (if any) is run.
+
Memory deallocated
 +
</pre>
  
The critical features of delete() are:
+
The critical features of <code>heapAllocate</code> are:
  
* The destructor (if any) has already been called on the argument p, so the data it points to should be assumed to be garbage.
+
* A null is not returned if storage cannot be allocated. Instead, an exception is thrown. Which exception gets thrown is up to the programmer, in this case, <code>onOutOfMemoryError()</code> is called to throw an <code>OutOfMemoryError</code> exception.
* The pointer p may be null.
+
* When scanning memory for root pointers into the garbage collected heap, the static data segment and the stack are scanned automatically. The C heap is not. Therefore, if Foo or any class derived from Foo using the allocator contains any references to data allocated by the garbage collector, the GC needs to be notified. This is done with the <code>std.gc.addRange()</code> method.
* If the GC was notified with std.gc.addRange(), a corresponding call to std.gc.removeRange() must happen in the deallocator.
 
* If there is a delete(), there should be a corresponding new().
 
  
If memory is allocated using class specific allocators and deallocators, careful coding practices must be followed to avoid memory leaks and dangling references. In the presence of exceptions, it is particularly important to practice RAII to prevent memory leaks.
+
The critical features of <code>heapDeallocate</code> are:
 +
 
 +
* The destructor (if any) is executed with a call to <code>destroy</code>, so the data <code>obj</code> points to should be assumed to be garbage.
 +
* If the GC was notified with <code>std.gc.addRange()</code>, a corresponding call to <code>std.gc.removeRange()</code> must happen in the deallocator.
 +
* If there is a <code>heapDeallocate</code>, there should be a corresponding <code>heapAllocate</code>.
 +
 
 +
If memory is allocated using this method, careful coding practices must be followed to avoid memory leaks and dangling references. In the presence of exceptions, it is particularly important to practice RAII to prevent memory leaks.
  
 
Custom allocators and deallocators can be done for structs and unions, too.
 
Custom allocators and deallocators can be done for structs and unions, too.
  
== Mark/Release ==
+
=== Mark/Release ===
 
Mark/Release is equivalent to a stack method of allocating and freeing memory. A ‘stack’ is created in memory. Objects are allocated by simply moving a pointer down the stack. Various points are ‘marked’, and then whole sections of memory are released simply by resetting the stack pointer back to a marked point.  
 
Mark/Release is equivalent to a stack method of allocating and freeing memory. A ‘stack’ is created in memory. Objects are allocated by simply moving a pointer down the stack. Various points are ‘marked’, and then whole sections of memory are released simply by resetting the stack pointer back to a marked point.  
  
 
<syntaxhighlight lang="D">
 
<syntaxhighlight lang="D">
import std.c.stdlib;
+
import std.stdio;
import core.exception;
 
import core.memory : GC;
 
  
class Foo
+
void[] buffer;
 +
size_t currentIndex;
 +
const size_t bufferSize = 100;
 +
 
 +
// Static constructor will be called before main to allocate the buffer memory
 +
static this()
 
{
 
{
     static void[] buffer;
+
     import core.stdc.stdlib : malloc;
     static int bufindex;
+
    import core.memory : GC;
     static const int bufsize = 100;
+
   
 
+
    writeln("Allocating buffer memory");
     static this()
+
      
 +
     auto p = malloc(bufferSize);
 +
   
 +
     if (p is null)
 
     {
 
     {
         void* p;
+
         import core.exception : onOutOfMemoryError;
         p = malloc(bufsize);
+
         onOutOfMemoryError();
 +
    }
 +
   
 +
    // notify garbage collector that it should scan this memory
 +
    GC.addRange(p, bufferSize);
  
        if (p is null)
+
    buffer = p[0 .. bufferSize];
            throw new OutOfMemoryError;
+
}
  
        GC.addRange(p, bufsize);
+
// Static destructor will be called after leaving main to deallocate buffer memory
        buffer = p[0 .. bufsize];
+
static ~this()
     }
+
{
 
+
     if (buffer.length)
    static ~this()
 
 
     {
 
     {
         if (buffer.length)
+
         import core.stdc.stdlib : free;
        {
+
        import core.memory : GC;
            GC.removeRange(buffer.ptr);
 
            free(buffer.ptr);
 
            buffer = null;
 
        }
 
    }
 
  
    new(size_t sz)
+
        // garbage collector should no longer scan this memory
    {
+
        GC.removeRange(buffer.ptr);
        void* p;
 
  
         p = &buffer[bufindex];
+
         free(buffer.ptr);
         bufindex += sz;
+
         buffer = null;
 +
    }
 +
   
 +
    writeln("Deallocated buffer memory");
 +
}
  
        if (bufindex > buffer.length)
+
// remember where to return to when memory is released
            throw new OutOfMemoryError;
+
size_t mark()
 +
{
 +
    writefln("Marked at %s", currentIndex);
 +
    return currentIndex;
 +
}
  
        return p;
+
// release the memory by returning to where it was marked
     }
+
void release(size_t markedIndex)
 +
{
 +
    currentIndex = markedIndex;
 +
      
 +
    writefln("Released memory back to %s", currentIndex);
 +
}
  
     delete(void* p)
+
// Reserve memory for the object, and instantiate it
 +
T create(T, Args...) (Args args)
 +
{
 +
    import std.conv : emplace;
 +
   
 +
    writefln("Reserving memory for %s", T.stringof);
 +
   
 +
    // get class size of class instance in bytes
 +
    auto size = __traits(classInstanceSize, T);
 +
   
 +
    // check if there's enough room in the buffer
 +
    auto newIndex = currentIndex + size;
 +
     if (newIndex >= buffer.length)
 
     {
 
     {
         assert(0);
+
         import core.exception : onOutOfMemoryError;
 +
        onOutOfMemoryError();
 
     }
 
     }
 +
   
 +
    // get location where new instance will be emplaced
 +
    auto memory = buffer[currentIndex..newIndex];
 +
   
 +
    // reserve the memory by advancing the index
 +
    currentIndex = newIndex;
 +
   
 +
    // call T's constructor and emplace instance on
 +
    // newly reserved memory
 +
    return emplace!(T, Args)(memory, args);
 +
}
  
     static int mark()
+
class TestClass
 +
{
 +
     int x;
 +
 +
    this(int x)  
 
     {
 
     {
         return bufindex;
+
         writeln("TestClass's constructor called");
 +
        this.x = x;
 
     }
 
     }
 
+
     static void release(int i)
+
     ~this()  
 
     {
 
     {
         bufindex = i;
+
         writeln("TestClass's destructor called");
 
     }
 
     }
}
+
}  
  
 
void main()
 
void main()
 
{
 
{
     int m  = Foo.mark();
+
     writeln("Entered main");
     Foo f1 = new Foo;           // allocate
+
   
     Foo f2 = new Foo;           // allocate
+
    // Remember where to return to when memory is released
 
+
    size_t markedIndex = mark();
     Foo.release(m);             // deallocate f1 and f2
+
     scope(exit)
 +
    {
 +
        release(markedIndex);  
 +
    }
 +
   
 +
    // Instantiate new class on the buffer
 +
     auto test = create!TestClass(42);
 +
    scope (exit)
 +
    {
 +
        // be sure to call its destructor
 +
        destroy(test);
 +
     }
 +
   
 +
    writefln("test.x = %s", test.x);
 +
   
 +
    writeln("Leaving main");
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
  
The allocation of buffer[] itself is added as a region to the GC, so there is no need for a separate call inside Foo.new() to do it.
+
Output:
 +
<pre>
 +
Allocating buffer memory
 +
Entered main
 +
Marked at 0
 +
Reserving memory for TestClass
 +
TestClass's constructor called
 +
test.x = 42
 +
Leaving main
 +
TestClass's destructor called
 +
Released memory back to 0
 +
Deallocated buffer memory
 +
</pre>
  
== RAII (Resource Acquisition Is Initialization) ==
+
The allocation of buffer[] itself is added as a region to the GC, so there is no need for a separate call when instantiating <code>TestClass</code>.
RAII techniques can be useful in avoiding memory leaks when using explicit allocators and deallocators. Adding the [http://dlang.org/attribute.html#scope scope attribute] to such classes can help.  
 
  
== Allocating Class Instances On The Stack ==
+
=== RAII (Resource Acquisition Is Initialization) ===
 +
RAII techniques can be useful in avoiding memory leaks when using explicit allocators and deallocators. Adding the [http://dlang.org/attribute.html#scope scope attribute] to class instances will allocate them on the stack, potentially avoiding such issues.
 +
 
 +
=== Allocating Class Instances On The Stack ===
 
Class instances are normally allocated on the garbage collected heap. However, if they:
 
Class instances are normally allocated on the garbage collected heap. However, if they:
  
Line 280: Line 413:
 
If the class has a destructor, then that destructor is guaranteed to be run when the class object goes out of scope, even if the scope is exited via an exception.
 
If the class has a destructor, then that destructor is guaranteed to be run when the class object goes out of scope, even if the scope is exited via an exception.
  
== Allocating Uninitialized Arrays On The Stack ==
+
=== Allocating Uninitialized Arrays On The Stack ===
 
Arrays are always initialized in D. So, the following declaration:
 
Arrays are always initialized in D. So, the following declaration:
  
Line 310: Line 443:
 
* Uninitialized data can be a source of bugs and trouble, even when used correctly. One design goal of D is to improve reliability and portability by eliminating sources of undefined behavior, and uninitialized data is one huge source of undefined, unportable, erratic and unpredictable behavior. Hence this idiom should only be used after other opportunities for speed optimization are exhausted and if benchmarking shows that it really does speed up the overall execution.
 
* Uninitialized data can be a source of bugs and trouble, even when used correctly. One design goal of D is to improve reliability and portability by eliminating sources of undefined behavior, and uninitialized data is one huge source of undefined, unportable, erratic and unpredictable behavior. Hence this idiom should only be used after other opportunities for speed optimization are exhausted and if benchmarking shows that it really does speed up the overall execution.
  
== Interrupt Service Routines ==
+
=== Interrupt Service Routines ===
 
When the garbage collector does a collection pass, it must pause all running threads in order to scan their stacks and register contents for references to GC allocated objects. If an ISR (Interrupt Service Routine) thread is paused, this can break the program.
 
When the garbage collector does a collection pass, it must pause all running threads in order to scan their stacks and register contents for references to GC allocated objects. If an ISR (Interrupt Service Routine) thread is paused, this can break the program.
  
Therefore, the ISR thread should not be paused. Threads created with the [http://dlang.org/phobos/core_thread.html core.thread] functions will be paused. But threads created with C's <code>_beginthread()</code> or equivalent won't be, the GC won't know they exist.
+
Therefore, the ISR thread should not be paused. Threads created with the [http://dlang.org/phobos/core_thread.html core.thread] functions will be paused but threads created with C's <code>_beginthread()</code> or equivalent won't be. The GC won't know they exist.
  
 
For this to work successfully:
 
For this to work successfully:
Line 319: Line 452:
 
* The ISR thread cannot allocate any memory using the GC. This means that the global <code>new</code> cannot be used. Nor can dynamic arrays be resized, nor can any elements be added to associative arrays. Any use of the D runtime library should be examined for any possibility of allocating GC memory - or better yet, the ISR should not call any D runtime library functions at all.
 
* The ISR thread cannot allocate any memory using the GC. This means that the global <code>new</code> cannot be used. Nor can dynamic arrays be resized, nor can any elements be added to associative arrays. Any use of the D runtime library should be examined for any possibility of allocating GC memory - or better yet, the ISR should not call any D runtime library functions at all.
 
* The ISR cannot hold the sole reference to any GC allocated memory, otherwise the GC may free the memory while the ISR is still using it. The solution is to have one of the paused threads hold a reference to it too, or store a reference to it in global data.
 
* The ISR cannot hold the sole reference to any GC allocated memory, otherwise the GC may free the memory while the ISR is still using it. The solution is to have one of the paused threads hold a reference to it too, or store a reference to it in global data.
 +
 +
== Writing GC free code ==
 +
 +
As of D release version 2.066, it is possible to disallows GC-heap allocation in code sections, by marking them with the '''@nogc''' attribute.
 +
 +
<syntaxhighlight lang="D">
 +
@nogc void foo(char[] a)
 +
{
 +
    auto p = new int;  // error, operator new allocates
 +
    a ~= 'c';          // error, appending to arrays allocates
 +
    bar();            // error, bar() may allocate
 +
}
 +
 +
void bar() { }
 +
</syntaxhighlight>
 +
 +
This allows the compiler to enforce that the GC heap is not going to be used.
 +
 +
Array concatenation, dynamic closures, calls to new operator and calls to functions not marked as '''@nogc''' are not allowed inside functions marked as '''@nogc'''.
 +
 +
Work is in progress to make the D standard library, Phobos, usable without any use of the garbage collector. Eventually Phobos will be fully '''@nogc''' compliant.
 +
 +
== Locating GC Allocations ==
 +
 +
As of release 2.066, the compiler switch ''-vgc'' provides a mechanism to locate GC heap allocations.  When enabled, the compiler will list locations in the source code where GC heap allocations are being performed.  The following example illustrates this.
 +
 +
<syntaxhighlight lang="D">
 +
// main.d
 +
module main;
 +
 +
class TestClass
 +
{ }
 +
 +
void main(string[] args)
 +
{
 +
    auto c = new TestClass();
 +
}
 +
</syntaxhighlight>
 +
 +
Compile with:
 +
<pre>
 +
dmd -vgc main.d
 +
</pre>
 +
 +
Output:
 +
<pre>
 +
test.d(9): vgc: 'new' causes GC allocation
 +
</pre>
 +
 +
Note, however, that this is ''not'' a compile-time error; the source code still compiles to an executable.
 +
 +
== Composable Memory Allocators ==
 +
 +
There is work in progress to add composable memory allocators as part of Phobos.
 +
 +
A peek at the current state of implementation is possible at:
 +
 +
https://github.com/D-Programming-Language/phobos/tree/master/std/experimental (Source code)
 +
 +
http://dlang.org/phobos/std_experimental_allocator.html (Documentation)
 +
 +
==External links==
 +
* [http://bitbucket.org/infognition/dstuff Some other GC related hacks]
 +
* [https://dlang.org/blog/2017/03/20/dont-fear-the-reaper/ Don’t Fear the Reaper - A Basic Introduction to the GC]
 +
* [https://dlang.org/blog/2017/06/16/life-in-the-fast-lane/ Life in the Fast Lane - Introduction to Avoiding the GC and GC Profiling]
 +
* [https://dlang.org/blog/2017/07/07/go-your-own-way-part-one-the-stack/ Go Your Own Way (Part One: The Stack)]
 +
* [https://dlang.org/blog/2017/09/25/go-your-own-way-part-two-the-heap/ Go Your Own Way (Part Two: The Heap)]
 +
* [https://jakobovrum.github.io/d/2016/01/20/memory-safety.html Memory Safety]

Latest revision as of 03:45, 16 May 2019

Most non-trivial programs needs to allocate and free memory. Memory management techniques become more and more important as programs increase in complexity, size, and performance.

Built-in types that allocate GC memory

D has built-in types that may be difficult to use without the GC: exceptions, strings, dynamic arrays, associative arrays, and delegate closures. See D Builtin Rationale.

Options for managing memory

The three primary methods for allocating memory in D are:

  • Static data, allocated in the default data segment.
  • Stack data, allocated on the CPU program stack.
  • Garbage collected data, allocated dynamically on the garbage collection heap.

The techniques for using them, as well as some advanced alternatives are:

Strings (and Array) Copy-on-Write

Consider the case of passing an array to a function, possibly modifying the contents of the array, and returning the modified array. As the contents of an array are accessed through a reference, a crucial issue is who owns the contents of the array? For example, a function to convert an array of characters to upper case:

char[] toupper(char[] s)
{
    int i;

    for (i = 0; i < s.length; i++)
    {
        char c = s[i];
        if ('a' <= c && c <= 'z')
            s[i] = cast(char)(c - ('a' - 'A'));
    }
    return s;
}

Note that the caller's version of s[] is also modified. This may be not at all what was intended, or worse, s[] may be a slice into a read-only section of memory.

If a copy of s[] was always made by toupper(), then that will unnecessarily consume time and memory for strings that are already all upper case.

The solution is to implement copy-on-write, which means that a copy is made only if the string needs to be modified. Some string processing languages do do this as the default behavior, but there is a huge cost to it. The string "abcdeF" will wind up being copied 5 times by the function. To get the maximum efficiency using the protocol, it'll have to be done explicitly in the code. Here's toupper() rewritten to implement copy-on-write in an efficient manner:

char[] toupper(char[] s)
{
    int changed;
    int i;

    changed = 0;
    for (i = 0; i < s.length; i++)
    {
        char c = s[i];
        if ('a' <= c && c <= 'z')
        {
            if (!changed)
            {
                char[] r = new char[s.length];
                r[] = s;
                s = r;
                changed = 1;
            }
            s[i] = cast(char)(c - ('a' - 'A'));
        }
    }
    return s;
}

Copy-on-write is the protocol implemented by array processing functions in the D Phobos runtime library.

Real Time

Real-time programming means that a program must be able to guarantee a maximum latency, or time to complete an operation. With most memory allocation schemes, including malloc/free and garbage collection, the latency is theoretically not bound. The most reliable way to guarantee latency is to preallocate all data that will be needed by the time critical portion. If no calls to allocate memory are done, the GC will not run and so will not cause the maximum latency to be exceeded.

It is possible to create a real-time thread by detaching it from the runtime, marking the thread function @nogc, and ensuring the real-time thread does not hold any GC roots. GC objects can still be used in the real-time thread, but they must be referenced from other threads to prevent them from being collected.

Smooth Operation

Related to real time programming is the need for a program to operate smoothly, without arbitrary pauses while the garbage collector stops everything to run a collection. An example of such a program would be an interactive shooter type game. Having the game play pause erratically, while not fatal to the program, can be annoying to the user.

There are several techniques to eliminate or mitigate the effect:

  • Preallocate all data needed before the part of the code that needs to be smooth is run.
  • Manually run a GC collection cycle at points in program execution where it is already paused. An example of such a place would be where the program has just displayed a prompt for user input and the user has not responded yet. This reduces the odds that a collection cycle will be needed during the smooth code.
  • Call core.memory.GC.disable() before the smooth code is run, and core.memory.GC.enable() afterwards. This will cause the GC to favor allocating more memory instead of running a collection pass.

Free Lists

Free lists are a great way to accelerate access to a frequently allocated and discarded type. The idea is simple - instead of deallocating an object when done with it, put it on a free list. When allocating, pull one off the free list first.

class Foo
{
    static Foo freelist;		// start of free list

    static Foo allocate()
    {   Foo f;

	if (freelist)
	{   f = freelist;
	    freelist = f.next;
	}
	else
	    f = new Foo();
	return f;
    }

    static void deallocate(Foo f)
    {
	f.next = freelist;
	freelist = f;
    }

    Foo next;		// for use by FooFreeList
    ...
}

void test()
{
    Foo f = Foo.allocate();
    ...
    Foo.deallocate(f);
}

Such free list approaches can be very high performance.

  • If used by multiple threads, the allocate() and deallocate() functions need to be synchronized.
  • The Foo constructor is not re-run by allocate() when allocating from the free list, so the allocator may need to reinitialize some of the members.
  • It is not necessary to practice RAII with this, since if any objects are not passed to deallocate() when done, because of a thrown exception, they'll eventually get picked up by the GC anyway.

Reference Counting

The idea behind reference counting is to include a count field in the object. Increment it for each additional reference to it, and decrement it whenever a reference to it ceases. When the count hits 0, the object can be deleted.

D does not provide automated support for reference counting.

RefCounted provides limited support for reference counting; not for class types. Unlike C++ shared_ptr, it does not support multi-threading, weak pointers, or destructors. (See this forum thread.)

Win32 COM programming uses the members AddRef() and Release() to maintain the reference counts.

Explicit Class Instance Allocation

Note: Class allocators and deallocators are deprecated in D2, but the following example provides an alternative.

D provides a means of creating custom allocators and deallocators for class instances. Normally, these would be allocated on the garbage collected heap, and deallocated when the collector decides to run. For specialized purposes, this can be handled by creating New Declarations (heapAllocate in the example below) and Delete Declarations(heapDeallocate in the example below). For example, to allocate using the C runtime library's malloc and free:

import std.stdio;
 
class TestClass 
{
    int x;
    
    this(int x) 
    {
        writeln("TestClass's constructor called");
        this.x = x;
    }
    
    ~this() 
    {
        writeln("TestClass's destructor called");
    }
}      
 
T heapAllocate(T, Args...) (Args args) 
{
    import std.conv : emplace;
    import core.stdc.stdlib : malloc;
    import core.memory : GC;
    
    // get class size of class instance in bytes
    auto size = __traits(classInstanceSize, T);
    
    // allocate memory for the object
    auto memory = malloc(size)[0..size];
    if(!memory)
    {
        import core.exception : onOutOfMemoryError;
        onOutOfMemoryError();
    }                    
    
    writeln("Memory allocated");

    // notify garbage collector that it should scan this memory
    GC.addRange(memory.ptr, size);
    
    // call T's constructor and emplace instance on
    // newly allocated memory
    return emplace!(T, Args)(memory, args);                                    
}
 
void heapDeallocate(T)(T obj) 
{
    import core.stdc.stdlib : free;
    import core.memory : GC;
    
    // calls obj's destructor
    destroy(obj); 

    // garbage collector should no longer scan this memory
    GC.removeRange(cast(void*)obj);
    
    // free memory occupied by object
    free(cast(void*)obj);
    
    writeln("Memory deallocated");
}
       
void main() 
{
    // allocate new instance of TestClass on the heap
    auto test = heapAllocate!TestClass(42);
    scope(exit)
    {
        heapDeallocate(test);    
    }
    
    writefln("test.x = %s", test.x);
}


Output:

Memory allocated 
TestClass's constructor called 
test.x = 42 
TestClass's destructor called 
Memory deallocated

The critical features of heapAllocate are:

  • A null is not returned if storage cannot be allocated. Instead, an exception is thrown. Which exception gets thrown is up to the programmer, in this case, onOutOfMemoryError() is called to throw an OutOfMemoryError exception.
  • When scanning memory for root pointers into the garbage collected heap, the static data segment and the stack are scanned automatically. The C heap is not. Therefore, if Foo or any class derived from Foo using the allocator contains any references to data allocated by the garbage collector, the GC needs to be notified. This is done with the std.gc.addRange() method.

The critical features of heapDeallocate are:

  • The destructor (if any) is executed with a call to destroy, so the data obj points to should be assumed to be garbage.
  • If the GC was notified with std.gc.addRange(), a corresponding call to std.gc.removeRange() must happen in the deallocator.
  • If there is a heapDeallocate, there should be a corresponding heapAllocate.

If memory is allocated using this method, careful coding practices must be followed to avoid memory leaks and dangling references. In the presence of exceptions, it is particularly important to practice RAII to prevent memory leaks.

Custom allocators and deallocators can be done for structs and unions, too.

Mark/Release

Mark/Release is equivalent to a stack method of allocating and freeing memory. A ‘stack’ is created in memory. Objects are allocated by simply moving a pointer down the stack. Various points are ‘marked’, and then whole sections of memory are released simply by resetting the stack pointer back to a marked point.

import std.stdio;

void[] buffer;
size_t currentIndex;
const size_t bufferSize = 100;

// Static constructor will be called before main to allocate the buffer memory
static this()
{
    import core.stdc.stdlib : malloc;
    import core.memory : GC;
    
    writeln("Allocating buffer memory");
    
    auto p = malloc(bufferSize);
    
    if (p is null)
    {
        import core.exception : onOutOfMemoryError;
        onOutOfMemoryError();
    }
    
    // notify garbage collector that it should scan this memory
    GC.addRange(p, bufferSize);

    buffer = p[0 .. bufferSize];
}

// Static destructor will be called after leaving main to deallocate buffer memory
static ~this()
{
    if (buffer.length)
    {
        import core.stdc.stdlib : free;
        import core.memory : GC;

        // garbage collector should no longer scan this memory
        GC.removeRange(buffer.ptr);

        free(buffer.ptr);
        buffer = null;
    }
    
    writeln("Deallocated buffer memory");
}

// remember where to return to when memory is released
size_t mark()
{
    writefln("Marked at %s", currentIndex);
    return currentIndex;
}

// release the memory by returning to where it was marked
void release(size_t markedIndex)
{
    currentIndex = markedIndex;
    
    writefln("Released memory back to %s", currentIndex);
}

// Reserve memory for the object, and instantiate it
T create(T, Args...) (Args args) 
{
    import std.conv : emplace;
    
    writefln("Reserving memory for %s", T.stringof);
    
    // get class size of class instance in bytes
    auto size = __traits(classInstanceSize, T);
    
    // check if there's enough room in the buffer
    auto newIndex = currentIndex + size;
    if (newIndex >= buffer.length)
    {
        import core.exception : onOutOfMemoryError;
        onOutOfMemoryError();
    }
    
    // get location where new instance will be emplaced
    auto memory = buffer[currentIndex..newIndex];
    
    // reserve the memory by advancing the index
    currentIndex = newIndex;
    
    // call T's constructor and emplace instance on
    // newly reserved memory
    return emplace!(T, Args)(memory, args);
}

class TestClass 
{
    int x;
 
    this(int x) 
    {
        writeln("TestClass's constructor called");
        this.x = x;
    }
 
    ~this() 
    {
        writeln("TestClass's destructor called");
    }
} 

void main()
{
    writeln("Entered main");
    
    // Remember where to return to when memory is released
    size_t markedIndex = mark();
    scope(exit)
    {
        release(markedIndex);   
    }
    
    // Instantiate new class on the buffer
    auto test = create!TestClass(42);
    scope (exit)
    {
        // be sure to call its destructor
        destroy(test);
    }
    
    writefln("test.x = %s", test.x);
    
    writeln("Leaving main");
}

Output:

Allocating buffer memory 
Entered main 
Marked at 0 
Reserving memory for TestClass 
TestClass's constructor called 
test.x = 42 
Leaving main 
TestClass's destructor called 
Released memory back to 0 
Deallocated buffer memory

The allocation of buffer[] itself is added as a region to the GC, so there is no need for a separate call when instantiating TestClass.

RAII (Resource Acquisition Is Initialization)

RAII techniques can be useful in avoiding memory leaks when using explicit allocators and deallocators. Adding the scope attribute to class instances will allocate them on the stack, potentially avoiding such issues.

Allocating Class Instances On The Stack

Class instances are normally allocated on the garbage collected heap. However, if they:

  • are allocated as local symbols in a function and
  • are allocated using new and
  • use new with no arguments (constructor arguments are allowed) and
  • have the scope storage class

then they are allocated on the stack. This is more efficient than doing an allocate/free cycle on the instance. But be careful that any reference to the object does not survive the return of the function.

class C { ... }

scope c = new C();	// c is allocated on the stack
scope c2 = new C(5);    // allocated on stack
scope c3 = new(5) C();  // allocated by a custom allocator

If the class has a destructor, then that destructor is guaranteed to be run when the class object goes out of scope, even if the scope is exited via an exception.

Allocating Uninitialized Arrays On The Stack

Arrays are always initialized in D. So, the following declaration:

void foo()
{   byte[1024] buffer;

    fillBuffer(buffer);
    ...
}

will not be as fast as it might be since the buffer[] contents are always initialized. If careful profiling of the program shows that this initialization is a speed problem, it can be eliminated using a VoidInitializer:


void foo()
{   byte[1024] buffer = void;

    fillBuffer(buffer);
    ...
}

Uninitialized data on the stack comes with some caveats that need to be carefully evaluated before using:

  • The uninitialized data that is on the stack will get scanned by the garbage collector looking for any references to allocated memory. Since the uninitialized data consists of old D stack frames, it is highly likely that some of that garbage will look like references into the GC heap, and the GC memory will not get freed. This problem really does happen, and can be pretty frustrating to track down.
  • It's possible for a function to pass out of it a reference to data on that function's stack frame. By then allocating a new stack frame over the old data, and not initializing, the reference to the old data may still appear to be valid. The program will then behave erratically. Initializing all data on the stack frame will greatly increase the probability of forcing that bug into the open in a repeatable manner.
  • Uninitialized data can be a source of bugs and trouble, even when used correctly. One design goal of D is to improve reliability and portability by eliminating sources of undefined behavior, and uninitialized data is one huge source of undefined, unportable, erratic and unpredictable behavior. Hence this idiom should only be used after other opportunities for speed optimization are exhausted and if benchmarking shows that it really does speed up the overall execution.

Interrupt Service Routines

When the garbage collector does a collection pass, it must pause all running threads in order to scan their stacks and register contents for references to GC allocated objects. If an ISR (Interrupt Service Routine) thread is paused, this can break the program.

Therefore, the ISR thread should not be paused. Threads created with the core.thread functions will be paused but threads created with C's _beginthread() or equivalent won't be. The GC won't know they exist.

For this to work successfully:

  • The ISR thread cannot allocate any memory using the GC. This means that the global new cannot be used. Nor can dynamic arrays be resized, nor can any elements be added to associative arrays. Any use of the D runtime library should be examined for any possibility of allocating GC memory - or better yet, the ISR should not call any D runtime library functions at all.
  • The ISR cannot hold the sole reference to any GC allocated memory, otherwise the GC may free the memory while the ISR is still using it. The solution is to have one of the paused threads hold a reference to it too, or store a reference to it in global data.

Writing GC free code

As of D release version 2.066, it is possible to disallows GC-heap allocation in code sections, by marking them with the @nogc attribute.

@nogc void foo(char[] a)
{
    auto p = new int;  // error, operator new allocates
    a ~= 'c';          // error, appending to arrays allocates
    bar();             // error, bar() may allocate
}

void bar() { }

This allows the compiler to enforce that the GC heap is not going to be used.

Array concatenation, dynamic closures, calls to new operator and calls to functions not marked as @nogc are not allowed inside functions marked as @nogc.

Work is in progress to make the D standard library, Phobos, usable without any use of the garbage collector. Eventually Phobos will be fully @nogc compliant.

Locating GC Allocations

As of release 2.066, the compiler switch -vgc provides a mechanism to locate GC heap allocations. When enabled, the compiler will list locations in the source code where GC heap allocations are being performed. The following example illustrates this.

// main.d
module main;

class TestClass
{ }

void main(string[] args)
{
    auto c = new TestClass();
}

Compile with:

dmd -vgc main.d

Output:

test.d(9): vgc: 'new' causes GC allocation

Note, however, that this is not a compile-time error; the source code still compiles to an executable.

Composable Memory Allocators

There is work in progress to add composable memory allocators as part of Phobos.

A peek at the current state of implementation is possible at:

https://github.com/D-Programming-Language/phobos/tree/master/std/experimental (Source code)

http://dlang.org/phobos/std_experimental_allocator.html (Documentation)

External links