vector, but without the overhead of dynamic memory allocation

Discussion in 'C++' started by Virchanza, Mar 9, 2011.

  1. Virchanza

    Virchanza Guest

    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.
    Virchanza, Mar 9, 2011
    #1
    1. Advertising

  2. Virchanza

    Qi Guest

    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/
    Qi, Mar 9, 2011
    #2
    1. Advertising

  3. Virchanza

    red floyd Guest

    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)
    red floyd, Mar 9, 2011
    #3
  4. Virchanza

    Goran Guest

    On Mar 9, 4:25 am, 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).


    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.
    Goran, Mar 9, 2011
    #4
  5. Goran <> 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.
    Juha Nieminen, Mar 9, 2011
    #5
  6. Virchanza

    Paul Guest


    >"Goran" <> wrote in message
    >news:...
    >On Mar 9, 4:25 am, 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).


    >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.
    Paul, Mar 9, 2011
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dave Williamson
    Replies:
    2
    Views:
    445
    Rocky Moore
    Aug 15, 2004
  2. Ken
    Replies:
    24
    Views:
    3,837
    Ben Bacarisse
    Nov 30, 2006
  3. chris
    Replies:
    6
    Views:
    972
    chris
    Oct 28, 2005
  4. Replies:
    8
    Views:
    1,894
    Csaba
    Feb 18, 2006
  5. Daniel Lidström
    Replies:
    15
    Views:
    627
    Brendon Costa
    Oct 31, 2007
Loading...

Share This Page