vector, but without the overhead of dynamic memory allocation

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[i]; } const_reference operator[](size_t const i) const { return pbegin[i]; } 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.

On 2011-3-9 11:25, Virchanza wrote: > > 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/

On 3/8/2011 7:34 PM, Qi wrote: > On 2011-3-9 11:25, Virchanza wrote: >> >> 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/ Or std::tr1::array (C++03/TR1) or std::array (C++0x)

On Mar 9, 4:25=A0am, Virchanza <virt...@lavabit.com> wrote: > 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 { > > =A0 =A0 vector<Port_Data> ports; > > }; > > class MAC_Data { > > =A0 =A0 vector<IP_Data> ips; > > }; > > class SnifferDatabase { > > =A0 =A0 vector<MAC_Data> macs; > > }; > > SnifferDatabase *const g_sdb =3D 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.

On 09/03/2011 03:25, Virchanza wrote: > > 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[i]; } > const_reference operator[](size_t const i) const { return > pbegin[i]; } > > 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. Your class would likely not work if placed on the stack due to alignment problems; check out the "vecarray" container I wrote instead: http://i42.co.uk/stuff/vecarray.htm It is open source and should satisfy your requirements. /Leigh

Goran <goran.pusic@gmail.com> wrote: > 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.

>"Goran" <goran.pusic@gmail.com> wrote in message >news:55bd9b44-8df2-4b34-8cc9-81b4d6f41296@r4g2000vbq.googlegroups.com... >On Mar 9, 4:25 am, Virchanza <virt...@lavabit.com> wrote: >> 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). 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.