Memory system – Part 3

Continuing from where we left off last time, we’re about to optimize our NewArray and DeleteArray function templates for POD-types this time. Let’s start easy by talking about the implementation itself first, and then putting pieces of the puzzle together one by one. Following is the implementation of the function templates NewArrayPOD and DeleteArrayPOD:

template <typename T, class ARENA>
T* NewArrayPOD(ARENA& arena, size_t N, const char* file, int line)
{
  return static_cast(arena.Allocate(sizeof(T)*N, file, line));
}

template <typename T, class ARENA>
void DeleteArrayPOD(T* ptr, ARENA& arena)
{
  arena.Free(ptr);
}

That was easy, but how do we make sure that our macros call the correct function based on the type itself? There are several possibilities:

  • Use a simple if-statement based on the result of some traits-class (e.g. is_pod<T>), and call either NewArray or NewArrayPOD. The disadvantage of this approach is that we’re “branching” on something which could be determined at compile-time, and some compilers will warn about it (MSVC does).
  • Get rid of NewArrayPOD, and provide template specializations of NewArrayfor POD types instead. This approach has several disadvantages:
    1. It adds a lot of code bloat.
    2. Function templates cannot be partially specialized (which we would need to do), so we have to refactor our function templates and convert them into class templates.
    3. It will not work for user-defined POD types unless the user explicitly adds a specialization for each one of his POD types, which is tedious and error-prone.
  • Get rid of NewArrayPOD, and provide two distinct overloads of NewArray instead – one for POD types, one for non-POD types. This is what we’re after.

The first piece of the puzzle we need is a traits-class which decides whether a given type is POD or not. This can be done via a base template and some specializations:

template <typename T>
struct IsPOD
{
  static const bool Value = false;
};

template <>
struct IsPOD<char>
{
  static const bool Value = true;
};

template <>
struct IsPOD<int>
{
  static const bool Value = true;
};

// etc.

For any given type T, we can use the compile-time constant IsPOD<T>::Value to decide whether we’re dealing with POD types or not. Note that the base template evaluates to false, so we err on the safe side (it would be disastrous to not call constructors and destructors for non-POD types). Adding a few specializations for all integral types at least saves us the cost of doing unnecessary work for these types, but users still have to provide specializations for their own types (but only if they want to make use of the optimizations for POD types – the provided solution will still work correctly!). In this case, I would advise to either use a more sophisticated approach to the IsPOD<> implementation, or check whether your compiler already supports std::is_pod – Visual Studio 2010 does, and this is what I use:

template <typename T>
struct IsPOD
{
  static const bool Value = std::is_pod<T>::value;
};

std::is_pod<T> is still wrapped inside IsPOD so I just have to change this template in order to make it work with other compilers/platforms as well.

Having solved the first piece of the puzzle, we need to add overloads to our NewArray and DeleteArray function templates:

template <typename T, class ARENA>
T* NewArray(ARENA& arena, size_t N, const char* file, int line, NonPODType)
{
  // implementation for non-POD types
}

template <typename T, class ARENA>
T* NewArray(ARENA& arena, size_t N, const char* file, int line, PODType)
{
  // implementation for POD types
}

template <typename T, class ARENA>
void DeleteArray(T* ptr, ARENA& arena, NonPODType)
{
  // implementation for non-POD types
}

template <typename T, class ARENA>
void DeleteArray(T* ptr, ARENA& arena, PODType)
{
  // implementation for POD types
}

Of course, function overloads in C++ only work based on types, not values. This means that we cannot add overloads for false and true (which is what IsPOD<T>::Value yields), but need to somehow turn them into distinct types first. Enter type-based dispatching:

template <bool I>
struct IntToType
{
};

typedef IntToType<false> NonPODType;
typedef IntToType<true> PODType;

Our NewArray and DeleteArray function templates provide overloads for both NonPODType and PODType, and by using the IntToType class template, we can turn compile-time boolean results into distinct types. With the above in place, we can finally change our ME_NEW_ARRAY macro to the following:

// old version
#define ME_NEW_ARRAY(type, arena)    NewArray<TypeAndCount<type>::Type>(arena, TypeAndCount<type>::Count, __FILE__, __LINE__)

// new version
#define ME_NEW_ARRAY(type, arena)    NewArray<TypeAndCount<type>::Type>(arena, TypeAndCount<type>::Count, __FILE__, __LINE__, IntToType<IsPOD<TypeAndCount<type>::Type>::Value>())

For the ones not used to compile-time programming mechanics like the above, let’s put on our compiler hat again, and see what happens with the rather long expression IntToType<IsPOD<TypeAndCount<type>::Type>::Value>() in the macro expansion for ME_NEW_ARRAY(Test[3], arena):

  • The innermost expression is TypeAndCount<type>::Type, which yields Test.
  • IsPOD<Test>::Value yields false in our case.
  • The outermost expression then becomes IntToType<false>(), which is a temporary of type NonPODType (note the parentheses at the end).

Voila! The ME_NEW_ARRAY will now automatically benefit from the optimizations we implemented for POD types. The last missing part is the ME_DELETE_ARRAY macro, which is shown below in its unchanged form:

#define ME_DELETE_ARRAY(object, arena)    DeleteArray(object, arena)

We cannot use IsPOD<T> or IntToType<T> in this macro, because object is a value and not a type. We don’t want the user to explicitly specify the type in the macro either, because the compiler already knows it. What we need is a helper function which extracts the type by relying on the compiler’s template argument deduction, and forwards it to the correct overload:

template <typename T, class ARENA>
void DeleteArray(T* ptr, ARENA& arena)
{
  DeleteArray(ptr, arena, IntToType<IsPOD<T>::Value>());
}

This DeleteArray function template is called by the macro – having access to the type T now, we use it for turning IsPOD<T>::Value into a distinct type using IntToType<>(). This results in calling the correct overload in our ME_DELETE_ARRAY macro as well, which ends today’s post.

One detail we haven’t talked about yet is how the memory arenas themselves are implementedĀ  – this has to wait until the next installment in the series.

Advertisements

4 thoughts on “Memory system – Part 3

  1. I am enjoying reading your series on the ME Memory System. There are some great pieces of information in here. Some of them aren’t even specific to the Memory System. You are doing some things with templates that I didnt even know was possible. Not saying I am an expert on the topic though.

    One thing I did want to bring to your attention is that it seems like the formatting on your code segments is doing something funky whenever “” are present. Seems like its eating some of your template arguments and such inside the code samples. After looking closely I was able to decipher what was missing in order to understand the code, but you may want to look into fixing that for clarity.

    Thanks for this awesome article. Looking forward to your future posts.

  2. Pingback: Memory allocation strategies: a linear allocator | Molecular Musings

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