Click here to Skip to main content
16,021,810 members
Articles / Programming Languages / C++

listvector: Continuous Memory, no reallocation on insert!

Rate me:
Please Sign up or sign in to vote.
4.67/5 (24 votes)
16 Sep 2015CPOL6 min read 37.1K   296   19   27
A combination of std::vector and std::list which does not copy or move elements in insertion and still has continuous memory

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

C++
// 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

C++
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

C++
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

C++
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

C++
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;
    }
So first we cast it to size_t, then add the element size (which is a multiply of the aligment), then back to pointer.
 
 
MapTheList() loops through the elements, then uses MapViewOfFileEx to force the base address. 
 
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();
    }
Because we had tester earlier that the file mapping can map the entire capacity, we know that the call will succeed (unless of course someone else has already mapped to that memory!).
 
 
emplace functions use placement new to call the constructor:
 
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;
    }
Note the usage of variadic templates so to forward all the arguments "in-place" to the constructor.
 
 
The sort functions simply use std::sort and then remapping the result:
 
void sort()
    {
    UnmapTheList();
    std::sort(elements.begin(),elements.end());
    MapTheList();
    }
Because the elements array holds pointers, nothing is reallocated or reconstructed.
 
 
 

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.

 

Conclusion

Of course, not all the functions have been tested with any sort of contain-ee. Do contribute and report bugs to me.

Have fun!

 

History

  • 13 - 09 - 2015: First Release

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Greece Greece
I'm working in C++, PHP , Java, Windows, iOS, Android and Web (HTML/Javascript/CSS).

I 've a PhD in Digital Signal Processing and Artificial Intelligence and I specialize in Pro Audio and AI applications.

My home page: https://www.turbo-play.com

Comments and Discussions

 
GeneralMy vote of 5 Pin
hooodaticus17-Nov-16 10:18
hooodaticus17-Nov-16 10:18 
GeneralRe: My vote of 5 Pin
Michael Chourdakis19-Dec-16 3:02
mvaMichael Chourdakis19-Dec-16 3:02 
QuestionExample of usage? Pin
Marius Bancila12-Nov-15 10:43
professionalMarius Bancila12-Nov-15 10:43 
AnswerRe: Example of usage? Pin
Michael Chourdakis12-Nov-15 11:40
mvaMichael Chourdakis12-Nov-15 11:40 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA17-Oct-15 16:01
professionalȘtefan-Mihai MOGA17-Oct-15 16:01 
GeneralRe: My vote of 5 Pin
Michael Chourdakis17-Oct-15 22:19
mvaMichael Chourdakis17-Oct-15 22:19 
GeneralMy vote of 5 Pin
Farhad Reza8-Oct-15 18:12
Farhad Reza8-Oct-15 18:12 
Good Article.
Question[My vote of 2] What are the advantages of using your listvector instead of something simpler and portable? Pin
PedroMC17-Sep-15 2:57
PedroMC17-Sep-15 2:57 
AnswerRe: [My vote of 2] What are the advantages of using your listvector instead of something simpler and portable? Pin
Michael Chourdakis17-Sep-15 20:01
mvaMichael Chourdakis17-Sep-15 20:01 
GeneralRe: [My vote of 2] What are the advantages of using your listvector instead of something simpler and portable? Pin
PedroMC18-Sep-15 0:24
PedroMC18-Sep-15 0:24 
GeneralRe: [My vote of 2] What are the advantages of using your listvector instead of something simpler and portable? Pin
Michael Chourdakis18-Sep-15 2:20
mvaMichael Chourdakis18-Sep-15 2:20 
GeneralInteresting ... Pin
koothkeeper15-Sep-15 12:14
professionalkoothkeeper15-Sep-15 12:14 
QuestionReinventing the wheel Pin
Member 1198633515-Sep-15 7:01
Member 1198633515-Sep-15 7:01 
AnswerRe: Reinventing the wheel Pin
Michael Chourdakis15-Sep-15 7:25
mvaMichael Chourdakis15-Sep-15 7:25 
GeneralMy vote of 5 Pin
sprice8615-Sep-15 6:12
professionalsprice8615-Sep-15 6:12 
QuestionYou have lost me Pin
_kb_14-Sep-15 3:26
_kb_14-Sep-15 3:26 
AnswerRe: You have lost me Pin
Michael Chourdakis14-Sep-15 6:12
mvaMichael Chourdakis14-Sep-15 6:12 
GeneralInteresting trick, but... Pin
ZhenyOK15-Sep-15 11:26
ZhenyOK15-Sep-15 11:26 
GeneralRe: Interesting trick, but... Pin
Michael Chourdakis16-Sep-15 11:03
mvaMichael Chourdakis16-Sep-15 11:03 
GeneralRe: Interesting trick, but... Pin
ZhenyOK16-Sep-15 12:18
ZhenyOK16-Sep-15 12:18 
GeneralRe: Interesting trick, but... Pin
Michael Chourdakis17-Sep-15 20:02
mvaMichael Chourdakis17-Sep-15 20:02 
GeneralRe: You have lost me Pin
_kb_15-Sep-15 23:37
_kb_15-Sep-15 23:37 
GeneralRe: You have lost me Pin
Michael Chourdakis16-Sep-15 11:05
mvaMichael Chourdakis16-Sep-15 11:05 
GeneralRe: You have lost me Pin
Paulo Zemek25-Sep-15 14:08
Paulo Zemek25-Sep-15 14:08 
GeneralRe: You have lost me Pin
Michael Chourdakis25-Sep-15 21:22
mvaMichael Chourdakis25-Sep-15 21:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.