# Custom vector that uses less memory than std::vector

I'm using vectors to create matrix and the vector itself is consuming a large space. So I implemented a version that would use less memory and, if possible, be as fast or faster than std::vector.

How can I improve the performance and is there anything that should be changed?

#ifndef __DATAARRAY_H__
#define __DATAARRAY_H__
#include <memory>
#include "core/Exceptions/ArgumentException.h"

template <size_t S> class Sizer { };
namespace Core
{
#pragma pack(1)
template <class DataType, class MaxSizeType>
class DataArray
{
public:
}
DataArray(MaxSizeType size) :m_iDataSize(0){
_Reserve(size);
}

DataArray(const DataArray& dArray)
{
_Reserve(dArray.m_iDataCapacity);
_CopyData(dArray);
}
void reserve(MaxSizeType size){
}

void resize(MaxSizeType size){
if (size < m_iDataSize)
{
m_iDataSize = size;
}
else if (m_iDataSize < size){
_Reserve(size);
DataType* pData = (m_aData + m_iDataSize);
for (; pData < m_aData + size; ++pData) {
new (pData)DataType;
}
m_iDataSize = size;
}
}

void push_back(DataType element){
if (m_iDataCapacity <= m_iDataSize)
{
_Reserve(m_iDataCapacity + 1);
}
m_iDataSize++;
}

DataType& operator[](MaxSizeType id)
{
if (id < 0 || id >= size())
throw std::invalid_argument("Not enought memory");
}

DataType& operator=(const DataArray& dArray)
{
if (this == &dArray)
return *this;
_Reserve(dArray.m_iDataCapacity);
_CopyData(dArray);
return *this;
}

MaxSizeType size(){
return m_iDataSize;
}

MaxSizeType Capacity(){
return m_iDataCapacity;
}

~DataArray(){
}
protected:
inline void _Reserve(MaxSizeType size){
if (size > m_iDataCapacity){
if (new_Data != NULL){
m_iDataCapacity = size;
}
else{
throw std::invalid_argument("Not enought memory");
}
}
}
inline void _CopyData(const DataArray& dArray){
DataType* pOriEnd = pOrig + dArray.m_iDataSize;
for (; pOrig < pOriEnd; ++pDest, ++pOrig)
{
new (pDest)DataType(*pOrig);
}
m_iDataSize = dArray.m_iDataSize;
}

{
m_iDataSize = 0;
m_iDataCapacity = 0;
}

inline void _Delete_Data(DataType* begin, DataType* end)
{
DataType* pData = begin;
for (; pData < end; ++pData) {
((DataType*)pData)->~DataType();
}
}
MaxSizeType m_iDataCapacity;
MaxSizeType m_iDataSize;
};
#pragma pack()
}
#endif

• I have rolled back the last edit. Please see What to do when someone answers. – 200_success Nov 18 '15 at 18:31
• What's the class-template Sizer for? – Deduplicator Nov 18 '15 at 20:42
• if possible, be as fast or faster than std::vector Yep; not going to happen. std::vector is highly optimized, has had thousands of people look at the code for over a decade picking it apart and making it as efficient as possible. You are not going to come in and write something faster or more stable. If you do things perfectly you may achieve as fast but that's unlikely. – Martin York Nov 18 '15 at 21:33
• Are these actually vectors that change size at runtime? In one comment you mentioned you're creating 23 million of them for processing 3d data, which to me suggests a bulk body of data that you have more information about than you are actually using. Is it possible that you might know the size of each vector beforehand? If so, much of the complexity of a vector like class goes away. – Cort Ammon Nov 18 '15 at 22:39
• Like @Cort said, you will save much more memory and get better performance using a single std::vector to store a 2D or 3D array. See stackoverflow.com/questions/936687/… for example. You only need each row to be a separate vector if you need to add a column on the fly without shuffling around all existing row data (or if you need a "ragged" array where different rows are different lengths). You want your whole matrix stored in one big block of memory, not each row allocated and tracked separately. – Peter Cordes Nov 19 '15 at 1:18

Size Requirements

You talk about wanting to "use less memory" than std::vector. But std::vector doesn't use that much memory. It's three pointers. I guess if you set your MaxSizeType to int instead of size_t, you can have a vector of 16 bytes instead of 24, but I would really have to see what you're doing that that difference should matter.

Performance

There's two glaring issues that jump out at me as far as performance goes. I suspect this would be substantially slower than std::vector.

First one is on push_back:

void push_back(DataType element){
if (m_iDataCapacity <= m_iDataSize)
{
_Reserve(m_iDataCapacity + 1);
}
m_iDataSize++;
}


First, you're taking your DataType by value. That's incurring an extra copy, which you don't want to do. Secondly, your resize policy is increasing capacity by one. This means that your push_back() is expected $O(n)$. There's an easy explanation for this too: once we reach our capacity, we will have to _Reserve() on every subsequent push_back(), which means we're copying $n$ elements every time. The right thing to do is to increase capacity by a constant factor.

The next issue comes from indexing:

DataType& operator[](MaxSizeType id)
{
if (id < 0 || id >= size())
throw std::invalid_argument("Not enought memory");
}


First, the exception is misleading. A better exception type would be std::out_of_range, and a message indicating this - since the issue isn't that we ran out of memory. That's an error that we would throw if allocation fails (in _Reserve, you do the same thing - there you should throw std::bad_alloc).

But the main problem is this kills performance because on every lookup, we have a branch. Every time. And branches are slow. That's why on std::vector, operator[] is defined simply as:

reference
operator[](size_type __n)
{
return *(this->_M_impl._M_start + __n);
}


If you want bounds checking, you can provide a separate member function called at().

Other Issues

You're missing a lot of other nice features that std::vector provides:

• Missing iterators, begin(), and end().
• Missing const overloads of member functions
• This cast is unnecessary, since pData is already a DataType.

((DataType*)pData)->~DataType();

• First of all thanks Barry for your help. Regarding the size im going to use unsigned char which will save me 14bytes since im allocating 23000000 vectors thats alot of memory. Regarding the memory allocation. i´m not using new to alocate memory . Im actually using std::realloc the line new (pDest)DataType(*pOrig); does not allocates memory, thats why i use free. – Jaime Machado Nov 18 '15 at 16:37
• @JaimeMachado 2.3 million vectors?!? – Barry Nov 18 '15 at 16:44
• Last time I had to implement a similar thing (think std::valarray for operators but std::array for the rest) the branch itself in the operator[] was mostly irrelevant since it's predicted extremely well by the branch predictor (the check always fails) and the compiler put the exception-throwing code out of the hot path. The real problem was that the exception-creation code was big enough to prevent the function from being inlined, so it was the function call overhead to kill performance. Separating the throw in a function may give the bounds checking at extremely reduced cost. – Matteo Italia Nov 18 '15 at 20:30
• Do you really need dynamically resizable vectors, or would a far simpler and more efficient std::array suffice? – Deduplicator Nov 18 '15 at 20:33
• A branch is the "main thing" that kills performance!? A successfully-predicted branch is practically free, while even a failed branch prediction (which will be rare in this case) is still faster than a single integer division. And all of these things are orders of magnitude faster than a single allocation. The real performance-killer here was the excess allocations in push_back(). I wrote a blog post relating to timings here. – BlueRaja - Danny Pflughoeft Nov 19 '15 at 0:44
• There's an issue with your naming convention. Names starting with an underscore, followed by a capital letter (e.g.: _Reserve) and double underscore (e.g.: __DATAARRAY_H__), are using a notation reserved for future expansion of the Standard Library and compiler extensions. To avoid name clashes, prefer not using the underscore prefix on your own names. You can find more details about the naming rules of C++ in here: What are the rules about using an underscore in a C++ identifier?

• None of your class methods are const, which means I can't, for instance, call operator[] on a const DataArray instance. Methods that don't change member data should always be declared as const. More about const member functions in here.

• Consider adding a move constructor and operator. It might optimize your class quite a bit by allowing the compiler to avoid unnecessary copies.

realloc essentially does a memcpy to the newly allocated buffer. This will create issues if the move construction is non-trivial and/or the moved-from object still needs proper destruction.

If this is the case for the DataType then you should allocate a new buffer and placement-move-construct into the new buffer, destruct the objects in the old buffer and finally free the old buffer.

• A link on SO for that: stackoverflow.com/questions/33706528/… oops, nearly forgot to vote ;-) – Deduplicator Nov 18 '15 at 20:37
• +1 this is the real issue here. The class has to have something like this: static_assert(std::is_trivially_copyable<DataType>::value, "Only trivial types!") – Shaggi Nov 18 '15 at 22:28
• @Shaggi or use a mutually template-disabled pair of reserve functions where one uses realloc for trivial types and the other that does the method I described for all others. – ratchet freak Nov 18 '15 at 22:38
• @ratchetfreak Yes, you're right, that would be a perfect solution. – Shaggi Nov 18 '15 at 22:40
• @ratchetfreak Would this problem happen even if im not allocating memory with new. If you take a look at line new (m_aData + m_iDataSize)DataType(element); I´m not alocating memory i´m using the memory that was previously allocated with realloc. And before freeing the memory i call the destructor for each object. – Jaime Machado Nov 19 '15 at 12:41

### Reserved Identifiers:

An identifier with a leading underscore followed by a capital letter is reserved for use by the system in all scopes.

            inline void _Reserve(MaxSizeType size)
inline void _CopyData(const DataArray& dArray)
inline void _Delete_Data(DataType* begin, DataType* end)


### Use constructors to initialize all members

            DataArray(MaxSizeType size) :m_iDataSize(0){
_Reserve(size);
}


Looks good. But _Reserve() does not always initialize all the remaining members!! (If size == 0) the two remaining members are left undefined.

Also doing this is bad practice because you are assuming that somebody that modifies _Reserve() knows the contract it has with the constructor (ie that it must initialize those two members). The contract is not specified anywhere...

### Dead code should be removed

            void reserve(MaxSizeType size){
}


### Pass values by reference.

            void push_back(DataType element){
///     ^^^   parameter copied


### Resizing for more than you need.

                if (m_iDataCapacity <= m_iDataSize)
{
_Reserve(m_iDataCapacity + 1);
}


This is very inefficient if you add lots of elements in a row. Once you reach the initial size every time you push back you are reserving more capacity. When you hit the limit reserve more than you need so that you don't have to reserve every time.

### Provide const versions of some methods:

            DataType& operator[](MaxSizeType id)


There should be two version of this method. This will allow your object to use in const contexts (thus allowing you to build const correct code).

            DataType&       operator[](MaxSizeType id);
DataType const& operator[](MaxSizeType id) const;


### Operator [] is non checking

                if (id < 0 || id >= size())
throw std::invalid_argument("Not enought memory");


For efficiency operator[] does not check bounds (as after testing you have fixed all those bugs). For code where the index is calculated at run time and needs to be validated you usually provide the method at(MaxSizeType id).

### That's not the correct exception:

                if (id < 0 || id >= size())
throw std::invalid_argument("Not enought memory");


This is an out of range access. There is already an exception specifically for this. Alos it has nothing to do with "enought" memory.

### Prefer to use the copy and swap idiom

This assignment constructor is not exception safe.

If _Reserve throws an exception then the objects data is not in a consistent state. Because you have called the destructor on all the members (but not reset the size of the array and not copied new values into their place).

You should never destroy old data if there is a possibility of failure.

            DataType& operator=(const DataArray& dArray)
{
if (this == &dArray)
return *this;
_Reserve(dArray.m_iDataCapacity);  // If this throws your out of luck.
_CopyData(dArray);                 // Because this is not called
return *this;                      // to set the correct members.
}


### These look like it should be const methods.

            MaxSizeType size(){
return m_iDataSize;
}

MaxSizeType Capacity(){
return m_iDataCapacity;
}


### There is a bug in _Reserve.

If this is called from the assignment operator after all the elements have been deleted. Now if there is a realoc failure. The you are calling _Delete_m_aData() which calls _Delete_Data() which calls the destructor on the objects again. Even though they have previously been destroyed.

                    else{
throw std::invalid_argument("Not enought memory");
}


### Different types of brace style

Be consistent.

        DataArray(const DataArray& dArray)
{
_Reserve(dArray.m_iDataCapacity);
_CopyData(dArray);
}
void reserve(MaxSizeType size){
}


### Move Semantics not supported.

Your class does not provide move semantics. Supporting them would make your class a whole bunch more efficient it a lot of situations.

• void push_back(DataType element){ If the parameter must be copied in that function, sometimes it is preferred to pass it by value and move the copy in the function, so we don't need to overload on DataType&& and const DataType&. – jingyu9575 Nov 19 '15 at 9:37