Yaaaa!

Vu la vie de Genghis Khan hier à la télé... Ça me donne envie de rejouer à Mount & Blade. Pas bon pour le développement, ça!

C'est maintenant que ça commence

De très bons retours de ma présentation de Médoc sur LinuxFr (ici et là). Merci à tous les commentateurs! J'en retire plus particulièrement ces quelques points:

• Tout d'abord, faire fonctionner Médoc sur la machine de quelqu'un d'autre est un sacré défi. L'on a découvert des soucis liés aux locales, et je soupçonne peut-être certains problèmes 32/64 bits. Enfin, les autres scanners ont des options spécifiques que je n'avais pas implémentées


• Ensuite, utiliser du JPG pour mes images n'est probablement pas l'idée du siècle: en effet, un format comme DjVu semble bien plus approprié. J'espère pouvoir réduire significativement la taille de la base, qui devient de plus en plus difficile à sauvegarder.


• Enfin, il semble pertinent de réintégrer la reconnaissance de caractères, d'autant plus que Debian fournit maintenant la bibliothèque ocrad. Les autres solutions de reconnaissance de caractères ne fournissaient pas de bibliothèque C, ce qui m'avait refroidi.

Pas mal de boulot devant moi, donc. Tout d'abord, je vais, ou plutôt, je suis en train d'installer une Ubuntu 32 bits avec une locale française dans une machine virtuelle, pour tenter de reproduire certains bugs qui m'ont été signalés. Ensuite, je vais m'attaquer à l'amélioration du logiciel, ajout de fonctionnalités, et simplification du processus d'installation.

Médoc v1.0

Voilà, la dernière fonctionnalité de base vient d'être implémentée. La galerie étant maintenant munie de fonctions de sélection et de ré-ordonnancement, j'annonce que Médoc est pleinement utilisable, et tague donc cette version 1.0. Un peu de documentation sur l'installation est disponible sur le wiki du dépôt chez Github.

Murf

C'était bien la peine de passer une heure à faire des benchmarks. J'utilisais au boulot un boost::unordered_set d'entiers, avec des performances très décevantes, et l'on m'avait recommandé de remplacer la fonction de hachage par défaut avec MurmurHash, avec des résultats tout à fait impressionnants. J'ai donc tenté de les reproduire à la maison, mais, étrangement, ce fut impossible... La version standard de l'unordered_set est légèrement plus lente dans la bibliothèque standard que chez Boost, mais surtout, l'utilisation de MurmurHash plombe les performances très sérieusement.

Avec des chaines de caractères, par contre, MurmurHash commence à montrer les dents, et se montre plus rapide. Étrangement, dans ce cas, le hashset de la bibliothèque standard est plus rapide.

J'ai dû rater quelque chose, mais quoi?

Une gallerie en wxWidgets

C'est basique, mais ça fait le boulot. Je viens de merger la branche gallerie dans la branche principale, maintenant que mon contrôle de galerie d'images est suffisamment fonctionnel. Voici la bête:



Vu que je n'avais rien modifié dans ma branche principale, le merge a été particulièrement simple:

git branch master <= hop, de retour sur la branche princpale
git merge gallery <= on merge la gallerie, de fait un simple fast forward
git branch -d gallery <= et on détruit la branche devenue inutile

Il reste encore à permettre le réarrangement des pages, et on devrait être fonctionnellement complet.

En vrac

Pic de fréquentation aujourd'hui!

Pour une raison que j'ignore, tout le monde (enfin, toutes proportions gardées) s'est précipité sur mon tutorial lwt, qui trainait sur le blog depuis 6 mois. La révolution fonctionnelle est en marche!

Petit souci classique dans mon composant wxWidgets de galerie: je code en dur la largeur du composant, ce qui me permet d'y placer exactement le nombre d'images requis en largeur. Malheureusement, quand il y a trop d'images en longueur, la barre de défilement verticale apparait, ce qui réduit de quelques dizaines de pixels la largeur de la zone client, provoquant une très inutile barre de défilement horizontale (ça va, vous suivez?). Je pense tenter de corriger cela en forçant la barre verticale à être toujours présente, et ma zone client juste assez grande pour faire tenir mes images en largeur plus la barre.

Ah, et je suis enfin plongé dans la partie "sociale" de Github. Je ne pensais pas y rencontrer quiconque, mais si, Dongorath, commentateur de ce blog, me "follow"! Si tu me lis encore, coucou Dongo :)

Github - Ça vient doucement...

Aujourd'hui, je me suis mis à implémenter une vraie galerie d'images au lieu de la bête listbox, pour représenter la liste des images déjà importées. Ce fut donc l'occasion d'essayer de comprendre comment faire une branche sur git, et la pousser sur github. Avec l'aide de StackOverflow, voilà ce que je fis:

Tout d'abord, créer une nouvelle branche à l'aide de la commande "checkout":

# git checkout -b gallery

Git me confirme que mes changements sont maintenant bien situés sur la branche, et m'indique "Switched to a new branch 'gallery'".

# git branch

* gallery
master

C'est bien la confirmation que j'ai maintenant deux branches, et que ma branche courante est gallery. Ouf!

# git commit

# git push origin gallery

Voilà, ma branche est partie sur github. Je vérifie sur le graphe des branches que tout est bien comme je m'y attendais.

Je vais finir par y comprendre quelque chose.

Benchmark

Je testais aujourd'hui les performances d'un nouveau bout de code pour faire de la sérialisation, templaté de partout, le comparant à du vieux code moins générique, mais réputé rapide.

Et je ne comprenais pas pourquoi mon nouveau code, sur un bout tout simple, le calcul de la taille du buffer nécessaire à la sérialisation d'un vecteur de chaînes de caractères, était plus lent. Pour un vecteur de 10000 chaînes, mon code tournait à 19µs, et l'autre à 14µs.

L'algorithme était pourtant tout bête: on prend 4 pour contenir la taille du vecteur, puis on ajoute pour chaque chaîne 4, pour la longueur de la chaine, puis la longueur de la chaîne elle-même. En pseudo-code, pour un vecteur v: 4 + (for each c in v : 4 + length(c)).

Je tente de remplacer mes itérateurs par des entiers et des index, j'enlève et remets les templates, je vérifie bien que le compilo inline tout... Toujours la différence.

Finalement, c'était tout bête. Une telle différence vient rarement des micro-optimisations du code, et bien plus souvent d'un algorithme suboptimal. Le vieux code calculait la longueur de cette manière: 4 + 4 * length(v) + (for each c in v : length(c)). Ce qui sauvait 10000 additions contre une simple multiplication, et me coûtait les 4µs.

wxWidgets - Un OK plus standard

Avant:


Après:


La méthode wxDialog::CreateStdDialogButtonSizer créé automatiquement les boutons standards pour la plateforme, en termes de disposition (à droite, OK puis Cancel pour Windows, Cancel puis OK pour Apple et GTK, avec le texte et les icônes...). La méthode renvoie un sizer, qu'il est possible d'ajouter directement au sizer principal de la boite de dialogue.

C'est y pas plus joli comme ça?

OCaml détecté

Yay, Github a manifestement refait tourner les statistiques, et détecte bien maintenant que Médoc est fait à 45% d'OCaml.

Écrire son propre wxImageHandler - Lire des PDF

La bibliothèque wxWidgets fait reposer son système de chargement d'images sur la classe wxImageHandler. L'idée est d'en dériver, et de fournir l'implémentation pour lire son type d'image particulier. Une fois ajouté au framework, l'application peut lire le nouveau type d'image de manière transparente.

Voici un wxImageHandler très basique pour afficher, sous forme d'image, des fichiers PDF, en utilisant les routines de la bibliothèque ImageMagick.

Tout d'abord, le fichier d'en tête, tout simple: l'on dérive de wxImageHandler, et l'on implémente les méthodes "GetImageCount", "LoadFile", "SaveFile", et "DoCanRead".

#include <wx/wx.h>

class PdfImageHandler : public wxImageHandler
{
public:
  PdfImageHandler();

  virtual int GetImageCount(wxInputStream & stream);
  virtual bool LoadFile(wxImage * image,
                        wxInputStream & stream, 
                        bool verbose=true, 
                        int index=-1);
  virtual bool SaveFile(wxImage * image, 
                        wxOutputStream & stream, 
                        bool verbose=true);
  
protected:
  bool DoCanRead(wxInputStream & stream);
};

À l'implémentation, l'on utilise l'API Magick++, et un peu de MagickCore, pour lire le fichier PDF et le renvoyer sous forme d'image.

#include "PdfImageHandler.h"

#include <Magick++.h> 
#include <wx/mstream.h>

namespace
{
  std::list<Magick::Image> loadImages(wxInputStream & stream)
  {
    wxFileOffset offset = stream.TellI();
    wxMemoryOutputStream buffer;
    stream.Read(buffer);
    stream.SeekI(offset);
    
    Magick::Blob blob  
      (buffer.GetOutputStreamBuffer()->GetBufferStart(),
       buffer.GetOutputStreamBuffer()->GetBufferSize());
    
    std::list<Magick::Image> images;
    Magick::readImages(&images, blob);
    return images;
  }
}

PdfImageHandler::PdfImageHandler()
{
  SetName(_("PdfImageHanlder"));
  SetExtension(_("pdf"));
}

int PdfImageHandler::GetImageCount(wxInputStream & stream)
{
  return loadImages(stream).size();
}

bool PdfImageHandler::LoadFile(wxImage * image, 
                               wxInputStream & stream, 
                               bool verbose, 
                               int index)
{
  std::list<Magick::Image> images = loadImages(stream);
  std::list<Magick::Image>::iterator it = images.begin();
  if(index != -1)
  {
    std::advance(it, index);
  }
  if(it != images.end())
  {
    Magick::Image & page = *it;
    Magick::Blob blob;
    page.write(&blob);
    wxMemoryInputStream input(blob.data(), blob.length());
    *image = wxImage(input);
    return true;
  }
  else
  {
    return false;
  }
}

bool PdfImageHandler::SaveFile(wxImage * image, 
                               wxOutputStream & stream, 
                               bool verbose)
{
  return false;
}

bool PdfImageHandler::DoCanRead(wxInputStream & stream)
{
  unsigned char hdr[4];
  if(!stream.Read(hdr, WXSIZEOF(hdr)))
  {
    return false;
  }
  else
  {
    return memcmp(hdr, "%PDF", WXSIZEOF(hdr)) == 0;
  }
}

La routine est malheureusement très inefficace: l'on se retrouvera à charger l'ensemble du PDF pour retourner le nombre de pages, puis recharger l'ensemble du PDF pour retourner chaque page. ImageMagick propose des routines permettant de "pinger" une image, c'est à dire d'en charger les propriétés sans les données. Pas sûr que le chargement de fichiers PDF, qui passe par GhostScript, permette ce genre d'astuce pour ne charger que l'image courante.

Mais si ce n'est pas rapide, au moins, ça marche! Une fois le handler ajouté, via une ligne du type

wxImage::AddHandler(new PdfImageHandler);

il devient possible de charger directement un fichier PDF dans une wxImage. L'on pourra utiliser wxImage::GetImageCount et le paramètre d'index du constructeur pour aller chercher chaque page individuellement.

Je commence à apprécier Github

Ce site est un vrai petit bijou. Je découvre leur système de tickets, qui permet de lever des bugs ou des feature requests, de les assigner à un développeur et à une release et de les tagger. Ensuite, lorsque l'on corrige le ticket n, il suffit d'avoir "fix #n", "fixes #n", "close #n" ou "closes #n" dans le message de commit. Par exemple, mon dernier commit: "Added possibility to clear all loaded images. Fixes #1." ferme automatiquement le ticket correspondant, en y incluant le commentaire et un lien vers le commit, et ceci, pratiquement immédiatement après le push.

Par contre, étrangement, les statistiques en termes de langages utilisés ont l'air un poil cassé: j'ai commité ce week-end un millier de lignes d'OCaml et un peu de SQL, mais Github indique obstinément 100% de C++.

Médoc - C'est utilisable

Mon dernier commit complète la phase initiale du client lourd Médoc: il est maintenant possible d'importer un document via le scanner, puis de le sauver dans la base de données. Il aura fallu ajouter quelques boites de dialogues pour entrer la configuration de la base, et pour définir les détails du document.




Il va falloir travailler sur bon nombre de détails pour rendre le client vraiment efficace, comme par exemple pouvoir effacer ou réordonner les pages, ou sauver les paramètres de la session précédente pour ne pas avoir à tout redéfinir à chaque fois.

Le problème principal, pour l'instant, est d'arriver à trouver enfin la configuration du scanner qui fonctionne correctement. Pour mon scanner HP, SANE me sort la liste d'options suivante:



Déjà, pour "Length measurement", il faut absolument changer l'option de "Padded" à "Approximate", sinon le scanner ajoute de lui même une horrible bande blanche en dessus des documents. Ensuite, vient le souci du batch: mon scanner peut scanner une pile de documents d'un coup, dans lequel cas il faut à la fin de chaque page boucler et tester si le scanner est prêt. Si l'on a bien mis l'option "Batch", le scanner répond après la dernière page qu'il n'y a plus de documents, et tout s'arrête. Tout va bien. Si l'on oublie l'option "Batch", par contre, le scanner tourne indéfiniment.

Pire, lors du scan à plat: dans ce cas, le scanner indique toujours un document comme étant disponible. Dans ce cas, il ne faut simplement pas boucler. Il semblerait donc que je sois obligé de demander à l'utilisateur son intention. J'aurais préféré que le scan soit plus intelligent, et me retourne une condition d'arrêt dans tous les cas.

Bien entendu, ce n'est valide que pour mon modèle de scanner. À partir de là, si quiconque veut tenter l'aventure, hic sunt dracones.

Mélanger pqxx et wxWidgets

Une part non négligeable du boulot de développeur est de convertir des données d'un format vers un autre pour faire causer deux composants séparés.

Alors, pour une fois que c'est simple, l'on ne va pas bouder notre plaisir. C'est que le concepteur de libpqxx a eu la bonne idée de fournir des type traits pour passer ses propres types à la base de données pour les requêtes préparées.

Si l'on veut donc pouvoir sauver des chaînes de caractères wxWidgets (wxString) ou des dates (wxDateTime), il suffit d'implémenter le trait qui va bien. Cela ressemble à ça:

namespace pqxx
{
  template<> struct PQXX_LIBEXPORT string_traits<wxString>
  {
    static const char * name() { return "wxString"; }
    static bool has_null() { return false; }
    static bool is_null(const wxString &) { return false; }
    static wxString null() 
    { internal::throw_null_conversion(name()); return wxString(); }
    static void from_string(const char Str[], wxString & Obj) 
    { Obj = wxString(Str, wxConvUTF8); }
    static PGSTD::string to_string(const wxString & Obj) 
    { return std::string(Obj.mb_str(wxConvUTF8)); }
  };
  
  template<> struct PQXX_LIBEXPORT string_traits<wxDateTime>
  {
    static const char * name() { return "wxDateTime"; }
    static bool has_null() { return false; }
    static bool is_null(const wxDateTime &) 
    { return false; }
    static wxDateTime null() 
    { internal::throw_null_conversion(name()); return wxDateTime(); }
    static void from_string(const char Str[], wxDateTime & Obj) 
    { Obj.ParseDateTime(wxString(Str, wxConvUTF8)); }
    static PGSTD::string to_string(const wxDateTime & Obj) 
    { return std::string(Obj.Format().mb_str(wxConvUTF8)); }
  };
}

L'on indique simplement comment convertir une PGSTD::string (qui est en fait une bête std::string) dans le type de travail, et basta, avec ça, les appels du type

T.prepared("statement")(wxString1)(wxString2)(wxDateTime1).exec();

passent comme une lettre à la poste.

La punchcard de github

J'aime bien le graphique "punchcard" de github. Pour Médoc, par exemple, l'on voit bien que je ne suis pas un matinal, et que je code le week-end et en soirée (forcément, le reste du temps, je code pour manger). Plus étrange, il semble que je sois plus productif en début de semaine qu'en fin.

L'on pourra comparer (façon de parler...) avec la punchcard du noyau linux, où les développeurs travaillent principalement la semaine entre 9h et 17h.

Je suis plutôt satisfait de GitHub, non que j'utilise plus d'un pouillème de ses fonctionnalités. Le push est très rapide, le site réactif, et les stats rigolotes.

std::lower_bound

Imaginons que l'on veuille enregistrer une série de segments [a; b[, et à partir d'un point donné, rapidement retrouver le segment auquel il appartient. Typiquement: sachant que chaque événement court entre deux dates, pour une date donnée, trouver de quel événement il s'agit.

• Comment donc placer ses segments dans une structure pour s'y retrouver simplement et efficacement?


• Et comment gérer plusieurs segments qui se chevauchent?

Médoc - Dernières nouvelles

Belles améliorations ce week-end de la partie import. J'ai découvert que je m'étais planté sur le nombre d'options disponibles, et qu'il y en avait de fait bien plus. Deux options en particulier:

• La length-measurement: mon scanner HP considère (et renvoie via l'API) que la longueur de la page est environ deux fois plus grande que la largeur. Par défaut (l'option Padded), il ajoute donc une grande bande blanche en dessous de la page standard 210x297. Mais en mode Approximate, il me renvoie un signal de fin de données lorsqu'il arrive à la vraie fin de la page.


• Le batch-scan: sans cette option, le scan à plat fonctionne normalement, mais le scan déroulant pour plusieurs documents s'y perd, et après la dernière page se met à scanner des pages vides jusqu'à ce que l'on termine le job manuellement. Avec l'option, il s'arrête à la dernière page, mais c'est alors le scan à plat qui refuse d'avancer! Il n'est pas sûr que j'arrive à trouver la combinaison d'options qui marche tout le temps, donc il va peut-être falloir que l'utilisateur indique s'il compte scanner une seule ou plusieurs pages.

Ceci dit, et pour peu que l'on fasse attention aux options, l'import est parfaitement fonctionnel. Quelques options supplémentaires, comme le réarrangement des pages, ou la rotation d'une image, seront utiles, bien sûr. Mais maintenant, le minimum nécessaire pour rendre l'outil utile est d'implémenter les fonctions d'export, vers une base de données Médoc, ou vers un pdf.

Et Jira se facebookise

Décidément, c'est la saison.

Atlassian Software est une petite boite australienne qui a fait son trou dans les outils collaboratifs, et notamment Jira, qui est un outil web de suivi de bugs, plutôt bien fait d'ailleurs.

Nous avons bondi de la version 3.7 à la version 4.4, et là, c'est le drame. Cette transition corrige quelques défauts qui étaient certes ennuyeux, mais mineurs, mais surtout propulse le système de suivi à l'ère Facebook. Fausse bonne idée? Probablement.

Flux RSS de partout, avatars personnalisés, aucun doute, c'est du Web 2.0.

Que vous aimiez Ajax ou pas, vous aller en manger. L'ensemble de la plateforme, et plus particulièrement l'écran principal (le "dashboard") est maintenant asynchrone. Au démarrage, plutôt que de voir ses filtres habituels (typiquement, la liste des bugs assignés), l'on a droit à des panneaux vides avec des petites barres de progression type enseigne de barbier, pour finalement afficher quelque chose d'intéressant plusieurs secondes plus tard. C'est la même chose pour ajouter un commentaire à un ticket, ou enregistrer son temps de travail. Le javascript est présent en doses pour rhinocéros, chaque menu est dynamique, chaque panneau ou section du bug peut se replier ou se déplier, et les différentes sections de la page peuvent être réarrangées par glisser déposer.

Le résultat, c'est un site beaucoup plus lent sous Firefox, et à peu près inutilisable sous Internet Explorer 8.

Mais c'est joli, ce qui a probablement été suffisant pour convaincre le manager kivabien de procéder à la mise à jour.

Project Euler fait peau neuve

Le site de Project Euler, le site de problèmes informatico-mathématiques, faisait un peu figure de dinosaure du Web. Eh bien, c'est fini, à la mi-Septembre le site web a été refondu en une version bien plus Web 2.0.

Le style est plus aéré, les statistiques ont été légèrement modifiés, et il y a maintenant un système de médailles basé sur les problèmes résolus, comme par exemple avoir résolu 50 problèmes liés aux nombres premiers, ou d'avoir résolu 12 problèmes au dessus du centième. L'on notera également un système de suivi permet de tenir ses amis à l’œil.

Les performances semblent avoir décru, et le site parait vraiment ramer. C'était parfois le cas avec l'ancien, donc difficile de savoir si c'est dû à une plus grande popularité, ou que le nouveau site cause une charge plus importante sur leurs serveurs. Ce n'est de toutes façons pas très gênant, ce n'est pas comme si je résolvais les problèmes si vite que leur chargement devienne fastidieux.

Médoc et wxWidgets

Il est tentant de vouloir adapter les bibliothèques, au passé souvent chargé, aux concepts et techniques du C++ moderne. Et pourtant, principalement pour les projets assez indépendants, il vaut mieux s'asseoir un peu sur ses principes, et utiliser la bibliothèque de la manière qu'elle a été pensée.

Prenons la bonne vieille wxWidgets, avec laquelle je suis en train de créer mon client lourd Médoc. Elle utilise sa propre classe de chaines de caractères, afin de supporter plusieurs types d'encodage, ses propres tableaux dynamiques en place du bon vieux std::vector, et utilise des macros un peu partout.

J'ai tendance à importer immédiatement quelques utilitaires de base que je garde dans un coin, du genre conversion entre wxString et std::string. Mais pour Médoc, je crois bien pouvoir m'en passer: mes entrées comme mes sorties passant soit par wxWidgets elle-même, soit par des bibliothèques en C pur, il est plus cohérent de simplement utiliser des wxString partout.

Voilà donc, en 300 lignes, un programme qui permet de charger des images dans une liste, et de les afficher en cliquant dessus:



C'est maintenant que ça se gâte: remplacer la liste d'images par une vraie galerie, permettant d'afficher une miniature de l'image, et d'en changer l'ordre par du glisser-déposer.

4 ans...

Je postais mon premier message sur ce blog le 1er Octobre 2007. 4 ans et 324 messages plus tard, les thématiques n'ont pas beaucoup changé (C++, OCaml, Postgresql, jeux vidéos). On a causé C++0x, on a causé Blender, on a même causé Emacs et astuces Debian.

Merci à mes lecteurs de chez l'université de Metz, de chez LinuxFR, de chez le "site du zéro", de chez Identi.ca (des Adaistes...) et de partout ailleurs de leur assiduité. Je leur souhaite de vouloir me lire encore pendant de nombreuses années, parce que j'ai bien des choses à dire!

Entre le C++0x qui va commencer à arriver en production dans divers systèmes à travers le monde, des nouveautés attendues dans Postgresql (je pense notamment aux ranges, qui je l'espère permettront de simplifier les bases de données historiques), les nombreux jeux que j'attends de pied ferme (Skyrim!), et diverses bêtises à partager, nous en avons pour un petit bout de temps.

@+!

Un client lourd Médoc

Mon projet de documentation Médoc continue de fonctionner impeccablement, du moins du côté de la base de données et du client Web. Par contre, le client lourd en OCaml et LablGTK, chargé de charger les documents dans la base à partir du scanner ou d'un fichier, commence à tomber en ruines.

Pas très ergonomique d'une part, et pas très intégré d'autre part (la plupart des commandes, telles le chargement de fichier ou le scan en lui-même, sont faites à partir de lignes de commandes lancées par le programme). Je me suis donc mis à écrire un client lourd en C++ avec WxWidgets qui soit un peu plus pratique à utiliser. La libsane se chargera de piloter le scanner, libmagick++ sait apparemment transformer un pdf en image, et la libharu sait transformer une image en pdf.

Y'a plus qu'à coller les morceaux.

Courir après sa base de données

Julien me parlait de systèmes de suivi de courses type marathon ou trail à base de RFID, et il n'en a pas fallu plus pour enflammer mon imagination. Je pensais à ce à quoi ressemblerait un schéma de base de données enregistrant le passage des coureurs à des points donnés, afin de permettre le suivi par les commissaires de courses, le public, et la publication des résultats et des statistiques pour les coureurs. Et on dirait bien qu'un tel système présente une sacrée dose de défis.

L'on s'intéressera plutôt aux courses de type ultramarathon ou trail, sur chemins ou en pleine nature, où les coureurs doivent s'enregistrer auprès des commissaires de courses à des points de passages déterminés. Le coureur passe donc son RFID au dessus de l'appareil du commissaire de course, et repart.

Voyons donc ce schéma. Les faits sont assez simples: une table contenant chaque détection d'un coureur à un point de passage. Mais qu'est-ce qu'un coureur, et qu'est-ce que c'est qu'un point de passage? Redéfinissons: notre table contient chaque détection d'un RFID par un appareil. Et il ne doit pas être possible de modifier ou d'enlever une ligne: une détection est une détection. Elle s'est effectuée à une certaine heure déterminée par l'appareil, et reçue à une autre heure (parfois beaucoup plus tard s'il y a des soucis de connectivité) par la base de données.

(device_id, rfid, device_timestamp, local_timestamp)

L'on pensera bien sûr aux pannes: si un rfid ou un appareil ne fonctionne plus, le commissaire pourrait se retrouver forcé d'enregistrer les coureurs manuellement via un autre type d'identification, comme un dossard.

(marshal_id, runner_id, marshal_timestamp, local_timestamp)

Ce sont les faits: irréfutables.

Maintenant, tout le problème est de rajouter les tables qui permettront d'associer les appareils aux points de passages, et les RFID aux coureurs.

- Un coureur découvre en milieu de course que son RFID est défectueux, et un commissaire de course lui en fournit un autre
- N'ayant cependant pas rendu son premier RFID, qui s'est tout à coup mis à remarcher, il passe parfois l'un, parfois l'autre aux points de passages
- Deux coureurs échangent un sac, et oublient que leur RFID était dedans

- Un commissaire change de point de passage, et garde avec lui son appareil
- Les commissaires découvrent que l'appareil pour la détection à l'arrivée est en panne, et décident de rapatrier un autre appareil pour l'arrivée, où une détection précise est plus importante

Toute la difficulté est donc de maintenir l'état le plus fréquent (un coureur ayant correctement été enregistré par son RFID par les bon appareils aux bons endroits), tout en permettant un réglage fin de toutes les petites déviations qui surviennent lorsque la réalité débarque avec ses gros sabots dans la théorie.

Peut-on rajouter la positien GPS de chaque appareil à chaque enregistrement pour tenter de les associer automatiquement à un point de passage?
Peut-être des tables se basant sur des plages horaires ou géographiques: de telle heure à telle heure, ou de tel point de passage à tel point de passage, le coureur A avait le RFID f, puis il est passé au RFID g?
Ou tout simplement des tables d'override: tel enregistrement doit être ignoré, tel autre doit être considéré comme ayant détecté le RFID g et non f?

Pas évident.

Github

J'ai enfin fait le saut, et me voici sur github. Ayant depuis longtemps eu l'envie de m'essayer à git, le logiciel de contrôle de version décentralisé crée par Linus Torvalds, je me suis ouvert un compte sur github, et j'ai commencé à commiter.

Github est particulièrement bien: guidant pas à pas la création du dépôt et la configuration de git, réactif et ergonomique, c'est un petit bijou d'interface. Les performances ont également l'air d'être au rendez-vous.

Utilisant git de manière mono-utilisateur et mono-branche, mon utilisation est très proche de Subversion (en beaucoup plus rapide cependant, mais les dépôts Subversion de tortue de chez Sourceforge n'aident pas non plus), j'espère cependant au moins m'y initier suffisamment pour ne plus être complètement perdu lorsque certains collègues plus dégourdis jonglent avec git-svn sur les dépôts du boulot.

Déjà quelques trucs qui m'ont un petit peu bloqué: il n'est pas possible d'avoir des répertoires vides. La solution standard est de créer un .gitignore vide dans le répertoire, et d'ajouter ce fichier. Également, ajouter un répertoire est récursif, ce qui est souvent bien, mais parfois lourd lorsque ce répertoire contient déjà un build, par exemple. Le plus simple est de commencer par nettoyer tous les fichiers non voulus avant d'ajouter.

Le crible en détail, partie 2

Continuons donc à décortiquer le programme.

La fonction principale de notre crible contient la sous-fonction do_sieve, qui permet une fois de plus de devenir tail recursive, ou à récursion terminale en bon français.

Elle prend comme paramètres l'entier courant à tester, l'ensemble des multiples des nombres premiers précédents, et la liste courante des nombres premiers. À partir de là, c'est tout bête: l'on retire le premier élément de nos multiples, et on le compare à l'entier à tester. S'ils sont égaux, notre entier courant est un multiple, donc non premier, l'on ré-appelle donc notre fonction récursive avec l'entier suivant. Si ce n'est pas l'entier à tester, on a trouvé un nombre premier! L'on ajoute tous ses multiples à la liste des multiples, l'on rajoute l'entier à la liste de nos nombres premiers, et l'on appelle la fonction récursivement. Et bien sûr, puisqu'il faut bien sortir un jour de la récursion, n'oublions pas notre condition de sortie: lorsque l'entier courant atteint le maximum passé en paramètre de la fonction principale, l'on retourne nos nombres premiers.

Notez l'optimisation qui consiste à zapper les multiples de 2: l'on démarre à 3, et l'on passe de 2 en 2 pour l'entier courant et pour le calcul des multiples.

Voici une indication des performances. Loin des meilleurs résultats impératifs, mais tout à fait utilisables.

Limite	Temps
100 000	140ms
1 000 000	2.7s
10 000 000	41s

Le crible en détail, partie 1

Mon post précédent était un poil laconique, je vais donc reprendre quelques détails d'implémentation, et en profiter pour vous convaincre que OCaml, ça roxe.

Les premières lignes sont simplement la définition d'un set sur les entiers. Les sets en OCaml fonctionnent via des modules paramétrés par d'autres modules suivant une certaine signature. L'on créé donc un module définissant un type t et sa comparaison, avec lequel on paramétrise le module Set.Make.

module OrderedInt =
struct
  type t = int
  let compare = compare
end

module IntSet = Set.Make(OrderedInt)

Ceci va donc définir un module tout neuf, que j'appelle IntSet, et qui fournit des fonctions pour travailler sur des sets fonctionnels, c'est à dire sans effets de bords. Ainsi, ajouter un élément au set retourne en fait un nouveau set contenant l'élément. C'est plus efficace qu'il n'y parait, et surtout, cela permet de raisonner à plus haut niveau, d'une manière plus mathématique.

Ensuite, définissons une fonction qui nous sera utile plus tard, qui retourne une liste d'entiers entre deux entiers définis, avec un pas.

let seq_step a b t = 
  let rec do_seq_step a acc = 
    if a > b then 
      acc
    else
      do_seq_step (a + t) (a::acc)
  in
  List.rev (do_seq_step a [])

La fonction définit une sous-fonction do_seq_step, prenant l'entier courant a, et la liste d'entiers accumulés jusque là acc. La récursion est triviale: si mon entier courant a atteint ma borne supérieure, retournons la liste accumulée jusque là. Sinon, appelons récursivement la fonction, avec mon entier courant incrémenté du pas, et ma liste à laquelle j'aurais ajouté mon entier courant.

Depuis la fonction externe, l'on appelle la sous-fonction en passant la borne inférieure, et une liste vide. Enfin, parce que l'on a accumulé les entiers à l'envers (en partant de 3 de 2 en 2: [3], puis [5; 3], puis [7; 5; 3]...), l'on inverse la liste avec List.rev. Le résultat:

# seq_step 3 10 2;;
- : int list = [3; 5; 7; 9]

Notez que l'on aurait pu implémenter la fonction d'un coup, de cette façon:

let rec seq_step2 a b t = 
  if a > b then
    []
  else
    a::(seq_step2 (a + t) b t)

Le résultat semble strictement le même, et pourtant:

# seq_step 1 1000000 1;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; ...]

# seq_step2 1 1000000 1;;
Stack overflow during evaluation (looping recursion?).

La deuxième version est arrêtée nette par un dépassement de pile. C'est que la première version est une récursion terminale (ou tail-recursion en anglais), c'est à dire qu'elle peut être trivialement transformée en une fonction itérative, ce que fait le compilateur. La deuxième, elle, utilise la pile comme accumulateur implicite, et provoque donc un dépassement de pile lorsque le nombre de récursions devient trop important.

Pour des raisons de performances et d'extensibilité, il est donc recommandé d'implémenter ses fonctions de manière récursive terminale à chaque fois que cela est possible.

Voilà, suivant l'approche ascendante qui sied bien à OCaml et aux langages fonctionnels, c'est à dire la construction de fonctions de base, puis de fonctions plus haut niveau utilisant ces briques, les utilitaires utilisés pour le crible. Dans la deuxième partie, je reprendrait plus en détails l'algorithme du crible lui-même.

Implémentation fonctionnelle d'un crible d'Ératosthène

Voilà l'engin:

module OrderedInt =
struct
  type t = int
  let compare = compare
end

module IntSet = Set.Make(OrderedInt)

let seq_step a b t = 
  let rec do_seq_step a acc = 
    if a > b then 
      acc
    else
      do_seq_step (a + t) (a::acc)
  in
  List.rev (do_seq_step a [])

let sieve n = 
  let rec do_sieve current multiples primes = 
    if current > n then
      primes
    else if IntSet.is_empty multiples || IntSet.min_elt multiples <> current then
      do_sieve 
        (current + 2) 
        (List.fold_left 
           (fun acc e -> IntSet.add e acc)
           multiples
           (seq_step (current * 3) n (current * 2)))
        (current::primes)
    else
      do_sieve (current + 2) (IntSet.remove current multiples) primes
  in
  do_sieve 3 IntSet.empty [2]

Sur ma machine, compilé en natif, trouver les nombres premiers en dessous du million prend 2,7 secondes.

Un peu de fonctionel

Je me suis remis à Project Euler, et résolu quelques problèmes supplémentaires. Je continue à tenter d'apporter des solutions aussi fonctionnelles pures que possible, ce qui m'a amener à réfléchir à un crible d’Ératosthène fonctionnel pur. Jusqu'ici, j'utilisais les fonctionnalités impératives d'OCaml pour m'en tirer un avec un gros tableau de booléens, mais en fait, si l'on considère un set d'entiers pour les multiplies, il est facile de faire quelque chose de plutôt efficace. Je dois mettre un peu d'ordre dans mon code, et je le posterai ici.

Normal maps et Blender 2.5 - Créer un astéroïde

Le nouveau Blender ayant changé pas mal de choses, voici la version mise à jour de mon tutoriel sur les normal map, cette foi-ci pour créer un astéroïde.



Voici l'écran initial de Blender, après être passé à 4 vues (Ctrl-Alt-Q). Virons le cube (sélection avec bouton droit, puis DEL), et ajoutons une icosphère (Shift-A, Mesh => Icosphere).



L'on peut maintenant tortiller la sphère dans tous les sens: s + déplacements de souris pour changer sa taille, et s suivi de x, y ou z pour changer la taille dans une dimension seulement. L'on peut sélectionner les points individuellement en passant en mode vertex (TAB), et en sélectionnant les points avec le bouton droit. La touche g permet de déplacer les vertex, et l'on peut une fois de plus restreindre la dimension avec les touches x, y ou z. Formons donc un patatoïde.



Lequel patatoïde nous pouvons maintenant donner une forme plus douce, en y ajoutant le modifier "subdivisions". Dans le menu de droite, allez chercher le tab "Modifiers" (la petite clé à molette), et choisissez "Subdivision Surface". Mettons View et Render à 2.



L'on va ensuite rendre notre patatoïde tout doux: passez en mode vertex (TAB), selectionnez tout (a), et choisissez dans le menu "Mesh Tools" à gauche le shading "Smooth".



Allez chercher le tab "Material", et ajoutez un nouveau matériau.



Allez ensuite chercher le tab "Texture", et ajoutez une nouvelle texture. Pour donner un aspect rugueux à notre astéroïde, nous allons choisir une texture de type "Cloud", choisir un "noise" à "Hard", et changer son influence en désactivant "Colo" (pour couleur) et en activant "Nor" pour normales.



Ajustez vos couleurs, et admirez!



Maintenant, passons à la création de l'objet à exporter. D'abord, dupliquez l'astéroïde (Shift-D). Il est possible de renommer les objets en "high poly" et "low poly", par exemple, dans le menu "Object", histoire de ne pas se perdre. Enlevez le modifier de subdivisions afin de retrouver notre objet initial.



Ensuite, générez la texture UV (mode vertex, u, "Smart UV project"). Vous pouvez maintenant effectuer le rendu de la texture, en allant dans le tab "Render" (le petit appareil photo), et en allant tout en bas dans "Bake". Choisissez le bake mode "Normals", avec normal space "Object". Lancez le rendu avec "Bake".



Tout en haut, passez de la vue "Default" à la vue "UV editing" pour admirer votre œuvre. Sauvez l'image, puis exportez l'objet!



Avec OSG, je transforme l'objet exporté en Wavefront (.obj) vers un .osg, puis j'édite manuellement le .osg afin de dupliquer le noeud de texture, pour ajouter une deuxième texture avec un identifiant à 1. Je change ensuite les noms pour avoir ma texture de couleurs en 0, et ma texture de normales en 1, comme l'attend mon programme.

Et voilà le travail:

1000 cubes

Un millier de cubes orbitant tranquillement. Le système monte gentiment en charge, avec une charge CPU à 125%, c'est à dire un proc à 100% pour afficher le plus d'images possible à la seconde, et 25% en calcul d'orbites et en passage de messages.

Orbites

Il faut voir le cube tourner (je vais essayer de générer une vidéo), mais voilà déjà une image. Mon framework fonctionne, et devrait monter en charge facilement.

Cela représente donc un cube, doué d'une vitesse initiale, orbitant autour d'une masse pour l'instant non représentée. Cela devrait prouver ou pas la possibilité de mettre à jour des centaines d'objets, et de les représenter de façon fluide en recalculant "rarement" la position et la vitesse, puis en faisant une extrapolation à chaque image.

Week-end de folie chez Debian

La bonne vieille Wheezy prend du poil de la bête: non seulement nous sommes passés en noyau 3.0, mais en plus Iceweasel 5 est sorti! Au menu, un très bon support de Youtube en HTML5. Peut-être vais-je enfin pouvoir me débarrasser de Flash?

Mon compilo est intelligent

Brave g++!

#include <array>



int main()

{

  std::array<int, 5> a = {1, 2, 3, 4};

  std::array<int, 5> b = {1, 2, 3, 4, 5};

  std::array<int, 5> c = {1, 2, 3, 4, 5, 6};

  

  return 0;

}

Les tableaux a et b passent comme une lettre à la poste, mais le compilo hurle fort justement sur le tableau c, avec l'on ne peut plus explicite message:

array.cpp:9:43: error: too many initializers for ‘std::array<int, 5ul>’

Je n'en attendais pas tant. Magnifique!

Événements

Je suis en train d'essayer de construire un truc qui se tient autour de boost::asio et de la programmation orientée événements. L'idée est de construire quelques briques de plus haut niveau autour d'asio, et d'en tirer quelque chose d'utilisable.

Tout tourne autour d'un boost::asio::io_service::strand, que j'ai collé dans une classe de base. J'en dérive (virtuellement!) ensuite des classes d'utilitaires tels un timer, ou un notifier / listener. Ensuite, il ne reste qu'à dériver sa classe depuis les classes d'utilitaires: l'on veut écouter tel type d'événements, recevoir un signal toutes les secondes, etc. Tout passer par le strand unique à la classe (d'où l'héritage virtuel), ce qui permet de s'affranchir complétement des locks.

Cela veut également dire que l'état de l'objet ne doit être modifié que depuis le strand, ce qui n'est aucunement garanti lorsque l'on appelle une méthode de l'objet. Il faut donc réexpédier tous les appels de méthodes publiques vers une méthode privée correspondante, à travers le strand. Vu que l'on passe alors un message, il n'est plus possible d'obtenir des valeurs de retour, uniquement des callbacks ou des objets protégés.



Bien évidemment, ce genre d'approche n'est utile que pour une classe limitée de problèmes. Écrire un raytracer orienté événement n'est probablement pas une bonne idée. En revanche, ces techniques pourraient bien se prêter aux jeux.

Iceweasel 5 bientôt dans Squeeze!

La page d'"excuses" de Debian:

Too young, only 3 of 10 days old

Il y a quelques autres points, mais j'ai bien l'impression qu'on se dirige vers un Firefox un poil moderne pour dans une semaine. Chouette!

Et moi qui vous délaisse!

C'est que, entre le recrutement d'espions britanniques cherchant à se recaser (eh oui), les batailles incessantes avec un système de middleware dont le nom commence par Tib et finit par Co, et le passage une fois de plus de la souris de la main droite à la main gauche pour des raisons de santé, il faut encore que j'arrive à caser du code à moi.

Le système d'update callbacks pour faire mon système de navigation à l'estime marche d'enfer: je puis passer entre mon système graphique, tournant à plusieurs centaines d'images par seconde, et le système de gamplay, tournant lui à 20 cycles, voire moins, par seconde, sans risquer ni de hacher l'un ni d'envahir l'autre.

En revanche, ma nième tentative pour obtenir un bump mapping dans l'espace tangent s'est achevé par une cuisante défaite. Je n'y arrive simplement pas. Je vais donc rester aux normales dans l'espace objet, telles que je les ai gérées jusqu'à présent.

Read

"Mais pourquoi", me demande mon collègue, "est-ce que mon programme fonctionne quand je le débugge, mais pas lorsque je l'exécute? On dirait qu'il attrape de mauvais paquets du réseau, et il se retrouve à lire n'importe quoi."

Arf, du C#. Tentons d'y voir clair.

D'habitude, j'ai absolument horreur de débugger un programme qui ne donne pas les mêmes résultats lorsqu'il tourne dans un débuggeur. Mais là, il m'a semblé que ça ne devait pas être trop difficile. Déjà, il fut facile de s'en assurer, ce n'était pas le débuggeur, mais les breakpoints. Sans breakpoints, le programme foirait, semblant effectivement lire des données pourries sur le réseau. Avec breakpoints, ça passait.

Je tentais de voir quels étaient les breakpoints "magiques", en les ajoutant et les retirant suivant la rigoureuse méthode de Monte Carlo (c'est à dire au pif). Finalement, une ligne attira mon attention. Quelque chose comme:

networkStream.Read(data, length);

Je changeais prestement la ligne pour afficher côte à côte "length" et la valeur de retour de la méthode. S'affiche:

67889 - 1280

Tête du collègue médusé. Eh oui. Même en C#, et comme en C, "Read" va lire et retourner ce qu'il trouve dans le tampon, et peut donc renvoyer moins que la taille demandée. Le breakpoint permettait simplement à l'ensemble du paquet d'arriver dans le tampon, et donc de faire fonctionner le programme (le contenu des données était ignoré). Mais lors d'une exécution normale, Read était appelé avant que tout le paquet ne soit arrivé. Lors de la deuxième lecture, c'était la fin du premier paquet qui passait, et qui était donc interprété en dépit du bon sens.

Je dirigeais mon coreligionnaire vers une méthode à nous, répondant au doux nom de ReadExactly, et implémentée avec une belle boucle qui accumulait les Read jusqu'à la taille désirée.

Trop de choix

void cb::EntityManager::processEvents()
{
  std::deque<std::shared_ptr<EntityEvent> > events;
  m_eventQueue->popAll(events);
  // version 1
  std::for_each(events.begin(),
                events.end(),
                std::bind(&EntityEvent::accept, std::placeholders::_1, this));
  // version 2
  for(const std::shared_ptr<EntityEvent> & event : events)
  {
    event->accept(this);
  }
  // version 3
  std::for_each(events.begin(),
                events.end(),
                [this](const std::shared_ptr<EntityEvent> & event){event->accept(this);});
}

Et je fais comment, moi, maintenant?

Autant j'adore les lambdas, autant c'est ici la solution la moins préférable: l'on a la déclaration explicite du contenu, contrairement à la solution basée sur std::bind, et l'on a l'overhead du la création de l'objet lambda, contrairement au range-based for.

Au final, je crois que je la solution du range-based for me plaît plus, car elle me semble vaguement plus efficace. Il faudra que je benchmarke un peu tout ça.

Coder efficacement avec Emacs - Partie 6 - Compilation

Une de mes fonctionnalités favorites d'Emacs, c'est la console qui affiche les résultats de compilation. Il est possible de cliquer (ou d'utiliser d'absconses commandes clavier) pour aller d'erreur en erreur à travers le source. C'est quand même bien plus pratique que d'avoir la compilation dans une console à côté, et d'aller chercher le fichier et la ligne.

La commande, c'est M-x compile. Tout bête, mais déjà trop lorsque l'on est un serial compileur comme moi. Un petit

(define-key global-map [f5] 'compile)

dans mon .emacs et voici la touche F5 affectée à la compilation. Tapons F5: la ligne de compilation par défaut apparaît. Entrée, et c'est lancé. La combinaison F5-Entrée est devenue chez moi un automatisme. L'on peut changer la ligne de compilation, qui sera maintenue tant que la session est ouverte.

La commande de compilation par défaut est make -k, mais il est possible de la changer pour un mode particulier. Si comme moi vous êtes un fanatique d'omake pour compiler vos projets C ou C++:

(add-hook 'c-mode-common-hook
  (lambda ()
    (set (make-local-variable 'compile-command) "omake -j 4 -R")))

Et pour changer la commande par défaut hors d'un mode particulier:

(setq compile-command "omake -j 4 -R") 

Bon codage!

C++0x - std::unique_ptr et types partiels

Prenons un exemple très simple: l'idiome "pimpl" (dont le nom m'horripile, mais bon), encore appelé "pointeur opaque". Dans le .h, on forward déclare notre type interne, que l'on définit dans le .cpp. L'idée est de cacher l'implémentation, ce qui a également l'avantage de permettre une compilation plus rapide en évitant à l'interface l'inclusion d'une myriade d'en têtes pour les types privés.

Là, en bon dev C++11, l'on se dit, chic, je vais utiliser un std::unique_ptr. Voyons ce que cela donne. Ici, l'on a la classe Impl, forward déclarée, utilisée dans un std::unique_ptr, suivi d'un bout de code confirmant au compilo que l'on a bien l'intention d'instancier la classe Interface:

#include <memory>

class Impl;

class Interface
{
public:
  Interface();

private:
  std::unique_ptr<Impl> m_impl;
};

void create()
{
  Interface i;
}

L'on est immédiatement couvert d'injures par le compilateur:

g++ -std=gnu++0x -c uniq.cpp
In file included from /usr/include/c++/4.6/memory:85:0,
from uniq.cpp:1:
/usr/include/c++/4.6/bits/unique_ptr.h: In member function ‘void std::default_delete<_Tp>::operator()(_Tp*) const [with _Tp = Impl]’:
/usr/include/c++/4.6/bits/unique_ptr.h:245:4: instantiated from ‘void std::unique_ptr<_Tp, _Dp>::reset(std::unique_ptr<_Tp, _Dp>::pointer) [with _Tp = Impl, _Dp = std::default_delete, std::unique_ptr<_Tp, _Dp>::pointer = Impl*]’
/usr/include/c++/4.6/bits/unique_ptr.h:169:23: instantiated from ‘std::unique_ptr<_Tp, _Dp>::~unique_ptr() [with _Tp = Impl, _Dp = std::default_delete]’
uniq.cpp:5:7: instantiated from here
/usr/include/c++/4.6/bits/unique_ptr.h:63:14: error: invalid application of ‘sizeof’ to incomplete type ‘Impl’

Rajoutons juste un destructeur:

#include <memory>

class Impl;

class Interface
{
public:
  Interface();
  ~Interface();

private:
  std::unique_ptr<Impl> m_impl;
};

void create()
{
  Interface i;
}

Et g++ nous claque deux bises.

En effet, et d'après ce tableau, contrairement à std::shared_ptr, std::unique_ptr ne peut être détruit que si son type sous-jacent est complètement défini. Dans le premier exemple, le destructeur n'est pas défini, et g++ en définit donc un par défaut, inline. Il n'a donc pas accès au type Impl, ce qui cause l'erreur. Par contre, dans le deuxième exemple, l'on a décidé de fournir un destructeur quelque part ailleurs. Le compilateur n'a donc pas besoin de générer le code pour détruire notre pointeur. Celui-ci sera généré à la définition du destructeur, probablement dans le fichier source, et donc probablement après la définition complète d'Impl.

Design

Je ne suis pas convaincu par ma manière actuelle de mettre à jour mon graphe de scènes. Attendant entre chaque frame pour mettre à jour mes objets, je ne puis utiliser à fond les dernières fonctionnalités de threading d'OpenSceneGraph.

J'ai donc pensé à un système de queue d'événements, qui sont lus via un callback, et mettent à jour les structures qui sont lus par les nœuds dans leurs propres callbacks de mise à jour. Ces structures seraient de la forme (timestamp, position, direction), et permettraient au nœud de mettre à jour sa position à chaque image en extrapolant.

Tout est là dedans:

Debian downgrade

Arf, petit bug! À la suite d'un crash dans la libdbd, je ne pouvais plus démarrer le bon vieux gnucash et faire mes comptes. Downgradons donc dans la joie et la bonne humeur.

Après quelques recherches, j'atterris sur la page snapshot de Debian, dans laquelle je puis retrouver mon paquet. Je décide de passer de la 0.8.3-1+s-1 à la 0.8.2-1-4.1, et me retrouve avec un lien vers la libdbd-pgsql 0.8.2-1-4.1. Un petit dpkg -i plus tard, je démarre GnuCash, et miracle, j'y suis!

Par contre, il va maintenant falloir faire attention à chaque fois que je mets à jour: ne pas laisser le système me remplacer ma précieuse libdbd avant que le bug soit fixé.

Debian, c'est comme attendre le bus...

On attend une version de gcc, et y'en a 3 qui arrivent en même temps :)

Maintenant qu'avec g++4.6, on a à peu près toutes les fonctionnalités de c++0x (c++11), j'attends maintenant avec impatience la mise à jour d'Iceweasel. Les web sockets m'intriguent, et bien qu'étant un peu allergique au Javascript, j'aimerais bien expérimenter avec des applications réellement réactives.

C++0x - std::set vs std::unordered_set

Il aura tout de même fallu attendre C++0x (ou devrais-je commencer à dire C++2011?) pour voir enfin apparaître les tables de hachage dans la bibliothèque standard. Diverses extensions, ansi que Boost, proposaient leurs implémentations, mais ça fait toujours plaisir de voir les choses se standardiser.

Je dois cependant avouer que les tables de hachage m'ont souvent laissé un peu perplexe: leurs performances dépendent énormément du bon choix pour la fonction de hachage, ce qui rend fort difficile les prédictions. Je préfère généralement un bon arbre binaire, qui va certes nécessiter une allocation à chaque insertion et une recherche logarithmique, mais que j'ai l'impression de mieux comprendre.

Voyons donc un petit benchmark afin de se faire une idée. D'un côté, le bon vieux std::set, de l'autre, le std::unordered_set. L'on insère 1000 entiers, on mesure le temps, et l'on recommence.




Comme l'on pouvait s'y attendre, l'on voit que l'insertion dans un std::set augmente de manière logarithmique. L'on voit également que l'insertion dans un std::unordered_set augmente de manière linéaire, sauf au moment des rehash: une fois que la table est trop pleine, le conteneur réalloue une nouvelle table plus grande, et y hache de nouveau chaque élément.

Alors oui, le std::unordered_est est plus rapide que le std::set, sur un ensemble qui tendrait plutôt à défavoriser ce dernier: ayant utilisé des entiers consécutifs, le hachage est très efficace (c'est l'entier lui même), et il n'y a pas de collisions.

Cependant, si le std::unordered_set est plus efficace sur le long terme, ses performances instantanées peuvent tout d'un coup devenir absolument horribles si l'on doit re-hacher. Un programme qui nécessite de bonnes performances à chaque insertion, et pas seulement dans l'ensemble, devra l'éviter.

Une approche intéressante pour profiter des performances des tables de hachage sans payer un rehash couteux de temps en temps est d'amortir ce hachage: lorsque la table devient trop grande, l'on alloue une nouvelle table dans laquelle on met le nouvel élément. Chaque nouvelle insertion embarque avec elle quelques éléments de la vieille table, et chaque recherche vérifie les deux tables. Ainsi, au fur et à mesure, les éléments de la petite table sont déplacés dans la grande, et l'on peut se débarrasser de la petite, et recommencer le processus une fois que la grande devient à son tour trop pleine.

Voici le code du benchmark. Étrangement, la table de hachage a de meilleures performances à froid, et le std::set à chaud, ce qui est la raison pour laquelle je commence à insérer dans un set sans mesurer. Et je ne m'explique absolument pas le blip aux 3/4 de l'insertion dans le std::set, qui se reproduit à chaque exécution

#include <iostream>
#include <chrono>
#include <vector>
#include <set>
#include <unordered_set>

int main()
{
  int interval = 1000;
  int points = 1000000;
  
  std::vector<std::chrono::microseconds> setTimes;
  std::vector<std::chrono::microseconds> hashTimes;
  
  setTimes.reserve(points / interval);
  hashTimes.reserve(points / interval);
  
  {
    std::unordered_set<int> container;
    auto base = std::chrono::system_clock::now();
    for(int i = 0; i < points; ++i)
    {
      container.insert(i);
      if(i % interval == 0)
      {
        hashTimes.push_back(std::chrono::system_clock::now() - base);
      }
    }
  }

  {
    std::set<int> container;
    auto base = std::chrono::system_clock::now();
    for(int i = 0; i < points; ++i)
    {
      container.insert(i);
    }
  }
  {
    std::set<int> container;
    auto base = std::chrono::system_clock::now();
    for(int i = 0; i < points; ++i)
    {
      container.insert(i);
      if(i % interval == 0)
      {
        setTimes.push_back(std::chrono::system_clock::now() - base);
      }
    }
  }
  
  auto it = setTimes.begin();
  auto end = setTimes.end();
  auto it2 = hashTimes.begin();
  for(; it != end; ++it, ++it2)
  {
    std::cout << it->count() << "\t" <<  it2->count() << "\n";
  }
  std::cout.flush();
}

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.

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?

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.

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.

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.

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.

Postgresql et Postgis pour l'aviation

Découvert via le planet de Postgresql, une excellente présentation d'une utilisation de Postgis, le module Postgresql de gestion des données géographiques, dans le domaine de l'aviation, et plus particulièrement de la gestion des plans de vols.

XSD - Pas évident

Assez moches, finalement, les schémas XSD. Documentation absconse, grammaire peu claire, et bien trop de façons de générer la même chose.

C'est que j'essaie de reprendre le bon vieux mlxsd et de le rendre un peu plus respectueux des standards. Et c'est pas de la tarte.

Ocaml Lwt - Mini tutorial

Connaissez-vous Lwt? C'est une bibliothèque proposant un modèle asynchrone autour des fibres, ou threads légers (déjà qu'un thread était un processus léger, est-ce qu'une fibre est un processus vachement léger?) coopératifs, c'est à dire que la fibre va s'exécuter jusqu'à ce qu'elle laisse le champ libre à une autre fibre, via des appels spéciaux, par exemple pour effectuer des opérations d'entrée sortie, ou attendre un résultat fourni par une autre fibre.

Je trouve le manuel un poil léger, donc voici une série d'exemples très simples pour se faire une idée de l'utilisation du bazar. L'idée est généralement de créer un thread lwt, puis de le faire tourner via un appel à Lwt_main.run jusqu'à ce que l'exécution du thread soit complétée, et d'en récupérer une valeur de retour.

Dans un terminal ocaml, ces commandes permettent de charger les bibliothèques lwt:

#use "topfind";;
#require "lwt";;
#require "lwt.extra";;

C'est parti. L'exemple le plus simple: ce bout de code créé un bête thread lwt déjà terminé, contenant la valeur 3. Le Lwt_main.run attend que le thread soit complété et en retourne la valeur. Dans ce cas, il n'a rien à faire que de simplement retourner 3.

let t = Lwt.return 3 in
Lwt_main.run t

Un premier exemple faisant enfin quelque chose: l'on utilise la fonction Lwt_unix.sleep, lequel retourne un thread qui se termine au bout d'un certain temps. Cette fonction va donc dormir pendant 2 secondes avant de retourner unit.

let t = Lwt_unix.sleep 2. in
Lwt_main.run t

Voici l'utilisation d'une routine d'entrée sortie. Parce que les threads sont coopératifs, il est nécessaire de ne jamais bloquer ou utiliser des fonctions d'entrée / sortie non bénies par lwt. L'on utilisera donc Lwt_io pour lire et écrire des fichiers ou les entrées sorties standard. Le modèle est le même: notre thread écrit "Miaou" sur la sortie standard, et le thread est complété.

let t = Lwt_io.write_line 
  Lwt_io.stdout
  "Miaou"
in
Lwt_main.run t

Ah, la fonction Lwt.bind! Elle permet de chaîner les threads: quand un thread est complété, il passe son résultat au suivant, qui s'exécute à son tour. Dans notre cas, le plus simple, nous passons unit à la fonction qui écrit. Vous l'aurez deviné, ce bout de code attend 2 secondes, puis affiche "Miaou" à l'écran.

let t = 
  Lwt.bind
    (Lwt_unix.sleep 2.)
    (fun () -> Lwt_io.write_line Lwt_io.stdout "Miaou")
in
Lwt_main.run t

Enfin, un exemple démontrant les capacités asynchrones de Lwt. Dans cet exemple, l'on créé 3 threads qui chacun attendent un certain temps avant d'afficher un message. La fonction Lwt.join retourne une fois que les 3 threads sont complétés. Quelque soit l'ordre dans lequel les threads ont été passés à la fonction, ils s'afficheront bien en temps voulu.

let sleep_and_print duration message = 
  Lwt.bind
    (Lwt_unix.sleep duration)
    (fun () -> Lwt_io.write_line Lwt_io.stdout message)
in
let t = Lwt.join
  [sleep_and_print 3. "3 secondes";
   sleep_and_print 4. "4 secondes";
   sleep_and_print 2. "2 secondes"]
in
Lwt_main.run t

Voilà les bases, à partir de là il ne s'agit plus que de chaîner les fonctions d'entrées sorties Lwt décrites dans le manuel.

J'ai l'intention d'essayer d'écrire un petit moteur asynchrone orienté événements, permettant à l'utilisateur de souscrire dynamiquement à un certain nombre d'entrées, comme par exemple une horloge, des entrées réseau, ou des passages de messages (probablement pas pour OpenRailz, mais on ne sait jamais...).

Le mot de la fin: OCaml ne permet pas l'exécution concurrente de code car il possède, tout comme Python d'ailleurs, un verrou global. Lwt ne change pas cette règle, et n'est donc pas orienté vers du "number crunching", par exemple, mais permet en revanche de designer de manière très élégante des applications réactives devant gérer des événements complexes. Les appels coopératifs s'assurent que l'application n'est jamais en train d'attendre alors qu'un autre bout de code pourrait être exécuté, ce qui permet d'aller taper dans la base de données, écouter des messages réseau, lire des fichiers, et logger dans d'autres d'une manière transparente et claire. Cool non?