In-Depth: A Blob Array

Author: by John McCutchan

[In this reprinted #altdevblogaday-opinion piece, SCEA's senior developer support engineer John McCutchan shares a useful blob array that he says is a departure from every other array class he's ever read.] After reading my last article, some readers asked for an example of a structure that lives inside a blob. For this article, I thought I would share my blob array (std::vector equivalent). It is, internally, a departure from every other array class I've ever read. Also, my blob array demonstrates the utility of decoupling memory allocation from algorithms, which I touched on near the end of my previous article. Before presenting my blob array, I will present my foil, the typical dynamic array:

template<typename T>
struct dynamicArray {
  T* buffer;
  size_t capacity;
  size_t size;
};

Pretty straight forward, right? You have a contiguous chunk of Ts in buffer, of which [0, size) are used. The buffer has room for capacity elements. When elements are added and size becomes equal to capacity, the capacity is increased and the old buffer is copied into the new larger buffer' before being deallocated. Text book. The keen reader won't be satisfied with this array. First of all, it has memory allocation and algorithms coupled together. What if you want to use a static buffer to store the contents of the array? Sure, the capacity is fixed when using a static buffer but the algorithms for working with the array haven't changed and thus shouldn't be tied to the memory management scheme. Also, what if you know that you only ever need 8-bits to store the capacity and size information instead of 64-bits (the size of size_t on a 64-bit OS)? What if you want to serialize this in and out of a file? This dynamic array is starting to look tired. There's gotta be a better array.

template<typename T, typename INDEX_TYPE = int32_t>
struct blobArray {
  uintptr_t memory;
};

That's it. Where is the capacity, size and contents? As usual with blob structures, you will have to look inside the blob to gain insight: Assuming INDEX_TYPE is int32_t, capacity is offset 0 bytes into the blob, size is offset 4 bytes into the blob and contents is offset 8 bytes into the blob. blobArray has an Initialization method which takes a memory address and a size. The type of contents is specified as a template parameter, so Initialize just has to zero out size and set capacity using the following formula:

capacity = (blob_size - sizeof(INDEX_TYPE) * 2) / sizeof(T);

Note: I've simplified the above formula by removing alignment considerations. Compared to my foil, my blobArray is looking good. Most importantly, it has decoupled memory allocation from the algorithms used to manage a dynamic sized array. Put another way, it works beautifully with static buffers. The type of the index is parametrized, allowing for the most compact storage. Because the entire state is encoded into one contiguous piece of memory, serializing is free, you can write the entire array to a file and read it back atomically. Keen readers should take this opportunity to point out that a blobArray couldn't possibly expand it's capacity. Don't worry, I'm with you. Enter dynamicBlobArray:

template<typename T, typename INDEX_TYPE = int32_t>
struct dynamicBlobArray {
  blobArray<T, INDEX_TYPE> blob_array;
  allocatorInterface* allocator;
};

This class couples the algorithms offered by blobArray with a memory allocator. Allowing the capacity to increase when needed. dynamicBlobArray exposes the same interface that blobArray exposes by forwarding function calls, example:

T* dynamicBlobArray::begin() {
  return blob_array.begin();
};

Both of these template classes will be implemented in header files, allowing the compiler to inline the function forwarding. Of course, dynamicBlobArray will special case methods that add elements to the array, example:

void dynamicBlobArray::push_back(const T& e) {
  if (IsFull()) {
    ExpandCapacity();
  }
  _blob_array.push_back(e);
}

Hopefully, no one thought I was going to make push_back a virtual method, use inheritance and override it in dynamicBlobArray. Ick. Both blobArray and dynamicblobArray expose a super-set of std::vector methods. Making them transparent replacements for an existing code base. There is one down side to using this blob structure: the debugger cannot automatically display state information for these arrays. To get around this, you need to extend the debugger so that it can visualize the internal state hidden in the blob. You can extend Visual Studio by adding custom visualizers to autoexp.dat. This container has worked well for me. I get both static and dynamic capacity arrays with just one implementation. Also, easy serialization and compact storage. How have you implemented yours? [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]