Heap Memory Fragmentation

CS 321 Lecture, Dr. Lawlor, 2006/02/27

Memory allocators like new have a fatal flaw: once memory has been allocated at a particular location, the memory is stuck there forever.  This means if you repeatedly allocate a mix of big and small blocks, then delete the big blocks, the small blocks are left cluttering up ("fragmenting") the allocated space.  This unordered "heap" allocation is a headache, especially for long-running programs or low-memory machines.

Currently, the only workarounds for memory fragmentation are:
  1. Be sure to deallocate everything you've allocated, both big and small blocks.  However, sometimes the logic of the program requires some blocks live longer than others!
  2. Allocate long-lived or small blocks beforehand, all in one continguous peice.
Method (2) can be accomplished fairly easily in C++ with the standard header "<new>" and the funky technique of "placement new".  That is, C++ actually lets you allocate a pointer beforehand (say, in one contiguous piece), then call a class's constructor on that pointer *without* allocating memory. 

The syntax is bizarre: instead of an ordinary memory-allocating new like
    className *p=new  className(args);
you say
    className *p=new(destPointer)  className(args);
And then instead of allocating memory, "new(destPointer)" will just call the constructor using the space at destPointer, which must be at least "sizeof(className)" bytes.

Overall this looks like:
(Executable NetRun Link)
#include <new> /* needed for placement new */

// An ordinary class bar:
class bar {
public:
	std::string s;
	bar(const std::string &s_) :s(s_) {}
};

int foo(void) {
    char *buf=new char[2*sizeof(bar)]; // space for two bar objects.
    bar *b1=new(buf) bar("first"); //<- "placement" new
    buf+=sizeof(bar);
    bar *b2=new(buf) bar("second"); //<- "placement" new
    std::cout <<"b1:"<< b1->s <<"   b2:"<< b2->s <<"\n";
    return 0;
}


The Classic MacOS could "compact" memory, changing the addresses of allocated blocks.  This was possible because most memory was accessed via "handles", or pointers to pointers, which meant the address of the block itself could be changed without changing the block's handle.