views:

407

answers:

10

Consider the following code:

class A
{
    B* b; // an A object owns a B object

    A() : b(NULL) { } // we don't know what b will be when constructing A

    void calledVeryOften(…)
    {
        if (b)
            delete b;

        b = new B(param1, param2, param3, param4);
    }
};

My goal: I need to maximize performance, which, in this case, means minimizing the amount of memory allocations.

The obvious thing to do here is to change B* b; to B b;. I see two problems with this approach:

  • I need to initialize b in the constructor. Since I don't know what b will be, this means I need to pass dummy values to B's constructor. Which, IMO, is ugly.
  • In calledVeryOften(), I'll have to do something like this: b = B(…), which is wrong for two reasons:
    • The destructor of b won't be called.
    • A temporary instance of B will be constructed, then copied into b, then the destructor of the temporary instance will be called. The copy and the destructor call could be avoided. Worse, calling the destructor could very well result in undesired behavior.

So what solutions do I have to avoid using new? Please keep in mind that:

  • I only have control over A. I don't have control over B, and I don't have control over the users of A.
  • I want to keep the code as clean and readable as possible.
+8  A: 

Simply reserve the memory required for b (via a pool or by hand) and reuse it each time you delete/new instead of reallocating each time.

Example :

class A
{
    B* b; // an A object owns a B object
    bool initialized;
public:
    A() : b( malloc( sizeof(B) ) ), initialized(false) { } // We reserve memory for b
    ~A() { if(initialized) destroy(); free(b); } // release memory only once we don't use it anymore

    void calledVeryOften(…)
    {
        if (initialized)
            destroy();

        create();
    }

 private:

    void destroy() { b->~B(); initialized = false; } // hand call to the destructor
    void create( param1, param2, param3, param4 )
    {
        b = new (b) B( param1, param2, param3, param4 ); // in place new : only construct, don't allocate but use the memory that the provided pointer point to
        initialized = true;
    }

};

In some cases a Pool or ObjectPool could be a better implementation of the same idea.

The construction/destruction cost will then only be dependante on the constructor and destructor of the B class.

Klaim
Don't forget the `free(b)` in the destructor of `A`. Otherwise this seems pretty good. Also, you forget to set `initialized` to true. Lastly, I'd move the `if(initialized)` into the `destroy` function. Then you just `destroy(); create()` in `calledVeryOften`, and `destroy(); free(b)` in the destructor.
GMan
anon
Yes I just added it while you posted, and added some infos.
Klaim
Oops, Neil wins. No `malloc`/`free`.
GMan
Neil> It seems overkill to me but in fact it's really dependant on the implementation. I wouldn't even write it with malloc in a lot of cases -- but never used a vector. It's just to give the idea.
Klaim
Well, why not, I'll rewrite it.
Klaim
After some thoughts, I'll let that way, it's much simpler to understand and answers the question.However I agree that for a safer implementation I shouldn't use malloc/free directly.Feel free to answer this question with a better implementation to let the reader see how he could write it better (or edit my answer?)
Klaim
GMan> fixed initialization related code, thanks, I forgot that.
Klaim
In your constructor, you should check to make sure that `malloc()` didn't fail and return `NULL` (which it sometimes does). Or you might be able to use `new` instead, in which case you'd change the destructor.
Chris Lutz
+5  A: 

How about allocating the memory for B once (or for it's biggest possible variant) and using placement new?

A would store char memB[sizeof(BiggestB)]; and a B*. Sure, you'd need to manually call the destructors, but no memory would be allocated/deallocated.

   void* p = memB;
   B* b = new(p) SomeB();
   ...
   b->~B();   // explicit destructor call when needed.
Kornel Kisielewicz
Storing a static buffer *may* cause alignment issues. Better to use `malloc` once in the beginning.
GMan
You can avoid alignment problems with a declspec(align), and besides, malloc may not be aligned like you want either (IIRC it only aligns to 8 bytes). The char array keeps the instance of B close to A in memory, so you might get fewer cache misses.
celion
@celion: `malloc` allocates to the maximum alignment; it's guaranteed to be aligned for anything you could allocate. (Otherwise, how would we properly allocate anything in C?)
GMan
@GMan: ish. It should be guaranteed to be aligned for anything, but SIMD types create problems there. So in practice it's aligned for types required by the standard, but not necessarily for other built-in types.
Steve Jessop
@Steve: Instristics are always an exception. :]
GMan
+1  A: 

Are you sure that memory allocation is the bottleneck you think it is? Is B's constructor trivially fast?

If memory allocation is the real problem, then placement new or some of the other solutions here might well help.

If the types and ranges of the param[1..4] are reasonable, and the B constructor "heavy", you might also consider using a cached set of B. This presumes you are actually allowed to have more than one at a time, that it does not front a resource for example.

sdg
+3  A: 

If B correctly implements its copy assignment operator then b = B(...) should not call any destructor on b. It is the most obvious solution to your problem.

If, however, B cannot be appropriately 'default' initialized you could do something like this. I would only recommend this approach as a last resort as it is very hard to get safe. Untested, and very probably with corner case exception bugs:

// Used to clean up raw memory of construction of B fails
struct PlacementHelper
{
    PlacementHelper() : placement(NULL)
    {
    }

    ~PlacementHelper()
    {
        operator delete(placement);
    }

    void* placement;
};

void calledVeryOften(....)
{
    PlacementHelper hp;

    if (b == NULL)
    {
        hp.placement = operator new(sizeof(B));
    }
    else
    {
        hp.placement = b;
        b->~B();
        b = NULL;  // We can't let b be non-null but point at an invalid B
    }

    // If construction throws, hp will clean up the raw memory
    b = new (placement) B(param1, param2, param3, param4);

    // Stop hp from cleaning up; b points at a valid object
    hp.placement = NULL;
}
Charles Bailey
A: 

I'd go with boost::scoped_ptr here:

class A: boost::noncopyable
{
    typedef boost::scoped_ptr<B> b_ptr;
    b_ptr pb_;

public:

    A() : pb_() {}

    void calledVeryOften( /*…*/ )
    {
        pb_.reset( new B( params )); // old instance deallocated
        // safely use *pb_ as reference to instance of B
    }
};

No need for hand-crafted destructor, A is non-copyable, as it should be in your original code, not to leak memory on copy/assignment.

I'd suggest to re-think the design though if you need to re-allocate some inner state object very often. Look into Flyweight and State patterns.

Nikolai N Fetissov
A: 

Erm, is there some reason you can't do this?

A() : b(new B()) { }

void calledVeryOften(…) 
{
    b->setValues(param1, param2, param3, param4); 
}

(or set them individually, since you don't have access to the B class - those values do have mutator-methods, right?)

BlueRaja - Danny Pflughoeft
B is immutable after construction.
e-t172
Why would they have such methods? Blindly providing such things is terrible practice.
anon
@Neil: Providing mutators is bad practice? What?
BlueRaja - Danny Pflughoeft
@BlueRaja You mean you do provide such things? For all your member variables? Oh dear...
anon
@Neil: You're saying providing setters is bad practice? What do you do, make your variables public?
BlueRaja - Danny Pflughoeft
@BlueRaja It is wrong to be able to set a member variable via a "setter" with no reference to the object's semantics (and changing it with respect to those semantics is often impossible). Most std::string implementations maintain a "size" data member - do you think you should be able to change it via a "setSize" function?
anon
@Neil: I didn't say that; but, since all of e-t172's parameters *are* set by the user (of the object), it seems quite possible that they're all exposed to the user. I didn't realize B is immutable.
BlueRaja - Danny Pflughoeft
@BlueRaja It doesn't matter if the object is mutable or not. It is simply wrong, in the general case, to provide "setter" functions for all data members of a class.
anon
@Neil: Once again, I never said all data members. However, most of the time members which can be set in the constructor are given mutators.
BlueRaja - Danny Pflughoeft
+1  A: 

Like the others have already suggested: Try placement new..

Here is a complete example:

#include <new>
#include <stdio.h>

class B
{
  public:
  int dummy;

  B (int arg)
  {
    dummy = arg;
    printf ("C'Tor called\n");
  }

  ~B ()
  {
    printf ("D'tor called\n");
  }
};


void called_often (B * arg)
{
  // call D'tor without freeing memory:
  arg->~B();

  // call C'tor without allocating memory:
  arg = new(arg) B(10);
}

int main (int argc, char **args)
{
  B test(1);
  called_often (&test);
}
Nils Pipenbrinck
+9  A: 

I liked Klaim's answer, so I wrote this up real fast. I don't claim perfect correctness but it looks pretty good to me. (i.e., the only testing it has is the sample main below)

It's a generic lazy-initializer. The space for the object is allocated once, and the object starts at null. You can then create, over-writing previous objects, with no new memory allocations.

It implements all the necessary constructors, destructor, copy/assignment, swap, yadda-yadda. Here you go:

#include <cassert>
#include <new>

template <typename T>
class lazy_object
{
public:
    // types
    typedef T value_type;
    typedef const T const_value_type;
    typedef value_type& reference;
    typedef const_value_type& const_reference;
    typedef value_type* pointer;
    typedef const_value_type* const_pointer;

    // creation
    lazy_object(void) :
    mObject(0),
    mBuffer(::operator new(sizeof(T)))
    {
    }

    lazy_object(const lazy_object& pRhs) :
    mObject(0),
    mBuffer(::operator new(sizeof(T)))
    {
        if (pRhs.exists())
        {
            mObject = new (buffer()) T(pRhs.get());
        }
    }

    lazy_object& operator=(lazy_object pRhs)
    {
        pRhs.swap(*this);

        return *this;
    }

    ~lazy_object(void)
    {
        destroy();
        ::operator delete(mBuffer);
    }

    // need to make multiple versions of this.
    // variadic templates/Boost.PreProccesor
    // would help immensely. For now, I give
    // two, but it's easy to make more.
    void create(void)
    {
        destroy();
        mObject = new (buffer()) T();
    }

    template <typename A1>
    void create(const A1 pA1)
    {
        destroy();
        mObject = new (buffer()) T(pA1);
    }

    void destroy(void)
    {
        if (exists())
        {
            mObject->~T();
            mObject = 0;
        }
    }

    void swap(lazy_object& pRhs)
    {
        std::swap(mObject, pRhs.mObject);
        std::swap(mBuffer, pRhs.mBuffer);
    }

    // access
    reference get(void)
    {
        return *get_ptr();
    }

    const_reference get(void) const
    {
        return *get_ptr();
    }

    pointer get_ptr(void)
    {
        assert(exists());
        return mObject;
    }

    const_pointer get_ptr(void) const
    {
        assert(exists());
        return mObject;
    }

    void* buffer(void)
    {
        return mBuffer;
    }

    // query
    const bool exists(void) const
    {
        return mObject != 0;
    }

private:
    // members
    pointer mObject;
    void* mBuffer;
};

// explicit swaps for generality
template <typename T>
void swap(lazy_object<T>& pLhs, lazy_object<T>& pRhs)
{
    pLhs.swap(pRhs);
}

// if the above code is in a namespace, don't put this in it!
// specializations in global namespace std are allowed.
namespace std
{
    template <typename T>
    void swap(lazy_object<T>& pLhs, lazy_object<T>& pRhs)
    {
        pLhs.swap(pRhs);
    }
}

// test use
#include <iostream>

int main(void)
{
    // basic usage
    lazy_object<int> i;
    i.create();
    i.get() = 5;

    std::cout << i.get() << std::endl;

    // asserts (not created yet)
    lazy_object<double> d;
    std::cout << d.get() << std::endl;
}

In your case, just create a member in your class: lazy_object<B> and you're done. No manual releases or making copy-constructors, destructors, etc. Everything is taken care of in your nice, small re-usable class. :)

EDIT

Removed the need for vector, should save a bit of space and what-not.

EDIT2

This uses aligned_storage and alignment_of to use the stack instead of heap. I used boost, but this functionality exists in both TR1 and C++0x. We lose the ability to copy, and therefore swap.

#include <boost/type_traits/aligned_storage.hpp>
#include <cassert>
#include <new>

template <typename T>
class lazy_object_stack
{
public:
    // types
    typedef T value_type;
    typedef const T const_value_type;
    typedef value_type& reference;
    typedef const_value_type& const_reference;
    typedef value_type* pointer;
    typedef const_value_type* const_pointer;

    // creation
    lazy_object_stack(void) :
    mObject(0)
    {
    }

    ~lazy_object_stack(void)
    {
        destroy();
    }

    // need to make multiple versions of this.
    // variadic templates/Boost.PreProccesor
    // would help immensely. For now, I give
    // two, but it's easy to make more.
    void create(void)
    {
        destroy();
        mObject = new (buffer()) T();
    }

    template <typename A1>
    void create(const A1 pA1)
    {
        destroy();
        mObject = new (buffer()) T(pA1);
    }

    void destroy(void)
    {
        if (exists())
        {
            mObject->~T();
            mObject = 0;
        }
    }

    // access
    reference get(void)
    {
        return *get_ptr();
    }

    const_reference get(void) const
    {
        return *get_ptr();
    }

    pointer get_ptr(void)
    {
        assert(exists());
        return mObject;
    }

    const_pointer get_ptr(void) const
    {
        assert(exists());
        return mObject;
    }

    void* buffer(void)
    {
        return mBuffer.address();
    }

    // query
    const bool exists(void) const
    {
        return mObject != 0;
    }

private:
    // types
    typedef boost::aligned_storage<sizeof(T),
                boost::alignment_of<T>::value> storage_type;

    // members
    pointer mObject;
    storage_type mBuffer;

    // non-copyable
    lazy_object_stack(const lazy_object_stack& pRhs);
    lazy_object_stack& operator=(lazy_object_stack pRhs);
};

// test use
#include <iostream>

int main(void)
{
    // basic usage
    lazy_object_stack<int> i;
    i.create();
    i.get() = 5;

    std::cout << i.get() << std::endl;

    // asserts (not created yet)
    lazy_object_stack<double> d;
    std::cout << d.get() << std::endl;
}

And there we go.

GMan
Is a `std::vector<char>` guaranteed to be immune to alignment issues? (If so, how: I'm quite curious.)
Chris Lutz
Hard to choose the best answer amongst those using placement new… yours is the most general so I'll give you the tick :)
e-t172
@Chris: Yes. AFAIK: Dynamic memory *always* caters to alignment issues. (Contrary to a static buffer.) For what it's worth, this answer could use `malloc(sizeof(T))` or `::operator new(sizeof(T))` and not a vector, to save some memory. I may update it to do so. (May as well, since we have to provide all the copy-functions anyway.)
GMan
And thank you, @e-t172.
GMan
Steve Jessop
@Steve: Correct. My flag is merely null in `mObject`, and the only defined way to use an object is when it's initialized. The only way to initialize an object in some memory is placement-new.
GMan
Steve Jessop
Oh right. I don't like improper allocations :]
GMan
+1 for genericity :)
Klaim
@Steve: Made a stack-allocated version. If you don't mind, could you test the speed of that? Should be constant time (and very fast). Also, I used `operator new` instead of `vector`, now.
GMan
Same speed as my very simple "automatic" version. Yours is maybe slightly slower on GCC 4 (3.8s vs 3.7s), but not a big enough difference to believe in. Only change to your code was to add a 2-arg `create` so that I can use it with my A class.
Steve Jessop
@Steve: Sweet, thanks. And in general, for what it's worth copy and swap could be reintroduced by using a temporary aligned buffer + `memset`, but of course copying/swapping is no longer trivial.
GMan
What use is memset? I'd have thought you'd want placement new again, but this time using a copy ctor of B. If B doesn't have a copy ctor then you're stuck but that's OK, because if B doesn't have a copy ctor then we wouldn't expect the questioner's original class to be copyable either.
Steve Jessop
@Steve: The problem is when one of the objects is null. What do we copy? The "correct" way is to swap buffers.
GMan
Sure, if you can't swap a pointer to B, then you want to swap B, but you can't because it's immutable. So you can't have a nothrow swap for A unless the copy ctor of B is nothrow, which in turn means you can't have strongly exception-safe assignment for A unless B has a nothrow copy ctor. I guess A could use some traits of B, and only "inline" B into an array member if the traits say it's safe. Otherwise, stick with new.
Steve Jessop
In `destroy`, after `mObject->~T();`, shouldn't you set `mObject` to NULL?
e-t172
@e-t172: Right you are. You see, I liked Klaim's original answer so much I implemented his bug... :] Fix'd.
GMan
A: 

Just have a pile of previously used Bs, and re-use them.

Mike Dunlavey
+3  A: 

A quick test of Martin York's assertion that this is a premature optimisation, and that new/delete are optimised well beyond the ability of mere programmers to improve. Obviously the questioner will have to time his own code to see whether avoiding new/delete helps him, but it seems to me that for certain classes and uses it will make a big difference:

#include <iostream>
#include <vector>

int g_construct = 0;
int g_destruct = 0;

struct A {
    std::vector<int> vec;
    A (int a, int b) : vec((a*b) % 2) { ++g_construct; }
    ~A() { 
        ++g_destruct; 
    }
};

int main() {
    const int times = 10*1000*1000;
    #if DYNAMIC
        std::cout << "dynamic\n";
        A *x = new A(1,3);
        for (int i = 0; i < times; ++i) {
            delete x;
            x = new A(i,3);
        }
    #else
        std::cout << "automatic\n";
        char x[sizeof(A)];
        A* yzz = new (x) A(1,3);
        for (int i = 0; i < times; ++i) {
            yzz->~A();
            new (x) A(i,3);
        }
    #endif

    std::cout << g_construct << " constructors and " << g_destruct << " destructors\n";
}

$ g++ allocperf.cpp -oallocperf -O3 -DDYNAMIC=0 -g && time ./allocperf
automatic
10000001 constructors and 10000000 destructors

real    0m7.718s
user    0m7.671s
sys     0m0.030s

$ g++ allocperf.cpp -oallocperf -O3 -DDYNAMIC=1 -g && time ./allocperf
dynamic
10000001 constructors and 10000000 destructors

real    0m15.188s
user    0m15.077s
sys     0m0.047s

This is roughly what I expected: the GMan-style (destruct/placement new) code takes twice as long, and is presumably doing twice as much allocation. If the vector member of A is replaced with an int, then the GMan-style code takes a fraction of a second. That's GCC 3.

$ g++-4 allocperf.cpp -oallocperf -O3 -DDYNAMIC=1 -g && time ./allocperf
dynamic
10000001 constructors and 10000000 destructors

real    0m5.969s
user    0m5.905s
sys     0m0.030s

$ g++-4 allocperf.cpp -oallocperf -O3 -DDYNAMIC=0 -g && time ./allocperf
automatic
10000001 constructors and 10000000 destructors

real    0m2.047s
user    0m1.983s
sys     0m0.000s

This I'm not so sure about, though: now the delete/new takes three times as long as the destruct/placement new version.

[Edit: I think I've figured it out - GCC 4 is faster on the 0-sized vectors, in effect subtracting a constant time from both versions of the code. Changing (a*b)%2 to (a*b)%2+1 restores the 2:1 time ratio, with 3.7s vs 7.5]

Note that I've not taken any special steps to correctly align the stack array, but printing the address shows it's 16-aligned.

Also, -g doesn't affect the timings. I left it in accidentally after I was looking at the objdump to check that -O3 hadn't completely removed the loop. That pointers called yzz because searching for "y" didn't go quite as well as I'd hoped. But I've just re-run without it.

Steve Jessop
I don't understand this part: "the GMan-style (destruct/placement new) code takes twice as long". It looks like the DYNAMIC=0 version took about half as long, not twice as long.
bk1e