Murilo :P

C++, Computação, Programação, Web e afins :)

Posts Tagged ‘boost

Políticas de Controle de Comportamento em C++

leave a comment »

Trabalhando no meu projeto na Boost, fui requisitado a implementar uma função para calcular o logaritmo na base 2 de números inteiros. De prontidão pesquisei qual a melhor forma e implementei-a da maneira mais otimizada possível. Fiz um Request For Comments (RFC) na mail list da Boost para saber opiniões sobre qual deveria ser o nome de tal função. Bom, depois de alguma conversa ficou (ao menos por enquanto) decidido que o melhor nome é ilog2.

Bom mas havia um problema logaritmo de 0 é indefinido. E na documentação eu coloquei:

If `value` is equal to 0, the value returned is undefined

Foi aí que um contribuidor da Boost chamado Paul Bristow recomendou a mim que fizesse com que esse comportamento (ilog2(0)) pudesse ser controlável através de políticas, mais especificamente usando boost::math::policies. Resisti um pouco no começo mas cedi e achei bastante interessante.

O que são políticas de tratamento de comportamento?

Basicamente são meios de controlar o comportamento de um algoritmo em certas situações (como o ilog2(0) por exemplo).

Um exemplo de política muito utilizada na biblioteca padrão são as classes que usam std::allocator.

Em C++ podemos implementar políticas facilmente em tempo de compilação.

Implementando Políticas

Vamos então implementar um modelo de política bem simples. Tomei por base as Policies da biblioteca Math da Boost, porém muito mais simplificada por questão de didática.

#ifndef POLICIES_HPP_INCLUDED
#define POLICIES_HPP_INCLUDED

#include <cerrno>      // errno
#include <stdexcept> // std::domain_error

namespace policies
{

// Nossa política
enum error_policy_type
{
	ignore_error = 0,
	errno_on_error,
	throw_on_error,
	user_error
};

// continua

Esse enum define a regra que queremos utilizar em nossa política.

  • ignore_error: ignora o erro e retorna um valor padrão.
  • errno_on_error: seta errno e retorna um valor padrão.
  • throw_on_error: dispara uma exceção.
  • user_error: executa uma função customizada definida pelo usuário, note que a declaração dessa função já existe, tendo apenas que ser feita a definição dessa função.

No caso defini 4 tipos de erros mas pode-se ter mais coisas como “dialog_on_error” se seu projeto utiliza GUI e você quer que apareça uma dialog box informando algo, de qualquer maneira pode-se também usar o user_error se for aplicável.

// continuação

template <int P>
struct domain_error
{
	const static int policy = P;
};

template <int P>
struct overflow_error
{
	const static int policy = P;
};

Aqui declaramos nossos tipos de erro. É basicamente um wrapper para nossas constantes declaradas no enum anterior. P é a política que queremos aplicar. Por exemplo typedef overflow_error<errno_on_error> my_pol;, my_pol é uma política que para tratar overflow_error seguindo a regra errno_on_error. Novamente podemos ter vários tipos de erros que queiramos tratar, coloquei esses dois como exemplo. Notemos também que para simplicidade não tratei os possíveis valores que P pode assumir.

typedef domain_error<ignore_error> default_domain_policy;
typedef overflow_error<errno_on_error> default_overflow_policy;

Aqui definimos quais as políticas padrões para cada tipo de erro. No caso definimos que a política padrão que deve ser seguida quando um domain_error for lançado é a ignore_error. Veremos mais para frente sugestões de como tratar cada política.

// Only the declaration, must be defined somewhere
template <typename T>
T user_domain_error(const char* function, const char* message, const T& val);

template <typename T>
T user_overflow_error(const char* function, const char* message, const T& val);

Aqui nós apenas declaramos os protótipos das funções que serão chamadas quando um user_error for lançado. Se alguém usar a política user_error, este deverá codificar essas funções em algum outro lugar.

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<ignore_error>&)
{
	// Simply ignoring the error
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<errno_on_error>&)
{
	// Sets errno to Error DOMain
	errno = EDOM;
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<throw_on_error>&)
{
	throw std::domain_error(message);
	
	// This will never be returned
	return val;
}

template <typename T>
T raise_domain_error(const char* function, const char* message, const T& val, const policies::domain_error<user_error>&)
{
	return user_domain_error(function, message, val);
}

}

Essas são as funções chamadas para lançar um domain_error. Note que para cada política definimos uma função para tratá-la. Por questão de simplicidade, defini apenas as funções que tratam as políticas de domain_error, para overflow_error por exemplo, precisaríamos definir raise_overflow_error() com sobrecargas para cada política diferente.

O protótipo das funções pode ser modificado de acordo com o que você necessitar. Aqui defini quatro parâmetros:

  • function – o nome da função que causou o comportamento (erro)
  • message – a descrição do que causou o comportamento.
  • val – o valor que essa função deve retornar (quando aplicável)
  • const policies::domain_error& – utilizado para fazer a sobrecarga de função, onde X é a política a ser tratada.

Pode paracer meio desgastante porém depois de pronto, seu sistema complexo pode se beneficiar com transparência das políticas que não devem ser tantas.

A Boost Math por exemplo define apenas 6 tipos de erros e as mesmas 4 políticas que estou usando como exemplo.

Exemplo de uso

Agora suponhamos que tenhamos que implementar uma função que faz a divisão de dois elementos a e b (ohhh divisão!). Essa função, chamada divide, está sendo representada abaixo.

Como sabemos, divisão por zero não existe, então para uma solução elegante para nossa função super complexa, iremos utilizar as nossas políticas.

#include "policies.hpp"

template <typename T, typename Policy>
T divide(T a, T b, const Policy& pol)
{
	if (b == 0) {
		return policies::raise_domain_error("divide(a, b)", 
			"Cannot divide by zero", 
			T(0),   // Value to be returned  
			pol  // Our policy
		);
	}
	
	return a / b;
}

template <typename T>
inline T divide(T a, T b)
{
	return divide(a, b, policies::default_policy());
}

Como pudemos notar, declarei duas funções divide, uma aceitando dois parâmetros que serão computados e a outra aceitando um parâmetro a mais que é a política a ser utilizada. A versão de dois parâmetros na verdade é somente um forwarder para a outra passando a política padrão para ser utilizada. O valor padrão a ser retornado é 0, como podemos notar em T(0).

O “mau” comportamento ocorre quando b == 0, então, se essa condição for satisfeita, simplesmente lançamos um domain_error utilizando a função raise_domain_error.

Para o usuário da função isso é transparente se ele não quiser trabalhar com as políticas, já que uma política padrão é adotada e um valor padrão é retornado.

int main()
{	
	using namespace policies;
	
        // Default policy, zero is returned
	assert((divide(1, 0) == 0));

	typedef domain_error<errno_on_error> errno_pol;
	typedef domain_error<ignore_error>   ignore_pol;
	typedef domain_error<throw_on_error> throw_pol;
	
	// Testing errno_on_error policy, errno is set equal EDOM
	errno = 0;
	divide(1, 0, errno_pol());
	assert((errno == EDOM));
	
	// Testing ignore_error policy, zero is returned
	assert((divide(1, 0, ignore_pol()) == 0));
	
	// Testing throw_on_error policy, a std::domain_error is threw
	try {
		divide(1, 0, throw_pol());
		
		// Never is threw
		throw "error 0";
	}
	catch (std::domain_error&) {
		// FINE!!!
        // Sucessfully caught!
	}
	catch (...) {
                // Bad!
		throw "error 1";
	}
	
	return 0;
}

Se estiver tudo certo, programa acima deve (após ser compilado) ser executado sem nenhuma saída e com nenhuma exceção.

Ficou agora faltando demonstrar apenas como usar as políticas com user_error.

#include <iostream>
#include "policies.hpp"
#include "divide.hpp"

namespace policies {
template <typename T>
T user_domain_error(const char* function, const char* message, const T& val)
{
	std::cout << "Problem on calling function "<< function << std::endl;
	std::cout << "Value " << val << " will be returned " << std::endl;
	
	// DialogBox db(message); or anything you want
	
	return val;
}
}

int main()
{
	policies::domain_error<policies::user_error> usr_err;
	divide(1, 0, usr_err);
        /*  Saída:
  	     Problem on calling function divide(a, b)
             Value 0 will be returned 
         */

	return 0;
}

Como pudemos ver, basta apenas definirmos a função user_domain_error do modo que quisermos para que possamos usar essa política. No caso acima apenas imprimimos uma mensagem com duas linhas e retornamos val.

Arquivos

policies.hpp
divide.hpp
policies_example.cpp
user_error.cpp

Referências

Boost Math Policies
ilog2 implementation
Policy Classes On Generic Programming Techniques from Boost

Advertisements

Written by Murilo Adriano

29 de July de 2010 at 22:02

C++ Idioms: SFINAE

leave a comment »

Introdução

Nesse post falarei sobre uma técnica (ou recurso) utilizada em  C++ que estou utilizando muito no meu projeto[0][1] na Boost Libraries[2] no GSoC, essa técnica é o SFINAE.

SFINAE[3] é uma sigla para “Substitution failure is not an error” que em uma tradução livre quer dizer “Falha na substituição não é um erro”. Segundo[3]:

SFINAE se refere a uma situação em C++ que uma substituição inválida de templates não é um erro.

Especificamente, na criação de um conjunto candidato para a resolução de sobrecarga, alguns (talvez todos) os candidatos deste conjunto pode ser resultante da substituição de argumentos templates deduzidos para os parâmetros de template. Se um erro ocorre durante a substituição, o compilador remove essa potencial sobrecarga do conjunto candidato ao invés de parar com um erro de compilação. Se restam um ou mais candidatos (i.é: pelo menos uma sobrecarga é válida), a resolução é feita e a invocação é bem formada.

Como funciona

Para entender melhor vejamos esse trecho de código:

template <typename T>
struct A
{
	typedef T type;
	T value;
};

template <>
struct A<bool>
{
};

template<typename T>
typename A<T>::type func(const A<T>& param)
{
	std::cout << param.value << std::endl;
}

Esse código compila sem warnings. A função template func() é sobrecarregada e retorna o tipo T. Mas você deve estar se perguntando, o que acontece quando T = bool? Esse é justo o ponto do SFINAE!
Para T = bool, typename A::type seria uma declaração inválida já que A não contém o tipo type declarado, porém, com SFINAE, essa sobrecarga é simplesmente descartada e para qualquer outro T que não bool, func(A) é uma chamada legal porque sua sobrecarga é gerada.

Aplicações

Como eu disse no começo deste post eu estou utilizando bastante SFINAE no meu projeto do Google Summer of Code com uma utilidade chamada enable_if[4] encontrado na Boost.

Enable_if é uma classe (ou struct) que “ativa” a declaração de algo (classe, função, etc) se uma condição for satisfeita por meio do SFINAE. Vou mostrar aqui uma maneira de fazer um enable_if like, e quem quiser saber mais sobre o enable_if da Boost é encorajado a ler[4][5].

Vamos ao código:

/* Cond é a condição de ativação
 * Type é o tipo que será declarado pelo membro type.
 */
template <bool Cond, typename Type = void>
struct enable_if_c
{
	typedef Type type;
};

/*
 * Especialização, quando Cond for false,
 * 	esse template vazio é invocado.
 */
template <typename Type>
struct enable_if_c<false, Type>
{
	// empty
};

Ou seja, sempre quando Cond for true, existirá um membro type declarado em enable_if_c, quando Cond for false o membro type não existirá.

Um exemplo de uso:

/*
 * Nossa função pega o bit mais significativo de value e retorna um bool.
 * 	***Note que nesse exemplo estamos assumindo que T é um tipo inteiro.***
 */

/*
 * Para retornar o bit mais significativo de um T com 4bytes (32 bits),
 * 	deslocamos 31 bits para a direita e fazemos um & com 1.
 */
template <typename T>
typename enable_if_c<sizeof(T) == 4, bool>::type msb(T value)
{
	std::cout << "Value have 4 bytes.\n";
	return (value >> 31) & T(1);
}

/*
 * Porém se T é um tipo de 1byte (8 bits) o deslocamento deve ser de
 * 	7 bits para pegarmos o bit mais significativo.
 */
template <typename T>
typename enable_if_c<sizeof(T) == 1, bool>::type msb(T value)
{
	std::cout << "Value have 1 byte.\n";
	return (value >> 7) & T(1);
}

Ou seja, a função de cima, é sobrecarregada para todos os tipos que tenham 32 bits (sizeof(T) == 4) e a de baixo é sobrecarregada para todos os tipos que tenham 8 bits (sizeof(T) == 1). Assim, no processo de resolução de sobrecarga, os outros tipos que não tem nem 8 nem 32 bits, são descartadas pois cairá na especialização enable_if_c que não possui um membro type (usado como retorno da função msb), comportamento citado anteriormente.

Para testar:

int main()
{
	int a = -3;
	unsigned b = 190000;
	char c = 129;
	uint16_t d = 10;
	uint64_t e = 10000000;
	
	std::cout << "Retorno int: " << msb(a) << std::endl;
	std::cout << "Retorno unsigned: " << msb(b) << std::endl;
	std::cout << "Retorno char: " << msb(c) << std::endl;
}

Se tentarmos executar com uma condição que não é true, teremos um erro em tempo de compilação, como podemos ver abaixo:

...
uint16_t d = 10;
uint64_t e = 10000000;

std::cout << "Ret: uint16_t: " << msb(d) << std::endl
std::cout << "Ret: uint64_t: " << msb(e) << std::endl;
...

/*
/Users/murilo/Documents/programming/blog/sfinae.cpp: In function ‘int main()’: /Users/murilo/Documents/programming/blog/sfinae.cpp:61: error: no matching function for call to ‘msb(uint16_t&)’ 
/Users/murilo/Documents/programming/blog/sfinae.cpp:62: error: no matching function for call to ‘msb(uint64_t&)’
*/

Alguns outros exemplos usando o enable_if da Boost você pode encontrar no meu projeto[1] na Boost onde utilizo enable_if aos montes.

Nesse post exemplifiquei SFINAE com funções, mas também é aplicável para classes. Um exemplo você pode ver aqui [6].

Até a próxima!

Referências

[0] – Estou no Google Summer of Code 2010https://murilo.wordpress.com/2010/05/03/estou-no-google-summer-of-code-2010
[1] – Source of Bits and Ints projecthttps://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer
[2] – Boost C++ Librarieshttp://www.boost.org/
[3] – Artigo “Substitution failure is not an error” na Wikipediahttp://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
[4] – Boost enable_ifhttp://www.boost.org/doc/libs/1_43_0/libs/utility/enable_if.html
[5] – enable_if.hpphttp://www.boost.org/doc/libs/1_35_0/boost/utility/enable_if.hpp
[6] – static_sign_extend.hpp at Boost Trac – https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer/static_sign_extend.hpp

Written by Murilo Adriano

19 de June de 2010 at 17:02

Posted in Boost, C/C++, Programação

Tagged with , , , ,

C++: Uma introdução a Threads com boost::thread

with 10 comments

boostPara quem ainda não conhece, Boost é um conjunto de bibliotecas C++ multiplataforma que trabalha bem com a STL e é muito bem aceita na comunidade. Já existem dez bibliotecas Boost incluídas no C++ TR1 e que estarão no C++0x além de muitas outras que estarão no C++0x e que atualmente não estão no TR1.

Para instalar o boost siga esse Getting Started.

Fazer threads com boost::thread é muito simples. Basta criar uma função ou um functor e passar pro construtor da classe boost::thread:

class functor
{
public: void operator()() {};
};

functor::operator()()
{
	/* content */
}

void function()
{
	/* content */
}

functor obj;
boost::thread tObj(obj); //passa uma cópia de obj
boost::thread tObjRef(boost::ref(obj)); //passa uma referência para obj
boost::thread tFunc(&funcao);

// aguarda a finalização das threads
tObj.join();
tObjRef.join();
tFunc.join();

//ou pode-se criar grupos de threads

boost::thread_group my_threads;
my_threads.create_thread(obj);
my_threads.create_thread(boost::ref(obj));
my_threads.create_thread(&function);

my_threads.join_all(); // aguarda o grupo de threads retornar

Para ilustrar como funciona, fiz dois programinhas simples:

cin.cpp

#include <iostream>
#include <boost/thread/thread.hpp>
#include <boost/thread/xtime.hpp>

//determina se o usuário já entrou com o número
bool flag = false;

struct in
{
	int n;

	in() : n(0) {};

	void operator()()
	{
		//try to read the number
		while (!(std::cin >> n)) {
			std::cin.clear();
			std::cin.ignore(10000, '\n');

			std::cout << "Enter a valid number" << std::endl;
		}
		
		flag = true;
	}

};

void my_alarm()
{
	while (!flag) {
		//shows the message
		std::cout << "Enter a number" << std::endl;
		
		boost::xtime time;
		boost::xtime_get(&time, boost::TIME_UTC); //current time

		time.sec += 5; //adds 5 secs to time
		//sleep 5 secs
		boost::thread::sleep(time);
	}

	//exiting function
	std::cout << "Alarm finished" << std::endl;
}

int main()
{
	in test;
	
	//create the two threads
	boost::thread tin(boost::ref(test));
	boost::thread tal(&my_alarm);

	// wait
	tin.join();
	tal.join();

	//show the user's number
	std::cout << "Ok " << test.n << std::endl;
	
	return 0;
}

Esse programa é composto por duas threads (fora o fluxo principal) uma que é responsável por fazer a leitura de um número e a outra que fica a cada 5 segundos mostrando uma mensagem “Enter a number” enquanto o usuário não digitar um número válido. Quando o usuário digita um número válido, a flag é setada e os loops das duas threads são finalizados. Finalmente quando as duas threads são finalizadas, o fluxo normal de main() é reestabelecido e é mostrado o número digitado pelo usuário.

Lembrando que para usar boost::thread é necessário “linkar” a biblioteca ao programa. No caso do Linux é necessário linkar também a biblietca pthread em Windows “linkar” a win32api. No meu caso preferi usar linkagem estática.

murilo@blacksheep:~/programacao/boost$ g++ cin.cpp libboost_thread-gcc43-mt-1_39.a -o cin -lpthread
murilo@blacksheep:~/programacao/boost$ ./cin
Enter a number
Enter a number
naoehumnumero
Enter a valid number
Enter a number
4
Alarm finished
Ok 4

O outro exempo que fiz é um programinha que faz a multiplicação de duas matrizes e “simultaneamente” (depende de processador e SO) mostra uma barra de progresso com o progresso da operação.

multiplica.cpp

#include <iostream>
#include <boost/thread/thread.hpp>
#include <boost/thread/xtime.hpp>

const int MAX = 1000;

int A[MAX][MAX];
int B[MAX][MAX];
int C[MAX][MAX];

int porcentagem = 0;

void multiplica()
{
	int soma;	
	
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			soma = 0;
			for (int k = 0; k < MAX; k++) {
				soma += A[i][k] * B[k][j];
			}
			
			C[i][j] = soma;			
		}
		if (i % 10 == 0) porcentagem++;
	}
}

void barra_de_progresso()
{
	int atual = 0;
	while (porcentagem != 100) {
		if (atual != porcentagem) {
			if (porcentagem % 10 == 0) {
				std::cout << "\b\b" << porcentagem << '%';
			}
			else std::cout << '=' << std::flush;
			
			atual++;
		}
	}
}

int main()
{
	boost::thread tMultiplica(&multiplica);
	boost::thread tProgresso(&barra_de_progresso);
	
	boost::xtime inicio, fim;
	boost::xtime_get(&inicio, boost::TIME_UTC);
	
	std::cout << "Iniciando a multiplicação de matrizes" << std::endl;
	
	tMultiplica.join();
	tProgresso.join();
	
	boost::xtime_get(&fim, boost::TIME_UTC);
	
	std::cout << "\n\nProcesso terminado em " << 
		(fim.sec - inicio.sec) << " segundos" << std::endl;
	
	return 0;	
}

Saída:

murilo@blacksheep:~/programacao/boost/thr$ g++ multiplica.cpp libboost_thread-gcc43-mt-1_39.a -lpthread -o multiplica
murilo@blacksheep:~/programacao/boost/thr$ ./multiplica
Iniciando a multiplicação de matrizes
=======10%=======20%=======30%=======40%=======50%=======60%=======70%=======80%=======90%=======100%

Processo terminado em 43 segundos

Claro que o que menos nos importa nesse momento é o valor das matrizes e a multiplicação em si, por isso nem me dei ao trabalho de inicializar as matrizes nem de fazer nada com a matriz resultante.

Acredito que para uma introdução está bom e deu pra mostrar como é fazer programas com boost::thread com esses simples exemplos. Mais exemplos você pode encontrar na pasta libs do boost.

Links:

Written by Murilo Adriano

6 de August de 2009 at 18:06

Posted in C/C++, Programação

Tagged with , , ,