why does std::allocator::deallocate require a size?

Question

std::allocator is an abstraction over the underlying memory model, which wraps the functionality of calling new and delete. delete doesn't need a size though, but deallocate() requires it.

void deallocate( T* p, std::size_t n );
"The argument n must be equal to the first argument of the call to allocate() that originally produced p; otherwise, the behavior is undefined."

Why?

Now I either have to make additional calculations before deallocating, or start storing the sizes that I passed to allocate. If I didn't use the allocator I wouldn't have to do this.

Pigmy

There is a movement toward supplying the size edplicitly because it leads to better optomization andgor faster heap code. Most of the time the compiler knows it when delete is called. I recall this from some Going Native or Boostcon talks about changes to allocator stuff. – Rumormonger

@JDługosz The compiler doesn't know it, the C library's implementation of free does, and the C++ library's implementation of delete [] does so independently, too. – Diacritical

@KubaOber See n3778. “The compiler shall call the sized version in preference to the unsized version when the sized version is available.” ergo, the compiler does know it, and as I said, it saves work for the memory manager to look it up based on the pointer. The allocator, like operator delete, follows this new principle. Find the presentation if you don’t beleive that or to get the reasons explained in detail. – Rumormonger

All the compiler knows is the size of the type of the instance being deleted. It'll work if it's the same size that the type originally allocated at a given location. If the type has morphed, e.g. due to in-place destructor and placement new, the sized delete will lead to undefined behavior :( Sure this isn't exactly everyday code, but sized delete preference kind-of forces your hand and makes you reallocate any time an object's type changes... I'm not sure if I like it. I'd love to see allocator benchmarks that show the benefit of this. I have code that is faster by in-place type changing. – Diacritical

Users of allocators know the size, but I wouldn't task the compiler with knowing the size. The compiler knows the size of the deleted type and assumes it is same as the size of the originally allocated type. This assumption needn't hold, so it seems to introduce new undefined behavior into the standard I think... Or, we must now pay attention to uphold that invariant in our code. – Diacritical

Answer 1

The design of the std::allocator API - the Allocator concept - is to facilitate the job of potential replacements.

std::allocator is an abstraction over the underlying memory model

It doesn't have to be! In general, an allocator does not need to use C malloc and free, nor delete or the not-in-place new. Yes, the default one usually does it, but the allocator mechanism isn't merely an abstraction over C's memory model. To be different is often the whole purpose of a custom allocator. Remember that allocators are replaceable: a particular std::allocator might not need the size for deallocation, but any replacements are likely to.

A compliant implementation of std::allocator is free to assert that you indeed pass the correct n to deallocate, and to otherwise depend on the size being correct.

It happens that malloc and free store the chunk size in its data structures. But in general an allocator might not do it, and requiring it to do so is premature pessimization. Suppose you had a custom pool allocator and were allocating chunks of ints. On a typical 64-bit system it'd be a 200% overhead to store a 64-bit size_t along with the 32-bit int. The user of the allocator is much better positioned to either store the size along in the allocation, or to determine the size in a cheaper fashion.

Good malloc implementations don't store allocation size for every small allocation; they and are able to derive the chunk size from the pointer itself e.g. by deriving a block pointer from the chunk pointer, and then inspecting the block header for the chunk size. That's but a detail of course. You could obtain the lower bound on the size using platform-specific APIs, such as malloc_size on OS X, _msize on Windows, malloc_usable_size on Linux.

Melissamelisse

Answer 2

It is often useful for memory-allocation algorithms to minimize the amount of overhead they require. Some algorithms which keep track of free areas rather than allocated areas can reduce the total amount of overhead to a low constant value with zero per-block overhead (book-keeping information is stored entirely within the free areas). On systems using such algorithms, an allocation request removes storage from the free pool, and a de-allocation request adds storage to the free pool.

If allocation requests for 256 and 768 bytes get satisfied using a contiguous region of the pool, the memory-manager state would be identical to what it would be if two requests for 512 bytes had been satisfied using that same region. If the memory manager were passed a pointer to the first block and asked to release it, it would have no way of knowing whether the first request had been for 256 bytes, or 512 bytes, or any other number, and thus no way of knowing how much memory should be added back to the pool.

Implementing "malloc" and "free" on such a system would require that it store the length of each block at the beginning of its region of storage and return a pointer to the next suitably-aligned address that would be available after that length. It's certainly possible for an implementation to do that, but it would add 4-8 bytes of overhead to each allocation. If the caller can tell the deallocation routine how much storage to add back to the memory pool, such overhead can be eliminated.

Decelerate

Answer 3

Furthermore, it is quite easy to accommodate this design point:   simply allocate things as a struct, and store the size as an element within that struct. Your code that calls the deallocator now knows what value to provide, since the structure itself contains it.

By doing this, you're essentially doing exactly what any other language-implementation might be graciously doing for you. You're just doing the same thing explicitly.

Now, given that we're talking about C++, which has oodles of great container-classes already built in, I would candidly encourage you to avoid "rolling your own" if you can possibly avoid it. Just find a way to use one of the nifty container-classes that the language and the standard library already provide.

Otherwise, be sure to package what you're building here as a home-grown container class. Be sure that the logic which deals with the allocator and the deallocator occurs only once in your program. (Namely, within this class.) Sprinkle it generously with logic that is specifically designed to detect bugs. (For instance, a sentinel value that is inserted into an object when it is allocated, and that must be found when the object is deallocated, and which is wiped-out just before it is. Explicit checks of the stored size-value to make sure that it makes sense. And so on.)

Refluent

Answer 4

You're not required to keep track of the size. The standard allocator does not keep track of the size because it assumes a size for all allocations. Of course, there are different types of allocators for different purposes. A block size allocator, as you may have guessed, has a fixed size. Some applications like video games pre-allocate memory all upfront and eliminate the overhead of needing to keep track of the size for each allocation.

The standard library tries to be as generic as possible. Some allocators need to keep track of the size, others do not, but all allocators are required to conform to the interface.

Dapper

This is wrong: Yes, the user of any allocator is required to keep track of the size, since the allocators are meant to be replaceable. std::allocator is is an implementation of an Allocator concept. All such implementations require the proper n to be passed to deallocate! They are free to ignore it, but the user should provide it nevertheless as the use of n is an implementation detail. The user can of course store the size in the allocation itself if she so chooses. – Diacritical

@KubaOber You seem to be misunderstanding my answer. You do not need to keep track of n if it's a fixed size. It is an implementation-detail. The standard cannot possibly predict how all allocators will be implemented. So the interface is rigid. – Dapper

It doesn't matter how you divine the n, as long as you pass the correct value, you're doing it right. Sure you don't need explicit storage for n, but you're obtuse if you say it as "you do not need to keep track of n". Yes, you do need to keep track of it, but not necessarily by using a variable or any other runtime storage. The typical malloc-using standard allocator doesn't assume any size for all allocations: you pass a correct n to allocate. If it uses free instead of delete[], it will need a correct n to invoke destructors! – Diacritical

Sorry, of course deallocate doesn't invoke destructors. – Diacritical

Answer 5

I do not have a conclusive proof, but my gut feeling is that allocator is not required to use C++ operator new/delete and might as well use memory management routines which do not have the capability of allocating arrays and knowing their sizes - like malloc, for example.

Pipit