Systematic Gaming

September 8, 2008

Load Times: Asynchronous Loading

Filed under: file management, game programming — Tags: , — systematicgaming @ 5:26 am

We looked at how files are read earlier, and saw how much time is wasted by waiting for file operations to finish. So the only real solution is to not wait for operations to complete. This is called asynchronous reading, where the file operation happens in parallel with our game, controlled by the OS.

Asynchronous file loading requires more structure and organization than normal file reading, so we’ll need to create a file manager to provide portable asynchronous loading. We will need to change how we handle file data inside out game to support this functionality. But it’s worth it because it gives us a huge win in load times, and in the end gives us a more robust game engine as a bonus.

Asynchronous File Reads

The biggest difference in asynchronous file operations is structuring your program to effectively use them. The flow of asynchronous files can be broken down into three stages

  • The program requests the device to perform the operation
  • The device executes the operation, in parallel with the program
  • The program completes the operation, once the device is finished executing

The general idea that you request your file read, do something else, then come back later and process the data. Requests are usually straightforward, with the OS file API returning a handle when you request the operation. The execution is handled by the OS, often in another thread or hardware. The completion will happen either by receiving a signal (via callback) or by polling the system, querying the status of the operation.

The exact approach varies by platform, let’s look at one way to perform asynchronous file operations on Windows.

HANDLE file = CreateFile(
        L"testfile",            // pointer to name of the file
        GENERIC_READ,           // access (read-write) mode
        0,                      // share mode
        NULL,                   // pointer to security attributes
        OPEN_EXISTING,          // how to create
        FILE_ATTRIBUTE_NORMAL | FILE_FLAG_OVERLAPPED,
        NULL );

// overlapped is Win32s async io file handle
OVERLAPPED overlapped;
memset( &overlapped, 0, sizeof(OVERLAPPED) );

// read 100 bytes of the file in overlapped mode
char buffer[1024];
ReadFile( file, buffer, 100, NULL, &overlapped );

// poll until completed
BOOL complete = false;
DWORD bytesTransferred = 0;
do
{
   // to make good use of overlapped IO, we really
   // should be doing something useful here
   complete = GetOverlappedResult(
      file, &overlapped, &bytesTransferred, FALSE);
}
while ( !complete );
assert( bytesTransferred == 100 );

The above Win32 code uses what Microsoft calls Overlapped IO, which essentially allows you to have multiple IO operations running at the same time, “overlapping” each other. Ignoring how ugly I think the Win32 API is, lets break down the key steps.

  1. Open a file (via CreateFile) with the overlapped flag, telling windows we’ll be doing async IO
  2. Create a OVERLAPPED structure which we use to track the state of an IO operation
  3. We request a few bytes, passing the OVERLAPPED structure to ReadFile
  4. The system executes our request while we loop
  5. We poll the overlapped IO system until it is complete

Steps 3-5 are the same key stages that we mentioned earlier. Now that we can use asynchronous IO, lets look at how we can use it in a game.

Integrating Asynchronous Files

To really take advantage of asynchronous IO we need to do something while the IO operation is being processes by the OS. To allow this our game objects will need to support asynchronous loading by deferring their creation.

If our basic object was like this:

class Object
{
   Object(const char *filename)
   {
      FILE *f = fopen(filename);
      fread( &data, dataSize, 1, f );
      fclose(f);
   }
}

We need to transform it to something like this:

class Object
{
   Object(const char *filename)
   {
      mFileHandle = AsyncLoad(filename, &data);
   }

   bool IsLoaded()
   {
      return mFileHandle.IsLoaded();
   }

   ASYNCFILE mFileHandle;
};

You can probably imagine that retro-fitting this type of change into an existing code base is difficult. You can no longer just create your Object and use it, you need to wait until the file requests have finished before the Object can finish instantiating. Ideally you’ve designed your game engine this way to begin with.

Designing a File Manager

So now that we understand the basic principles of asynchronous file loading, let’s design our own file manager. The file manager will be responsible of handling all file reads system-wide. When someone wants to read a file they’ll go through this file manager. Similar to the goals of a memory manager, we will treat the file system as a global resource and manage access as such.

A complete file manager will need to be robust and take care of all the edge cases and errors that you can encounter, such as what you do when someone ejects the DVD while you’re loading your game. The file manager should also be able to abstract the storage device, so you can read from not just the optical disc but also a hard drive if available or other more exotic formats like memory cards or the network.

However in this article we’ll just go over the basics – handling asynchronous file operations in a single thread. We won’t bother with file writing since it’s not very common in games.

We want to use the same interface on multiple platforms, so we’ll start by defining a class to represent individual asynchronous file operations

class FileOperation
{
   friend class FileManager;

public:
   FileOperation(HANDLE handle = HANDLE);
   ~FileOperation();

   enum Operation
   {
      OP_NONE,
      OP_OPEN,
      OP_CLOSE,
      OP_SEEK,
      OP_READ,
   };

   enum State
   {
      STATE_NONE,    // initial creation state
      STATE_BEGIN,   // operation requested
      STATE_END,     // operation completed
      STATE_ERROR,   // operation encountered an error
   };

   State GetState() const { return mState; }
   Operation GetOperation() const { return mOperation; }

   void Open(const wchar_t* filename);
   void Close();
   void Seek( uint64_t offset );
   void Read( void *buffer, uint64_t size );

private:
   State mState;
   Operation mOperation;

   void *mBuffer;
   uint64_t mSize;
   uint64_t mPosition;

   HANDLE mHandle;
   OVERLAPPED mOverlapped;
};

Here’s a partial implementation using the Win32 overlapped I/O

FileOperation::FileOperation()
: mState(STATE_NONE), mOperation(OP_NONE), mHandle(handle)
{
   memset(&mOverlapped, 0, sizeof(OVERLAPPED);
}

void FileOperation::Open(const wchar_t *filename)
{
   assert( OP_NONE == mOperation && STATE_NONE == mState );

   mOperation = OP_OPEN;

   mHandle = CreateFile(
        filename,            // pointer to name of the file
        GENERIC_READ,           // access (read-write) mode
        0,                      // share mode
        NULL,                   // pointer to security attributes
        OPEN_EXISTING,          // how to create
        FILE_ATTRIBUTE_NORMAL | FILE_FLAG_OVERLAPPED,
        NULL );

   // CreateFile is a synchronous open operation, so our operation
   // is either completed
   if ( INVALID_HANDLE_VALUE == mHandle )
   {
      mState = STATE_ERROR;
   }
   else
   {
      mState = STATE_END;
   }
}

void FileOperation::Read( void *buffer, uint64_t size )
{
   assert( INVALID_HANDLE_VALUE != mHandle ); 

   mOperation = OP_READ;
   mState = STATE_BEGIN;

   mBuffer = buffer;
   mSize = size;

   ReadFile( mHandle, mBuffer, mSize, NULL, &mOverlapped );
}

This class is pretty low-level, and a little awkward to use by itself. It simply manages the state of a single operation. However since 99% of the time we want to read an entire file at once, so lets create a higher level file manager to handle this. Our manager will keep track of multiple operations and properly handle to open -> read -> close flow.

typedef int FileHandle;
const int INVALID_FILE_HANDLE = -1;

class FileManager
{
public:
   FileHandle LoadFile(const wchar_t *filename, void **buffer, uint64_t *size);
   bool IsCompleted(const FileHandle &handle);

   void Update();

private:
   FileHandle GetFreeOperation();

   // list of operations
   enum
   {
      MAX_OPERATIONS = 32,
   };
   FileOperation mOperations[MAX_OPERATIONS];

   // structure to store user parameters (to be returned to user)
   struct OperationParams
   {
      void **mBufferPtr;
      uint64_t *mSizePtr;
   };
   OpertaionParams mParams[MAX_OPERATIONS];
};

FileHandle FileManager::LoadFile(const wchar_t *filename, void **buffer, uint64_t *size)
{
   FileHandle file = GetFreeOperation();
   if ( INVALID_FILE_HANDLE == file ) return file;

   mOperations[file].Open(filename);
   mParams[file].mBufferPtr = buffer;
   mParams[file].mSizePtr = size;

   return file;
}

void FileManager::Update()
{
   for ( int i = 0; i < MAX_OPERATIONS; i++ )
   {
      switch ( mOperations[i].GetOperation() )
      {
         case OP_NONE:
            break;

         case OP_OPEN:
            // we're opened, so start reading
            DWORD fileSize = GetFileSize( mOperations[i].mHandle, NULL );

            void *fileBuffer = new uint8_t[fileSize];
            *mParams[i].mBufferPtr = fileBuffer;
            *mParams[i].mSizePtr = fileSize;

            mOperations[i].Read( fileBuffer, fileSize );
            break;

         case OP_READ:
            // overlapped reads are asynchronous, so poll, if done close
            bool complete = GetOverlappedResult(
                  mOperations[i].mHandle,
                  &mOperations[i].mOverlapped, NULL, FALSE);            

            if ( complete )
            {
               mOperations[i].mState = STATE_END;
               mOperations[i].Close();
            }
            break;

         case OP_CLOSE:
            // nothing to do here
            break;
      }
   }
}

bool FileManager::IsCompleted(FileHandle handle)
{
   assert( handle >= 0 && < MAX_OPERATIONS );
   return mOperations[handle].GetState() == STATE_END &&
          mOperations[handle].GetOperation() == STATE_CLOSE;
}

The FileManager is responsible for handling the state transitions of the file loading, giving the user a simpler way of loading files asynchronously. Keep in mind this is a Win32 implementation, other platforms will have different APIs and features, such as asynchronous open operations. Also I pretty much ignored error handling to keep the code small, but proper error handling is a requirement for a fully featured file manager.

Some key implementation details are

  • The FileManager is responsible for allocating the memory for the file. This is required because you usually don’t know the size of a file until you’ve opened it. A more flexible alternative would be to provide a memory allocator (vis IAllocator) to the LoadFile call.
  • This FileManager need to be Update’d by the game. This is because we use a polling API, some platforms may have a callback based system.
  • Each platform would need its own FileOperation and FileManager (or at least a per-platform Update). It’s possible to add some more abstractions – like a FileDevice – to abstract the platform specific calls away so we have a portable FileManager, but for brevity’s sake I’ve kept it simple.

Now our asynchronous loading game object would look something like this

class Object
{
   Object(const char *filename)
   {
      mFileHandle = gFileManager.ReadFile( filename, &mFileData, mFileSize );
   }

   bool IsLoaded()
   {
      return gFileManager.IsCompleted(mFileHandle);
   }

   void *mFileData;
   uint64_t mFileSize;
   FileHandle mFileHandle;
};

Batch Loading

We’ve hidden the stalls that occur when the disc device and CPU need to synchronize, so that’s removed one of the big problems with load times. Is there anything else we can do with our file manager to help load times?

Well, earlier we noticed just how bad seek times were on consoles (and any optical media). Seek times are relative to the distance the drive head has to move, and that the disc only really likes to move in one direction, going back and forth can be slow. Since we’re loading more than one file at a time we can use this information to reduce seek time.

It’s a simple matter of sorting all active file operations by their location on disc. This will reduce the seeks needed to a minimum, which can be a substantial win in total time. Even more advanced file managers could merge reads of adjacent files.

The FileManager above starts operations as soon as then are available, alternatively we could queue operations up and execute them so we reduce the amount of seeking we do. However it has one problem: files aren’t loaded in the order they were requested. The other major problem is that many APIs don’t provide this information anyways, so we have no way of properly sorting them by disc location.

What Next?

We can now have our game not waste time waiting for file loads, we can perform loading as a background task. However this is really just the first step to better load times. To reduce load times a much as possible we need to reduce the amount of data loaded. So next we’ll look at data compression, packfiles and disc layout. All of which can give us better load times.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: