6
\$\begingroup\$

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 19, 2014 at 17:24
  • \$\begingroup\$ @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 \$\endgroup\$ Commented Oct 19, 2014 at 17:34
  • \$\begingroup\$ 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). \$\endgroup\$ Commented Oct 19, 2014 at 17:43
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Oct 19, 2014 at 17:47
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Oct 19, 2014 at 17:49

2 Answers 2

Reset to default
6
\$\begingroup\$

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;
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 19, 2014 at 12:52
1
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.