(C++) An interesting Container design

Okay, this will be one of my first programing posts. I won’t feature a lot of code since I don’t want this to be a how to tutorial. Basically I will present you an idea and give you some thoughts about it (and I will show a little test).

Some time ago I designed a container class (well I named it mango::vector) since the std::vector made a trade I was not willing to accept so I designed a little container class to suit my needs.

Well, here is the situation. A vector is a dynamic array. That means you have a pointer to an array of elements. if the array capacity is reached, the vector allocates a new array which is larger than the original one and copies/moves all the content to the new array. And there is the problem. A vector is fast as long as you won’t bust it’s initial (or reserved capacity) since allocating new memory and moving all the content takes “a lot” of time.

But that’s only on of a few problems. Another flaw comes with erasing or inserting values from/to the vector. If you erase a vector every element after the erased element have to be moved/copied one slot towards the erased elements index which also takes “a lot” of time. (inserting happens to be the other way around –> moving and index away from the insert-index)

Ok, where does that information lead us to you may ask? Well, that’s a damn good question. Some of you will say now “why don’t you just us a std::list?”. Well that’s also a damn good question.

For those who don’t know: If a vector in your memory looks like this:

vector_memory

Then a list can be imagined like this:

list_memory

Ok now you see a memory model, but why?

It’s easy if you want to access a vector element you just shift a pointer to the begin of the array index * elementsize “to the left”. One operation. If you want to add an element at the end (and we suggest we have enough space in our vector so we don’t have to reallocate memory) we just add it. Also one operation.

Let’s look at the list. If we want to add an element at the end we have to allocate memory for a new element and place the element there. Allocation isn’t the fastest thing on earth, that takes some time. If we want to access for example the 4th element we have to drag ourself along 4 pointers. That won’t take to long but it’s still slower than the vector. Inserting into a list is really interesting. If we want to insert an element in our list, we allocate a new one and add it into our list. That’s a lot faster than inserting into a vector as you may remember (no elements to move).

So basically we can break our conclusion into two points. Inserting, deleting or appending elements from/into a list works at a constant speed.

Inserting, deleting elements/from/into a vector is slow, appending elements to the end on the other hand is really fast.

Each of the above mentioned containers do have their ups and downs, so why no container wich is good at both? And that’s exactly the conclusion I came to when I started to think about that topic. This wouldn’t be an interesting post if I hadn’t a wonderful stupid idea to solve that particular problem (kind of)

semivector

That’s the idea I came up with. Simple said, I made a “vector” with 2 arrays, one with elements, one with pointers to the elements.

What is the advantage of that? Well that’s easy. If you want to access an element you access it over the array of element pointers. That’s not significant slower than accessing them the regular way since you just have to access the array of pointers.

Here comes the interesting part. If you want to delete an element for example (let’s take the second one) you only have to shift the pointer to the second element to the end of the pointer array.

semivector_deleted

Now if you want to access the “second” element in your vector you’re actually accessing the third element in your array, but the second pointer (you won’t spot the difference).

(that’s how the “vector” would look like after an insert)

semivector_inserted

So what is the benefit of this? Also easy: If you make an insert/erase you won’t have to shift the actual elements, instead of you are shifting the pointers to the elements. If you have a custom::vector you will see no improvement in performance compared to a std::vector (the performance will even get worse) since shifting int variable is as fast as shifting pointer. On the other hand if you got a custom::vector your performance will increase significant since shifting pointers is a lot faster than shifting std::strings.

Most likely you will ask now: If this is the holy grail of a container, why isn’t vector implemented that way?

Legit question. The answer is simple. This container has other flaws. Yes it is fast. But you pay the speed benefit by using more memory. On each element you add there comes a pointer to that element. Lets consider we have a 32 Bit system: If you have 200 elements with size 8 bytes we got 1600 bytes (+ ca 16 bytes for the actual std::vector object) for our std::vector. If we have 200 elements which 8 bytes in a custom::vector we will have 2400 Bytes of memory in use (if we consider a 32 bit pointer is 4 bytes). That’s a third more. I still like to use my custom container since in my opinion in the most cases the size difference won’t have to much of an impact since memory isn’t always the limiting factor. The standard container a build to be flexible and with things like embedded systems in mind. It’s not always the raw execution performance that matters.

Well now I threw around with a load of claims and proofed nothing by now, funny aye? But this wouldn’t be fun if I hadn’t tested this at least a bit. (Just for those of you who are curious, no I won’t provide the code for my vector since I did some ugly thing down there which I want nobody to know about, sorry. But you are clever guys and I am pretty sure you will be able to implement this one yourself)

This test only shows the insert capabilities of this container, erasing won’t perform much different. The test is not perfect but it will give you a relation of numbers which will at least give you a feeling for the speed improvement.

here is the test code:

vector_test_code

and here comes the result:

vector_test_result

These results are in seconds, maybe I should have written that. The custom::vector (in my case mango::vector) inserts 100x faster (if you believe this test). That’s a number isn’t it? Well, reality seems a bit difference. The number will change, but in both directions. The bigger the elements in your vector are, the faster your custom::vector will get in relation to the std::vector. The smaller the elements are… well you got it I think.

The test was built in release with activated optimizations.

If you actually made an implementation for this custom container which is clean enough to share it with the world feel free to link it in a comment.

Advertisements

Author: mango2go

I am a software developer for a big pharmaceutical trading company. I am interested in C++ and C# programming in general and in game development in particular (only as a hobby atm). My experience about game development is restricted to what I tought me myself so I am still in the process of learning. My goal is to become a professional game developer and find my name in the credits of a popular game one day.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s