listvector: Continuous Memory, no reallocation on insert!

• Download main.zip - 4.2 KB

GOD mode on

I just invented a new type of memory which is always continuous but there is no repositioning of the elements when I do insert() or push_back(). It's made of radioactive Astatine 210, has a half-life of 32 ms and will cost you 1,43 billion USD per MB. 

I 'm about to present it in the 2042 Conference of Computer Science, taking place in the International Space Station. If you can't participate, then you can at least take a look at the 6,023x10^23 pages proceedings later. 

I will have won a Turing prize by that time. Remember std::future() and std::promise() ? Yes they 've promised me lots of money. Unfortunately, implementing such a container is a LOT cheaper and easier than what I have to do to justify the famous trophy :)

GOD mode off

OK, I 'm not the god. I just like to experiment with weird stuff. 

It's not that difficult anyway. Basically, it's a Windows file mapping trick. Each element in the container has it's own address which is fixed and, of course, elements in the list are not continuous in memory (like std::list), but also there is another mapping for each item which points to the actual address and the iterators you get contain these pointer addresses.

You have two types of pointers. One, the internal set. This is where the elements are actually stored, and this is managed like std::list: Insertion/Removal is constant because nothing is moved, but the internal set is not continuous.

The external set (what the user sees through the iterators) are simply maps (via MapViewOfFileEx) to the internal pointers. On insertion/delete, they are remapped so they point to the correct elements, while always being continuous.

Therefore, you have both continuous memory AND very optimized inserts/erases!

-THE- catch

The alignment is 65536 bytes. Ouch. Sorry, but that's the page granularity in Win32. Therefore each element in the container needs a multiple of 65536 bytes, which means that, in order to use our container, you either have large objects to store (in fact, a bit below the multiplies of 65536) or you are totally obsessed for performance.

Well, both apply to me :P. Let's go!

 

Why a new container?

There are difficulties when trying to extend the existing containers. 

• STL containers are not meant to inherit from (no virtual functions/destructors) etc.
• Custom allocators can only allocate/free, no notification whatsoever about who is calling, the iterator positions etc.

Therefore, I just couldn't inherit from std::list or std::vector, and I couldn't just write a custom allocator. A totally new class has to be created.

 

Internals

Each element is stored as a listvector::MAP class. This structure contains a pointer to the actual memory (which remains fixed) and a pointer to the mapped memory.

GetSystemInfo() function returns us the minimux allocation granularity. In my system it is 64KB.

InitFull() creates handles and mappings (called from the constructors).

MemPerElement() function decides how much memory is needed per each element, aligned to the allocation granularity.

GetMaxMemoryNeeded() decides how much memory we need based on the container's capacity and the memory needed per element.

MapTheList() and UnmapTheList() map and unmap the actual, fixed, non continuous memory addresses of the elements to the non fixed continuous memory addresses so data(), at() and operator[] can work. Mapping is done with read/write access with the aid of MapViewOfFileEx which forces Windows to use a specific mapping address for us.

SetMinAddress() finds the best base mapping address for the current capacity. This is what data() returns.

CreateH() and DestroyH() actually create and destroy the file mapping object and the actual map of the memory.

recreate() recreates the entire container if capacity has to grow. 

ClearAndDestroy() cleans up (used by recreate() and the destructor).

FindMapAtPosition() finds the element from an actual address. It is used from FindFreeAreaForElement() to create a fixed memory for a new element.

smartadd() changes the capacity based on the current and requested size.

CreateMemoryAtEnd() is called by functions such as push_back to create memory for insertions at the end. It is an optimized version of CreateMemoryBeforePosition().

CreateMemoryBeforePosition() is called by any other memory creation.

 

 

template <typename T> listvector

The class is a combination of std::list and std::vector, providing an almost identical function set except from a few exceptions that we will note. The class is in template form, which means it works for all types that are eligible to be contained in a STL container.

The class throws std::bad_alloc if some Win32 operation fails. 

Constructors,operator =()s and destructor

// Creates an empty listvector with capacity = 10
listvector();

// Creates a listvector with a specific size.
listvector(size_t); 

// Constructs from an initializer_list.
listvector(const std::initializer_list<T>&); 
listvector(std::initializer_list<T>&&);

// Constructs from a vector
listvector(const std::vector<T>&);
listvector(std::vector<T>&&);

// Constructs from a list
listvector(const std::list<T>&);
listvector(std::list<T>&&);

// Constructs from a listvector
listvector(const listvector<T>&);
listvector(listvector<T>&&);

// Destructor
~listvector(); 

Each of the constructors is accompagnied by it's relevant operator =().

 

 

at(), operator[] and position requests

T& at(size_t idx);
T& operator[](size_t idx);
T& back();
T& front();

Similar to STL. at() performs bounds checking (throwing std::out_of_range), whereas operator[] does not. const versions are also there.

 

iterarors

listvectoriterator<T> begin();
const listvectoriterator<T> cbegin() const;
listvectoriterator<T> rbegin();
const listvectoriterator<T> crbegin() const;
listvectoriterator<T> end();
const listvectoriterator<T> cend() const;
listvectoriterator<T> rend();
const listvectoriterator<T> rend() const;

Similar to STL. const versions are also there. The iterators always point to the mapped addresses of the elements, which are changed on resizing, but the actual elements are not changed because their original address remains fixed.

listvectoriterator also provides operators such as ++,+,-,==,!= etc.

 

insert(), emplace(), splice() and pushes

template <class... Args>
        listvectoriterator<T> emplace(const listvectoriterator<T> position,Args&&... args);
template <class... Args>
        void emplace_back(Args&&... args);
template <class... Args>
        void emplace_front(Args&&... args);
listvectoriterator<T> insert(const listvectoriterator<T> position,const T& val);
listvectoriterator<T> insert(const listvectoriterator<T> position,T&& val);
void insert(const listvectoriterator<T> pos,size_t count,const T& value);
void insert(const listvectoriterator<T> pos,std::initializer_list<T> li);
template <class InputIterator>
        listvectoriterator<T> insert(const listvectoriterator<T> pos,InputIterator first,InputIterator last);
void push_back(const T& val);
void push_back(T&& val);
void push_front(const T& val);
void push_front(T&& val);
void splice(const listvectoriterator<T> pos,listvector& x);
void splice(const listvectoriterator<T> pos,listvector&& x);
void splice(const listvectoriterator<T> pos,listvector& x,const listvectoriterator<T> i);
void splice(const listvectoriterator<T> pos,listvector&& x,const listvectoriterator<T> i);
void splice(const listvectoriterator<T> pos,listvector& x,const listvectoriterator<T> first,const listvectoriterator<T> last);
void splice(const listvectoriterator<T> pos,listvector&& x,const listvectoriterator<T> first,const listvectoriterator<T> last);

Similar to STL. When an insertion occurs, the container does not move/copy any of the other elements. Instead, it remaps their actual addresses (which they are fixed and not continuous) to the mapping addresses, which are always continuous.  If the insertion does not force a change in the capacity, the original start address (i.e. the one returned from data()) is the same. If the insertion forces a capacity change, the base memory also changes and the items are moved to their new positions.

 

erase(), remove() and pops

void remove(const T& val);
template <class Predicate>
        void remove_if(Predicate pred);
listvectoriterator<T> erase(listvectoriterator<T> position);
listvectoriterator<T> erase(listvectoriterator<T> first,listvectoriterator<T> last);
void pop_back();
void pop_front();

Similar to STL. Erasing does not change the capacity.

 

More internals

Here you will see some interesting details about the container.

Iterator's increase/decrease is not simply a += of the pointer type itself, because we need alignment. Therefore let's see a sample:

listvectoriterator<T>& operator++()
    {
    size_t pp = (size_t)p;
    if (R)
        pp -= sz;
    else
        pp += sz;
    p = (T*)pp;
    return *this;
    }

for (size_t i = 0; i < elements.size(); i++)
    {
    size_t bb = b;
    bb += i*MemPerElement();
    ULARGE_INTEGER mp = {0};
    mp.QuadPart = (unsigned long long)elements[i].ActualPtr;
    mp.QuadPart -= (unsigned long long)FullMap;
    elements[i].Map = (T*)MapViewOfFileEx(hF,FILE_MAP_ALL_ACCESS,mp.HighPart,mp.LowPart,grd,(LPVOID)bb);
    if (!elements[i].Map)
        throw std::bad_alloc();
    }

template <class... Args>
listvectoriterator<T> emplace(const listvectoriterator<T> position,Args&&... args)
    {
    MAP& m = CreateMemoryBeforePosition(position.idx());
    new (m.ActualPtr) T(std::forward<T>(args...));
    listvectoriterator<T> r((size_t)MinAddress,(size_t)m.Map,MemPerElement());
    return r;
    }

void sort()
    {
    UnmapTheList();
    std::sort(elements.begin(),elements.end());
    MapTheList();
    }

Other STL helpers

The following functions are also there:

• capacity();
• clear();
• data();
• size();
• max_size();
• reserve();
• resize();
• reverse();
• shrink_to_fit();
• sort() and template sort with Compare class.
• swap();
• unique() and template unique with BinaryPredicate class

A few others are missing, such as assign() and merge(). 

Testing

In the file there are some testing functions that will show you how the container works. I 've also created a class F with copy/move constructors etc to verify that the correct ones are called.

History

• 13 - 09 - 2015: First Release