What is the memory layout of dynamic arrays?

Question

auto  array =  new Foo[100];

My first question is how does this look internally? What I assume:

If Foo is a class, then array is a pointer to an array of pointer of foo objects vector<Foo*> v //c++

If Foo is a struct , then array is a pointer to an array of Foo objects. vector<Foo> v //c++

Is a dynamic array in D contiguous in memory like in C++?

Answer 1

A D dynamic array looks like this:

struct Array(T) {
     size_t length;
     T* ptr;
}

Doing new T[size] is basically running this:

Array!T array;
array.length = size;
array.ptr = GC.malloc(size * T.sizeof);

So, yes, the memory of the elements is contiguous like in C++. The rest of your question gets into the specifics of what T is, and you're right about what you thought:

If Foo is a class, that means any reference to Foo works like a pointer, so it is like Foo* array in C++ - T.sizeof when T is a class is always equal to void*.sizeof*, the objects work by reference. If it is a struct, it is all in-place, like vector<Foo> in C++.

Fun fact with structs btw: they aren't necessarily packed in the array due to alignment issues. Consider the following:

struct Foo {
   ushort s;
   uint i;
}

Foo.sizeof you might expect to be 6... but it is actually 8 because the uint will be aligned on a 4-byte boundary, causing two bytes of padding after s. If you add align(1) to the uint field, you'll override this, putting i right next to s in memory. However, since we're talking about arrays, you'll want to node that Foo[] elements would /still/ have its own alignment... Foo.sizeof == 8 still so a Foo[2] has a size of 16. The inner align(1) just moved the padding to the end of the struct, it didn't remove it entirely for the cases of arrays.

If you want a Foo[] that is packed with no padding between elements, you'd also want to add align(1) to the outside of the struct: align(1) struct Foo { /* ... */ }. Then Foo.sizeof == 6 and there's no padding in the array.

• If you want to get the size of the object itself, for example if you're writing your own version of new MyClass, there's a way to do that too: __traits(classInstanceSize, Foo). http://dlang.org/traits.html#classInstanceSize But D does classes by reference because it is easier to keep sanity in the presence of inheritance.

Anyway, I probably went into more detail than you actually wanted/needed but in short, you're right about what happens with Foo and a D dynamic array is laid out similarly to a C++ vector. Biggest difference between the two is a C++ vector can be copied with the assign operator, it is a value type. A D array will always just be sliced - the length and pointer (remember the first layout in this post) is copied, but the contents are not. You need to explicitly copy the data in D with array.dup or foo[] = bar[].

Further reading:

• http://dlang.org/arrays.html ("Array Operations" is the foo[] = bar[] stuff, "Array Properties" has dup, and much more in there)
• http://dlang.org/abi.html (see the "Arrays" header - this describes the length/ptr layout)

• http://dlang.org/d-array-article.html (talks about the array itself vs the slice you manipulate and explains some internals about dynamic array memory management)

• http://dlang.org/struct.html (you can find info about the struct alignment stuff there)

• http://wiki.dlang.org/Books

Answer 2

array itself is a struct with a size_t length and a Foo* ptr

This is described in http://dlang.org/abi.html (look for arrays)

And yes the storage is in contiguous memory.