In the previous article on Fast File Loading, I described techniques directly related with the hardware and the operating system to load files in the most efficient way. In this one, a technique for organizing the data to be loaded as fast as possible is described. Basically, we are going to load data without doing any parsing at all. Although the techniques described here are oriented towards real-time applications, any application could use them to accelerate its load times.

The implementation and all the samples shown here can be found in a project that you can download. It is a project for Microsoft Visual Studio 8.0 and it has been tested under a 32-bit architecture. Extensions to other compilers and other architectures should be easy to add. This code must be taken as a proof of concept and not as a solid and robust implementation ready to be used in a project. I have tried to isolate the dependencies with other systems so that you can concentrate in the topic of this article.

1. Load-In-Place (aka Relocatable Data Structures)

The basic philosophy under Load-In-Place is “preprocess as much as possible“: do not waste CPU ticks with operations that can be done offline, do not waste CPU ticks so that the the loading process can run in parallel without interfering with your main process.

Imagine that you could load your data with a simple fread() from a file. Without doing any parsing at all. This is basically what we are going to try to do without modifying the structures we usually have.

If we had, for example, a data file with a vector of floats, loading with this philosophy in mind would be as simple as memcpying the file to memory and pointing a float* to the beginning of the memory buffer. And that would be all. We would have our data ready for being used.

For simple structures that would be enough but this simplicity disappears when we start to use more complex structures in C++:

• Pointers: it is usual to have pointers embedded in the data. Pointers can not be saved to disk without a proper management. And when you load those pointers they have to be relocated properly.
• Dynamic Types: a pointer to a type T doesn’t imply that the dynamic type is T. With polymorphism we have to solve the problem of loading/saving the proper dynamic type.
• Constructors: objects in C++ have to be properly constructed (invoking one of its constructors). We wouldn’t have a generic enough implementation if we didn’t allow object construction. Constructors are used by the compiler to create internal structures associated to a class like vtables, dynamic type info, etc.

Basically, what we want is a system being able to take a snapshot of a memory region and to save it to disk. Later, when loading the block, we need the system to make the proper adjustments to have the data in the same state that it was before saving. The mechanisms described here are very similar to those used by the compilers to generate modules (executables, static libraries, dynamic libraries) that later have to be loaded by the OS (relocating the pointers for example).

With this technique, native hardware formats are loaded by the runtime. This may imply a redesign of your data pipeline. A good approach is having a platform-independent format that is processed for each platform giving a native format that is loaded-in-place. This is the same procedure that is followed when generating binaries (executables, libraries). So it may be a good idea to unify this because now code and data are all the same.

2. Implementation Details

The class SerializationManager is in charge of loading/saving objects to/from file. Basically you have a function for saving where you pass a pointer to a root object and a function for loading with the same parameters. The root class has to satisfy some requirements for being serialized. The implementation is designed to be as less intrusive as possible. It means that you can design the classes as you wish. To make a class in-placeable you have to implement 2 functions for each class you want to save:

• CollectPtrs(): This function is used when saving. In this function you collect all the pointers and continue gathering recursively.
• In-Place Constructor(): this function is used when loading. There is a special constructor for Load-In-Place where you relocate the pointers. It is a good idea not having default constructors in the classes you want to in-place. That way default constructors are not silently called if you forget to call the in-place constructor.

The SerializationManager traverses the pointers starting from the root object looking for contiguous memory blocks. When all the contiguous memory blocks are localized, the pointers are adjusted to become an offset from the beginning of the block. When loading, those pointers are relocated (the stored offset is relative to the beginning of the block) and initialized (each pointer is only initialized once) using the placement syntax of the new operator:

// Class constructor is called but no memory is reserved Class *c = new(ptr) Class();

Let’s see a simple example:

class N0;
class N1;
class N2;
class N3;

class N3
{
public:

float a, b, c;

N3() {}

N3(const SerializationManager &sm) {}

void CollectPtrs(SerializationManager &sm) const {}
};

class N0

public:

N2 *n2;
N1 *n1;

N0() {}

N0(const SerializationManager &sm)
{
sm.RelocatePointer(n2);
sm.RelocatePointer(n1);
}

void CollectPtrs(SerializationManager &sm) const
{
sm.CollectPtrs(n2);
sm.CollectPtrs(n1);
}
};

class N2
{
public:

N2() {}

N1 *n1;
N3 *n3;
N2(const SerializationManager &sm)
{
sm.RelocatePointer(n1);
sm.RelocatePointer(n3);
}

void CollectPtrs(SerializationManager &sm) const
{
sm.CollectPtrs(n1);
sm.CollectPtrs(n3);
}
};

class N1
{
public:

float val;
N2 n2;

N1() {}

N1(const SerializationManager &sm): n2(sm) {}

void CollectPtrs(SerializationManager &sm) const
{

sm.CollectPtrs(n2);
}
};

With the above class definitions we serialize the following instances:

N0 n0;
N1 n1;
N3 n3;

n1.val = 1.0f;
n0.n1 = &n1;
n0.n2 = &n1.n2;
n0.n2->n1 = n0.n1;
n0.n2->n3 = &n3;

manager.Save(”raw.class”, n0);

This is a graphical representation of how the In-Place process would be applied to this sample:

To save classes in this way, you need to add to them the two functions described above. This intrusive method doesn’t allow, for example, saving STL containers. To solve this problem (and probably to avoid dependencies with a specific STL implementation) you probably will need to develop your own in-placeable containers. I have included in the sample project, a Vector and StaticVector implementation.