In C++, what is the difference between new and new[] for array allocations

Question

I am aware of the differences between free and delete in C++. But one thing I never understood is why in C malloc/free can allocate de-allocate both single 'objects' and arrays but in C++ we need to use the correct new/delete vs new[]/delete[] pair.

Searching on Stackoverflow, it seems that in C++, new[] allocates extra memory to hold the size of the allocated array and new only allocates the memory to the object itself. And because of that, you should be aware of this extra overhead.

If the previous paragraph is indeed the case, then how malloc/free handles this overhead? Or they just accept this overhead? And if it is tolerable in C, why not in C++?

On the other hand, in case it's not because of memory overhead, but because of calling constructors and destructors, couldn't the compiler be smart enough to generate the appropriate code under the hood and let the programmer just write new/delete for both single objects and arrays of objects?

I am writing a compiler for a toy language whose semantics is similar to C++ and it seems that it is possible to let the compiler decides how to allocate and de-allocate only using new/delete, but as C++ uses new/delete and new[]/delete[], maybe there's a catch that I am not seeing right now. Maybe something related to polymorphism and virtual tables?

If you're curious, my naive idea is to simple allocate an integer together with the object/array where this integer is the size of the array or simple 1 in case of being an object. Then, when calling delete, it checks the value of the integer, if it is 1, it calls the destructor. If it greater than 1, then it iterates the array calling the destructor to each object in the array. As I said, it seems to work and would let the programmer just write new/delete instead of new/delete vs new[]/delete. But then again, maybe there's a catch that I am not seeing.

Edited part:

After some answers, I decided to try to provide some pseudo-code and a better background.

In C language, memory allocations are usually made with malloc() and de-allocations with free(). Either if you are allocating a single POD, a single struct or an array, malloc() fits all these cases. There is no need for different versions of malloc() if you are allocating a single struct vs a malloc_array() version if you are allocating an array. At least at the public API level. In other words, it seems it doesn't matter if you are allocating a few bytes or many bytes, there will be no overhead for bookkeeping the allocation size information.

As many of you are aware, including myself, new and delete do more than just allocate and de-allocate memory. New allocate memory and call the constructor and delete calls the destructor and then de-allocate memory. But in C++, you need to be aware if you are allocating just a single object or an array of objects. In case you are allocating an array, you need to use the new[]/delete[] pair.

In C, if you implement a binary tree, nodes will be allocated with malloc and de-allocated with free and in C++ with new and delete. But if you are implementing something like the vector class in C++, in C you still would use malloc/free, but now in C++ you would need to use new[]/delete[] (considering a sane implementation without too much black magic).

Consider the following pseudo-code that is executed by the compiler. In this pseudo-code, the delete function somehow gets access to the malloc internals and knows how many bytes there are, which in turn can be easily used to calculate how many objects there are. As this delete implementation is using malloc internals to know how much memory is allocated, in theory there should be no overhead of bookkeeping.

// ClassType is a meta type only know by the compiler
// it stores a class info such as name, size, constructors and so on
void *new(ClassType c) {
    // allocates memory with malloc. Malloc() do the storage bookkeeping
    // note that somehow malloc is allocating just a single object
    c *ptr = malloc(sizeof(c));

    // now, call the constructor of the requested class
    c.constructor(ptr);

    // return the new object
    return ptr;
}

void *new(ClassType c, size_t n) {
    c *ptr = malloc(sizeof(c) * n);

    // iterate over the array and construct each object
    for (i = 0; i < n; ++i) {
        c.constructor(ptr[i]);
    }

    return ptr;
}

// this delete version seems to be able to de-allocate both single
// objects and arrays of objects with no overhead of bookkeeping because
// the bookkeeping is made by malloc/free. So I would need 
// just a new/delete pair instead of new/delete vs new[]/delete[]
// Why C++ doesn't use something like my proposed implementation? 
// What low-level details prohibits this implementation from working?
void delete(ClassType c, void *ptr) {
    // get raw information of how many bytes are used by ptr;
    size_t n = malloc_internals_get_size(ptr);

    // convert the number of bytes to number of objects in the array
    n = c.bytesToClassSize(n);

    c* castedPointer = (c*) ptr;

    // calls the destructor
    for (i = 0; i < n; ++i) {
        c.destructor(castedPointer[i]);
    }

    // free memory chunk
    free(ptr);
}

Rossuck

free will not call the destructor, delete will. If there's a side effect in the destructor you are basically adding a bug which will be hard to find. – Pustulate

If you look at malloc declaration, it accepts size in bytes and returns an unitialized chunk of memory of type void *, which free later releases. On the contrary, new constructs obects and delete destructs them so it needs to know it should act on each element of the array. It could be made array-aware, but they chose such a boilerplate approach, I have no idea why. – Fugue

I am aware of this, but it doesn't explain why free can handle both single 'object' and arrays but in C++ we need delete/delete[]. If my question is not clear on this topic, please help me improve it – Rossuck

And because of that, you should be aware of this extra overhead. new could be doing a lot of things. So could malloc. Or whatever is beneath malloc. You could ask for 2 bytes and get a 4K allocation if that what the source of memory has available to give. – Tmesis

Your "naive idea" implements delete[]. To implement delete it is not necessary to have that integer at all, hence lesser overhead – Ptero

@HadleySiqueira "it doesn't explain why free can handle both single 'object' and arrays" - malloc()/free() has no concept of arrays at all. malloc() just allocates a single chunk of memory, and free() just deallocates it. They don't care what is stored inside that memory, that is your responsible to handle. new/new[], on the other hand, do care what is in the memory, so they need to differentiate. – Justen

@RemyLebeau what I meant is that it seems that there is no overhead to malloc allocate a single byte vs many bytes and free still be able to de-allocate properly having access to how many bytes were allocated. On the other hand, considering the other answers, it seems that the overhead for new[]/delete[] seems to be considerable. I know malloc just allocates memory, but somehow knows how much was allocated and there is no overhead. So why can't new[]/delete[] uses the same storage scheme as malloc/free? Which in turn would be superfluous and lead to only use new/delete – Rossuck

@HadleySiqueira the overhead of malloc()/free() is implementation-defined. What you describe is just 1 possible implementation. The standard doesn't dictate any implementation. And anyway, malloc() and new[] are semantically different, as new[]/delete[] have to loop through array elements individually for non-trivial types, while malloc()/free() don't. So the element count has to be stored somewhere no matter what, whereas the byte count can be optimized. And FYI, many implementations of new/delete and new[]/delete[] use malloc()/free() internally – Justen

Answer 1

Some clever implementations of malloc don't actually keep track of the size per allocation (by clever use of rounding up), thus it have extremely low space overhead. They'll allocate a large block of memory, and anytime a dev allocates <64 bytes, it'll just use the next 64 bytes of this block, and mark a single bit elsewhere that tracks that this block of 64 bytes is now in use. Even if the user only wants to allocate 1 byte, it hands out a whole block. This means each allocation has only a single bit overhead, so every 8 allocations has a shared byte of overhead. Practically nothing. (There are far smarter strategies than this, this is just a simplified example)

new and delete can share this super-low-overhead implementation, because delete knows to always destroy one object, regardless of the amount of space it actually has. This is again, super fast, and has low space overhead.

delete[] can't do that because it has to know exactly how many destructors to call. So it has to keep track of how many items are in the array, up to std::size_t, which means ~4 bytes have to be added to every new[]. If the data requires an alignment >4, then each allocation also has to have wasted padding bytes between the count and the first item in the array. And delete[] therefore has to know how to look past the padding, find the count, so it knows exactly how many objects to destroy. This takes both time and more space, for every allocation.

C++ gives you the choice between "always works, but slower and bigger", and "only works for one item, but faster and smaller", so the program can run as fast as possible.

Slender

Answer 2

why in C malloc/free can allocate de-allocate both single 'objects'

Malloc doesn't create any objects. It allocates "raw memory" which doesn't contain any objects. Correspondingly, free doesn't destroy any objects. new expressions do create objects, and delete destroys an object, while delete[] destroys an array of objects.

In order for the language implementation to know how many objects need to be destroyed by delete[], that number has to be stored somewhere. In order for the language implementation to know how many objects need to be destroyed by delete, that number does not need to be stored anywhere because it is always one.

Storing a number is not free, and storing an unused number is an unnecessary overhead. The different forms of deletion exist so that the language implementation can destroy the correct number of objects without having to store the number of objects created by a non-array new.

then how malloc/free handles this overhead?

malloc/free doesn't have this overhead since it doesn't create or destroy objects. As such, there is nothing that needs to be handled.

There is an analogous issue of storing the number of allocated bytes that malloc does need to deal with. There is no analogous separate function for allocation or freeing of a single byte. This may be because such use case is probably rare. Malloc has more clever ways of dealing with storing this because allocating more memory than is needed is not observable, while such trick is not possible with number of objects because creation and destruction of objects is observable (at least in case of non-trivial types).

new typically deals with the issue of storing the number of allocated bytes through using malloc internally.

couldn't the compiler be smart enough to generate the appropriate code under the hood

Not without some kind of overhead, no. With overhead yes, it could.

But then again, maybe there's a catch that I am not seeing.

I'm not sure if it is a catch that you haven't seen, but the catch with your idea is the overhead of the integer that is to be allocated even when a single object is allocated.

Mors

You've answered the title, but the body of the question is far more complex and your answer does not answer the real question, which is why are there non-array forms of new and delete – Slender

@MooingDuck it seems to me the core issue of the question is answered by noting that delete[] has to call several destructors – Ptero

@M.M: The OP is aware of that, and thus why delete[] is needed. OP seems to want to know why there is delete which can't do that. – Slender

"seems to want to know why there is delete which can't do that". That's right. I would like to know the reason for this – Rossuck

Answer 3

Not all implementations have a difference between new/delete vs new[]/delete[] but they exist because new expression act differently in case of array. thing is that the new expression is not just call to the new operator, underlying operators might be identical:

#include <iostream>
// class-specific allocation functions
struct X {
    static void* operator new(std::size_t sz)
    {
        std::cout << "custom new for size " << sz << '\n';
        return ::operator new(sz);
    }
    static void* operator new[](std::size_t sz)
    {
        std::cout << "custom new[] for size " << sz << '\n';
        return ::operator new(sz);
    }
};
int main() {
     X* p1 = new X;
     delete p1;
     X* p2 = new X[10];
     delete[] p2;
}

But they maybe overloaded to different ones as well. It might be important difference for native compiler, if you're writing an interpreter or if you don't expect users to modify new\delete, you can do this differently. In C++ new expression call one constructor after allocating memory with provided function, new[] expression would call several and store the count. Of course if compiler got object-oriented memory model, like Java does, then array would be an object with property of size. Single object is just an array of one instance. And as you said, we won't need a separate delete expression.

Theorem

Then perhaps there were some use cases when these operators were proposed that could benefit from 'radical' different implementations? It could be. But as I am just a regular programmer, I never came across with such situation where I could benefit of having different implementations – Rossuck

@HadleySiqueira In specialized systems where small few objects might be less important than big long arrays but pose threat of defragmenting heap: you eventually loose ability to allocate a large array. Also, afaik on Windows allocation for array implemented differently because how memory model of OS works, at least in MS runtime. Java's memory model is object oriented and WM defragments and able move things around, the "pointer" there would be an ID of created memory object. On certain level Windows memory model acts in same way, App "lock" object in place and receives its address. – Theorem