Prototypes

Aller au contenu | Aller au menu | Aller à la recherche

mardi 27 mars 2007

AutoDAL

Le prototype du jour est une petit bibliothèque permettant d'automatiser la récupération des propriétés d'un objet depuis une ligne d'un DataReader. En un mot, il automatise vos codes qui ressemblent à ça :

public void GetDataFromRow(Utilisateur obj, IDataReader dr)
{
  obj.Nom = (string)dr["nom_utilisateur"];
  obj.Prenom = (string)dr["prenom_utilisateur"];
  obj.Id = (int)dr["id_utilisateur"];
}

Qui s'écrit alors :

AutoDal.GetDataFromRow(obj, dr);

Evidemment, la bibliothèque ne devine pas les noms de vos colonnes, ni les types de données. Un attribut doit être ajouté sur les propriétés de vos objets : Exemple :

private string m_Nom;
[DbColumn("nom_utilisateur", DbType = DbType.String)]
public string Nom
{
  get { return m_Nom; }
  set { m_Nom = value; }
}

Une notion de "segment" est également présente, elle permet de définir les champs à récupérer dans votre objet. Chaque champ appartient à un segment (par exemple : ID, informations générales, informations détaillées). Vous spécifiez dans le GetDataFromRow les segments à récupérer. Certains diront que ca n'est pas "object oriented", qu'un objet ne peut s'envisager que totalement défini, etc. A quoi je répondrai que je m'en fiche, ca n'est pas le propos de mon proto.

En interne, le mécanisme se base évidemment sur de l'introspection (reflection), mais repose également sur la génération de code MSIL (Reflection.Emit). En fait, lors du premier appel d'un LoadFromRow pour un objet (et pour un segment donné), l'objet est inspecté, et le code MSIL de récupération des données depuis la datarow est généré. Lors des appels suivants, ce code sera immédiatement utilisé. Au final, les performances seront du même ordre que si vous aviez tout fait "à la main", et non pas équivalentes à celles obtenues en pure introspection (dans ce cas, les performances seraient catastrophiques).

Le code supporte également les types Nullable (par exemple int? ou DateTime?). La spécification du type de données de la colonne est optionnelle mais permet d'optimiser l'accès aux données (sinon, le moteur doit inspecter le type de la donnée pour la convertir dans le même type que la propriété de l'objet).

Le code source contient une petite utilisation minimaliste reposant sur une base de données SQLite. A priori, cela devrait également fonctionnner avec les autres bases (en particluier SQL server ou MySql).

Après un certain nombre d'essais, je n'ai toujours pas trouvé de façon élégante d'automatiser les autres parties de la couche DAL : la création / récupération des requêtes SQL et le passage des paramètres. J'ai fait un certain nombre de protos non probants, mais je ne désespère pas de faire quelque chose d'intéressant à un moment ou un autre.

Télécharger AutoDal rev 6

vendredi 2 mars 2007

EnumNames

Le but de ce prototype est de faire de la performance sur un problème assez basique. A l'origine, un problème récurrent : associer à une valeur d'Enum un texte de description. En effet, si cet enum est choisi par l'utilisateur depuis une interface, mieux vaut lui présenter quelque chose d'assez intuitif plutôt qu'un code hexadecimal.

Une solution .NET élégante consiste à mettre des attributs sur les enum. Exemple sur Code project : Mapping Text to Enum entries.

Le problème principal de cette implémentation est la performance. Elle se base sur de la reflection, et reste donce assez lente.

Le but du prototype que j'ai fait ici est de conserver cette implémentation, mais d'en augmenter les performances par divers moyens, et de mesurer cette performance.

Pour mesurer la performance, je me base sur un enum avec quatre valeurs :

   public enum MyEnum : long
   {
       [EnumName("Valeur 1")]
       EnumValue1 = 6,
       [EnumName("Valeur 2")]
       EnumValue2 = 7,
       [EnumName("Valeur 3")]
       EnumValue3 = 8,
       [EnumName("Valeur 4")]
       EnumValue4 = 9
   }

Ensuite, j'appelle pour chaque implémentation à tester la méthode de récupération de la valeur 2, et ceci 2 millions de fois. Un premier appel à la méthode est fait avant la mise en place du compteur de temps : on évite ainsi de chronométrer le premier appel, qui peut en profiter pour faire une mise en cache. Le but est donc bien de vérifier le comportement sur un grand nombre d'accès.

J'ai mis en place deux implémentations témoin :

  • Fast_Fastidious : Une implémentation "Rapide mais fastidieuse" : elle consiste à ne pas utiliser l'attribut sur l'enum, mais à implémenter à la main un select sur chaque valeur de l'enum qui renvoie la valeur correspondante. Je considère que cette implémentation est l'implémentation de référence, vers laquelle il faudra tendre au maximum en termes de performances. Son score est sur ma machine 0s203
  • Slow : Une implémentation "Lente" : Elle consiste à récupérer via reflection la valeur de l'enum, sans mise en cache ou optimisation d'aucune sorte (comme dans l'article du Code Project). Score : 30s961

Comme vous pouvez le constater, il y a un monde entre ces deux implémentations : La première est 150 fois plus rapide.

J'ai ensuite proposé trois implémentations visant à augmenter la performance de la méthode de récupération du nom de l'enum.

  • Caching : Une implémentation avec une mise en cache des résultats. Lors du premier accès à une énumération, on récupère toutes ses valeurs possibles, et on met en cache les résultats dans une table de hash. Les résultats sont bien meilleurs que dans Slow, mais loins de la cible : 2s219. La perte de performance se fait très probablement lors de l'accès aux éléments des tables de hash (deux tables de hash imbriquées : trouver d'abord l'enum, puis la valeur au sein de l'enum).
  • Emit : Une implémentation avec mise en cache également, mais au lieu de représenter les valeurs pour l'enum sous forme de table de hash, on créé dynamiquement une méthode équivalente à Fast_Fastidious à l'aide de Reflection.Emit. Cette méthode est utilisée par la suite. Reste un point de perte de performance : La sélection de la méthode en fonction de l'Enum en entrée. Ici, on se rabat sur une table de hash contenant des delegates avec les méthodes générées). Résultat : 0s797. On se rapproche.
  • Generic : Cette fois ci, je repars de Emit, et j'essaie d'améliorer les performances de la première étape : la sélection de la méthode de récupération de la description. J'utilise pour cela les Generics. En créant une classe générique avec comme type générique le type de l'énumération, cela remplace avantageusement une table de hash. Résultat : 0s359. Deux fois plus rapide que Emit mais encore deux fois plus lent que Fast_Fastidious.

On pourrait peut-être gagner un peu en performances en optimisant encore plus le code MSIL généré par Emit et Generic. J'ai fait ce code en tentant de l'optimiser autant que possible, mais je n'avais pas la documentation sur les nombres de cycles des instructions, donc cela reste approximatif. La méthode Generic reste plus restrictive que Emit, puisqu'elle impose de connaître le type de l'énumération à la compilation.

N'hésitez-pas à me dire si vous avez des idées différentes ou plus efficaces pour ce prototype, je suis intéressé.

Télécharger EnumNames

BrainFuck Compiler

Connaissez-vous le BrainFuck ? C'est un langage de compilation qui, il faut l'avouer, ne sert à rien d'autre qu'à se détruire les méninges. Le concept est simple : 8 opérateurs "<", ">", "+", "-", ".", ",", "[", "]", et ... c'est tout. Un langage très simple donc, ce qui donne des petits programmes sympathiques, à écrire d'une part, et à maintenir d'autant plus.

Par exemple, le programme habituel Hello World devient :

 ++++++++++[>++++++\+>++++++++++>++\+>+<<<<-]>++.>+.++++++\+..++\+.>++.<<++++++++++++++\+.>.+++.------.--------.>+.>.

Vous trouverez plus d'informations sur brainfuck sur Wikipedia

Le proto que je vous propose aujourd'hui est un compilateur / interpréteur BrainFuck .NET

Il propose plusieurs modes :

  • Compilation en utilisant CodeDom : un arbre DOM du code C# équivalent au BF en entrée est créé, puis est compilé en utilisant les outils de compilation du framework. C'est un bon exemple de l'utilisation de la techno CodeDOM
  • Compilation en utilisant Reflection.Emit : Le code généré est directement de l'assembleur MSIL
  • Interprétation brtuale : le code BF est lu et exécuté directement à la volée
  • Interprétation précompilée : le code BF est compilé en mémoire en utilisant Reflection.Emit, puis est exécuté directement.

Télécharger BFC-rev3

Au final, je pense que ce proto peut être un bon exemple pour apprendre un peu Reflection.Emit. N'oubliez-pas d'utilliser également Reflector, cet outil génial qui permet de désassembler du code .Net (de façon plus sympathique qu'avec ILDASM).

Par contre, j'ai été très déçu par CodeDom. L'arbre DOM ne couvre pas l'ensemble de la grammaire de C#, du coup, impossible de faire le code que l'on veut. CodeDOM serait à priori plus utile pour générer du code (qui sera ensuite affiché / prettyprinté) que pour générer du code exécutable (qui est ce que je désirais faire ici). Mais même dans ce cas, on est vite limités par les abscences de certains tokens du langage (en particulier dansles boucles).

mercredi 14 février 2007

PriorityQueue

Un peu plus frais que DCR : un proto sur lequel je travaille en ce moment.

C'est une implémentation de queue avec priorité en .NET / C# 2.0. J'utilise ça pour un autre proto que je publierai probablement un de ces quatre. En gros, la queue avec priorité est une bête queue (basée sur une liste chaînée dans mon cas), pour laquelle l'insertion d'élément se fait avec une priorité. Si on insere un objet avec une priorité n, il passe devant tous les objets avec une priorité < n dans la queue. Derrière, j'utilise également un arbre AVL, donc il y a aussi une implémentation de l'AVL générique. Bon, je l'ai pas encore testée à fond, il y a quelques rotations que j'aimerais éprouver un peu plus, mais ça concerne surtout la suppression, qui n'est pas utilisée pour la queue. La queue, elle, me semble plutôt solide - je l'ai pas mal utilisée sans trop de problème. J'ai également mis une petite implémentation de l'ensembe (Set), vraiment minimaliste, et basée sur un Dictionary .NET. Je vais essayer de formaliser ça avec une interface et plusieurs implémentations (pourquoi pas une avec un AVL, ça me semble également bien adapté).

Niveau perfs, c'est pas mal en théorie. Pour l'AVL on a les complexités habituelles de ce genre de structure. Pour la queue, on est en O(1) pour Dequeue(), et O(log(nbprio)) pour Enqueue(), avec nbprio le nombre de priorités différentes utilisées. En pratique, je suis vachement déçu par l'AVL. J'ai essayé de lui mettre 1 000 000 d'éléments dans la tête, il met environ 1 seconde pour faire les insertions, mais ça reste bien plus important qu'un équivalent avec une Hashtable. Heureusement, il reprend de l'interêt sur certains algos de recherche spécifique du genre "Trouver le plus grand élément inférieur à n", où la Hashtable échoue lamentablement (je donne les résultats des tests de perf de tête, j'ai plus la classe de test sous la main - à vérifier donc).

Je pense publier des mises à jour rapidement. En particulier, les noeuds internes de l'AVL sont completement opaques à l'heure actuelle (tout en internal). Il pourrait être intéressant de publier une partie de ces noeuds (par exemple en lecture seule), un peu comme pour les LinkedList du framework .NET2, afin de laisser plus de marge de manoeuvre à l'implémentation d'algorithmes de parcours de l'arbre.

Au passage, je tiens à parler des numéros de version de mes programmes. Je vais essayer le plus souvent de mettre des numéros de type Revxxxxxx est en fait mon numéro de révision subversion. Donc faut pas vous inquiéter si je passe de la révision 10 à la révision 16, vous avez rien raté à part des build intermédiaires inutiles. Concernant l'utilisation de mes prototypes, j'ai rien contre, mais je préfère ne rien autoriser pour le moment. Demandez-moi juste avant d'utiliser, il y a pas de raison que je refuse, mais pour le moment je préfère contrôler un peu la distribution de mon code.

Télécharger PriorityQueue Rev10

Damaged CD Recover

Bon, alors ça c'est un vieux proto que j'ai fait voilà facilement 2 ans. Je l'utilise encore régulièrement. Il permet en gros de lire un fichier, en sautant les "zones" du fichier qui génèrent des erreurs de lecture. Personellement, j'utilise ça pour récupérer le contenu de vieux CD rayés. Les zones illisibles sont remplacées par des '\0' (par blocs de 4Ko). Pour certains médias (genre les vidéos), ça permet de lire correctement le films, en faisant juste quelques artefacts rapides.

Je suis sûr qu'il y a déjà plein de programmes qui font mieux. L'idéal serait de "couper" la vérification CRC dur lecteur de CD sur les zones illisibles, pour avoir au lieu des '\0' les informations (partiellement erronées) que le lecteur arrive à lire. Dans l'archive, j'ai mis le fichier source (c'est du C) et l'executable. Je crois que j'avais complié ça avec le compilateur gratuit de Borland à l'époque.

Télécharger DCR-V1.0

Mon blog Prototypes

Voilà, je rejoins la sphère des bloggeurs. Je suis pas le premier. Bon, je me donne quelques règles rédactionnelles, on verra ensuite si je les suis (dans le cas où je maintiens vraiment ce blog, c'est déjà pas gagné).

Bon alors rapidement, mes objectifs

  • Mettre éventuellement mes humeurs du jour, mais à priori c'est pas le but
  • Publier mes protoypes, tous ces petits programmes que je fais de temps en temps pour tester telle ou telle techno ou idée qui me passe par la tête, et qui généralement restent sans suite.
Dans un premier temps, je vais voir si j'ai un peu de temps pour retrouver et publier quelques prototypes que j'ai pu faire cette année.