C++ growing std::vector of movable reference counting pointer

John Yates 0
Viewed 36

I have a class that implements reference counting:

  • It's sole data member is a pointer to an object containing an invasive reference count
  • The "Rule of 5" methods are all declared noexcept
  • The default constructor initializes the pointer data member to nullptr
  • Move operations set the moved-from pointer data member to nullptr
  • When the pointer data member is nullptr the destructor is effectively a nop

By instrumenting the methods I do see that growing the vector occurs by repeatedly move-constructing from an old object into new memory and then destroying that old object.

Intuitively, I known that growing the vector could be performed more efficiently as

  • Allocate new, larger chunk of memory
  • Block copy the contents of the old chunk to the front of the new chunk
  • Install the new chunk
  • Free the old chunk

Is there, in C++20, any magic incantation that can persuade std::vector to be this efficient?

stdvector move-semantics c++
1 Answers

There is a discussion of the efficiency of custom memory allocators in this article and the author discusses comparison of custom memory allocation strategies and why its worth the effort to write your own. The article states that you can't mix memory allocators and that is a caution worth learning more about.

I explored a custom allocator starting from malloc and free looking at the code example here.

#include <cstdlib>
#include <new>
#include <limits>
#include <iostream>
#include <vector>

// from https://en.cppreference.com/w/cpp/named_req/Allocator
 
template <class T>
struct Mallocator
{
  typedef T value_type;
 
  Mallocator () = default;
  template <class U> constexpr Mallocator (const Mallocator <U>&) noexcept {}
 
  [[nodiscard]] T* allocate(std::size_t n) {
    if (n > std::numeric_limits<std::size_t>::max() / sizeof(T))
      throw std::bad_array_new_length();
 
    if (auto p = static_cast<T*>(std::malloc(n*sizeof(T)))) {
      report(p, n);
      return p;
    }
 
    throw std::bad_alloc();
  }
 
  void deallocate(T* p, std::size_t n) noexcept {
    report(p, n, 0);
    std::free(p);
  }
 
private:
  void report(T* p, std::size_t n, bool alloc = true) const {
    std::cout << (alloc ? "Alloc: " : "Dealloc: ") << sizeof(T)*n
      << " bytes at " << std::hex << std::showbase
      << reinterpret_cast<void*>(p) << std::dec << '\n';
  }
};
 
template <class T, class U>
bool operator==(const Mallocator <T>&, const Mallocator <U>&) { return true; }
template <class T, class U>
bool operator!=(const Mallocator <T>&, const Mallocator <U>&) { return false; }
 
int main()
{
  std::vector<int, Mallocator<int>> v(8);
  for ( auto i = 0 ; i < 16 ; i++  ) v.push_back(i);
}

g++ --std=c++20 main.cpp
./a.out

Alloc: 32 bytes at 0x600002ecd120
Alloc: 64 bytes at 0x600003bcc180
Dealloc: 32 bytes at 0x600002ecd120
Alloc: 128 bytes at 0x6000000cc080
Dealloc: 64 bytes at 0x600003bcc180
Dealloc: 128 bytes at 0x6000000cc080
atl0
Related