C++ Efficiently Moving Object Created Via Placement New In Raw Memory Buffer

Question

After a fair amount of googling I haven't found a clear answer to this question. I am writing a custom memory pool for a project I am working. You can think of this as a sparse set mapping to a tightly packed data array. The code works as follows:

There is a vector of raw memory 'chunks' each with a size that is a multiple of the stored object's size.

sparseIndices maps a large set of potential indices to a small set in packedIndices where each stores an index pointing to the other.

index            0   1   2
memory         | a | b | c |
                 |   |   |
                 |   |   |                       
packedIndices  | 3 | 4 | 1 |             // indices in the sparse set

sparseIndices  | - | 2 | - | 0 | 1 |     // indices in the packed set
index            0   1   2   3   4

Objects are created using code like the code listed below. I'ved ommited the parts where the index vectors are updated.

// chunkSize usually much larger than 1 (i.e. 8192)
uint8_t* chunk = new uint8_t[chunkSize * sizeof(T)];
memory.push_back(chunk);

// new objects are always placed at the end of 'memory' so every valid object lies in contiguous memory
// there is always enough space for another object since I allocate memory as required.
// the index arrays are modified near this code to have the correct mappings.
T* myT = new (memory[chunkIndex] + offset)T();

vector<uint8_t*> memory;
vector<size_t> packedIndices
vector<size_t> sparseIndices;

When an object needs to be removed I would like to "swap" the object with the last object, delete the last object (now the one to be deleted) and then resize the memory 'pool' - 1.

My question is, what is the proper way to "swap" the two objects? So, far I have been using memcpy & memset as illustrated below. This works, but, I have a feeling this is A.) not good practice B.) flat out wrong for complex types. I considered template polymorphism being an issue but, from my limited understanding, this doesn't seem possible since C++ doesn't seem to support covariant templates (C++ covariant templates).

  // the goal here is to keep the objects tightly "packed" in contiguous memory
  T* element = static_cast<T*>(this->GetRawPointer(memoryIndexToRemove));
  element->~T();
  void* lastElement = this->GetRawPointer(lastValidMemoryIndex);
  memcpy(static_cast<void*>(element), lastElement, sizeof(T));
  memset(lastElement, 0, sizeof(T));
  // the size will be modified here so the previous last object is now free memory

@user2368778 `placement-new` can invoke any constructor. In this case, use the type's copy constructor, specifying the destroyed `element`'s memory block as the target, eg: `T* element = static_cast(GetRawPointer(memoryIndexToRemove)); element->~T(); T* lastElement = static_cast(GetRawPointer(lastValidMemoryIndex)); new (element) T(*lastElement); lastElement->~T();` — Remy Lebeau, Apr 14 '22 at 00:14
So, rather than memcpy and memset you would do something like.. `T* last = static_cast(lastElement); new (element) T(*last); last->~T(); // is this last destructor call required?` could this not result in a memory leak? i.e. some type has ref counted smart pointers and the other has raw pointers. — user2368778, Apr 14 '22 at 00:18
It does not leak. The `lastElement` object is *copied* into a new object in `element`'s memory, and then the copied object is destroyed. Ref-counts are handled properly. A move constructor could be used instead: `T* element = ...; element->~T(); T* lastElement = ...; new (element) T(std::move(*lastElement)); lastElement->~T();` Or, simply don't destroy the original `element` object at all: `T* element = ...; T* lastElement = ...; std::swap(*element, *lastElement); lastElement->~T();` Alternatively: `T* element = ...; T* lastElement = ...; *element = std::move(*lastElement); lastElement->~T();` — Remy Lebeau, Apr 14 '22 at 00:22
Ah.. seems like swap is the answer. The case I was thinking of was a double free on the valid object that was moved. But, this way, I could invoke the destructor on only the object I want to destroy, avoiding any potential issue with the object that will continue to exist. Thanks! — user2368778, Apr 14 '22 at 00:25
By double free, I mean double free on members of the valid object. e.g. if it's using raw pointers internally and the destructor has something like "delete member;" — user2368778, Apr 14 '22 at 00:31
@user2368778: `swap` is valid only if it works to keep all your objects alive (if moved-from) forever. That’s highly likely for objects that are movable anyway (as they must be for this to work at all), but it’s not what users might expect based on ordinary containers. — Davis Herring, Apr 14 '22 at 02:30

C++ Efficiently Moving Object Created Via Placement New In Raw Memory Buffer

0 Answers0