Accessing overallocated memory in C++

Question

I have a huge tree that can take up to several gigabytes. The node structure is as below. You'll notice that I made the last member an array of size 1. The reason for this is that I can over-allocate a Node with flexible sizes. Similar to what C natively supports as a flexible array member. I could use std::unique_ptr<T[]> or std::vector<T> instead, but the problem is that then there is double dynamic allocation, double indirection, and extra cache misses per each tree node. In my last test, this made my program take about 50% more time, which is simply not acceptable for my application.

template<typename T>
class Node
{
public:
  Node<T> *parent;
  Node<T> *child;

  /* ... */

  T &operator[](int);
private;
  int size;
  T array[1];
};

The simplest way to implement operator[] would be this.

template<typename T>
T &Node::operator[](int n)
{
  return array[n];
}

It should work fine in most sane C++ implementations. But as the C++ standard allows insane implementations doing array bounds checking, as fas as I know this is technically invoking undefined behaviour. Then can I do this?

template<typename T>
T &Node::operator[](int n)
{
  return (&array[0])[n];
}

I'm a little confused here. The [] operator for primitive types is just a syntactic sugar to *. Thus (&array[0])[n] is equivalent to (&*(array + 0))[n], which I think can be cleaned up as array[n], making everything the same as the first one. Okay but I can still do this.

template<typename T>
T &Node::operator[](int n)
{
  return *(reinterpret_cast<T *>(reinterpret_cast<char *>(this) + offsetof(Node<T>, array)) + n);
}

I hope I'm now free from the possible undefined behaviours. Perhaps inline assembly will show my intent better. But do I really have to go this far? Can someone clarify things to me?

By the way T is always a POD type. The whole Node is also POD.

Answer 1

First of all, an implementation is free to reorder class members in all but trivial cases. Your case is not trivial because it has access specifiers. Unless you make your class POD, or whatever it's called in C++11 (trivial layout?) you are not guaranteed your array is actually laid out last.

Then of course flexible members do not exist in C++.

All is not lost however. Allocate a chunk of memory large enough to house both your class and your array, then placement-new your class in the beginning, and interpret the portion that comes after the object (plus any paddibg to ensure proper alignment) as the array.

If you have this, then the array can be accessed with

reinterpret_cast<T*>(
 reinterpret_cast<char*>(this) +
 sizeof(*this) + padding))

where adfing is chosen such that sizeof(T) divides sizeof(*this) + padding.

For inspiration, look at std::make_shared`. It also packs two objects into one allocated block of memory.

Answer 2

The main problem with "out of bounds" array access is that no object lives there. It's not the out of bounds index itself which causes the problem. Now in your case there presumably is raw memory at the intended location. That means you can in fact create a POD object there via assignment. Any subsequent read access will find the object there.

The root cause is that C didn't really have array bounds. a[n] is just *(a+n), by definition. So the first two proposed forms are already identical.

I'd be slightly more worried about any padding behind T array[1], which you'd be accessing as part of array[1].

Answer 3

You also wondered if there was an alternative approach. Given your recent comment about "no reallocation", I'd store the array data as a pointer to heap-allocated storage, but:

Trees has predictable access patterns, from root to child. Therefore, I'd have a Node::operator new and make sure that child nodes are allocated directly after their parent. This gives you locality of reference when walking the tree. Secondly, I'd have another allocator for the array data, and make this return contiguous memory for the parent array and their first child (followed by its first grandchild of course).

The result is that the node and its array have no locality of reference between them, but instead you get locality of reference both for the tree graph and the associated array data.

It's quite possible that the array data allocator can be a trivial pool allocator for the tree. Just allocate 256 KB chunks at a time, and parcel them out a few ints at a time. The whole state you need to track is how much of that 256 kB you've already allocated. This is much faster than std::vector<T, std::allocator> can achieve because it cannot know the memory lives for as long as the tree lives.