jeudi 23 juin 2011

Commit 1024

Un beau chiffre rond pour une implémentation fonctionnelle (dans le sens paradigme, pas dans le sens qualitatif) d'une couche client serveur au dessus de boost asio.

samedi 18 juin 2011

g++ 4.6 et C++0x - Range based for

Petit bonus du week-end, g++4.6 débarque sur Debian Wheezy. La principale avancée concerne les "range based for", qui sonnent le glas pour la bonne vielle macro BOOST_FOREACH.

Pour une macro, BOOST_FOREACH était plutôt propre et utile, mais en dehors des détails d'implémentation à s'arracher les cheveux (cherchez un peu si ça vous amuse), elle souffrait de ne pas pouvoir utiliser proprement des déclarations templates, à cause notamment des virgules. Exemple:


#include <vector>
#include <string>
#include <iostream>
#include <boost/foreach.hpp>

int main()
{
std::vector<std::pair<int, std::string> > v =
{std::make_pair(1, "a"),
std::make_pair(2, "b")};

BOOST_FOREACH(const std::pair<int, std::string> & item, v)
{
std::cout << item.first << " - " << item.second << std::endl;
}

return 0;
}

Oh, la belle erreur de compile!

foreach.cpp:12:60: error: macro "BOOST_FOREACH" passed 3 arguments, but takes just 2
foreach.cpp: In function ‘int main()’:
foreach.cpp:12:3: error: ‘BOOST_FOREACH’ was not declared in this scope
foreach.cpp:13:3: error: expected ‘;’ before ‘{’ token

La solution est triviale:

typedef std::pair<int, std::string> ItemT;
BOOST_FOREACH(const ItemT & item, v)
{
std::cout << item.first << " - " << item.second << std::endl;
}

Triviale, mais ennuyeuse. Et non-standard. Et quand bien même utiliser des typedef pour ses types est une bonne idée, l'on on a parfois pas envie. Place donc à la solution 0x:

#include <vector>
#include <string>
#include <iostream>

int main()
{
std::vector<std::pair<int, std::string> > v =
{std::make_pair(1, "a"),
std::make_pair(2, "b")};

for(const std::pair<int, std::string> & item : v)
{
std::cout << item.first << " - " << item.second << std::endl;
}

return 0;
}

C'est pas plus joli?

Entre les range based for et les lambdas, plus aucune raison d'utiliser la macro boost, et presque plus aucune raison d'utiliser une vieille boucle for. L'est pas belle, la vie?

dimanche 12 juin 2011

Asio et sockets - Un design alternatif

Jusqu'à présent, j'avais plutôt pris une route orientée objet, avec une session de base qui contient les appels socket asio dont il fallait dériver.

Cependant, je suis en train de me demander si une approche purement basée sur les callbacks pourrait donner de meilleurs résultats.

Je viens de commiter une classe très simple, dont on ne dérivera à priori pas, et dont voici la signature:


class SocketSession : public std::enable_shared_from_this<SocketSession>
{
public:
SocketSession(boost::asio::io_service & io_service);

void connect(const std::string & host,
int port,
const std::function<void()> & callback);

template<typename BODY>
void readMessage(const std::function<void(const std::shared_ptr<Header> &,
const std::shared_ptr<BODY> &)>
& callback);

template<typename BODY>
void sendMessage(const BODY & body);
}


Toutes les méthodes publiques sont thread safe, car appelant en interne les méthodes correspondantes à travers un strand. L'appelant, lui, se contente de passer les callbacks, lequels peuvent être également protégés par leur propre strand.

Avantages:
  • Le système est complètement thread safe

  • Pas besoin de locks, les appels sont tous protégés par le strand. C'est particulièrement utile pour l'envoi de messages, puisqu'il faut pousser les messages dans une queue afin de n'avoir qu'un seul appel à async_write

  • Contrairement à mon implémentation "dérivante", la partie socket pourra tourner de manière concurrente avec l'appelant, ce qui pourrait permettre une meilleure montée en charge (à vérifier, cependant). Tout du moins, en laissant à l'utilisateur de la classe le choix de protéger ses callbacks à travers un strand, on peut permettre une meilleure parallélisation lorsque c'est possible


L'inconvénient majeur est la multiplication des callbacks, et donc de copies et d'allocations.

mercredi 8 juin 2011

Postgresql et encore plus de requêtes récursives

L'on m'a posé récemment un intéressant problème de base de données qui pourrait se traduire ainsi: étant donné la liste d'employés suivante, déterminer le premier directeur auquel se rattache chaque employé:


create table employees(
id integer not null,
name text not null,
level text not null,
manager_id integer null);

insert into employees values
(1, 'Anne', 'CEO', null),
(2, 'Barbara', 'Director', 1),
(3, 'Carole', 'Director', 2),
(4, 'Delphine', 'Director', 2),
(5, 'Eleonore', 'Supervisor', 2),
(6, 'Fanny', 'Supervisor', 3),
(7, 'Gwen', 'Supervisor', 5),
(8, 'Henriette', 'Supervisor', 7),
(9, 'Isabelle', 'Employee', 5),
(10, 'Juliette', 'Employee', 6),
(11, 'Kariane', 'Employee', 5),
(12, 'Lucie', 'Employee', 4);

La première étape est de pondre une requête récursive, nous donnant pour chaque employé la liste de ses chefs. L'on tiendra à jour également la distance hiérarchique:

with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select
e1.id,
e1.name,
m.depth,
e2.id,
e2.name,
e2.level
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id

Cette requête retourne les résultats suivants:

2,Barbara,1,1,Anne,CEO
3,Carole,1,2,Barbara,Director
4,Delphine,1,2,Barbara,Director
5,Eleonore,1,2,Barbara,Director
6,Fanny,1,3,Carole,Director
7,Gwen,1,5,Eleonore,Supervisor
8,Henriette,1,7,Gwen,Supervisor
9,Isabelle,1,5,Eleonore,Supervisor
10,Juliette,1,6,Fanny,Supervisor
11,Kariane,1,5,Eleonore,Supervisor
12,Lucie,1,4,Delphine,Director
3,Carole,2,1,Anne,CEO
4,Delphine,2,1,Anne,CEO
5,Eleonore,2,1,Anne,CEO
6,Fanny,2,2,Barbara,Director
7,Gwen,2,2,Barbara,Director
8,Henriette,2,5,Eleonore,Supervisor
9,Isabelle,2,2,Barbara,Director
10,Juliette,2,3,Carole,Director
11,Kariane,2,2,Barbara,Director
12,Lucie,2,2,Barbara,Director
6,Fanny,3,1,Anne,CEO
7,Gwen,3,1,Anne,CEO
8,Henriette,3,2,Barbara,Director
9,Isabelle,3,1,Anne,CEO
10,Juliette,3,2,Barbara,Director
11,Kariane,3,1,Anne,CEO
12,Lucie,3,1,Anne,CEO
8,Henriette,4,1,Anne,CEO
10,Juliette,4,1,Anne,CEO


On approche. Prenons donc seulement le cas où un chef est un directeur, et voyons ce que cela donne:

with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select
e1.id,
e1.name,
m.depth,
e2.id,
e2.name,
e2.level
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id
where e2.level = 'Director'

3,Carole,1,2,Barbara,Director
4,Delphine,1,2,Barbara,Director
5,Eleonore,1,2,Barbara,Director
6,Fanny,2,2,Barbara,Director
6,Fanny,1,3,Carole,Director
7,Gwen,2,2,Barbara,Director
8,Henriette,3,2,Barbara,Director
9,Isabelle,2,2,Barbara,Director
10,Juliette,3,2,Barbara,Director
10,Juliette,2,3,Carole,Director
11,Kariane,2,2,Barbara,Director
12,Lucie,2,2,Barbara,Director
12,Lucie,1,4,Delphine,Director

Mieux! Mais comme parfois un directeur dépend d'un autre directeur, les pauvres Fanny, Juliette et Lucie sont en double. Il faut donc ne récupérer pour un employé que le cas où la profondeur est la plus basse. Cela donne des requêtes plutôt ésotériques en vieux SQL. Mais une fois de plus, la modernité nous tend les bras, et les window function permettent de résoudre le problème (presque) immédiatement. Prenons donc la fonction rank(), qui retourne le rang d'une ligne sur une certaine partition. Nous cherchons donc le rang d'une ligne d'employé, partitionné sur cet employé, et ordonné par la profondeur:

with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select
e1.name as employee_name,
e2.name as director_name,
rank() over (partition by e1.name order by depth)
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id
where e2.level = 'Director'

Carole,Barbara,1
Delphine,Barbara,1
Eleonore,Barbara,1
Fanny,Carole,1
Fanny,Barbara,2
Gwen,Barbara,1
Henriette,Barbara,1
Isabelle,Barbara,1
Juliette,Carole,1
Juliette,Barbara,2
Kariane,Barbara,1
Lucie,Delphine,1
Lucie,Barbara,2

On y est presque. Nous voilà donc avec le rang basé sur la profondeur, par nom. Lucie dépend donc d'abord de Delphine, et ensuite de Barbara. Maintenant, obtenir le résultat final est trivial:

select employee_name, director_name
from
(
with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select
e1.name as employee_name,
e2.name as director_name,
rank() over (partition by e1.name order by depth)
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id
where e2.level = 'Director'
) t
where rank = 1

Carole,Barbara
Delphine,Barbara
Eleonore,Barbara
Fanny,Carole
Gwen,Barbara
Henriette,Barbara
Isabelle,Barbara
Juliette,Carole
Kariane,Barbara
Lucie,Delphine

La requête n'est certes pas tout à fait basique, mais elle est relativement claire grâce à la séparation entre la partie récursive d'abord, la window fonction ensuite, et enfin la sur-requête finale pour présenter les résultats. Sans ces outils, l'on aurait eu une panoplie de sous-requêtes se joignant elles-mêmes, pour un résultat bien moins propre, et bien moins efficace.

dimanche 5 juin 2011

Plus d'asio, et copy_if

Je me remets à Asio, et j'essaie notamment de ré-implémenter un handler potable pour mes connections socket en multithreadé. L'idée est également d'abstraire un peu toute la cochonnerie derrière, afin de pouvoir implémenter très proprement son protocole à l'aide de callbacks. J'espère obtenir quelque chose de suffisamment puissant et réactif avec une intégration asynchrone avec un pool de connections vers la base.

Dans un tout autre registre, je me suis battu récemment avec la STL, et notamment avec l'absence de copy_if. Ce que je voulais vraiment:


std::copy_if(input.begin(),
input.end(),
std::back_inserter(output),
boost::bind(&Class::predicate, this, _1));

Mais, copy_if ayant (selon Stroustrup) été oublié, il faut faire avec et utiliser remove_copy_if, qui fait exactement l'inverse. Je me suis battu avec des std::not1 et des bind dans tous les sens, sans arriver à faire compiler la chose. En fait, c'était tout bête.

std::remove_copy_if(input.begin(),
input.end(),
std::back_inserter(output),
!boost::bind(&Class::predicate, this, _1));

Pourquoi ça marche? J'avoue que je ne comprends pas vraiment le fonctionnement interne de bind, et que je le vois plus comme un pointeur sur fonction, avec lequel un ! ne fonctionnerait pas. C'est donc assez magique.

vendredi 3 juin 2011

Valgrind massif - Mémoire un peu trop vive

Je me suis mis à utiliser massif de la suite Valgrind, destiné à mesurer l'utilisation mémoire d'un programme au cours du temps, plus spécifiquement du tas (c'est à dire de la mémoire allouée via malloc/new).

L'outil est très bien tourné: il suffit de compiler son programme avec -g, et de le faire tourner sous massif. Un petit rapport est généré, contenant un certain nombre de snapshots avec le détail de l'utilisation mémoire, et la liste des appels l'ayant générée.

C'est là que l'on retrouve nos bonnes vieilles structures de données: les std::set et les std::map sont des structures tout à fait épatantes, mais l'overhead est significatif. L'on retrouvera ainsi quelles structures bénéficieraient d'une transformation vers un std::deque trié, par exemple.

C'est également une bonne manière de trouver les buffers qui grandissent perpétuellement. Un bout de code qui lirait les paquets venus du réseau pourrait par exemple être implémenté avec un vecteur effectuant des resize() pour redimensionner à la taille du paquet. Mais si resize() peut augmenter la capacité si besoin, il ne la réduit jamais! La seule manière de réduire proprement un vecteur, c'est de l'échanger avec un vecteur tout neuf. Démonstration:


#include <iostream>
#include <vector>

int main()
{
std::vector<int> a;

std::cout << "size\tcapacity\n";
std::cout << a.size() << "\t" << a.capacity() << "\n";

a.resize(10000);

std::cout << a.size() << "\t" << a.capacity() << "\n";

a.resize(1);

std::cout << a.size() << "\t" << a.capacity() << "\n";

std::vector<int> b(a.begin(), a.end());
std::swap(b, a);

std::cout << a.size() << "\t" << a.capacity() << "\n";

std::cout.flush();

return 0;
}

À l'exécution:

size capacity
0 0
10000 10000
1 10000
1 1

La lib geos

La bibliothèque geos permet de gérer des objets géométriques en vue d'une intégration avec divers logiciels de gestion de données géographiques. L'on remarquera en particulier le support du format WKB (pour Well Known Binary) qui le rend donc compatible (efficacement!) avec Postgresql/Postgis.

J'étudie actuellement la possibilité d'utiliser ces outils pour gérer mes mondes OpenRailz. Le gros intérêt est d'avoir déjà tout un tas d'opérations sur les géométries. Les défauts sont tout une plus grande difficulté d'intégration (pas de visiteurs, donc probablement besoin de faire de moches dynamic_cast pour afficher la géométrie, par exemple), des std::auto_ptr un peu partout qui vont faire hurler mon compilo C++0x, et enfin probablement des soucis pour gérer les objets 3D correctement.

J'imagine qu'en considérant un certain nombre de couches horizontales dans le monde, l'on peut se ramener à des problèmes en 2D dans chaque couche.

Première étape, pondre un schéma de BDD qui tienne la route.