How does delete[] "know" the size of the operand array?

Question

Foo* set = new Foo[100];
// ...
delete [] set;

You don't pass the array's boundaries to delete[]. But where is that information stored? Is it standardised?

Bombard

sourceforge.net/projects/fastmm is open source and replaces the memory-manager. Here you can find out how memory management works and where the informations are come from for allocate and delete memories. – Middleoftheroader

Note that FastMM is specific to the Delphi/C++Builder compilers only, it is not a general-purpose memory manager for C++. It is not even written in C++. – Xerophyte

Answer 1

When you allocate memory on the heap, your allocator will keep track of how much memory you have allocated. This is usually stored in a "head" segment just before the memory that you get allocated. That way when it's time to free the memory, the de-allocator knows exactly how much memory to free.

Darter

Note that this only applies to array allocations in C++. All other allocations rely on the size of the type. Some libraries do store all allocation sizes, usually only in debugging mode. – Tadzhik

There is absolutely no reason why this information should not be available to the programmer. I can pass a pointer to a function and free it, but to get the size myself in that same function I have to pass around an extra parameter. Does that make any sense? – Northwestward

@Mark, it makes a small amount of sense, because in theory it does free the allocator to always store the size of the allocated block (which may differ from the size of the requested block). Certain allocator designs may need this information for their own purposes, or may not be sophisticated enough to use type information to track the size of non-array heap allocations, etc. Forcing the allocator to store the requested size (so that you wouldn't need to pass the array size yourself) might be a small encumbrance, but it could have performance impacts on conceivable allocator designs. – Dipterous

Sorry, but this answer misses the point. What QuantumPete described is basically "How free knows how much memory to deallocate". Yes, the memory block size is stored "somewhere" by malloc (normally in the block itself), so that's how free knows. However, new[]/delete[] is a different story. The latter basically work on top of malloc/free. new[] also stores the number of elements it created in the memory block (independently of malloc), so that later delete[] can retrieve and use that number to call the proper number of destructors. – Dateless

I.e. physically two counters are stored in the block: block size (by malloc) and element count (by new[]). Note, that the former cannot be used to calculate the latter, since in general case the size of the memory block can be larger than really necessary for the array of requested size. Also note that the array element counter is only needed for types with non-trivial destructor. For types with trivial destructor the counter is not stored by new[] and, of course, not retrieved by delete[]. – Dateless

Mark's point stands though. Since this information must be stored, there's no reason we shouldn't be able to access it as well. If it overallocates, vector could have used that to it's advantage, but as it is, vector must do pointless extra allocations and copies. If it doesn't overallocate, then we can get the array size of dynamic arrays. Either or both would be useful information. – Millenary

@Mark, if you use A* = new B(); delete A; how does compiler know what size of memory to free? – Scuta

@sasha.sochka: The compiler doesn't know. delete A simply calls the A destructor (if it is virtual, polymorphism calls the B destructor), and then passes the memory block pointed to by A to the memory manager for freeing. The memory manager knows how much memory it allocated to satisfy the new B() call. – Xerophyte

@MooingDuck It's not true that it "must" be stored. There are allocators that cannot determine the size of every block at all times. For example, buddy allocators may be designed such that they are unable to tell the size of an "odd" block unless its corresponding "even" block is free. – Bonsai

@DavidSchwartz fair enough for things with trivial destructors. For nontrivial destructors, the allocator needs to store the item count. – Millenary

@MooingDuck Only for an array allocator, otherwise the item count is always one. – Bonsai

Downvoted because, as AnT noted, it completely misses the point and doesn't answer the question. This really should be deleted (heh), or fixed to give the correct answer (as given in AnT's second comment). – Selfcentered

Where is the "head" segment? – Inclusive

@AnT Would it be possible for an implementation to use an allocator that always allocates blocks in such a way that the array size can be calculated from the block size, though? I.e. for T[] the amount of "extra" space in the block would always be less than sizeof(T), which would let the runtime compute the array size using truncated division. Or is the implementation not able to require such a property of the allocator? – Spaulding

@Kyle Strand: It is probably quite possible. Let's say, an implementation aligns each block size on W-byte boundary. Then for an T[N] array (S = sizeof(T[N])) it can allocate the properly aligned number of bytes B = (S + W - 1) / W * W, but store in the block header the actually requested number of bytes S. Then the array size will be correctly deducible from the stored value of S. The actual aligned block size B is also easily deducible from S. – Dateless

@AnT I talked to an LLVM dev the other day who confirmed that indeed this is how new[] and delete[] are implemented by default. – Spaulding

@RemyLebeau Your explanation makes sense! But some questions: Is the 'memory manager' a part of the OS? According to AnT's comment, the size of the array is recorded in the memory block, so it seems that the compiler knows the size of the array. (It depends on the implementation, but I mean a typical implementation) – Curt

@starriet "Is the 'memory manager' a part of the OS?" - no, it is part of the compiler and runtime library (but may use the OS' memory API internally). When your code calls new/new[], the compiler gens code to ask the MM to allocate space for the object/array (which internally tracks how much was allocated), and then calls the type's constructor(s) on that memory. When your code calls delete/delete[], the compiler gens code to call the type's destructor(s) on the memory, and then give the memory to the MM to free (which will refer to the tracking to know how much to free)... – Xerophyte

@starriet ... how the MM tracks the size of the allocation is indeed an implementation detail. Storing the size inside the allocated memory itself is a common implementation, but not a required one, or the only way. – Xerophyte

Answer 2

ONE OF THE approaches for compilers is to allocate a little more memory and to store a count of elements in a head element.

Example how it could be done:

Here

int* i = new int[4];

compiler will allocate sizeof(int)*5 bytes.

int *temp = malloc(sizeof(int)*5)

Will store "4" in the first sizeof(int) bytes

*temp = 4;

and set i

i = temp + 1;

So i will points to an array of 4 elements, not 5.

And deletion

delete[] i;

will be processed in the following way:

int *temp = i - 1;
int numbers_of_element = *temp; // = 4
... call destructor for numbers_of_element elements
... that are stored in temp + 1, temp + 2, ... temp + 4 if needed
free (temp)

Corcyra

Can this be modified to get array lengths at runtime? – Fluidics

Yes, if you want to abuse UB. For example you could do ptr[-1]. – Carbajal

Answer 3

The information is not standardised. However in the platforms that I have worked on this information is stored in memory just before the first element. Therefore you could theoretically access it and inspect it, however it's not worth it.

Also this is why you must use delete [] when you allocated memory with new [], as the array version of delete knows that (and where) it needs to look to free the right amount of memory - and call the appropriate number of destructors for the objects.

Kinin

Answer 4

It's defined in the C++ standard to be compiler specific. Which means compiler magic. It can break with non-trivial alignment restrictions on at least one major platform.

You can think about possible implementations by realizing that delete[] is only defined for pointers returned by new[], which may not be the same pointer as returned by operator new[]. One implementation in the wild is to store the array count in the first int returned by operator new[], and have new[] return a pointer offset past that. (This is why non-trivial alignments can break new[].)

Keep in mind that operator new[]/operator delete[]!=new[]/delete[].

Plus, this is orthogonal to how C knows the size of memory allocated by malloc.

Zsigmondy

Answer 5

Basically its arranged in memory as:

[info][mem you asked for...]

Where info is the structure used by your compiler to store the amount of memory allocated, and what not.

This is implementation dependent though.

Fabled

Answer 6

This isn't something that's in the spec -- it's implementation dependent.

Punnet

Answer 7

Because the array to be 'deleted' should have been created with a single use of the 'new' operator. The 'new' operation should have put that information on the heap. Otherwise, how would additional uses of new know where the heap ends?

Toreutics

Answer 8

This is a more interesting problem than you might think at first. This reply is about one possible implementation.

Firstly, while at some level your system has to know how to 'free' the memory block, the underlying malloc/free (which new/delete/new[]/delete[] generally call) don't always remember exactly how much memory you ask for, it can get rounded up (for example, once you are above 4K it is often rounded up to the next 4K-sized block).

Therefore, even if could get the size of the memory block, that doesn't tell us how many values are in the new[]ed memory, as it can be smaller. Therefore, we do have to store an extra integer telling us how many values there are.

EXCEPT, if the type being constructed doesn't have a destructor, then delete[] doesn't have to do anything except free the memory block, and therefore doesn't have to store anything!

Tosha

Answer 9

It is not standardized. In Microsoft's runtime the new operator uses malloc() and the delete operator uses free(). So, in this setting your question is equivalent to the following: How does free() know the size of the block?

There is some bookkeeping going on behind the scenes, i.e. in the C runtime.

Rajkot

Not true. Before calling free, the delete[] needs to call destructors first. For this knowing total allocations size is not enough. Actually new[] and delete[] works different for plain and destructed types in VC++. – Juvenal