Background
I've recently been looking into event handling in C++; the particular case is
SDL (a C library for cross-platform GUI, etc., implementations). The event is identified as some kind of integer, and the handling of each different integer is done via a specialised virtual function (allowing sub-classes to override the default behaviour).
Most cases I've seen have event integers as non-contiguous, and SDL is no exception. In straight C the best approach is to use a switch statement since there's little chance (short of creating your own struct) of making a sparse matrix handler to limit the amount of memory contained (SDL has a maximum event ID of 65536, though only a limited number of numbers below 4096 are actually assigned as event IDs).
In C++, there's a few different options for sparse matrix handling, but the two best out-of-the-box ones are std::map and boost:unordered_map.
I wanted to evaluate the execution speeds (read: overhead) of the different mechanisms (i.e. std::map, boost::unordered_map and switch). For completeness, I'll throw in a pure array and an if-else method.
Note: I used BOOST 1.47.0, which is not the latest (at the time of writing, that's 1.53.0), so there may be speed improvements between library versions.
The mechanism
The idea was to push 1,000,000 randomly-generated numbers between 0-99 inclusive (i.e. there are 100 different event IDs), using a normal distribution to mimic the fact that some events occur more frequently than others. To achieve this, I used the BOOST random library.
Each event ID is routed via the particular mechanism to a single virtual function of the class as the callback, which takes the event ID as a parameter (in lieu of more complex possible callbacks which typically require some kind of argument list). The callback is implemented to do nothing, minimising any overhead of the callback operation in skewing the timing data.
The array implementation was a simple array of member function pointers. The boost::unordered_map implementation was a map of the event id as the key with a member function pointer as the item. Likewise the std::map implementation. These 3 arrays were initialised with the callback pointer assigned in the constructor of the class; the overhead of doing so was not included in the timing calculations.
With a set of numbers fixed per run, each number set is pumped through the different algorithms and the elapsed execution time captured. Since each algorithm is executed sequentially but in the one program, the possibility of statistical anomalies caused by random external processes are reduced. Running the program multiple times and aggregating the results should hopefully further reduce the possibility of statistical anomalies.
The code was compiled under MS VC 2010 Express, in release mode, and run 10 times on my AMD A6 quad-core laptop with 4GB RAM running Win7 x64 home premium. The only other app open other than Visual Studio was Firefox.
The results
All numbers in the below table are in milliseconds.
| Algorithm | Run 1 | Run 2 | Run 3 | Run 4 | Run 5 | Run 6 | Run 7 | Run 8 | Run 9 | Run 10 | Mean |
| Array | 6 | 5 | 6 | 6 | 6 | 6 | 6 | 7 | 6 | 5 | 5.9 |
| boost::unordered_map | 36 | 31 | 33 | 35 | 34 | 33 | 32 | 33 | 38 | 31 | 33.6 |
| if | 88 | 87 | 88 | 90 | 88 | 88 | 89 | 85 | 88 | 86 | 87.7 |
| std::map | 77 | 75 | 77 | 76 | 77 | 77 | 76 | 75 | 78 | 74 | 76.2 |
| switch | 22 | 21 | 21 | 21 | 22 | 21 | 21 | 21 | 22 | 21 | 21.3 |
Analysis
At first, some of the results seem a little bizarre. Naturally, the slowness of the if mechanism was unsurprising, as was the absolute raw speed of the straight array implementation.
What was surprising was that the switch method was only 2/3 of the execution time of the boost::unordered_map. Likewise, the MSVC implementation of std::map meant it executed more than twice as slowly as the boost::unordered_map. It's probable that different compiler/library implementations of std::map will render different results to that here; I've used MSVC since as a non-open-source compiler/library I'm assuming that it will have the least efficient implementation.
It all needs to be kept in context, however, and that these times in milliseconds are for 1,000,000 events. For each event, then, these times for the callback are in nanoseconds; on the face of it, if you're talking frame rates in the 50-100 fps
category, then a processing time of even 88ns per event is not
significant. However, this timing doesn't take into account the follow-up processing done by the event handling and the corresponding memory updates required, e.g., for rending the frame using different textures that perhaps aren't cached. It's still therefore good to minimise the time spent doing the actual event isolation detection as fast as possible...
Conclusions
If your program can take the memory hit of a pure array, then clearly this is the single fastest method of handling the events. However, should the IDs of the events change, then there is a significant potential of problematic maintenance with changing the array element assignments (particularly if a sparse assignment is used with some kind of default "not-handled" handler for the rest). There is a significant drawback with this approach, which is the significant memory overhead required (e.g. for SDL, on a 32-bit system, allocating an array for the entire 65536 event ID space requires 256k); the sparse-matrix approach using boost::unordered_map or std::map can reduce this (especially if only a limited subset of events are intended to be handled), however on memory-limited platforms (e.g. mobiles) this approach should probably be avoided (even the sparse-matrix approach).
Of the more algorithmic handling (compared to the brute-force of the pure array), either the switch or the boost::unordered_map would be the options. The switch method is still faster, but it does lead to rather ugly code which could have significant maintenance issues unless the event IDs are rendered as constants somewhere. The boost::unordered_map throws up some different potential maintenance issues, in that the linkage between event IDs and the callbacks is not programatic, so changes would not necessarily be in the place a maintainer might expect.
Regardless, the choice of if and std::map should be avoided.
Code
Here's the code used in this experiment:
#include <map>
#include <boost/unordered_map.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <ctime>
#include <iostream>
class member_fns
{
public:
member_fns(void);
~member_fns(void);
void HandleIntViaArray(void);
void HandleIntViaHash(void);
void HandleIntViaIf(void);
void HandleIntViaMap(void);
void HandleIntViaSwitch(void);
protected:
static const unsigned int NUM_NUMBERS;
typedef void (member_fns::*mem_func)(int);
virtual void Handler(int n);
std::map<int, mem_func> _map;
boost::unordered_map<int, mem_func> _hashmap;
mem_func _array[100];
int * _nums;
};
const unsigned int member_fns::NUM_NUMBERS = 1000000;
member_fns::member_fns(void)
{
int i = 0;
for ( ; i < 100 ; ++i) {
_map[i] = &member_fns::Handler;
_hashmap[i] = &member_fns::Handler;
_array[i] = &member_fns::Handler;
}
boost::random::mt19937 gen;
boost::random::uniform_int_distribution<> dist(1, 100);
_nums = new int[member_fns::NUM_NUMBERS];
for (i = 0 ; i < member_fns::NUM_NUMBERS ; ++i) {
_nums[i] = dist(gen) - 1;
}
}
member_fns::~member_fns(void)
{
delete [] _nums;
}
void member_fns::HandleIntViaArray(void)
{
int i = 0;
clock_t end = 0;
clock_t start = clock();
for ( ; i < member_fns::NUM_NUMBERS ; ++i) {
(this->*_array[_nums[i]])(_nums[i]);
}
end = clock();
std::cout << "Array " << (end - start)/double(CLOCKS_PER_SEC)*1000 << " ms" << std::endl;
}
void member_fns::HandleIntViaIf(void)
{
int i = 0;
clock_t end = 0;
clock_t start = clock();
for ( ; i < member_fns::NUM_NUMBERS ; ++i) {
if (_nums[i] == 0) {
Handler(_nums[i]);
}
else if (_nums[i] == 1) {
Handler(_nums[i]);
}
else if (_nums[i] == 2) {
Handler(_nums[i]);
}
else if (_nums[i] == 3) {
Handler(_nums[i]);
}
else if (_nums[i] == 4) {
Handler(_nums[i]);
}
else if (_nums[i] == 5) {
Handler(_nums[i]);
}
else if (_nums[i] == 6) {
Handler(_nums[i]);
}
else if (_nums[i] == 7) {
Handler(_nums[i]);
}
else if (_nums[i] == 8) {
Handler(_nums[i]);
}
else if (_nums[i] == 9) {
Handler(_nums[i]);
}
else if (_nums[i] == 10) {
Handler(_nums[i]);
}
else if (_nums[i] == 11) {
Handler(_nums[i]);
}
else if (_nums[i] == 12) {
Handler(_nums[i]);
}
else if (_nums[i] == 13) {
Handler(_nums[i]);
}
else if (_nums[i] == 14) {
Handler(_nums[i]);
}
else if (_nums[i] == 15) {
Handler(_nums[i]);
}
else if (_nums[i] == 16) {
Handler(_nums[i]);
}
else if (_nums[i] == 17) {
Handler(_nums[i]);
}
else if (_nums[i] == 18) {
Handler(_nums[i]);
}
else if (_nums[i] == 19) {
Handler(_nums[i]);
}
else if (_nums[i] == 20) {
Handler(_nums[i]);
}
else if (_nums[i] == 21) {
Handler(_nums[i]);
}
else if (_nums[i] == 22) {
Handler(_nums[i]);
}
else if (_nums[i] == 23) {
Handler(_nums[i]);
}
else if (_nums[i] == 24) {
Handler(_nums[i]);
}
else if (_nums[i] == 25) {
Handler(_nums[i]);
}
else if (_nums[i] == 26) {
Handler(_nums[i]);
}
else if (_nums[i] == 27) {
Handler(_nums[i]);
}
else if (_nums[i] == 28) {
Handler(_nums[i]);
}
else if (_nums[i] == 29) {
Handler(_nums[i]);
}
else if (_nums[i] == 30) {
Handler(_nums[i]);
}
else if (_nums[i] == 31) {
Handler(_nums[i]);
}
else if (_nums[i] == 32) {
Handler(_nums[i]);
}
else if (_nums[i] == 33) {
Handler(_nums[i]);
}
else if (_nums[i] == 34) {
Handler(_nums[i]);
}
else if (_nums[i] == 35) {
Handler(_nums[i]);
}
else if (_nums[i] == 36) {
Handler(_nums[i]);
}
else if (_nums[i] == 37) {
Handler(_nums[i]);
}
else if (_nums[i] == 38) {
Handler(_nums[i]);
}
else if (_nums[i] == 39) {
Handler(_nums[i]);
}
else if (_nums[i] == 40) {
Handler(_nums[i]);
}
else if (_nums[i] == 41) {
Handler(_nums[i]);
}
else if (_nums[i] == 42) {
Handler(_nums[i]);
}
else if (_nums[i] == 43) {
Handler(_nums[i]);
}
else if (_nums[i] == 44) {
Handler(_nums[i]);
}
else if (_nums[i] == 45) {
Handler(_nums[i]);
}
else if (_nums[i] == 46) {
Handler(_nums[i]);
}
else if (_nums[i] == 47) {
Handler(_nums[i]);
}
else if (_nums[i] == 48) {
Handler(_nums[i]);
}
else if (_nums[i] == 49) {
Handler(_nums[i]);
}
else if (_nums[i] == 50) {
Handler(_nums[i]);
}
else if (_nums[i] == 51) {
Handler(_nums[i]);
}
else if (_nums[i] == 52) {
Handler(_nums[i]);
}
else if (_nums[i] == 53) {
Handler(_nums[i]);
}
else if (_nums[i] == 54) {
Handler(_nums[i]);
}
else if (_nums[i] == 55) {
Handler(_nums[i]);
}
else if (_nums[i] == 56) {
Handler(_nums[i]);
}
else if (_nums[i] == 57) {
Handler(_nums[i]);
}
else if (_nums[i] == 58) {
Handler(_nums[i]);
}
else if (_nums[i] == 59) {
Handler(_nums[i]);
}
else if (_nums[i] == 60) {
Handler(_nums[i]);
}
else if (_nums[i] == 61) {
Handler(_nums[i]);
}
else if (_nums[i] == 62) {
Handler(_nums[i]);
}
else if (_nums[i] == 63) {
Handler(_nums[i]);
}
else if (_nums[i] == 64) {
Handler(_nums[i]);
}
else if (_nums[i] == 65) {
Handler(_nums[i]);
}
else if (_nums[i] == 66) {
Handler(_nums[i]);
}
else if (_nums[i] == 67) {
Handler(_nums[i]);
}
else if (_nums[i] == 68) {
Handler(_nums[i]);
}
else if (_nums[i] == 69) {
Handler(_nums[i]);
}
else if (_nums[i] == 70) {
Handler(_nums[i]);
}
else if (_nums[i] == 71) {
Handler(_nums[i]);
}
else if (_nums[i] == 72) {
Handler(_nums[i]);
}
else if (_nums[i] == 73) {
Handler(_nums[i]);
}
else if (_nums[i] == 74) {
Handler(_nums[i]);
}
else if (_nums[i] == 75) {
Handler(_nums[i]);
}
else if (_nums[i] == 76) {
Handler(_nums[i]);
}
else if (_nums[i] == 77) {
Handler(_nums[i]);
}
else if (_nums[i] == 78) {
Handler(_nums[i]);
}
else if (_nums[i] == 79) {
Handler(_nums[i]);
}
else if (_nums[i] == 80) {
Handler(_nums[i]);
}
else if (_nums[i] == 81) {
Handler(_nums[i]);
}
else if (_nums[i] == 82) {
Handler(_nums[i]);
}
else if (_nums[i] == 83) {
Handler(_nums[i]);
}
else if (_nums[i] == 84) {
Handler(_nums[i]);
}
else if (_nums[i] == 85) {
Handler(_nums[i]);
}
else if (_nums[i] == 86) {
Handler(_nums[i]);
}
else if (_nums[i] == 87) {
Handler(_nums[i]);
}
else if (_nums[i] == 88) {
Handler(_nums[i]);
}
else if (_nums[i] == 89) {
Handler(_nums[i]);
}
else if (_nums[i] == 90) {
Handler(_nums[i]);
}
else if (_nums[i] == 91) {
Handler(_nums[i]);
}
else if (_nums[i] == 92) {
Handler(_nums[i]);
}
else if (_nums[i] == 93) {
Handler(_nums[i]);
}
else if (_nums[i] == 94) {
Handler(_nums[i]);
}
else if (_nums[i] == 95) {
Handler(_nums[i]);
}
else if (_nums[i] == 96) {
Handler(_nums[i]);
}
else if (_nums[i] == 97) {
Handler(_nums[i]);
}
else if (_nums[i] == 98) {
Handler(_nums[i]);
}
else if (_nums[i] == 99) {
Handler(_nums[i]);
}
else {
std::cout << "If: Unhandled number " << _nums[i] << std::endl;
}
}
end = clock();
std::cout << "If " << (end - start)/double(CLOCKS_PER_SEC)*1000 << " ms" << std::endl;
}
void member_fns::HandleIntViaHash(void)
{
int i = 0;
clock_t end = 0;
clock_t start = clock();
for ( ; i < member_fns::NUM_NUMBERS ; ++i) {
(this->*_hashmap[_nums[i]])(_nums[i]);
}
end = clock();
std::cout << "Hash " << (end - start)/double(CLOCKS_PER_SEC)*1000 << " ms" << std::endl;
}
void member_fns::HandleIntViaMap(void)
{
int i = 0;
clock_t end = 0;
clock_t start = clock();
for ( ; i < member_fns::NUM_NUMBERS ; ++i) {
(this->*_map[_nums[i]])(_nums[i]);
}
end = clock();
std::cout << "Map " << (end - start)/double(CLOCKS_PER_SEC)*1000 << " ms" << std::endl;
}
void member_fns::HandleIntViaSwitch(void)
{
int i = 0;
clock_t end = 0;
clock_t start = clock();
for ( ; i < member_fns::NUM_NUMBERS ; ++i) {
switch(_nums[i]) {
case 0:
Handler(_nums[i]);
break;
case 1:
Handler(_nums[i]);
break;
case 2:
Handler(_nums[i]);
break;
case 3:
Handler(_nums[i]);
break;
case 4:
Handler(_nums[i]);
break;
case 5:
Handler(_nums[i]);
break;
case 6:
Handler(_nums[i]);
break;
case 7:
Handler(_nums[i]);
break;
case 8:
Handler(_nums[i]);
break;
case 9:
Handler(_nums[i]);
break;
case 10:
Handler(_nums[i]);
break;
case 11:
Handler(_nums[i]);
break;
case 12:
Handler(_nums[i]);
break;
case 13:
Handler(_nums[i]);
break;
case 14:
Handler(_nums[i]);
break;
case 15:
Handler(_nums[i]);
break;
case 16:
Handler(_nums[i]);
break;
case 17:
Handler(_nums[i]);
break;
case 18:
Handler(_nums[i]);
break;
case 19:
Handler(_nums[i]);
break;
case 20:
Handler(_nums[i]);
break;
case 21:
Handler(_nums[i]);
break;
case 22:
Handler(_nums[i]);
break;
case 23:
Handler(_nums[i]);
break;
case 24:
Handler(_nums[i]);
break;
case 25:
Handler(_nums[i]);
break;
case 26:
Handler(_nums[i]);
break;
case 27:
Handler(_nums[i]);
break;
case 28:
Handler(_nums[i]);
break;
case 29:
Handler(_nums[i]);
break;
case 30:
Handler(_nums[i]);
break;
case 31:
Handler(_nums[i]);
break;
case 32:
Handler(_nums[i]);
break;
case 33:
Handler(_nums[i]);
break;
case 34:
Handler(_nums[i]);
break;
case 35:
Handler(_nums[i]);
break;
case 36:
Handler(_nums[i]);
break;
case 37:
Handler(_nums[i]);
break;
case 38:
Handler(_nums[i]);
break;
case 39:
Handler(_nums[i]);
break;
case 40:
Handler(_nums[i]);
break;
case 41:
Handler(_nums[i]);
break;
case 42:
Handler(_nums[i]);
break;
case 43:
Handler(_nums[i]);
break;
case 44:
Handler(_nums[i]);
break;
case 45:
Handler(_nums[i]);
break;
case 46:
Handler(_nums[i]);
break;
case 47:
Handler(_nums[i]);
break;
case 48:
Handler(_nums[i]);
break;
case 49:
Handler(_nums[i]);
break;
case 50:
Handler(_nums[i]);
break;
case 51:
Handler(_nums[i]);
break;
case 52:
Handler(_nums[i]);
break;
case 53:
Handler(_nums[i]);
break;
case 54:
Handler(_nums[i]);
break;
case 55:
Handler(_nums[i]);
break;
case 56:
Handler(_nums[i]);
break;
case 57:
Handler(_nums[i]);
break;
case 58:
Handler(_nums[i]);
break;
case 59:
Handler(_nums[i]);
break;
case 60:
Handler(_nums[i]);
break;
case 61:
Handler(_nums[i]);
break;
case 62:
Handler(_nums[i]);
break;
case 63:
Handler(_nums[i]);
break;
case 64:
Handler(_nums[i]);
break;
case 65:
Handler(_nums[i]);
break;
case 66:
Handler(_nums[i]);
break;
case 67:
Handler(_nums[i]);
break;
case 68:
Handler(_nums[i]);
break;
case 69:
Handler(_nums[i]);
break;
case 70:
Handler(_nums[i]);
break;
case 71:
Handler(_nums[i]);
break;
case 72:
Handler(_nums[i]);
break;
case 73:
Handler(_nums[i]);
break;
case 74:
Handler(_nums[i]);
break;
case 75:
Handler(_nums[i]);
break;
case 76:
Handler(_nums[i]);
break;
case 77:
Handler(_nums[i]);
break;
case 78:
Handler(_nums[i]);
break;
case 79:
Handler(_nums[i]);
break;
case 80:
Handler(_nums[i]);
break;
case 81:
Handler(_nums[i]);
break;
case 82:
Handler(_nums[i]);
break;
case 83:
Handler(_nums[i]);
break;
case 84:
Handler(_nums[i]);
break;
case 85:
Handler(_nums[i]);
break;
case 86:
Handler(_nums[i]);
break;
case 87:
Handler(_nums[i]);
break;
case 88:
Handler(_nums[i]);
break;
case 89:
Handler(_nums[i]);
break;
case 90:
Handler(_nums[i]);
break;
case 91:
Handler(_nums[i]);
break;
case 92:
Handler(_nums[i]);
break;
case 93:
Handler(_nums[i]);
break;
case 94:
Handler(_nums[i]);
break;
case 95:
Handler(_nums[i]);
break;
case 96:
Handler(_nums[i]);
break;
case 97:
Handler(_nums[i]);
break;
case 98:
Handler(_nums[i]);
break;
case 99:
Handler(_nums[i]);
break;
default:
std::cout << "Switch: Unhandled number " << _nums[i] << std::endl;
}
}
end = clock();
std::cout << "Switch " << (end - start)/double(CLOCKS_PER_SEC)*1000 << " ms" << std::endl;
}
void member_fns::Handler(int n)
{
}
int _tmain(int argc, _TCHAR* argv[])
{
member_fns analyser;
analyser.HandleIntViaArray();
analyser.HandleIntViaHash();
analyser.HandleIntViaIf();
analyser.HandleIntViaMap();
analyser.HandleIntViaSwitch();
return 0;
}