I’ve been meaning to use virtual memory to manage game objects for quite some time. The idea of doing a copy on write to update an object while keeping a consistent readable version is still very tempting but I haven’t been able to work out the details just yet (or even if something like that makes sense). The next best thing is to have quick object allocations at predictable addresses.

The inspiration to finally put virtual memory into practice came from Virtual Memory Tricks. This is an excellent article that goes over the variety of things you can do using virtual memory.

What we’re going to do is keep all game objects in a huge array. And I mean *all* game objects. Since we don’t know how many there are at the start let’s pick a number; 1048576 sounds pretty good. Also, because the code is highly platform specific let’s pick a platform as well. In this case we’ll be working on Windows.

On Windows, pages in virtual memory can be in one of three states. Free, reserved, and committed. A free page is not in use and is available to be reserved or committed. A reserved page is marked for future use in the virtual address space and requires no physical memory. A committed page is a reserved page that is backed by physical memory; this is the kind of page that takes up space in RAM. These three states should make it somewhat clear how we’re going to allocate space for all the game objects. We’re going to reserve enough pages for all objects but only commit them as needed.

Here’s how the pages are reserved using VirtualAlloc:

constexpr size_t MAX_OBJECTS = 1024 * 1024;
class Object { /* ... */ };
void* objectsBase = VirtualAlloc( nullptr, sizeof( Object ) * MAX_OBJECTS,
                                  MEM_RESERVE, PAGE_READWRITE );

Passing nullptr as the first argument tells the operating system to pick the starting address for us. We can totally pick this address manually and have objects allocated in the same place every time. At the end the whole region is released using VirtualFree:

VirtualFree( objectsBase, 0, MEM_RELEASE );

I tried two methods of allocating objects from this virtual memory region. The first method uses SEH(structured exception handling) to catch the EXCEPTION_ACCESS_VIOLATION exception to commit pages on demand. The second method keeps track of the amount of allocated space and commits a page when an allocation crosses to an uncommitted page. A quick benchmark revealed that the second method to be faste.

Method 1: SEH and EXCEPTION_ACCESS_VIOLATION

Sometime at initialization assign a cursor to point to the location of the next object allocation:

Object* nextObject = reinterpret_cast< Object* >( objectsBase );

When allocating an object, try twice. The first pass can potentially throw an access violation if it happens on a page that has not yet been committed. The exception handler will commit the page so the allocation can be attempted again.

Object* Allocate()
{
	Object* object = nullptr;

	for ( int i{}; i < 2; ++i )
	{
		__try
		{
			object = new ( nextObject ) Object();
			nextObject++;
		}
		__except ( GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION )
		{
			VirtualAlloc( nextObject, sizeof( Object ), MEM_COMMIT, PAGE_READWRITE );
		}
	}

	return object;
}

On my system the release build allocates 1024 * 1024 = 1048576 in about 0.4 seconds.

Method 2: Committed Memory Counter

As in method 1 keep a pointer to the next object allocation.

Object* nextObject = reinterpret_cast< Object* >( objectsBase );

This time also keep track of the size of a page along with the number of bytes that have been committed.

DWORDLONG bytesAvailable{};
DWORDLONG pageSize{};

SYSTEM_INFO info{};
GetSystemInfo( &info );
pageSize = info.dwPageSize;

To allocate an object first check to see if there’s enough committed space for it. If there isn’t enough commit the next page.

Object* Allocate()
{
	if ( bytesAvailable < sizeof( Object ) )
	{
		VirtualAlloc( nextObject, pageSize, MEM_COMMIT, PAGE_READWRITE );
		bytesAvailable += pageSize;
	}

	Object* object = new ( nextObject ) Object();
	nextObject++;
	bytesAvailable -= sizeof( Object );

	return object;
}

In release mode allocating 1024 * 1024 = 1048576 requires about 0.17 seconds.

Share