C++ Deallocate exact size of memory

Question

I've thought about how I can improve the performance of reading of a list sort by an (unsigned) integer that is read in at the program start and won't change until the program exits. I thought about different possibilities but then I got an idea and I'd like to know if that's possible and if not, why not - because in my theory it should be possible for the computer.

I have a list with something like 10.000 entries, every entry has an unique ID (an the unique ID is not 0). Now what about allocating memory with the size object* pList = new(sizeof(object) * max_unique_id) and then deleting all the unused memory (check what unique id is not existing and free the memory at the position with the size sizeof(object))... you would be using only the needed memory and you could just access to a list entry with pList[unique_id] -> would be really, really fast... but you cannot delete a single element in a dynamic allocated array :/ At the program termination you can of course free all the elements, it's no problem to safe the pointer + sizes in a std::vector or sth like that.

That's why I'm asking if my theory is incorrect or if the system just does not allow it or where the problem is.

Answer 1

No, you can't control memory like that. However, it IS possible to cheat a little bit. If you are allocating big chunks of memory, you can make your own memory pool. That way, you can create the holes yourself and use that memory for other parts of your program.

I wouldn't recommend it though, as you may have issues with strict aliasing, as well as having to deal with more complexity in your code.

Rewinding just a little, you are forgetting about caching effects, which are significant. Keeping your objects packed closely together will likely have more effect on speed than making the lookup faster.

To achieve this you could use a simple hash to look up your objects, or you could just make a sparse index array of 16-bit indices.

Answer 2

You can, (though I have no idea why you want to), but you will have to write it as your own custom memory allocation and deallocation routine or class. Using the standard C++ library out of the box, you can't.

See some of the interfaces for allocating memory in C++

void* operator new  ( std::size_t );
void* operator new[]( std::size_t );
void* operator new  ( std::size_t, const std::nothrow_t&);
void* operator new[]( std::size_t, const std::nothrow_t&);

Taking void* operator new[]( std::size_t ); for example. There is absolutely no way the this routine knows how many objects are stored in the memory region that will be returned.

Same with it's matching function

 void operator delete[]( void* ptr );

it only takes a void pointer, there is absolutely no way it knows how many you want to delete. The memory allocator that provided memory starting with that block pointed by ptr magically knows the size it allocated, and hence deletes it appropriately

Answer 3

Use placement new.

---

object* pList = new(sizeof(object) * max_unique_id)

Do not do this. new is NOT malloc. But you also cannot do this instead:

object* pList = new object[max_unique_id];
delete object[1];

C++ does not allow to delete individually allocated elements of a dyanmically allocated array with a simple delete.

C++ allows you to create an object in a pre-allocated memory space by using placement new. In this case, you must manually call the constructor with a call to placement new and the destructor.

Reference: Malloc and constructors

A* a = (A*)malloc(sizeof(A));
new (a) A();

a->~A();
free(a);

In other words, supply the exact place where you want a specific object to be created. I would suggest that you use a loop:

// Allocate the space using malloc()
object* pList = std::malloc(sizeof(object) * max_unique_id);

// Allocate using a loop. I would not trust a parallelization of this code.
// Doing memory allocation in parallel without the proper locks and stuff
// is probably wrong.
for (auto i = 0; i < max_unique_id; ++i) {
  // Supply the point as the argument to placement new.
  new (&pList[i]) object(/* arguments go here */);
}

Then, when you're done using a certain object, say i = 20...

// Select the object
object* todelete_object = pList[i];
// Manually call the destructor.
todelete_object->~object()
// Now, free the memory.
std::free(todelete_object);

I use std::malloc() and std::free() as defined in the C++-style C standard library includes.