Perfs : factoriser les if() au runtime grâce aux templates


Une petite bidouille que j'ai été amené à faire et qui je pense vaut le coup d'être partagée : je me suis retrouvé à devoir effectuer un même traitement sur un nombre important d'éléments (ex : on parcourt tous les pixels d'une image pour changer la luminosité...), mais je voulais pouvoir effectuer certaines parties de mon traitement de manière optionnelle, suivant certaines options de configuration. En gros, j'avais quelque chose sous la forme :

for e in elements
   if bOption1
      traitement 1
   if bOption2
      traitement 2

Ce qui est plutôt mauvais d'un point de vue performances (on fait des tests pour rien, et les sauts conditionnels c'est pas ce qu'il y a de mieux non plus).
Idéalement, je voudrais que la résolution des conditions bOption1 et bOption2 soit faite en dehors de la boucle, et que la boucle n'effectue que les traitements qui m'intéressent.


La solution que j'ai trouvée se base sur l'optimisation par le compilateur des instructions du type if(constante).
Prenons l'exemple suivant :

#include <stdio.h>
 
bool AskBoolean(const char* msg)
{
	char buffer[8];
	printf(msg);
	printf(" (y/n):");
	fgets(buffer, sizeof(buffer), stdin);
	return (buffer[0] == 'y');
}
 
inline void ProcessElement(int val, bool bPrintHexa, bool bAvoidOdd, bool bAvoidEven)
{
	if(bAvoidOdd && (val & 1))
		return;
	if(bAvoidEven && !(val & 1))
		return;
	if(bPrintHexa)
		printf("0x%x\n", val);
	else
		printf("%d\n", val);
}
 
int main()
{
	int	test_array[] = {46,58,44,90,99,61,81,23,33,1,49,64,69,94,27,98,58,81,89,98,71,56,30,88,15,70,24,74,2,59,40,51,};
	static const int	nb_elements = sizeof(test_array)/sizeof(test_array[0]);
 
	bool	bPrintHexa	= AskBoolean("Print hexadecimal representation?");
	bool	bAvoidOdd	= AskBoolean("Avoid odd numbers?");
	bool	bAvoidEven	= AskBoolean("Avoid even numbers?");
 
	for(int i=0 ; i < nb_elements ; i++)
	{
		int val = test_array[i];
		ProcessElement(val, bPrintHexa, bAvoidOdd, bAvoidEven);
	}
 
	return 0;
}

Le traitement de chaque élément est isolé dans la fonction inline ProcessElement(). L'idée est de rendre cette fonction template sur les paramètres booléens :

template<const bool bPrintHexa, const bool bAvoidOdd, const bool bAvoidEven>
void ProcessElement(int val)
{
	if(bAvoidOdd && (val & 1))
		return;
	if(bAvoidEven && !(val & 1))
		return;
	if(bPrintHexa)
		printf("0x%x\n", val);
	else
		printf("%d\n", val);
}

Seulement on ne peut pas simplement remplacer :

ProcessElement(val, bPrintHexa, bAvoidOdd, bAvoidEven);

par :

ProcessElement<bPrintHexa, bAvoidOdd, bAvoidEven>(val);

Car bPrintHexa, bAvoidOdd et bAvoidEven ne sont pas des constantes lors de l'appel. A la place, on va créer un tableau de pointeurs de fonctions qui pointera vers toutes les instanciations possibles de ProcessElement :

static void (*processElementTable[])(int) = {
		&ProcessElement<false, false, false>,
		&ProcessElement<true,  false, false>,
		&ProcessElement<false, true,  false>,
		&ProcessElement<true,  true,  false>,
		&ProcessElement<false, false, true>,
		&ProcessElement<true,  false, true>,
		&ProcessElement<false, true,  true>,
		&ProcessElement<true,  true,  true>,
	};

Vous remarquerez l'ordre choisi pour ces instanciations : "false, false, false", puis "true, false, false", puis "false, true, false", etc. Le premier booléen se comporte comme le bit de poids le plus faible d'un compteur, le second comme le bit numéro 1, etc : on a 000, 100, 010, 110, 001, 101, 011, 111.
On peut donc calculer l'index qui correspond à la combinaison qui nous intéresse ainsi :

int index = ( ((int)bPrintHexa) << 0 ) |
            ( ((int)bAvoidOdd)  << 1 ) |
            ( ((int)bAvoidEven) << 2 );

Et enfin, appeler le pointeur de fonction qui nous intéresse :

void	(*processElementFuncPtr)(int) = processElementTable[index];
for(int i=0 ; i < nb_elements ; i++)
{
	int val = test_array[i];
	processElementFuncPtr(val);
}

Cool ! Par contre, la même chose avec 10 options, et la table des possibilités fait 2^10 = 1024 entrées, autant dire qu'on ne va pas se les écrire à la main !
Heureusement, on peut s'en sortir beaucoup plus simplement à l'aide de macros :) Je passe sur les explications quant au code des macros qui permettent ça (on va dire que je le "laisse en exercice au lecteur", les gens aiment bien dire ça dans les articles quand ils ont la flemme d'expliquer quelque chose :D ), le voici :

// macros.h
 
// ---------- Macros for passing runtime boolean values as template arguments -----------
/*
Example:
	template<const bool bTest1, const bool bTest2, const bool bTest3>
	void testBoolean(int arg)
	{
		if(bTest1) {...}	// optimized out by the compiler
		if(bTest2) {...}
		if(bTest3) {...}
	}
 
	static void (*testBooleanTable[])(int arg) = {
		BUILD_FUNC_PTR_TABLE_3(&testBoolean< , >)
	};
 
	int index =	BUILD_FUNC_PTR_INDEX(	ADD_TEST( IsFlag(FL_FLAG_1), 0)
						ADD_TEST( bSomeTest,         1)
						ADD_TEST( var == 5,          2));
 
	testBooleanTable[index](42);	// call testBoolean with the correct values
*/
 
#define PASS_VA_ARGS(...) __VA_ARGS__
 
#define _INTERNAL_BUILD_FUNC_PTR_TABLE_1(FN_NAME_START, ...)	\
	FN_NAME_START false, __VA_ARGS__,		\
	FN_NAME_START true,  __VA_ARGS__,
 
#define _INTERNAL_BUILD_FUNC_PTR_TABLE_2(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_1( FN_NAME_START, PASS_VA_ARGS( false, __VA_ARGS__ ) )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_1( FN_NAME_START, PASS_VA_ARGS( true, __VA_ARGS__ ) )
 
#define _INTERNAL_BUILD_FUNC_PTR_TABLE_3(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_2( FN_NAME_START, PASS_VA_ARGS( false, __VA_ARGS__ ) )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_2( FN_NAME_START, PASS_VA_ARGS( true, __VA_ARGS__ ) )
 
#define _INTERNAL_BUILD_FUNC_PTR_TABLE_4(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_3( FN_NAME_START, PASS_VA_ARGS( false, __VA_ARGS__ ) )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_3( FN_NAME_START, PASS_VA_ARGS( true, __VA_ARGS__ ) )
 
#define _INTERNAL_BUILD_FUNC_PTR_TABLE_5(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_4( FN_NAME_START, PASS_VA_ARGS( false, __VA_ARGS__ ) )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_4( FN_NAME_START, PASS_VA_ARGS( true, __VA_ARGS__ ) )
 
// -------------
#define BUILD_FUNC_PTR_TABLE_1(FN_NAME_START, ...)	\
	FN_NAME_START false __VA_ARGS__,	\
	FN_NAME_START true __VA_ARGS__,
 
#define BUILD_FUNC_PTR_TABLE_2(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_1( FN_NAME_START, false __VA_ARGS__ )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_1( FN_NAME_START, true __VA_ARGS__ )
 
#define BUILD_FUNC_PTR_TABLE_3(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_2( FN_NAME_START, false __VA_ARGS__ )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_2( FN_NAME_START, true __VA_ARGS__ )
 
#define BUILD_FUNC_PTR_TABLE_4(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_3( FN_NAME_START, false __VA_ARGS__ )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_3( FN_NAME_START, true __VA_ARGS__ )
 
#define BUILD_FUNC_PTR_TABLE_5(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_4( FN_NAME_START, false __VA_ARGS__ )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_4( FN_NAME_START, true __VA_ARGS__ )
 
#define BUILD_FUNC_PTR_TABLE_6(FN_NAME_START, ...)	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_5( FN_NAME_START, false __VA_ARGS__ )	\
	_INTERNAL_BUILD_FUNC_PTR_TABLE_5( FN_NAME_START, true __VA_ARGS__ )
 
#define ADD_TEST(TEST, i)	| (((int)((bool)TEST))<<i)
#define BUILD_FUNC_PTR_INDEX(...)	0 __VA_ARGS__

Et le reste du code :

// main.cpp
 
#include <stdio.h>
#include "macros.h"
 
bool AskBoolean(const char* msg)
{
	char buffer[8];
	printf(msg);
	printf(" (y/n):");
	fgets(buffer, sizeof(buffer), stdin);
	return (buffer[0] == 'y');
}
 
template<const bool bPrintHexa, const bool bAvoidOdd, const bool bAvoidEven>
{
	if(bAvoidOdd && (val & 1))
		return;
	if(bAvoidEven && !(val & 1))
		return;
	if(bPrintHexa)
		printf("0x%x\n", val);
	else
		printf("%d\n", val);
}
 
int main()
{
	int	test_array[] = {46,58,44,90,99,61,81,23,33,1,49,64,69,94,27,98,58,81,89,98,71,56,30,88,15,70,24,74,2,59,40,51,};
	static const int	nb_elements = sizeof(test_array)/sizeof(test_array[0]);
 
	bool	bPrintHexa	= AskBoolean("Print hexadecimal representation?");
	bool	bAvoidOdd	= AskBoolean("Avoid odd numbers?");
	bool	bAvoidEven	= AskBoolean("Avoid even numbers?");
 
	static void (*processElementTable[])(int) = {
		BUILD_FUNC_PTR_TABLE_3(&ProcessElement< , >)
	};
 
	int index = BUILD_FUNC_PTR_INDEX(
				ADD_TEST(bPrintHexa,	0)
				ADD_TEST(bAvoidOdd,	1)
				ADD_TEST(bAvoidEven,	2)
						);
	void	(*processElementFuncPtr)(int) = processElementTable[index];
 
	for(int i=0 ; i < nb_elements ; i++)
	{
		int val = test_array[i];
		processElementFuncPtr(val);
	}
 
	return 0;
}

A noter par contre que notre appel à une fonction inline s'est transformé en véritable appel de fonction, puisqu'on utilise un pointeur de fonction. Pour faire les choses bien, il faudrait créer une autre fonction template ProcessAllElements() qui prend le pointeur de fonction en paramètre template et qui fait le parcours. C'est cette fonction qui serait instanciée dans notre tableau de pointeurs de fonctions et sur laquelle le véritable appel de fonction aurait lieu.
Pareil que plus haut : je laisse ça en exercice au lecteur ;)

Enjoy !

, , ,

  1. No comments yet.
(will not be published)

  1. No trackbacks yet.