Using SG14 Libraries

There’s recently been some outcry from the gaming industry regarding C++’s direction. I share some of the views expressed, but since I mostly write functional code for my engine, my expectations are somewhat different. I have certainly drunk the Kool-Aid.

To me, if constexpr and aligned new are real demonstrations the standard committee understands our woes. Once we get static reflection, hopefully before I retire, the need for template metaprogramming should be greatly dimished. One way the committee wishes to improve the language for gaming is through SG14.

The study group was created to give a voice to high-performance industries including, but not limited to, gaming. SG14 maintains a library with useful containers and tools for high-performance code. It is “their Boost”. Yet I’ve not heard much about the library in the wild. Of particular interest to me, and most likely gaming, are slot_map and inplace_function. Today, I will shed some light on these really useful containers.

Slot Map

Even though the terminology may be alien to you, slot maps are used everywhere in game engines. This container is backed by a std::vector or similar heap array. As such, it has great traversal performance due to CPU prefetching. The feature that makes slot maps so great are ids. A slot map will associate every element in your vector to a unique id. You can think of an id as an always valid iterator.

This allows you to swap and delete elements freely. For example, to reorder components that are “enabled” at the beginning of your container for maximum traversal performance. Or to write a performant erase (swap & pop_back) since element order doesn’t matter, etc. Access to an element using an id is O(1), though it is more heavy than direct vector element access.

The main trade-off is memory, as is often the case. You need to store ids and you need to store id generation information as well.

slot_map is also very early in its development cycle. You will certainly find some functionality missing and/or bugs. You may want to fork it and do a full review if you are planning on using slot_map in production code.

Inplace Function

Inplace function is a std::function replacement with fixed capacity storage. When using std::function, you may end up allocating on the heap if your capture is large. Yes, std::function has small buffer optimization. inplace_function, on the other hand, uses a pre-set storage size. You can think of the relationship between a std::function and inplace_function the same way you think about std::vector and std::array.

It is a way to guarantee contiguous storage of inplace_functions in, lets say, a vector. This will eliminate cache-misses when iterating and executing your functions. Of course, a user can always break this behavior with heap allocated capture parameters, but at that point you’ve done as much as you can. Or have we?

Yes, yes we have.

Inplace functions recently acquired noexcept move constructors, which was the remaining issue blocking their usage in high-performing code paths. It is important to note that, if an element in your capture throws during move construction, all bets are off and std::terminate is called. In my opinion, they are ready for prime-time.

The trade-off is less flexible captures. You may hit the maximum size the inplace_function can store. At that point, you’ll need to either change your storage size or think of another way. std::functions are more apropriate if you expect a wide range of storage sizes.

Event Stack vs. Event System

You may have never heard the term “event stack” before. That’s to be expected, as it isn’t some wide-spread terminology. I use the name event stack to denote a simpler event system building block. In a fully fledged event system, you would probably have channels or object pairing to propagate your events. An event stack is much simpler and is stored directly in an object as is.

You can use event stacks to build an event system pretty easily, especially if you want to use channels. For this post however, that’s a bit out-of-scope.

Compile Time Events

To make things interesting, we will create an event stack with compile-time defined events. This will help with our event signatures and is more fun :) The performance gain using compile-time defined events should be minimal. Adapting the example to support runtime events requires changing the container from a tuple to a vector or unordered_map, and a way to deal with your event function signatures.

To make this work, our users will declare an enum class of events. We will use this to create a tuple of events that users subscribe to. There are a few enum requirements. The enum must provide a count value and the values must be ordered from 0 to count. Lets declare some events, shall we?

enum class render_event {
	pre_render,
	render,
	post_render,
	count,
};

With our events declared, we can look into using these to create our event stack. We will use a mix of non-type templates and a nifty templating trick I do not know the name of. Lets call it “template reuse” for demonstration purposes. If I’d have to guess an official name, it would probably be something like “dependent non-type template parameter injection”, aka gobbledygook ;)

Some readers may not know you can specify enum classes directly as a template parameter. This is called non-type template parameters. It works the same as size_t, ints, etc. For example :

template <render_event e> // Hardcoded enum class.
void fancy_shmancy_function() {
	// e is a compile time constant. We can do fancy things with it.

	if constexpr (e == render_event::pre_render) {
		// Impress colleagues, or get fired.
	}
}

int main() {
	constexpr render_event my_event = render_event::pre_render;
	fancy_shmancy_function<my_event>();
}

So, a user could subscribe or unsubscribe to an event using non-type template parameters. We can also execute events the same way.

int main() {
	event_stack< /*...*/ > my_stack;
	my_stack.subscribe<render_event::render>( /*...*/ );
	my_stack.execute<render_event::render>( /*...*/ );
}

Thats great and all, but since the user will be creating the event enum class, we cannot hardcode a non-type template parameter in our container. Or can we?

Yes, yes we can.

Here, “template reuse” comes into play. A user can create an event stack and provide the event enum as a template parameter. Inside the event stack, we will be able to reuse that template parameter to “hardcode” the user enum class in our member functions. An example is worth 1'000 words, here’s how it works.

template <class EventEnum>
struct event_stack {
	template <EventEnum e> // Non-type template coming from struct template.
	void oh_yes_this_works() {
		// Now you are definitely fired.
	}
};

int main() {
	event_stack<render_event> my_system;
	my_system.oh_yes_this_works<render_event::pre_render>();
}

These are the fundamental techniques we will use to create a compile-time event stack. If you are thinking this is overkill right about now, you are absolutely right. However, my goal is not to provide copy-paste ready code for your project. It is to teach cool, and sometimes crazy, things.

Now that we have the basics down, lets use SG14 libraries to create a darn simple event stack (minus the template stuff). First, lets create our storage. We will use a tuple to store slot_maps of inplace_functions. We will need variadic templates to declare the event signatures. These are provided by the user.

To make the examples clearer, I will not provide all the static_asserts one would typically use. They will be included in the full example down below. You would check to make sure EventEnum is an enum and has the count value. You would also check to make sure the size of the provided variadic arguments is equal to the event count.

template <class EventEnum, class... FuncTypes>
struct event_stack {

private:
	std::tuple<stdext::slot_map<stdext::inplace_function<FuncTypes>>...> _data{};
};


int main() {
	event_stack<render_event, void(int), void(bool), void(float)> my_system;
}

When executing an event, we will access its specific slot_map and iterate all inplace_functions. As far as I know, there isn’t a more CPU friendly way to do this.

Things are shaping up nicely, time to subscribe and unsubscribe from events. Here, slot_map shines and makes the whole thing extremely simple. The subscribe and unsubscribe functions simply get the event slot_map and add or remove inplace_functions. The user will need to store the event_id if he later desires to unsubscribe from our event stack. Ids come into play with more complete event systems. For example when enabling/disabling event functions. Id generation and management is taken care of by slot_map, yay.

I use an alias event_id to make the api more readable. You can use a custom id class with slot_map, as long as you provide either std::get specializations or your custom id supports structured bindings. The first element of the pair is the id itself, the second is a generation. This is used to avoid collisions with recently deleted ids. You can read more about id generation in this classic bitsquid blog post.

using event_id = std::pair<unsigned, unsigned>;

template <class EventEnum, class... FuncTypes>
struct event_stack {

	template <EventEnum e, class Func>
	event_id subscribe(Func&& func) {
		return std::get<size_t(e)>(_data).insert(
				std::forward<Func>(func));
	}

	template <EventEnum e>
	void unsubscribe(event_id id) {
		std::get<size_t(e)>(_data).erase(id);
	}

private:
	std::tuple<stdext::slot_map<stdext::inplace_function<FuncTypes>>...> _data{};
};


int main() {
	event_stack<render_event, void(int), void(bool), void(float)> my_system;

	event_id id1 = my_system.subscribe<render_event::render>(
			[](bool) { printf("executing render event function\n"); });

	event_id id2 = my_system.subscribe<render_event::post_render>([](float f) {
		printf("executing post_render event function : %f\n", f);
	});
}

If you are new to perfect-forwarding, aka std::forward<Func>(func), here is a very complete post that explains all the details. A one sentence explanation would look like : “I do not care what type of value the user gives me, forward it to the next function and do the right thing, kthxbai.”

With these functions done, it is time to test things out.

Executing Events

Here, we will accept an event through a non-type template parameter and some arguments to call our functions with. These are not perfect forwarded, as we will use them for all stored functions. In the final example, I static_assert whether the stored functions can be called with the user provided arguments using std::is_invocable. This makes the error message easier to understand if we mess up the arguments.

using event_id = std::pair<unsigned, unsigned>;

template <class EventEnum, class... FuncTypes>
struct event_stack {

	template <EventEnum e, class Func>
	event_id subscribe(Func&& func) {
		return std::get<size_t(e)>(_data).insert(
				std::forward<Func>(func));
	}

	template <EventEnum e>
	void unsubscribe(event_id id) {
		std::get<size_t(e)>(_data).erase(id);
	}

	template <EventEnum e, class... Args>
	void execute(const Args&... args) const {
		const auto& s_map = std::get<size_t(e)>(_data);
		for (const auto& func : s_map) {
			std::invoke(func, args...);
		}
	}

private:
	std::tuple<stdext::slot_map<stdext::inplace_function<FuncTypes>>...> _data{};
};


int main() {
	event_stack<render_event, void(int), void(bool), void(float)> my_system;

	event_id id1 = my_system.subscribe<render_event::render>(
			[](bool) { printf("executing render event function 1\n"); });

	event_id id2 = my_system.subscribe<render_event::render>(
			[](bool) { printf("executing render event function 2\n"); });

	event_id id3 = my_system.subscribe<render_event::render>(
			[](bool) { printf("executing render event function 3\n"); });

	event_id id4 = my_system.subscribe<render_event::post_render>([](float f) {
		printf("executing post_render event function : %f\n", f);
	});


	my_system.execute<render_event::pre_render>(42);
	my_system.execute<render_event::render>(true);
	my_system.execute<render_event::post_render>(42.f);

	printf("\nunsubscribing\n");
	my_system.unsubscribe<render_event::render>(id1);
	my_system.unsubscribe<render_event::post_render>(id4);

	my_system.execute<render_event::pre_render>(42);
	my_system.execute<render_event::render>(true);
	my_system.execute<render_event::post_render>(42.f);

}

This prints :

executing render event function 1
executing render event function 2
executing render event function 3
executing post_render event function : 42.000000

unsubscribing
executing render event function 3
executing render event function 2

Exactly what we were looking for. Tada!

Of course, a production-ready event stack or event system would have many more features, but the basics remain the same. Users need a way to refer to event functions. You need a way to store functions, execute them quickly and the flexibility to reorder things without breaking user code.

That is it for today, I hope this motivates you to try out the SG14 libraries. Many thanks to Arthur O’Dwyer for proof-reading and the great feedback! Here is a more complete and safe example.