Vector backed by memory pages

Question

The purpose of this class is to wrap a std::vector in a class so that never a new object is added. We don't allocate a new object on the stack but we trying to fit it on the current memory page, or create a new page for it.

#include <vector>

template<class T>
class  PagedVector {

public :
    PagedVector(int initialCapacity, float load_factor = 1.5f):
    pageSize(static_cast<size_t>(load_factor*initialCapacity*sizeof(T))),
    current_byte_offset(0),
    current_page(0)
    {
        data.reserve(initialCapacity);

        //initialise one page:
        char* ptr = static_cast<char*>(malloc(pageSize));
        pages.push_back(std::make_pair(ptr, pageSize));
    }

    template<class U>
    U* create() {
        char* memoryPtr = getNextAdress(sizeof(U), std::alignment_of<U>::value);
        U* objectPtr = new (memoryPtr) U();
        data.push_back(objectPtr);
        return objectPtr;
    }

    ~PagedVector() {
        //delete objects
        for(T* obj : data) {
            obj->~T();
        }

        //free memory
        for(auto& pair : pages) {
            free(pair.first);
        }
    }

    void reset() {
        //delete objects
        for(T* obj : data) {
            obj->~T();
        }
        data.clear();

        //keep memory but reset page count
        current_page = 0;
        current_byte_offset = 0;
    }

    const std::vector<T*>& getData() const {
        return data;
    }

private :
    std::vector<T*> data;
    std::vector< std::pair<char* , size_t > > pages;

    size_t pageSize;
    size_t current_byte_offset;
    int current_page;

    char* getNextAdress(size_t size, size_t align) {
        //get next available adress for type with given size and aligment

        char* current_page_adress = pages[current_page].first + current_byte_offset;
        char* end_page_adress = pages[current_page].first + pages.back().second;

        size_t remainder_align = reinterpret_cast<uintptr_t>(current_page_adress) % align;
        size_t extra_alignment_padding = remainder_align==0 ? 0 : (align - remainder_align);

        char* next_aligned_adress = current_page_adress + extra_alignment_padding;
        char* end_aligned_adress = next_aligned_adress + size;

        if(end_aligned_adress < end_page_adress) {
            current_byte_offset += size + extra_alignment_padding;
            return next_aligned_adress;
        }

        //no more space on the current page, have to reallocate a new one:

        //in the rare case where the object size > page size
        size_t nextPageSize = std::max(pageSize, size);

        char* ptr = static_cast<char*>(malloc(nextPageSize));
        pages.push_back(std::make_pair(ptr, nextPageSize));
        current_byte_offset = size;
        ++current_page;
        return ptr;
    }

    //non-copiable:
    PagedVector(PagedVector&);
    PagedVector& operator=(PagedVector&);
};

Usage:

PagedVector<Base> pv(5);
    pv.create<Base>();
    Derived* p = pv.create<Derived>();

I'm wondering if this is correct (not relying on UB). I've never dealt that much with placement new and manual memory management.

Answer 1

I usually focus on the design and this review won't be different. You seem to have created some custom universal allocator, that will place all the (different) objects in continuous space (a page) or create new page if needed. The whole space can be released all at once, but no individual objects. So...

void reset() {
    //delete objects
    for(T* obj : data) {
        obj->~T(); // <<< will not call the appropriate destructor if not virtual

This can be very problematic, unless T has virtual destructor, you should place some static_assert:

template<class T>
class  PagedVector {
    static_assert(std::has_virtual_destructor<T>::value,
        "Objects without virtual destructor cannot be used");

Similar problem is in create allowing any class, should allow derived only:

template<class U>
U* create() {
    static_assert(std::is_same<U,T>::value || std::is_base_of<T,U>::value,
        "Objects not derived from T are not allowed");

---

Minor note about = delete:

//non-copiable:
PagedVector(PagedVector&);
PagedVector& operator=(PagedVector&);

The above should be written with const and = delete to avoid using it inside the class:

//non-copiable:
PagedVector(const PagedVector&) = delete;
PagedVector& operator=(const PagedVector&) = delete;

Answer 2

I'm having difficult understanding you choice of pagesize.
So I presume you want to save time by not allocating so often.

PagedVector(int initialCapacity, float load_factor = 1.5f):
pageSize(static_cast<size_t>(load_factor*initialCapacity*sizeof(T))),
current_byte_offset(0),
current_page(0) {
...
}

In your example the initial size is 5, so you reserve 5*1.5f*sizeof(T), lets assume that sizeof(Base)==16 and sizeof(Derived)==24 and alignment is 8.

So you reserve 5*1.5*16=120 bytes, this is perfect there is room for 5 Derived. If sizeof(Derived)==32, only 3 Derived can be placed, wasting 120-96=24 byes or 20%. This might not be a problem if we are talking relative small sizes, but the absolute size wasted is a problem in large systems.

Depending on your needs the allocations should be much larger to reduce the number of calls to malloc. This might also help in spatial locality for your data.