# Vector backed by memory pages

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):
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() {
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);

}

//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.

• You should not be wrapping the vector. But writing an allocator for the vector. Its passed as the second template argument to vector and handles all the underlying memory management of the vector. – Martin York Oct 19 '14 at 17:24
• @LokiAstari I disagree since I'm not going use all the specifics API of std::vector. Basically I will just add stuff to it, then deallocate everything at the end. I don't need to have a specific allocator that would handle removing single elements etc – lezebulon Oct 19 '14 at 17:34
• Sure if you want a non conformant container that does not work in a way that everybody else expects then fine. If you want a vector that uses paged memory then use an allocator. But if you are going to do it your way then you really should change the title (as a vector backed by paged memory is not your goal and that's what people will review you on). – Martin York Oct 19 '14 at 17:43
• @LokiAstari it's not a requirement that containers are stl-conformant. If I want to make a container that works for my use cases I should still be allowed to right ? I don't see why general people would expect it to work in a specific way when the documentation etc would state it's not meant to. – lezebulon Oct 19 '14 at 17:47
• You are calling it vector backed by pages. If you want to write something specific to you call it something else as the curent description is not what you are doing. Using vector to store the location of a set of pages so I can do global deallocation – Martin York Oct 19 '14 at 17:49

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;

• Side note: you could create universal non-templated class Allocator with techniques used in boost::any by wrapping any class U inside some helper private: template<U> struct Holder: HolderBase { U data; }; derived from basic class with virtual destructor (getting the pointer by this + 1). Quite advanced solution, but I can help if you wish. – firda Oct 19 '14 at 12:52

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):
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.