CODEWITHSUNDEEP
c++arraysinitializationc++23placement-new
Christopher Miller
Christopher Miller

Reputation: 3461

How can I allocate multiple arrays of different types in a single allocation?

I am coding a probing hash set which internally maintains an array of slots as well as a separate array of slot metadata:

template <typename T, typename Hasher = std::hash<T>, typename Allocator = std::allocator<T>>
class HashSet {
    T *slots;              // Array of slots
    uint8_t *metadata;     // Array of metadata (each slot has a single byte of metadata)
    Allocator allocator;
    /* ... */
}

Now, in my current implementation, the slots and metadata arrays use separate allocations. In particular, I use placement new/delete for slots (via std::allocator_traits) to avoid unnecessarily invoking T's default constructor. For metadata, however, I have just been using regular new[]/delete[], because the metadata always needs to be initialized at the start anyways. Thus, my code looks as follows (using my reserve function as an example):

// Inside `class HashSet`
void reserve(size_t new_capacity) {
    if (curr_capacity >= new_capacity) return;

    // Allocate new slots and metadata arrays separately
    auto new_slots = std::allocator_traits<Allocator>::allocate(allocator, new_capacity);
    auto new_metadata = new uint8_t[new_capacity];

    /* Rehash all elements, and move them to `new_slots`... */

    // Deallocate the old `slots` and `metadata` arrays
    if (slots) std::allocator_traits<Allocator>::deallocate(allocator, slots, curr_capacity);
    delete[] metadata;

    /* Set `slots` and `metadata` to `new_slots` and `new_metadata`, and update `curr_capacity`... */
}

Now, I've realized that allocating both arrays in a single allocation would improve locality of reference. However, I am unsure of how to do this. In particular, I'm pretty sure that simply allocating a large char* buffer and treating it as the elements array concatenated to the metadata array would violate memory alignment rules. At the same time, I'm worried about the fact that I use different strategies for managing the slots and the metadata (placement new/delete vs regular new/delete); I have been considering just using placement new/delete for everything.

Overall, my question is: How can I create two differently-typed arrays in a single contiguous allocation, for the purposes of improving cache locality?

The only thing I know of which is similar to this is the fact that std::make_shared allocates both the value as well as the reference counter in a single allocation. However, I don't know how that is achieved.

Upvotes: 0

Views: 106

Answers (1)

Remy Lebeau
Remy Lebeau

Reputation: 597941

You could define a struct that holds 1 T and 1 uint8_t, and then allocate 1 array with that struct as its element type.

Otherwise, you'll have to allocate a single char[] buffer that is large enough to hold both arrays and alignment padding between them, and then use placement-new to create the uint8_t elements in part of the memory, and the T elements in the remaining memory.

Upvotes: 1

Related Questions