Irrelevant Conclusion

Asserts are a brilliant paradigm for catching errors at run-time in your code. Whereas a unit test is usually written to catch errors in the constraints of a function, asserts are put in place to catch usage errors. Let’s go over a quick example of what a unit test might look like; I’m using UnitTest++ syntax, cause that’s the framework I’m familiar with.

TEST(CheckSqrtForNaN)
{
	float nan = sqrtf(-1.0f);
	CHECK(nan != nan);
}

This is a simple test that makes sure that the square-root of a negative number comes back as a NaN. This is a good test — there were actually platforms where sqrt(-1) would return 0. But say we decide that nobody should ever pass a negative value to sqrtf() to begin with. We can’t unit test that, so let’s assert it.

float MySqrt(float input)
{
	ASSERT(input >= 0.0f);
	return sqrtf(input);
}

Now we need to get rid of the previous unit test — taking the square root of a negative value is no longer within the constraints of the function. On the plus side, though, we don’t have to decide what to do about that pesky platform that never returned NaNs.

It turns out that there can be a lot of code you can write like this — simple functions where you would like to enforce run-time behavior. Let’s look at another one that has useful unit tests, but also should contain asserts.

float Lerp(float a, float b, float t)
{
	ASSERT(t >= 0.0f && t <= 1.0f);
	return (b - a) * t;
}

UNITTEST(CheckLerp)
{
	CHECK_EQUAL(Lerp(0.0f, 1.0f, 0.0f), 0.0f);
	CHECK_EQUAL(Lerp(0.0f, 1.0f, 0.5f), 0.5f);
	CHECK_EQUAL(Lerp(0.0f, 1.0f, 1.0f), 1.0f);
}

So if you have a Lerp() function, you should definitely assert the defined input range. You would, of course, also want to unit test it, just in case somebody changes it into Hermite spline interpolation when you’re not looking.

By now you should be getting the impression that if you are as anal retentive as me about putting asserts everywhere, you might be slowing down your code unnecessarily. Afterall, even with optimizations, the assert inside the Lerp() function is still doing floating point compares and branching, and the only way to get those asserts to compile out is to disable asserts for the entire program.

Local Asserts to the Rescue

Why don’t we just make another assert macro specifically for our math functions so that we can enable/disable them at the file level? If we start getting weird math-related bugs we can re-enable the asserts and see if any of them get hit as the bugs manifest.

#define ENABLE_MATH_ASSERTS		1

#if (ENABLE_MATH_ASSERTS)
	#define MATH_ASSERT(x)		ASSERT(x)
#else
	#define MATH_ASSERT(x)		NO_ASSERT(x)
#endif

float MySqrt(float input)
{
	MATH_ASSERT(input >= 0.0f);
	return sqrtf(input);
}

float Lerp(float a, float b, float t)
{
	MATH_ASSERT(t >= 0.0f && t <= 1.0f);
	return (b - a) * t;
}

#undef MATH_ASSERT

We can put these local asserts all over the place and turn them on and off selectively if we want to test for problems at run-time, and in final builds, where all asserts are disabled, we don’t need to do anything different.

Now something might be niggling at the back of your mind. If asserts are put in place to catch run-time errors, and we may or may not have them enabled, how exactly can we be sure that they even work?

Let’s unit test our asserts…

The first step in this whole process is to read Charles Nicholson’s blog post on asserts. You know nothing about asserts until you’ve completed that article.

Now the key takeaway here is setting up a customizable assert handler. Charles mentions in passing that this can be used for unit testing asserts, but doesn’t go into detail. If you’re using the UnitTest++ framework (which Charles also co-authored), there’s a handy macro for testing asserts. It relies on your assert handler throwing an exception. This is key — if you’re using another unit testing framework you can test your asserts in the exact same way.

int _CCALL ThrowDebugAssert(const char *expression, const char *path, int line, const char *reason, ...)
{
	throw UnitTest::AssertException(expression, path, line);

	return 0;
}

int MathTests::RunAllTests(void)
{
	Debug::SetAssertHandler(ThrowDebugAssert);

	int failures = UnitTest::RunAllTests();

	return failures;
}

And now you can test your asserts as follows…

TEST(CheckSqrtForNaN)
{
	CHECK_ASSERT(MySqrt(-1.0f));
}

UNITTEST(CheckLerp)
{
	CHECK_EQUAL(Lerp(0.0f, 1.0f, 0.0f), 0.0f);
	CHECK_EQUAL(Lerp(0.0f, 1.0f, 0.5f), 0.5f);
	CHECK_EQUAL(Lerp(0.0f, 1.0f, 1.0f), 1.0f);

	CHECK_ASSERT(Lerp(0.0f, 2.0f, -0.1f));
	CHECK_ASSERT(Lerp(0.0f, 2.0f, 1.1f));
}

Again, this is what you need for the UnitTest++ framework, but it should give you a clear idea of how to do it in any other framework that doesn’t have identical support for testing asserts.

But wait… we’re going in circles. If we disable the asserts locally, then they are disabled for the unit testing, and the unit tests will fail wanting an assert. We need some way to let CHECK_ASSERT() pass if we’ve disabled asserts locally for a module. One option is to write a nifty new UnitTest++ macro and add a global variable to our tested code, like so.

// Somewhere in our library...
bool g_MATH_AssertEnabled = ENABLE_MATH_ASSERTS;

// In our test framework...
#define CHECK_TOGGLE_ASSERT(name, condition) \
	extern bool g_##name##_AssertEnabled; \
	if (g_##name##_AssertEnabled) CHECK_ASSERT(condition)

// In our unit tests...
UNITTEST(CheckLerp)
{
	// ...

	CHECK_TOGGLE_ASSERT(MATH, Lerp(0.0f, 2.0f, -0.1f));
	CHECK_TOGGLE_ASSERT(MATH, Lerp(0.0f, 2.0f, 1.1f));
}

Now we can call CHECK_TOGGLE_ASSERT() in our unit tests in place of CHECK_ASSERT() and it will do nothing if the asserts for a module have been compiled out locally.

Finally, we could beautify all of this stuff with some more macros to make setup of this procedure a little bit less obtuse.

	#define _BUILD_VAR_NAME(name)				g_##name##_AssertEnabled
	#define IMPLEMENT_UNITTEST_ASSERT(module)	bool _BUILD_VAR_NAME(module) = ENABLE_##module##_ASSERT;

	#define CHECK_TOGGLE_ASSERT(name, condition)	\
		extern bool _BUILD_VAR_NAME(name);	\
		if (_BUILD_VAR_NAME(name)) CHECK_ASSERT(condition)

And, if you wanted, inside your unit tests you could wrap the toggle check like so:

	#define CHECK_MATH_ASSERT(condition)		CHECK_TOGGLE_ASSERT(MATH, condition)

Of course, the down side to this is that there is a lot more boilerplate that can’t be generated by preprocessor macros; like the macros themselves. There’s also the possibility that the global variables are not stripped from the executable in release (this is particularly possible if your code is built into a DLL). Most importantly, though, is that we’re not testing our asserts when they’re disabled — they can easily be forgotten about over the course of a project.

A better and simpler option is to just have your build machine make a build with full tests enabled. This is a clear win unless there is some dire reason you can’t do it. You get full test coverage, even of unit tests that have been disabled forever and forgotten about.

#if defined (UNITTEST_BUILD)
	#define ENABLE_MATH_ASSERTS		1	// Always 1...
#else
	#define ENABLE_MATH_ASSERTS		0	// Defined by user...
#endif

#if (ENABLE_MATH_ASSERTS)
	#define MATH_ASSERT(x)		ASSERT(x)
#else
	#define MATH_ASSERT(x)		NO_ASSERT(x)
#endif

Now there is even no real need for the CHECK_TOGGLE_ASSERT() macro, either.

Clearly you’ll want unit tests disabled in final code. If your build setup runs unit tests on final stuff (which seems even too anal for me) you can of course macro around final but you’ll need to keep the customized CHECK_ASSERT() macro.

#if !defined (_FINAL)
	#define CUSTOM_CHECK_ASSERT(condition)		CHECK_ASSERT(condition)
#else
	#define CUSTOM_CHECK_ASSERT(condition)		NO_ASSERT(condition)
#endif

To be clear, all this will do is cause your unit tests to NOT test the asserts, hence all passing. Now before you start thinking that we’re back to where we were with the global variable option, consider for a minute that it’s really moot to test asserts in final anyhow. They are compiled out and will never be hit in the actual product. Asserts are needed while developing…

So anyway, this post is long and scatter-brained, but I think the idea is evident. Assert everywhere with local asserts, disable the ones you feel like disabling, unit test them, and have the build machine test them all. So go forth and assert pedantically.

So it’s been a long time since I posted anything, relevant or otherwise. For various reasons, I’m still sans-computer… sorta. While it’s true that I’m still writing this on an iPad with a fantastic 3G internet connection, I actually have access to a crappy old MacBook with horrible, horrible Xcode on it. And no internet.

Anyhow, I was writing a data structure the other day (just for fun, of course), and being that I dislike the vagueness of the new/delete operators for managing memory, I decided to embed an allocator. This forced me to remember the trick to embedding generic allocator objects, which of course led me to think about STL allocators. It’s worth understanding how STL deals with allocator objects, because this problem has been solved in the best way by STL. Even if you write all your own data structures, you should understand how the STL method works. So without further adieu, let’s look at STL allocators.

If you were implementing an allocator to be used with STL containers, it would start out something like this:

template <typename Type_t>
class MyAllocator
{
     public:

          typedef size_t size_type;
          typedef Type_t * pointer;

          inline pointer allocate(size_type n, const void *p = 0);

          inline void deallocate(pointer ptr, size_type size);
};

Now there is more stuff required for an allocator than this. Most of it is boiler-plate — typedefs and a couple more mundane functions. But we’ll start with just this because it contains lots of interesting information regarding the design of the allocator model itself.

What’s so interesting, you ask? Well firstly, these functions are not static. This means that the allocator is designed to exist as part of the data structure class. Secondly, these functions are not templated. This means that they are only required to deal with one type — in our example case, Type_t. These two important observations affect the design of any containers that use an allocator.

Let’s address the latter issue first: MyAllocator can only allocate Type_t’s.

This might not seem like a problem until you start implementing data structures more complex than an array. For everything else you generally have some sort of node structure that contains your container’s type data, as well as other information, such as pointers to other nodes, or whatever. “Easy”, you say, “Just parameterize the allocator with the node type instead of the data structure type.” Not as easy as it sounds. Let’s see why.

template <typename Type_t, typename Alloc_t = MyAllocator<MyList::Node> >
class MyList
{
     protected:

          struct Node
          {
               Node *pNext;
               Type_t data;
          };

     // Implementation details...
};

So you can try the above code, but it won’t work. The problem is that you’re trying to create a class from a template based on a class inside the templated class which has yet to be created. In essence, a paradox. And the compiler will tell you such — something about instantiating from incomplete types and becoming you own grandpa, or whatever. Also, for the record, you can’t out-smart this problem by just moving the Node class around.

So the solution? The STL guys have come up with a brilliantly clever hack to get around this deficiency: rebind. Every allocator class needs to do this.

template <typename Type_t>
class MyAllocator
{
     public:

          template <typename Other_t>
          struct rebind
          {
               typedef MyAllocator<Other_t> other;
          };
};

Now this rebind stuff is boilerplate, but as I said, is clever enough to be worth understanding. Essentially, the allocator defines a type which is just itself allocating another type. This way it’s possible for the container class to create a different type of allocator using the one that it was forced to accept as a template argument. The description is much more confusing than just reading the code.

But you might be wondering why this is better than just having the allocator functions be templated. Well, let’s imagine the simplest allocator of Type_t. It would just be a big array, suitably aligned and sized, to hold these Type_t things. Now what happens to this elegantly simple model if the same chunk of prim and proper memory must now hold an Other_t? Or not just one Other_t, but any number of disparate Other_t types allocated in any order, each with their own size and alignment requirements. Things get messy. So the STL solution to the problem is to create an entirely new allocator from the shell type of the old one.

So how do we use this neat little solution in our own container classes? By utilizing every C++ keyword beginning with the letter “t” all at the same time. I’m deadly serious.

template <typename Type_t, typename Alloc_t = MyAllocator<Type_t> >
class MyList
{
     protected:

          struct Node
          {
               Node *pNext;
               Type_t data;
          };

          typedef typename Alloc_t::template rebind<Node>::other NodeAlloc;

          NodeAlloc m_allocator;
          Node *m_pHead;
};

Our little container class now has an allocator which allocates Nodes, and the world is once again a just place. Right?

But what about my little blurb regarding embedding the allocator? Surely this is solved in the above example. After all, there is a member variable called m_allocator inside the MyList class. We’re done, right?

Technically, this does work. There’s nothing wrong with the above code. But riddle me this, Batman: what is sizeof(MyList)? The answer is, greater than sizeof(Node *), even if MyAllocator contains no data.

This is tricky — it has to do with being able to take the address of an object. The C++ standard requires that you be able to do &m_allocator, and hence even a class with no data members, when instantiated, must have a size.

In this case, it sucks and is just a waste of space. If only there was some other clever hack that would allow the allocator to only take up space if it had data members. Well, let me end the suspense: there is. The trick is to give the allocator data that we will always use, albeit in a totally round-about fashion.

Let’s look again at the MyList class. It has an allocator, which is a policy more than it is state, and it has a head node, which is pure data, and totally necessary for the implementation. Let’s fuse them together into one object.

template <typename Type_t, typename Alloc_t = MyAllocator<Type_t> >
class MyList
{
     protected:

          struct Node
          {
               Node *pNext;
               Type_t data;
          };

          typedef typename Alloc_t::template rebind<Node>::other NodeAlloc;

          struct HeadProxy : public NodeAlloc
          {
               Node *m_pHead;
          };

          HeadProxy m_proxy;
};

There. All done. The HeadProxy object embeds the NodeAlloc allocator, and if the allocator has no data members it takes up no space. C++ gets to keep it’s silly rule about taking addresses of objects, and we get our space efficiency win. All at the expense of more typing and uglier code. But then again, if you cared about excessive typing and ugly code, you would be staying well away from templates. And probably from C++ too…

So I know this post doesn’t go over absolutely everything there is to know about STL allocators, and if you’re angry at the dramatic post title, I apologize. But I think these things are the trickiest parts to consider, both from the perspective of someone implementing an allocator, and as someone implementing a data structure that makes use of STL allocators.