C++ array of derived class vs array of pointers of base class to derived objects - why is amount of memory allocated so much different?

I need some clarification on an issue I don't quite understand. Using the two scenarios that follow, I would have thought that the amount of memory allocated would roughly be the same. However, scenario 2 gives me a bad_alloc exception after a while and appears to be chewing up memory like crazy (using Window's Task Manager as a proxy for the amount of memory allocated to the process). The following is compiled on Windows 32bit using MSVC10.

Say I have following base class:

template<class T>
class Base
{
protected:
    T x;
public:
    Base() {}
    Base(T _x) : x(_x){}
    virtual bool func() = 0;
};

Now, as for the derived class:

template<class T>
class Derived : public Base<T>
{
public:
    Derived开发者_JS百科() {}
    Derived(T _x) :  Base(_x){}
    bool func() { return true; };
};

Now consider two cases. First, allocate a dynamic array of the Derived class and fill it up with Derived objects, ie:

int main()
{
    int size = SOME_LARGE_NUMBER;
    Derived<int>* d = new Derived<int>[size];
    for (int i = 0; i < size; i++)
    {
        d[i] = Derived<int>(i);
    }

    // delete here
}

Second, allocate a dynamic array of pointers of the Base class and have them point to actual instances of the Derived class, ie:

int main()
{
    int size = SOME_LARGE_NUMBER;
    Base<int>** d = new Base<int>*[size];
    for (int i = 0; i < size; i++)
    {
        d[i] = new Derived<int>(i);
    }

    // delete here
}

I set SOME_LARGE_NUMBER in either scenario to 40,000,000. In the first scenario, the program completes fine - in the second one I get a bad_alloc exception. I am wondering whether this is expected behaviour or whether I am overlooking something here? If so, what's a better way of doing this? Note that I get the same problem using vector<Base<int>*> and boost::ptr_vector<Base<int>>.

Well, if you allocate in one block, it requires size times the size of Derived and a small overhead for single allocation. But if you allocate separately, it requires size times the size of pointer (4 bytes), plus size times the size of Derived and size (plus one) times the overhead for allocation, which is at least 8 bytes. If you are near the edge, the 12 times size extra bytes might well be the difference between still fitting in memory and not.

I won't tell you for certain that the allocator overhead is exactly 8 bytes, but making it less than 2 pointers would be quite complicated and it's highly unlikely the Microsoft standard allocator is that sophisticated.

Note, that since std::vector and boost::ptr_vector do exactly the same think as you do manually, they fail the same way. They are just wrappers to ensure delete will be called where appropriate, nothing more.

All the overheads would be double for 64-bit targets. Pointer is 8 bytes there and the allocator overhead is usually 2 pointers.

In the second example you are allocating memory to store both pointers to the objects and the objects themselves, which by itself uses at least:

(sizeof(Base<int>*)+sizeof(Derived<int>))*size

Depending on the pointer size on your platform this could result in quite an overhead compared to the first example.

Dynamically allocating each object separately as in the second example is also potentially wasteful, as the runtime could provide only memory blocks of certain sizes that badly match sizeof(Derived<int>).

I think in first case you haven't got enough memory in one block. In second case you have enough memory for the array of pointers and have enough memory to allocate for the objects different places/blocks in memory.

I don't see anything obviously wrong with either implementation (perhaps I havn't had enough coffee this morning.) I would suggest looking at the allocated memory in the debugger and see what is happening. For instance, if it crashes out at the same allocation item in example two, then it's likely you are running out of memory. (Which doesn't explain why the first implementation works and the second does not, but it will at least get you on the right path.)

You could also compare the block sizes of memory allocated in the debugger and ensure that they are, in fact, the same size when allocated.

Sorry I can't offer more.

EDIT: I did not read the code well, It seems that the overhead in the second example is in double memory allocation one for the pointer and the other for the object itself :)