{"id":1104,"date":"2017-09-25T14:11:07","date_gmt":"2017-09-25T14:11:07","guid":{"rendered":"http:\/\/dlang.org\/blog\/?p=1104"},"modified":"2021-10-08T11:07:43","modified_gmt":"2021-10-08T11:07:43","slug":"go-your-own-way-part-two-the-heap","status":"publish","type":"post","link":"https:\/\/dlang.org\/blog\/2017\/09\/25\/go-your-own-way-part-two-the-heap\/","title":{"rendered":"Go Your Own Way (Part Two: The Heap)"},"content":{"rendered":"

\"\"This post is part of an ongoing series<\/a> on garbage collection in the D Programming Language, and the second of two regarding the allocation of memory outside of the GC. Part One<\/a> discusses stack allocation. Here, we\u2019ll look at allocating memory from the non-GC heap.<\/p>\n

Although this is only my fourth post in the series, it\u2019s the third in which I talk about ways to avoid<\/em> the GC. Lest anyone jump to the wrong conclusion, that fact does not signify an intent to warn programmers away from the D garbage collector. Quite the contrary. Knowing how and when to avoid the GC is integral to understanding how to efficiently embrace it.<\/p>\n

To hammer home a repeated point, efficient garbage collection requires reducing stress on the GC. As highlighted in the first<\/a> and subsequent posts in this series, that doesn\u2019t necessarily mean avoiding it completely. It means being judicious in how often and how much GC memory is allocated. Fewer GC allocations means fewer opportunities for a collection to trigger. Less total memory allocated from the GC heap means less total memory to scan.<\/p>\n

It\u2019s impossible to make any accurate, generalized statement about what sort of applications may or may not feel an impact from the GC; such is highly application specific. What can be said is that it may not be necessary for many applications to temporarily avoid or disable the GC, but when it is, it\u2019s important to know how. Allocating from the stack is an obvious approach, but D also allows allocating from the non-GC heap.<\/p>\n

The ubiquitous C<\/h3>\n

For better or worse, C is everywhere. Any software written today, no matter the source language, is probably interacting with a C API at some level. Despite the C specification defining no standard ABI, its platform-specific quirks and differences are understood well enough that most languages know how to interface with it. D is no exception. In fact, all D programs have access to the C standard library by default.<\/p>\n

The core.stdc<\/code> package<\/a>, part of DRuntime<\/a>, is a collection of D modules translated from C standard library headers. When a D executable is linked, the C standard library is linked along with it. All that need be done to gain access is to import the appropriate modules.<\/p>\n

import core.stdc.stdio : puts;\nvoid main() \n{\n    puts(\"Hello C standard library.\");\n}<\/pre>\n
Some who are new to D may be laboring under a misunderstanding that functions which call into C require an extern(C)<\/code> annotation, or, after Walter\u2019s Bright\u2019s recent \u2018D as a Better C<\/a>\u2019 article, must be compiled with -betterC<\/code> on the command line. Neither is true. Normal D functions can call into C without any special effort beyond the presence of an extern(C)<\/code> declaration of the function being called. In the snippet above, the declaration of puts<\/code><\/a> is in the core.stdc.stdio<\/code> module, and that\u2019s all we need to call it.<\/p>\n
malloc<\/code> and friends<\/h4>\n
Given that we have access to C\u2019s standard library in D, we therefore have access to the functions malloc<\/code>, calloc<\/code>, realloc<\/code> and free<\/code>. All of these can be made available by importing core.stdc.stdlib<\/code>. And thanks to D\u2019s slicing magic, using these functions as the foundation of a non-GC memory management strategy is a breeze.<\/p>\n
import core.stdc.stdlib;\nvoid main() \n{\n    enum totalInts = 10;\n    \n    \/\/ Allocate memory for 10 ints\n    int* intPtr = cast(int*)malloc(int.sizeof * totalInts);\n\n    \/\/ assert(0) (and assert(false)) will always remain in the binary,\n    \/\/ even when asserts are disabled, which makes it nice for handling\n    \/\/ malloc failures    \n    if(!intPtr) assert(0, \"Out of memory!\");\n\n    \/\/ Free when the function exits. Not necessary for this example, but\n    \/\/ a potentially useful strategy for temporary allocations in functions \n    \/\/ other than main.\n    scope(exit) free(intPtr);\n\n    \/\/ Slice the D pointer to get a more manageable length\/pointer pair.\n    int[] intArray = intPtr[0 .. totalInts];\n}<\/pre>\n
Not only does this bypass the GC, it also bypasses D\u2019s default initialization. A GC-allocated array of type T<\/code> would have all of its elements initialized to T.init<\/code>, which is 0<\/code> for int<\/code>. If mimicking D\u2019s default initialization is the desired behavior, more work needs to be done. In this example, we could replace malloc<\/code> with calloc<\/code> for the same effect, but that would only be correct for integrals. float.init<\/code>, for example, is float.nan<\/code> rather than 0.0f<\/code>. We\u2019ll come back to this later in the article.<\/p>\n
Of course, it would be more idiomatic to wrap both malloc<\/code> and free<\/code> and work with slices of memory. A minimal example:<\/p>\n
import core.stdc.stdlib;\n\n\/\/ Allocate a block of untyped bytes that can be managed\n\/\/ as a slice.\nvoid[] allocate(size_t size)\n{\n    \/\/ malloc(0) is implementation defined (might return null \n    \/\/ or an address), but is almost certainly not what we want.\n    assert(size != 0);\n\n    void* ptr = malloc(size);\n    if(!ptr) assert(0, \"Out of memory!\");\n    \n    \/\/ Return a slice of the pointer so that the address is coupled\n    \/\/ with the size of the memory block.\n    return ptr[0 .. size];\n}\n\nT[] allocArray(T)(size_t count) \n{ \n    \/\/ Make sure to account for the size of the\n    \/\/ array element type!\n    return cast(T[])allocate(T.sizeof * count); \n}\n\n\/\/ Two versions of deallocate for convenience\nvoid deallocate(void* ptr)\n{   \n    \/\/ free handles null pointers fine.\n    free(ptr);\n}\n\nvoid deallocate(void[] mem) \n{ \n    deallocate(mem.ptr); \n}\n\nvoid main() {\n    import std.stdio : writeln;\n    int[] ints = allocArray!int(10);\n    scope(exit) deallocate(ints);\n    \n    foreach(i; 0 .. 10) {\n        ints[i] = i;\n    }\n\n    foreach(i; ints[]) {\n        writeln(i);\n    }\n}<\/pre>\n
allocate<\/code> returns void[]<\/code> rather than void*<\/code> because it carries with it the number of allocated bytes in its length<\/code> property. In this case, since we\u2019re allocating an array, we could instead rewrite allocArray<\/code> to slice the returned pointer immediately, but anyone calling allocate<\/code> directly would still have to take into account the size of the memory. The disassociation between arrays and their length in C is a major source of bugs<\/a>, so the sooner we can associate them the better. Toss in some templates for calloc<\/code> and realloc<\/code> and you\u2019ve got the foundation of a memory manager based on the C heap.<\/p>\n
On a side note, the preceding three snippets (yes, even the one with the allocArray<\/code> template) work with and without -betterC<\/code>. But from here on out, we\u2019ll restrict ourselves to features in normal D code.<\/p>\n
Avoid leaking like a sieve<\/h4>\n
When working directly with slices of memory allocated outside of the GC heap, be careful about appending, concatenating, and resizing. By default, the append (~=<\/code>) and concatenate (~<\/code>) operators on built-in dynamic arrays and slices will allocate from the GC heap. Concatenation will always allocate a new memory block for the combined string. Normally, the append operator will allocate to expand the backing memory only when it needs to. As the following example demonstrates, it always needs to when it\u2019s given a slice of non-GC memory.<\/p>\n
import core.stdc.stdlib : malloc;\nimport std.stdio : writeln;\n\nvoid main()\n{\n    int[] ints = (cast(int*)malloc(int.sizeof * 10))[0 .. 10];\n    writeln(\"Capacity: \", ints.capacity);\n\n    \/\/ Save the array pointer for comparison\n    int* ptr = ints.ptr;\n    ints ~= 22;\n    writeln(ptr == ints.ptr);\n}<\/pre>\n
This should print the following:<\/p>\n
Capacity: 0\nfalse\n<\/pre>\n
A capacity of 0<\/code> on a slice indicates that the next append will trigger an allocation. Arrays allocated from the GC heap normally have space for extra elements beyond what was requested, meaning some appending can occur without triggering a new allocation. It\u2019s more like a property of the memory backing the array rather than of the array itself. Memory allocated from the GC does some internal bookkeeping to keep track of how many elements the memory block can hold so that it knows at any given time if a new allocation is needed. Here, because the memory for ints<\/code> was not allocated by the GC, none of that bookkeeping is being done by the runtime on the existing memory block, so it must<\/em> allocate on the next append (see Steven Schveighoffer\u2019s \u2019D Slices<\/a> article for more info).<\/p>\n
This isn\u2019t necessarily a bad thing when it\u2019s the desired behavior, but anyone who\u2019s not prepared for it can easily run into ballooning memory usage thanks to leaks from malloc<\/code>ed memory never being deallocated. Consider these two functions:<\/p>\n
void leaker(ref int[] arr)\n{\n    ...\n    arr ~= 10;\n    ...\n}\n\nvoid cleaner(int[] arr)\n{\n    ...\n    arr ~= 10;\n    ...\n}<\/pre>\n
Although arrays are reference types, meaning that modifying existing elements of an array argument inside a function will modify the elements in the original array, they are passed by value as function parameters. Any activity that modifies the structure of an array argument, i.e. its length<\/code> and ptr<\/code> properties, only affects the local variable inside the function. The original will remain unchanged unless the array is passed by reference.<\/p>\n
So if an array backed by the C heap is passed to leaker<\/code>, the append will cause a new array to be allocated from the GC heap. Worse, if free<\/code> is subsequently called on the ptr<\/code> property of the original array, which now points into the GC heap rather than the C heap, we\u2019re in undefined behavior territory. cleaner<\/code>, on the other hand, is fine. Any array passed into it will remain unchanged. Internally, the GC will allocate, but the ptr<\/code> property of the original array still points to the original memory block.<\/p>\n
As long as the original array isn\u2019t overwritten or allowed to go out of scope, this is a non-issue. Functions like cleaner<\/code> can do what they want with their local slice and things will be fine externally. Otherwise, if the original array is to be discarded, you can prevent all of this by tagging functions that you control with @nogc<\/code>. Where that\u2019s either not possible or not desirable, then either a copy of the pointer to the original malloc<\/code>ed memory must be kept and free<\/code>ed at some point after the reallocation takes place, custom appending and concatenation needs to be implemented, or the allocation strategy needs to be reevaluated.<\/p>\n
Note that std.container.array<\/code><\/a> contains an Array<\/code> type that does not rely on the GC and may be preferable over managing all of this manually.<\/p>\n
Other APIs<\/h4>\n
The C standard library isn\u2019t the only game in town for heap allocations. A number of alternative malloc<\/code> implementations exist and any of those can be used instead. This requires manually compiling the source and linking with the resultant objects, but that\u2019s not an onerous task. Heap memory can also be allocated through system APIs, like the Win32 HeapAlloc<\/a> function on Windows (available by importing core.sys.windows.windows<\/code><\/a>). As long as there\u2019s a way to get a pointer to a block of heap memory, it can be sliced and manipulated in a D program in place of a block of GC memory.<\/p>\n
Aggregate types<\/h3>\n
If we only had to worry about allocating arrays in D, then we could jump straight on to the next section. However, we also need to concern ourselves with struct<\/code> and class<\/code> types. For this discussion, however, we will only focus on the former. The next couple of posts in the series will focus exclusively on classes.<\/p>\n
Allocating an array of struct<\/code> types, or a single instance of one, is often no different than when the type is int<\/code>.<\/p>\n
struct Point { int x, y; }\nPoint* onePoint = cast(Point*)malloc(Point.sizeof);\nPoint* tenPoints = cast(Point*)malloc(Point.sizeof * 10);<\/pre>\n
Where things break down is when contructors enter the mix. malloc<\/code> and friends know nothing about constructing D object instances. Thankfully, Phobos provides us with a function template that does.<\/p>\n
std.conv.emplace<\/code><\/a> can take either a pointer to typed memory or an untyped void[]<\/code>, along with an optional number of arguments, and return a pointer to a single, fully initialized and constructed instance of that type. This example shows how to do so using both malloc<\/code> and the allocate<\/code> function template from above:<\/p>\n
struct Vertex4f \n{ \n    float x, y, z, w; \n    this(float x, float y, float z, float w = 1.0f)\n    {\n        this.x = x;\n        this.y = y;\n        this.z = z;\n        this.w = w;\n    }\n}\n\nvoid main()\n{\n    import core.stdc.stdlib : malloc;\n    import std.conv : emplace;\n    import std.stdio : writeln;\n    \n    Vertex4f* temp1 = cast(Vertex4f*)malloc(Vertex4f.sizeof);\n    Vertex4f* vert1 = emplace(temp1, 4.0f, 3.0f, 2.0f); \n    writeln(*vert1);\n\n    void[] temp2 = allocate(Vertex4f.sizeof);\n    Vertex4f* vert2 = emplace!Vertex4f(temp2, 10.0f, 9.0f, 8.0f);\n    writeln(*vert2);\n}<\/pre>\n
Another feature of emplace<\/code> is that it also handles default initialization. Consider that struct<\/code> types in D need not implement constructors. Here\u2019s what happens when we change the implementation of Vertex4f<\/code> to remove the constructor:<\/p>\n
struct Vertex4f \n{\n    \/\/ x, y, z are default inited to float.nan\n    float x, y, z;\n\n    \/\/ w is default inited to 1.0f\n    float w = 1.0f;\n}\n\nvoid main()\n{\n    import core.stdc.stdlib : malloc;\n    import std.conv : emplace;\n    import std.stdio : writeln;\n\n    Vertex4f vert1, vert2 = Vertex4f(4.0f, 3.0f, 2.0f);\n    writeln(vert1);\n    writeln(vert2);    \n    \n    auto vert3 = emplace!Vertex4f(allocate(Vertex4f.sizeof));\n    auto vert4 = emplace!Vertex4f(allocate(Vertex4f.sizeof), 4.0f, 3.0f, 2.0f);\n    writeln(*vert3);\n    writeln(*vert4);\n}<\/pre>\n
This prints the following:<\/p>\n
Vertex4f(nan, nan, nan, 1)\nVertex4f(4, 3, 2, 1)\nVertex4f(nan, nan, nan, 1)\nVertex4f(4, 3, 2, 1)<\/pre>\n
So emplace<\/code> allows heap-allocated struct instances to be initialized in the same manner as stack allocated struct instances, with or without a constructor. It also works with the built-in types like int<\/code> and float<\/code>. Just always remember that emplace<\/code> is intended to initialize and construct a single instance<\/em>, not an array of instances.<\/p>\n
If the aggregate type has a destructor, it should be invoked before its memory is deallocated. This can be achieved with the destroy<\/code> function<\/a> (always available through the implicit import of std.object<\/code>).<\/p>\n
std.experimental.allocator<\/h3>\n
The entirety of the text above describes the fundamental building blocks of a custom memory manager. For many use cases, it may be sufficient to forego cobbling something together by hand and instead take advantage of the D standard library\u2019s std.experimental.allocator<\/code><\/a> package. This is a high-level API that makes use of low-level techniques like those described above, along with Design by Introspection<\/a>, to facilitate the assembly of different types of allocators that know how to allocate, initialize, and construct arrays and type instances. Allocators like Mallocator<\/code><\/a> and GCAllocator<\/code><\/a> can be used to grab chunks of memory directly, or combined with other building blocks<\/a> for specialized behavior. See the emsi-containers library<\/a> for a real-world example.<\/p>\n
Keeping the GC informed<\/h3>\n
Given that it\u2019s rarely recommended to disable the GC entirely, most D programs allocating outside the GC heap will likely also be using memory from the GC heap in the same program. In order for the GC to properly do its job, it needs to be informed of any non-GC memory that contains, or may potentially contain, references to memory from the GC heap. For example, a linked list whose nodes are allocated with malloc<\/code> might contain references to classes allocated with new<\/code>.<\/p>\n
The GC can be given the news via GC.addRange<\/code>.<\/p>\n
import core.memory;\nenum size = int.sizeof * 10;\nvoid* p1 = malloc(size);\nGC.addRange(p1, size);\n\nvoid[] p2 = allocate!int(10);\nGC.addRange(p2.ptr, p2.length);<\/pre>\n
When the memory block is no longer needed, the corresponding GC.removeRange<\/code> can be called to prevent it from being scanned. This does not deallocate<\/strong> the memory block. That will need to be done manually via free<\/code> or whatever allocator interface was used to allocate it. Be sure to read the documentation<\/a> before using either function.<\/p>\n
Given that one of the goals of allocating from outside the GC heap is to reduce the amount of memory the GC must scan, this may seem self-defeating. That\u2019s the wrong way to look at it. If non-GC memory is going to hold references to GC memory, then it\u2019s vital to let the GC know about it. Not doing so can cause the GC to free up memory to which a reference still exists. addRange<\/code> is a tool specifically designed for that situation. If it can be guaranteed that no GC-memory references live inside a non-GC memory block, such as a malloc<\/code>ed array of vertices, then addRange<\/code> need not be called on that memory block.<\/p>\n
A word of warning<\/h4>\n
Be careful when passing typed pointers to addRange<\/code>. Because the function was implemented with the C like approach of taking a pointer to a block of memory and the number of bytes it contains, there is an opportunity for error.<\/p>\n
struct Item { SomeClass foo; }\nauto items = (cast(Item*)malloc(Item.sizeof * 10))[0 .. 10];\nGC.addRange(items.ptr, items.length);<\/pre>\n
With this, the GC would be scanning a block of memory exactly ten bytes in size. The length<\/code> property returns the number of elements the slice refers to. Only when the type is void<\/code> (or the element type is one-byte long, like byte<\/code> and ubyte<\/code>) does it equate to the size of the memory block the slice refers to. The correct thing to do here is:<\/p>\n
GC.addRange(items.ptr, items.length * Item.sizeof);<\/pre>\n
However, until DRuntime is updated with an alternative, it may be best to implement a wrapper that takes a void[]<\/code> parameter.<\/p>\n
void addRange(void[] mem) \n{\n    import core.memory;\n    GC.addRange(mem.ptr, mem.length);\n}<\/pre>\n
Then calling addRange(items)<\/code> will do the correct thing. The implicit conversion of the slice to void[]<\/code> in the function call will mean that mem.length<\/code> is the same as items.length * Item.sizeof<\/code>.<\/p>\n
The GC series marches on<\/h3>\n
This post has covered the very basics of using the non-GC heap in D programs. One glaring omission, in addition to class<\/code> types, is what to do about destructors. I\u2019m saving that topic for the post about classes, where it is highly relevant. That\u2019s the next scheduled post in the GC series. Stay tuned!<\/p>\n
Thanks to Walter Bright, Guillaume Piolat, Adam D. Ruppe, and Steven Schveighoffer for their valuable feedback on a draft of this article.<\/p>\n","protected":false},"excerpt":{"rendered":"
This post is part of an ongoing series on garbage collection in the D Programming Language, and the second of two regarding the allocation of memory outside of the GC. Part One discusses stack allocation. Here, we\u2019ll look at allocating memory from the non-GC heap.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[26,24,20],"tags":[],"_links":{"self":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/1104"}],"collection":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/comments?post=1104"}],"version-history":[{"count":36,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/1104\/revisions"}],"predecessor-version":[{"id":2787,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/1104\/revisions\/2787"}],"wp:attachment":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/media?parent=1104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/categories?post=1104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/tags?post=1104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}