vector, but without the overhead of dynamic memory allocation

[Virchanza]

I'm currently writing a program that deals with containers which
contain containers which contain containers.

I'm simplifying things here a bit, but what I have is something like:

class Port_Data {};

class IP_Data {

vector<Port_Data> ports;
};

class MAC_Data {

vector<IP_Data> ips;
};

class SnifferDatabase {

vector<MAC_Data> macs;
};

SnifferDatabase *const g_sdb = new SnifferDatabase();

The program works but it's way too slow. What's slowing things down is
the vector class's use of "malloc/new" to allocate memory (this can be
improved slightly by calling reserve() on the vectors beforehand).

Now I don't know if I'm inventing the wheel here or not, but I've put
something together that fixes my performance problem.

Basically, I've created an Adapter class that lets you use a normal
array just as if it were a vector (it cuts out the dynamic memory
allocation). I get the feeling this has been done before??? My code
now looks like:

class Port_Data {};

class IP_Data {

SuperArray<Port_Data,255> ports;
};

class MAC_Data {

SuperArray<IP_Data,255> ips;
};

class SnifferDatabase {

SuperArray<MAC_Data,255> macs;
};

SnifferDatabase *const g_sdb = new SnifferDatabase();

Now, as you can see, there's only one case of dynamic memory
allocation (i.e. when the g_sdb variable gets initialised).

My particular Adapter class is different from an std::vector in a few
ways:
* It can't be copy-constructed or assigned to (this is purely for my
own needs in my own program).
* The "push_back" method can take an argument of any type (again, this
is for my own program).

Anyway here's my code for SuperArray:

#include <cstddef>

template< typename T, std::size_t len >
class SuperArray {

private:

/* ------ Prevent copy-construction and assignment------ */
SuperArray(SuperArray const &);

SuperArray &operator=(SuperArray const &);
/* ----------------------------------------------------- */

char unsigned raw_mem[ sizeof( T[len] ) ];

T *const pbegin;

T *pend;

T const *const pend_of_allocated_space;

public:

/* ---------- First here comes the types ---------- */
typedef std::size_t size_type;

typedef T value_type;

typedef T &reference;
typedef T const &const_reference;

typedef T *iterator, *pointer;
typedef T const *const_iterator, *const_pointer;
/* ------------------------------------------------ */

SuperArray()
: pbegin( static_cast<T*>( static_cast<void*>(raw_mem) ) ),
pend( pbegin ),
pend_of_allocated_space( pbegin + len )
{
/* Nothing */
}

bool empty() const { return pend == pbegin; }

size_type capacity() const { return len; }

size_type max_size() const { return len; }

size_type size() const { return pend - pbegin; }

reference operator[](size_t const i) { return pbegin; }
const_reference operator[](size_t const i) const { return
pbegin; }

iterator begin() { return pbegin; }
const_iterator begin() const { return pbegin; }

iterator end() { return pend; }
const_iterator end() const { return pend; }

reference front() { return *pbegin; }
const_reference front() const { return *pbegin; }

reference back() { return pend[-1]; }
const_reference back() const { return pend[-1]; }

template<class X>
void push_back(X const &val)
{
if ( pend_of_allocated_space == pend )
{
/* Wups we're full! */
throw -1;
}

/* Let the following throw if it wants to */
::new(pend) T(val);

++pend; /* This doesn't happens if the placement new throws
*/
}

void pop_back()
{
back().~T();

--pend;
}

void clear()
{
while ( !empty() )
pop_back();
}

};

Of course I could add stuff to it like rbegin() and rend() but I don't
need that stuff in my program right now.

 

[Qi]

I'm currently writing a program that deals with containers which
contain containers which contain containers.

I'm simplifying things here a bit, but what I have is something like:

You may check Array and Intrusive containers in boost library.
They may do what you need.

http://www.boost.org/doc/libs/1_46_0/

 

[red floyd]

You may check Array and Intrusive containers in boost library.
They may do what you need.

http://www.boost.org/doc/libs/1_46_0/

Or std::tr1::array (C++03/TR1) or std::array (C++0x)

 

[Goran]

I'm currently writing a program that deals with containers which
contain containers which contain containers.

I'm simplifying things here a bit, but what I have is something like:

class Port_Data {};

class IP_Data {

    vector<Port_Data> ports;

};

class MAC_Data {

    vector<IP_Data> ips;

};

class SnifferDatabase {

    vector<MAC_Data> macs;

};

SnifferDatabase *const g_sdb = new SnifferDatabase();

The program works but it's way too slow. What's slowing things down is
the vector class's use of "malloc/new" to allocate memory (this can be
improved slightly by calling reserve() on the vectors beforehand).

Once you've done a sufficiently big vector::reserve, there is no
additional allocation done by the vector. And yet, you say that this
improved things slightly. That is a clear-cut indication that
allocations done by the vector are not a problem (because there aren't
any!).

IOW... If you don't show your actual code, your performance results,
and your performance requirements, on an OPTIMIZED build, I don't
believe you, and you should not believe yourself when saying this,
either.

I put this to you: your problem is more likely to be in excessive
copying of things. (Re)allocation might be a problem, I am not denying
that in general, but I don't think that's your case, and I don't think
that you exhausted first rule of performance: eliminate busywork
(first target: random copying of stuff).

Goran.

 

[Juha Nieminen]

Once you've done a sufficiently big vector::reserve, there is no
additional allocation done by the vector. And yet, you say that this
improved things slightly. That is a clear-cut indication that
allocations done by the vector are not a problem (because there aren't
any!).

That would be incorrect: Of course std::vector is going to make at least
one allocation (eg. when you call reserve()).

If I understood correctly, the original poster's wrapper around a
static array is probably something like this:

template<typename Value_t, unsigned kCapacity>
class StaticArrayWrapper
{
Value_t valueArray[kCapacity];

public:
// Public member functions similar to the ones in std::vector
};

Notice that unlike std::vector, the above class makes no memory
allocations at all. This makes a huge difference when you instantiate
it many times. For example:

class A
{
std::vector<SomeType> data;

public:
A() { data.reserve(123); } // Makes an allocation
};

class B
{
StaticArrayWrapper<SomeType, 123> data; // Makes no allocations
};

std::vector<A> aVector(1000); // Makes 1001 allocations in total
std::vector<B> bVector(1000); // Makes 1 allocation in total

The difference is very significant.

 

[Paul]

Once you've done a sufficiently big vector::reserve, there is no
additional allocation done by the vector. And yet, you say that this
improved things slightly. That is a clear-cut indication that
allocations done by the vector are not a problem (because there aren't
any!).

IOW... If you don't show your actual code, your performance results,
and your performance requirements, on an OPTIMIZED build, I don't
believe you, and you should not believe yourself when saying this,
either.

I put this to you: your problem is more likely to be in excessive
copying of things. (Re)allocation might be a problem, I am not denying
that in general, but I don't think that's your case, and I don't think
that you exhausted first rule of performance: eliminate busywork
(first target: random copying of stuff).

Yes the code needs to be copy optimised and also I think Juha has made a
good point.

What is seems to need is ownership of the array/vector in the SnifferDB , I
think in pointers so I use dynamics arrays(ofc you could have pointers to
vectors):

class port_data{};

class IP_data{
port_data* p_port;
virtual void reserve(int val, port_data* p_data){};
public:
void reserve(int val){reserve(val, p_port);};
};

class MAC_data{
IP_data* p_ip;
virtual void reserve(int val, IP_data* p_data){};
public:
void reserve(int val){reserve(val, p_ip);}
};

class SnifferDB: public IP_data, public MAC_data{
MAC_data* p_mac;
void reserve(int val, IP_data* p_data){/*Allocate IP_data*/;}
void reserve(int val, port_data* p_data){/*Allocate port_data*/;}
};

So in the end you have 1 polymorphic object with 3 pointers, and easy access
to each array/vectors.

If you want to pass the data around just pass a pointer and no copying is
needed. Depending on program design it may require the flexiblity of a
common Interfase for IP_Data, MAC_data and port_data. This would then be a
diamond inheretance design though and this may introduce some complexity
with the virtual functions.