Deeper look at PHP’s array: worst case

As I did in the post about the PHP sort functions, I was looking at the PHP source, I found this an interesting thing: the hashing function used on PHP’s hash tables (aka associative arrays).

Above the function definition, a PHP contributor explained the function:

This is Daniel J. Bernstein’s popular `times 33′ hash function as posted by him years ago on comp.lang.c. It basically uses a function like hash(i) hash(i-1) * 33 + str[i]. This is one of the best known hash functions for strings. Because it is both computed very fast and distributes very well.

This function, known as DJBX33A, is very fast and indeed it distributes very well when the data follows an uniform distribution. That is the problem. A user can easily produce keys for an array that would collide in the same hash, making the array have a drastically lower performance on its operations than the usual.

The expected complexity of array operations such as lookup, add and update is constant (O(1)) as it is for any hash table. The thing is that is easy to generate keys so that the complexity of such operations turn into linear (O(N)). Such thing could be used by malicious users to produce a certain level of DoS on unaware systems.

The experiment

In the intent to observe my point, I generate more than 100,000 keys that hashed in the same key and filled an array with those keys and filled other array with the same size with random keys:

define(ARRAY_LEN, 100000);

$keys = file('php_hash_output.txt'); // Where I stored the keys
$biased = array();
$normal = array();

$i = 0;
foreach ($keys as $k) {
    $biased[$k] = ++$i;
    $normal[rand()] = $i;

    if ($i > ARRAY_LEN) break;
}

Then I measured the time spent to iterate over the keys of the two arrays (PHP 5.3.15 cli):

$normal_keys = array_keys($normal);
$t = microtime(true);
$var = 0;
for ($i = 0; $i < ARRAY_LEN; ++$i) {
        $var += $normal[$normal_keys[$i]];
}
echo 'Normal: ' . (microtime(true) - $t) . PHP_EOL;

$t = microtime(true);
$var = 0;
for ($i = 0; $i < ARRAY_LEN; ++$i) {
        $var += $biased[$keys[$i]];
}
echo 'Biased: ' . (microtime(true) - $t) . PHP_EOL;

The output on my 2,3 GHz Intel Core i7 was as expected:

Normal: 0.048759937286377
Biased: 123.01204395294

That means that a task which runs in less than 0.05 seconds could run in more than 2 minutes, that is, more than 2.510 times worse. This behavior happened because the for iterating over the $biased array performed around 10,000,000,000 (10^10, doesn’t fit on 32-bit integers) operations while the iteration over the $normal array performed only 100,000 (10^5).

What could be done?

Universal Hashing

One of the possible solutions is to use the universal hashing approach. Here is the definition given in the universal hashing article on Wikipedia:

Using universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography.

That would guarantee that nobody could generate a set of keys that would collide simply because he/she wouldn’t know what hashing function is being used. But because of that, it would be difficult (to not say impossible) to keep a feature of PHP’s associative arrays: order. This leads to our second alternative.

Implement as Balanced Binary Trees

Implementing PHP’s arrays balanced binary search trees like Red-Black Tree or AVL would allow them to keep the order of the keys at the cost of each operation no longer being constant, on the average case, but logarithmic on its size.

Conclusion

None of the proposed ideas to what can be done is ideal and a good solution would be very hard to come given that PHP is one of the most used programming languages and any major change would impact greatly. As Rasmus himself said a couple of years ago:

We are looking into it. Changing the core hash function in PHP isn’t a trivial change and it will take us some time.

– Rasmus Lerdorf

It is obvious that most part of the array uses in PHP do not suffer from the behavior described in this post because it is used independently of what user inputs. The thing is that programmers should have these things in mind  to know how to properly handle user inputs.

References

• Murilo 😛 – PHP’s sort functions are poorly designed
• Github – PHP Source
• Wikipedia – Hash tables
• Wikipedia – Uniform distribution
• Wikipedia – Universal hashing
• Wikipedia – Balanced binary search trees

Arrays with negative indexes

When we to deal with negative ranges in arrays and those ranges can be negative, we do shifts so we can use natural indexes. For example, if we’re given a range from -50 to 20, usually we allocate an array of 70 positions and when indexing an element we shift by +50 so the position -50 is actually stored on the position 0.

These days, while doing random stuff on the internet, I’ve figured that we can easily work with arrays not only starting from zero but starting from any integer we want. To illustrate that, I wrote this function which allocate sz elements of type T where the array’s first element is in min_index position:

template <typename T>
T* alloc(size_t sz, int min_index = 0)
{
	return (new T[sz]) - min_index;
}

An example of use:

int main()
{	
	char* p = alloc<char>(70, -50);
	
	p[-50] = 'h'; p[-49] = 'e'; 
	p[-48] = 'l'; p[-47] = 'l';
	p[-46] = 'o'; p[-45] = '\0';
	
	std::cout << &p[-50] << '\n';
	
	for (int i = -50; i < -45; ++i) {
		std::cout << p[i] << '\n';
	}
}

The result, as expected:

hello
h
e
l
l
o

Feature turning into bug

Me and one of Unicamp teams

Background

A few days ago, after a sub-regional phase of ACM ICPC, one integrant of a team I’m coaching claimed that there was a bug in their C++ compiler. The team had to solve a geometrical problem, and, for that he implemented a class representing a point and an overload for operator*:

 

class point
{
 public:
     double x, y;

     point(double d) : x(d), y(d) {}
     point(const point& p) : x(p.x), y(p.y) {}     

     point operator*(const point& p)
     {
         // ...
         return result;
     }
};

After coding, he’ve compiled the code and tested with sample input tests. But the results were wrong. After some time debugging he found that the problem was happening because in some part of the code, he was calling point::operator* passing a double as argument and he didn’t implement that overload for operator*. The question was: why the compiler didn’t issued errors?

Implicit object construction

C++ has a feature which allow us to construct a object implicitly when the object’s type have a constructor which accepts one argument. For example, if you have a function which takes a std::string as argument, you can call that function passing a c-style string:

void printstr(std::string s)
{
    std::cout << s << std::endl;
}

// ...

printstr("Foo bar baz"); // Implicitly passes std::string("Foo bar baz");

The Google C++ Style Guide states:

Normally, if a constructor takes one argument, it can be used as a conversion. For instance, if you define Foo::Foo(string name) and then pass a string to a function that expects a Foo, the constructor will be called to convert the string into a Foo and will pass the Foo to your function for you.

So, what happened on the contestant program was something like:

point pt;
double d;

// ...

pt = pt * d; // doesn't find an operator* receiving a double
             // so, it is evaluated as pt = pt * point(d);

This feature can lead in many undesired conversions, so it is recommended to “turn off” this type of object construction by declaring constructors with one single argument explicit. The Google C++ Style Guide requires that all single argument constructors to be explicit, except in cases in which the class is a transparent wrapper for other class.

So, the modified code would be something like:

class point
{
 public:
     double x, y;

     explicit point(double d) : x(d), y(d) {}
     point(const point& p) : x(p.x), y(p.y) {}     

     // ...  
};

Some Links

• Google C++ Style Guide
• Code without explicit http://ideone.com/5bq3h
• With explicit http://ideone.com/NnwWY

PHP’s sort functions are poorly designed

Everyone knows that is possible to sort an array in O(N log N) where N is the array’s length.

We know also, that Quicksort has expected complexity of O(N log N) but in worst case its complextity is O(N^2), and Quicksort is used more than Mergesort (worst case O(N log N)) because constants are smaller and it requires no extra memory and is easy to avoid Quicksort running on the worst case.

The easiest way to avoid bad inputs for Quicksort is choosing the pivot randomly, which means that a malicious user cannot guess a permutation for cracking it.

What I found at the PHP source is that the pivot choosing is done by picking the element at middle of array.

Here is the code (link line 76):

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
{
	void           *begin_stack[QSORT_STACK_SIZE];
	void           *end_stack[QSORT_STACK_SIZE];
	register char  *begin;
	register char  *end;
	register char  *seg1;
	register char  *seg2;
	register char  *seg2p;
	register int    loop;
	uint            offset;

	begin_stack[0] = (char *) base;
	end_stack[0]   = (char *) base + ((nmemb - 1) * siz);

	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];
		end   = end_stack[loop];

		while (begin < end) {
			offset = (end - begin) >> 1; // HERE: choosing the current subarray's middle element
			_zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);

			seg1 = begin + siz;
			seg2 = end;

			while (1) {
				for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
				     seg1 += siz);

				for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
				     seg2 -= siz);

				if (seg1 >= seg2)
					break;

				_zend_qsort_swap(seg1, seg2, siz);

				seg1 += siz;
				seg2 -= siz;
			}

			_zend_qsort_swap(begin, seg2, siz);

			seg2p = seg2;

			if ((seg2p - begin) <= (end - seg2p)) {
				if ((seg2p + siz) < end) {
					begin_stack[loop] = seg2p + siz;
					end_stack[loop++] = end;
				}
				end = seg2p - siz;
			}
			else {
				if ((seg2p - siz) > begin) {
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - siz;
				}
				begin = seg2p + siz;
			}
		}
	}
}

The pivot is named offset here.

Tests

I used the usort() function for counting how many comparisons was needed to sort the array in my cmp() function.
So, lets see the tests:

<?php

$counter = 0; // counts how many comparisons
function cmp($a, $b)
{
	global $counter;
	++$counter;
	return $a - $b;
}

$normal = array();
for ($i = 0; $i < 15; ++$i) {
	$normal[] = $i;
}
shuffle($normal);

$counter = 0;
print "<pre>Normal array:\n";
usort($normal, 'cmp');
print $counter . " comparisons\n\n";

$malicious = array(2, 9, 4, 12, 6, 11, 8, 1, 3, 5, 7, 9, 10, 14, 12);

$counter = 0;
print "Malicious array:\n";
usort($malicious, 'cmp');
print $counter . " comparisons\n</pre>";

?>

And the results:
Normal array:
64 comparisons // variable because of the shuffle

Malicious array:
208 comparisons // constant

It means that the PHP’s sort() family depends on the input array’s length and content while a Randomized Quicksort depends only on the input array’s length.

As we can see, usort() sorted the randomly generated array of length 20 very fast with a few number of comparisons, but in the case of a manipulated array of length 20, the number of comparisons are much more.

In the same way, taking an array of length 10.000, these functions do around 50.000.000 comparisons when the expected is around 132.000. This can be a problem if some “bad” guy inserts manipulated data which your script will sort.

Solution

The naive solution is shuffle()‘n the array before sorting.

<?php

$malicious = array(11, 3, 20, 5, 13, 7, 17, 9, 15, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 19);
shuffle($malicious);

$counter = 0;
print "No longer malicious:\n";
usort($malicious, 'cmp');
print $counter . " coparisons\n</pre>";

?>

Output:
No longer malicious:
76 comparisons


References

zend_qsort source
PHP: sort() function
PHP: usort() function
PHP: shuffle() function
Quicksort – Wikipedia
Mergesort – Wikipedia

Fast and Easy Levenshtein distance using a Trie (in C++)

I implemented this clever algorithm described on Steven Hanov’s blog in C++. Actually this algorithm is a bit different from the original because I wanted to know what is the least Levenshtein distance given a word.

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

/*
 * Algorithm: Edit distance using a trie-tree (Dynamic Programming)
 * Author: Murilo Adriano Vasconcelos <muriloufg@gmail.com>
 */

using namespace std;

// Trie's node
struct trie
{
	typedef map<char, trie*> next_t;

	// The set with all the letters which this node is prefix
	next_t next;

	// If word is equal to "" is because there is no word in the
	//	dictionary which ends here.
	string word;

	trie() : next(map<char, trie*>()) {}

	void insert(string w)
	{
		w = string("$") + w;
		
		int sz = w.size();
		
		trie* n = this;
		for (int i = 0; i < sz; ++i) {
			if (n->next.find(w[i]) == n->next.end()) {
				n->next[w[i]] = new trie();
			}

			n = n->next[w[i]];
		}

		n->word = w;
	}
};

// The tree
trie tree;

// The minimum cost of a given word to be changed to a word of the dictionary
int min_cost;

//
void search_impl(trie* tree, char ch, vector<int> last_row, const string& word)
{
	int sz = last_row.size();

	vector<int> current_row(sz);
	current_row[0] = last_row[0] + 1;

	// Calculate the min cost of insertion, deletion, match or substution
	int insert_or_del, replace;
	for (int i = 1; i < sz; ++i) {
		insert_or_del = min(current_row[i-1] + 1, last_row[i] + 1);
		replace = (word[i-1] == ch) ? last_row[i-1] : (last_row[i-1] + 1);

		current_row[i] = min(insert_or_del, replace);
	}

	// When we find a cost that is less than the min_cost, is because
	// it is the minimum until the current row, so we update
	if ((current_row[sz-1] < min_cost) && (tree->word != "")) {
		min_cost = current_row[sz-1];
	}

	// If there is an element wich is smaller than the current minimum cost,
	// 	we can have another cost smaller than the current minimum cost
	if (*min_element(current_row.begin(), current_row.end()) < min_cost) {
		for (trie::next_t::iterator it = tree->next.begin(); it != tree->next.end(); ++it) {
			search_impl(it->second, it->first, current_row, word);
		}
	}
}

int search(string word)
{
	word = string("$") + word;
	
	int sz = word.size();
	min_cost = 0x3f3f3f3f;

	vector<int> current_row(sz + 1);

	// Naive DP initialization
	for (int i = 0; i < sz; ++i) current_row[i] = i;
	current_row[sz] = sz;
	
	
	
	// For each letter in the root map wich matches with a
	// 	letter in word, we must call the search
	for (int i = 0 ; i < sz; ++i) {
		if (tree.next.find(word[i]) != tree.next.end()) {
			search_impl(tree.next[word[i]], word[i], current_row, word);
		}
	}

	return min_cost;
}

The modification for match all words within a given Leveshtein distance and returning that set is trivial. Just modify the line 72 for storing that word if its Leveshtein distance is less than or equal to a given distance.

For more details, read this: Fast and Easy Levenshtein distance using a Trie
See ya!

Políticas de Controle de Comportamento em C++

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

C++ Idioms: SFINAE

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 2010 – https://murilo.wordpress.com/2010/05/03/estou-no-google-summer-of-code-2010
[1] – Source of Bits and Ints project – https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boost/integer
[2] – Boost C++ Libraries – http://www.boost.org/
[3] – Artigo “Substitution failure is not an error” na Wikipedia – http://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
[4] – Boost enable_if – http://www.boost.org/doc/libs/1_43_0/libs/utility/enable_if.html
[5] – enable_if.hpp – http://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

Estou no Google Summer of Code 2010

Olá pessoal.

Esse ano fui um dos (2^10 + 4) selecionados para passar alguns meses programando nesse evento.

O que é o Google Summer of Code?

O Google Summer of Code (GS0C) é um programa realizado pela Google que consiste em incentivar o e divulgar o software livre entre os estudantes. A filosofia do GSoC é “flip bits not burgers” que é a de incentivar os estudantes em seu período de férias de verão (as nossas férias são no inverno) a programarem, não trabalhar por exemplo em fast-foods como é comum principalmente nos Estados Unidos.

Neste programa, a Google paga aproximadamente 5000 dólares para cada estudante que ao final do programa tenha completado seu projeto.

Funciona assim: os estudantes escolhem uma ou mais organizações de software livre que foram aceitas pelo programa para trabalhar com elas. Aí o estudante tem que propor um projeto para essa organização que pode ser algo do tipo:

• Implementar uma nova ferramenta
• Corrigir bugs
• Documentar código
• Melhorar o desempenho de alguma ferramenta
• Portabilizar para alguma(s) plataforma(s)
• Adicionar features à alguma ferramenta
• etc.

Feito isso, há uma seleção interna e logo é divulgado no site do GSoC a lista de aceitos.

Em seguida você tem uma pessoa alocada pela organização para te ajudar que chamamos de mentor.

Ao final do programa, além dos dólares a mais, o participante ganhará uma camiseta do programa e, no meu ver o mais importante, o certificado emitido pela Google atestando a sua participação.

Eu no GSoC 2010

Eu escolhi a Boost que é um conjunto de bibliotecas para C++ (com bindings para Python) amplamente utilizada no mundo inteiro. Algumas bibliotecas Boost já foram inseridas no padrão C++ através do TR1 (e algumas outras serão inseridas no próximo padrão) e por isso as bibliotecas Boost sejam talvez as mais respeitadas, digamos assim, bibliotecas para C++.

Minha proposta é implementar algoritmos rápidos para manipulação de dados binários em inteiros. Se você quiser saber como é a “cara” das coisas que terei que fazer, aqui você encontra alguns dos algoritmos que implementarei.

Meu mentor chama-se Vicente J. Botet Escribá que parece ser uma bastante pró-ativa e que saca bastante e que tem um blog com conteúdo bem interessante.

Ah, e parabéns ao Marcos Roriz meu colega de universidade que também teve seu projeto aprovado.

O abstract do meu projeto e do Marcos podem ser acessados aqui.

Até mais!

Meta-Programação por Templates

Ultimamente estou me aventurando por essas terras misteriosas e estou fascinado.

Segundo o Wikipedia[1] Meta-programação por templates (TMP ou Template metaprogramming) é:

Template metaprogramming is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates include compile-time constants, data structures, and complete function

Ou seja TMP é uma técnica usada para gerar código-fonte em tempo de compilação. Isso quer dizer que, no momento da compilação, as chamadas à esse tipo de código são avaliadas, o código correspondente é gerado e o resultado já é conhecido, antes mesmo do programa ser executado!

Uau!! Isso é perfeito! Resolverá todos meus problemas…

Não é bem assim, como tudo é feito em tempo de compilação, os valores de entrada para esses algoritmos também devem ser conhecidos em tempo de compilação. Isso quer dizer que os valores de entrada devem ser constantes.

Eis um exemplo de código C++ usando essa abordagem:

#include <iostream>

template<int V>
struct Int { enum { value = V }; }; // representa um valor inteiro

template<int V>
struct bin : Int<(V % 10) + 2 * (bin<V / 10>::value)> {}; // algoritmo recursivo

template<> struct bin<0> : Int<0> {}; // base da recursão

int main()
{
	std::cout << "1000b == " << bin<1000>::value << "d\n";
	std::cout << "10001b == " << bin<10001>::value << "d\n";
	std::cout << "111b == " << bin<111>::value << "d\n";
	std::cout << "10b == " << bin<10>::value << "d\n";
	
	return 0;
}

Como ainda estou aprendendo a respeito, vou finalizar esse post nesse código. Caso queiram discutir o tema em questão, sintam-se a vontade!

Links:

[1] Template Metaprogramming no Wikipedia
Outro material sobre TMP
Boost MPL – biblioteca Boost que provê frameworks para meta-programação

A importância de declarar os destrutores como virtual em C++

Funções Virtuais

Depois de muito tempo sem postar algo aqui vou falar sobre um especificador do C++ que muitas vezes é esquecido: a keyword virtual.

Essa keyword é utilizada para dizer que queremos que faça a avaliação da chamada dessa função em run-time, não em compile-time como é feito por padrão.

Mas no que isso pode ajudar?

#include <iostream>

struct base
{
	void funcao()
	{
		std::cout << "chamada da base\n";
	} 
	
	virtual void vfuncao()
	{
		std::cout << "chamada da base\n";
	}
};

struct derivada: public base
{
	void funcao()
	{
		std::cout << "chamada da derivada\n";
	} 
	
	void vfuncao()
	{
		std::cout << "chamada da derivada\n";
	}
};

int main()
{
	base* pt = new derivada;
	
	//nao virtual
	pt->funcao();
	
	//virtual
	pt->vfuncao();
	
	delete pt;
	
	return 0;
}

Saída:

chamada da base
chamada da derivada

Ou seja, quando uma função-membro (aka. método) é declarada como virtual na classe base, a checagem em run-time é feita e é possível encontrar a vfuncao() na classe

derivada

, assim chamando a função correta, o que não acontece com funcao(): apesar de ter uma função-membro com mesmo nome na classe derivada, é chamada a funcao() da classe base porque o ponteiro que a referencia é do tipo da classe base. Pra isso serve a keyword virtual (êba, vamos usá-la daqui pra frente!).

Mas e os destrutores virtuais?

Segue a mesma idéia e com um agrave de risco eminente de memory leaks!
Se na classe base não temos o destrutor declarado como virtual, temos um grande problema. Vejamos o exemplo:

#include <iostream>

class base 
{
	int* ptr;
public:
	base()
	{
		ptr = new int;
	}
	
	~base() 
	{
		delete ptr;
		std::cout << "'destruindo' base\n";	
	}
};

class derivada: public base
{
	int* dptr;
public:
	derivada() {
		dptr = new int;
	}
	~derivada()
	{
		delete dptr;
		std::cout << "'destruindo' derivada\n";
	}
};

int main()
{
	base* pt = new derivada;
	delete pt;
}

Saída:

'destruindo' base

Como podemos ver, apenas o destrutor da classe base é chamado, deletando o ponteiro ptr. Mas e o dptr declarado em derivada e alocado em seu construtor? Leaked! Se perdeu!

A solução é declarar o destrutor da classe base como virtual e a mágica acontece.

#include <iostream>

class base 
{
	int* ptr;
public:
	base()
	{
		ptr = new int;
	}
	
	virtual ~base() 
	{
		delete ptr;
		std::cout << "'destruindo' base\n";	
	}
};

class derivada: public base
{
	int* dptr;
public:
	derivada() {
		dptr = new int;
	}
	~derivada()
	{
		delete dptr;
		std::cout << "'destruindo' derivada\n";
	}
};

int main()
{
	base* pt = new derivada;
	delete pt;
}

Saída:

'destruindo' derivada
'destruindo' base

Conclusão

É aconselhável que seus destrutores sejam virtuais e que pondere nas outras funções, pois tudo que deixa de ser feito em compile-time e passa a ser feito em run-time, gera overhead na sua aplicação (é… nem tudo é maravilha). Até a próxima!