Ours & Hippy — le blog [~rz0]

Soon, it will be the Summer (of Code) again, and this year, too, NetBSD will be participating.^α At around the same time, last year, I was busy writing technical proposals for what would become xmltools, one of the accepted NetBSD SoC projects of 2009. Well, most of you have probably forgotten about that small project; some may even think it was a useless attempt and a waste of time and money, which could have been better spent elsewhere… Err, in fact, I’m writing this to say that my xmltools are not dead! And I still intend to contribute the code to the NetBSD tree sometime in the (near) future.

That being said, if you take a look at the Git repo, you’ll surely notice that nothing has moved for months… If you fool around a bit more, though, you may notice another project on the same Git host: regxml. Yep, this is a rewrite of my xmltools!

Why a rewrite, you ask? Well, basically because the old implementation was flawed by design, in addition to having become a mess.

The little boring story

And here’s the long answer, for those who care. Feel free to skip this section if it bores you.

During the second part of last year’s SoC, as I was trying to work on xmlsed, I realized my design was flawed. The main problem was that I had based all my efforts around a concept that was, for our purpose, completely inappropriate: node sets.

So what’s a node set? A node set is simply that: a set of nodes. Now, that’s great if you are extracting data from an XML document, as did xmlgrep, but it sucks if you’re going to operate further on that. In particular, removing arbitrary nodes from an XML tree doesn’t yield a tree, and replacing a node set made no sense at all. (How would you replace two far away nodes with one big chunk of XML? There are many ways to go about it… but they’re all wrong IMO.)

So what emerged at the end of the summer was that… I needed a new design, and as my original algorithm had become crippled with dubious ad hoc attempts to support operations that it never could, I needed a new algorithm too. (Besides, there was a deficiency in my algorithm that made it perform in super-polynomial time with some patterns and data sets, which was bad.)

It took me something like one month (since I wasn’t full-time on it) to jot down the new concepts and a (hopefully) good algorithm on paper. Then, for months, I’d try to implement it, but each time, something would feel really wrong, and I’d trash my new implementation. Well, that was till some days ago, when somehow, I got it right, and so the new xmltools were born!

XML intervals

So all this boils down to the following fundamental change: XML node sets have been replaced by XML intervals, as the core objects the xmltools operate on. An XML interval is really just that: a bunch of adjacent siblings and all their children. You should read the included xmltools(7) manual page for more information, from a user’s point of view.

From a more theoretical viewpoint, intervals have two important advantages over sets:

1. Inserting or removing an XML interval in an XML tree keeps it a tree. In other words, XML trees are stable by insertion and deletion of arbitrary XML intervals. (It may not have any meaning anymore, but remember xmltools are about syntax, not semantics.)

2. XML intervals map (injectively) to byte intervals in the XML file, hence all editing operations on XML intervals (sequences of insertions and deletions) can be expressed as operations on sequences of bytes in the file itself.

The first property is what I am convinced will make xmlsed possible. Previously, with node sets, it was a nightmare to give proper semantics to the various operations. But now, we have simple objects that still retain a great deal of expressivity but can be manipulated easily, with simple rules.

Although I do not use the second property yet, I’m definitely thinking about introducing an API for that sometime in the (not quite near) future.

The idea is that you run the XML matcher on a file mapped in memory (mapping new chunks as needed), and get a program script consisting of byte operations, that you can then run very efficiently on the memory-mapped file! Instead of printing an interval, you’d just copy over the entire memory region. Instead of deleting an interval, you’d just ignore that chunk. You get the idea. It could be used for efficient processing of massive data with complex transformation rules, but we’re not quite there, yet. :)

xmltools and NetBSD

As I’ve discussed with David (<dyoung>), I intend to import my core library, as well as xmlgrep into base sometime in the near future (once it has undergone more thorough testing). It depends on Expat for XML parsing, so I’ll need to import that too.

After much thinking, I think I’ll settle with a subdirectory in src/external/bsd, though I use the NetBSD build system, as I want to keep my development model using Git, and the ability to easily make packages of all my tools for non-NetBSD platforms.

The new code base uses (Net)BSD idioms more extensively than the old one (because I’ve got the time to read more NetBSD code since I started in May of last year). (E.g. I’ve followed David’s suggestion that I should make use of sys/queue.h.) Quite surprisingly, it compiles almost as is on GNU/Linux, with three additional defines and two trivial functions. I do provide a simple GNU makefile in addition to the default NetBSD build system makefiles, for GNU/Linux builds. Of course, you’re welcome to try to build it on other systems I don’t have access to!

What the future holds

Well, what’ll come next depends on a lot of factors, some of which are completely outside of my control. But there is one thing you can do: please download, compile, read the man pages, and test xmlgrep and give me some feedback, so I can fix bugs!

$ git clone git://git.huoc.org/regxml.git

Or through Git-Web: http://git.huoc.org/?p=regxml.git;a=summary

As far as the xmltools project is concerned, I’m now going to concentrate on xmlsed. I already have an idea of the implementation, and I think it’s not going to be too hard… hopefully, I’m not wrong. :)

P.S.: Oh, I forgot to talk about the new algorithm. Well, to get the idea, it’s basically an automaton backed by a backtracking memoizing work-queue-based interpreter, which roams the XML tree and try to match intervals. You should read the xmltools(7) man page for a high-level overview of the technique. Maybe I’ll write something more consistent on the subject later…

On entend souvent dire que l’on peut tout faire dans un langage comme dans un autre, Turing-complétude, tout ça. La variante de ce discours est que l’on peut tout faire en C parce que c’est un langage de bas niveau. Certes, on peut tout faire, mais on ne peut pas tout faire aussi bien, c’est-à-dire aussi efficacement.

Ainsi, avant de poursuivre avec mes articles sur les techniques de programmation en C, j’ai décidé de prendre le temps d’écrire un court billet sur ce que l’on ne peut pas faire en C. Ce petit texte n’a pas pour prétention d’être exhaustif, car la liste de ce que l’on ne peut pas faire en C est sûrement longue, très longue. Mais je souhaite donner ici quelques points de réflexion et principes de base, pour les plus débutants d’entre nous.

Le problème

Pourquoi donc ne peut-on pas faire aussi efficacement en C certaines choses que l’on peut bien faire dans un autre langage ? La réponse tient en cela : l’abstraction.

L’argument que l’on entend souvent est le suivant : le C étant plus bas niveau, il suffit de recoder les mécanismes internes abstraits par tel ou tel langage de plus haut niveau. Je suis d’accord avec cette méthode, je l’aime même beaucoup, étant moi-même assez spécialisé dans l’implémentation des langages. Mais il est important d’en connaître les limites.

Les limites, ce sont les limites de définition du langage. Si l’on veut utiliser le C comme un langage raisonnablement portable, et que l’on s’en tient à la norme, on hérite par la même occasion de contraintes normées, plus fortes que celles imposées par la plateforme pour laquelle on développe.

Concrètement, cela signifie que sur une machine donnée, votre beau C portable ne pourra pas recourir aux mêmes astuces que l’implémentation d’un langage de plus haut niveau (qui, elle, n’est pas portable). Prenez par exemple les variables de Scheme, ou tout autre langage dynamique. Dans ces langages, une variable peut pointer sur un objet, ou contenir une valeur numérique unboxed. En profitant de la représentation des pointeurs au sein du système hôte, et du fait que la mémoire n’y est jamais allouée que sur un alignement de 2, on peut utiliser un bit pour déterminer la nature de l’objet (boxed ou unboxed).^α C’est malin comme tout, et vieux comme le monde. Mais inapplicable en C. Question de portabilité. En effet, on n’a même pas la garantie que les pointeurs soient convertibles en entiers !

Mais, mais, me direz-vous, en Scheme non plus, on n’a pas cette garantie ! Oui… mais en Scheme, il n’y a pas de pointeurs comme en C ! Autrement dit, le programmeur s’en contrefiche : il utilise simplement son langage, et c’est au compilateur de décider comment telle ou telle fonctionnalité est traduite au niveau de la machine ; du point de vue du langage, on a perdu…

La solution ?

Mais on n’a qu’à implémenter des solutions spécifiques en plus de la version générale moins efficace ! C’est en effet une possibilité.

Par exemple, pour les objets dynamiquement polymorphes pointeurs / entiers, on pourrait se définir un petit jeu de macros dans ce genre-là :

#include <stdint.h>

#if UINTPTR_MAX && HAVE_2ALIGNPTRS

typedef uintptr_t VariantInt;
typedef uintptr_t Variant;

#define ISINT(x) ((x) & 0x1)
#define INTVAL(x) ((x) >> 1)
#define PTRVAL(x) ((void *)(x))
#define SETINT(x, y) ((x) = (y) << 1 | 0x1)
#define SETPTR(x, y) ((x) = (uintptr_t)(y))

#else

#if UINTPTR_MAX
typedef uintptr_t VariantInt;
#else
typedef long VariantInt;
#endif
typedef struct {
        union {
                VariantInt _int;
                void *_ptr;
        } _val;
        unsigned _isint: 1;
} Variant;

#define ISINT(x) ((x)._isint)
#define INTVAL(x) ((x)._val._int)
#define PTRVAL(x) ((x)._val._ptr)
#define SETINT(x, y) ((x)._val._int = (y), (x)._isint = 1)
#define SETPTR(x, y) ((x)._val._ptr = (y), (x)._isint = 0)

#endif

Bref, un truc du genre. Pas le plus beau jeu de macros du monde, mais vous comprenez le principe.

Et vous vous attendez sans doute maintenant à ce que je réfute cet argument… et bien non ! En réalité, c’est une manière parfaitement viable d’étendre un peu le langage. Cependant, elle requiert quelques précautions.

• Elle demande d’être méthodique, en cela qu’il faut patiemment écrire une macro (ou une fonction) pour abstraire chaque opération affectée par le changement d’implémentation. Cela peut être long, fastidieux, et si l’on teste plus une implémentation qu’une autre, on court le risque de se laisser biaiser, et d’oublier d’isoler des fonctionnalités qui devraient l’être.

• Elle tend à faire basculer les meilleurs programmeurs du côté obscur de la non-portabilité. :-° En effet, certains hacks marchent tellement biens que l’on est vite tenté de se dire qu’il ne sert à rien de maintenir une version générique, sous-optimale, mais conforme à la norme. Et c’est là un gros risque ! Parfois, on peut effectivement se laisser aller…

  C’est une question subjective, et je ne peux certainement pas décider à votre place. Je ne peux que vous offrir une règle générale que je m’applique de manière plus ou moins stricte :

  Plus le code se veut général (bibliothèques, composants réutilisables), plus il est important de maintenir une version standard, portable, de l’implémentation.

  Un avantage de cette stratégie est que vous pouvez en toute tranquillité utiliser l’implémentation simple, non optimisée, par défaut, et doucement migrer les différents systèmes, au cas par cas, vers votre code spécialisé, au fur et à mesure de vos tests (ou de ceux de vos utilisateurs !).

  Mais bien sûr, il ne faut pas se focaliser sur la portabilité, qui, de toute manière, est toute relative. En effet, si, par exemple, votre application dépend déjà fortement d’une bibliothèque tierce, telle que la GLib, qui elle-même fait certaines hypothèses sur l’implémentation, il peut être raisonnable de vous appuyer dessus.

Que retenir de tout ça ?

Au final, je dirais, pas grand chose, si ce n’est que j’essaierai, pour ma part, d’être précis quant aux implications des méthodes que je décris. Ce n’est pas (seulement) pour être pédant ; je pense qu’il est réellement important de comprendre (pour mieux ignorer, dirons certains) les limites des définitions et des standards que l’on accepte, parfois sans le dire.

À bientôt donc, pour de nouvelles aventures ! :)

Ce soir, j’ai décidé d’être paresseux, et comme beaucoup de blogueurs, je vous sers ici un peu de précuit, un peu de réchauffé : une liste de trucs et astuces !

Mais pas n’importe laquelle ! Récemment, j’ai twitté sur le triste état des ressources disponibles sur le Web français apparaissant dans des recherches telles que « généricité C ». Il y a beaucoup trop de cours et autres tutos superficiels, destinés à inculquer aux débutants quelques bases du langage ou de la programmation. J’ai donc décidé de réagir, à mon échelle, en publiant sur mon modeste blog des articles sur le C pour les bons ! :-° Voici donc le premier : le préprocesseur C, pour les bons !

Si en lisant ce qui suit, vous ne vous sentez pas très à l’aise, ou ne comprenez pas quelque chose, il vous manque peut-être quelques notions de base ; mais pas de panique, il vous suffit d’aller lire un cours quelconque, comme par exemple ce tuto dédié au préprocesseur, sur le SdZ.

La plupart des astuces que je présente ici sont illustrées dans des frameworks tels que COS. En moins violent, et plus usité, les en-têtes BSD `sys/queue.h` et `sys/tree.h`, dont je reparlerai probablement bientôt, sont également de bonnes illustrations de certaines techniques présentées ci-dessous. Citons aussi SGLIB, dans la même veine que sys/queue.h et sys/tree.h, mais poussant le concept un peu plus loin.

J’ai classé les astuces par ordre croissant de degré d’aliénation requis pour accepter de les utiliser. :-° Prêts ? Let’s rock!

Générez des séquences : opérateurs ,, ?:, && et ||

On vous a toujours dit que l’opérateur ,, c’était mal, que c’était Le Mal, après ‘goto‘. Mais il y a un cas où celui-ci peut s’avérer être un allié… intéressant. Il s’agit du contexte des macros.

Bien souvent, vous aurez envie que votre macro se comporte le plus possible comme une fonction, c’est-à-dire que si celle-ci renvoie une valeur, vous pouvez l’utiliser dans une expression.

C’est là que l’opérateur virgule (,) entre en jeu : il vous permet de placer plusieurs expressions dans votre macro, et que le tout soit réutilisable… comme une expression ! Les opérateurs ?:, && et || ajoutent un peu de variété à votre éventail de possibilités… mais rappelez-vous qu’il faut employer avec && ou || des opérandes à valeur entière (ou en tout cas qu’il est possible de convertir en entier).

Et un exemple bidon :

#define GETARG(argcptr, argvptr) (--*(argcptr), ++*(argvptr))
#define CMP(p, q) ((p) == (q) || cmpfunc((p), (q)) == 0)

Remarquez le problème des effets de bords potentiellement provoqués par l’évaluation de p ou q, dans la seconde macro ; nous allons y revenir…

Générez des structures de contrôle : utilisez la boucle for !

Mais les macros ne sont pas limitées à remplacer des fonctions, elles peuvent également être utilisées pour créer de nouvelles structures de contrôle.

À la différence d’un appel de fonction, l’utilisation d’une structure de contrôle inclut un (ou plusieurs) blocs de code. Le schéma de base simplifié est le suivant :

BEGIN (/* ... */) {
        /* ... */;
} END (/* ... */);

Il faut bien sûr remplacer BEGIN et END par des macros appropriées.

En utilisant des boucles for pour implémenter votre structure de contrôle, vous pouvez souvent omettre la partie END, et ainsi alléger l’usage de vos macros.

Un exemple de telles constructions peut être trouvé dans sys/queue.h ; dans cet exemple, on parcourt une liste (implémentation typique : une boucle for) :

LIST_FOREACH (var, head, next) {
        /* 'var' pointe successivement sur chaque élément. */
        /* ... */;
}

Un autre exemple, de structure plus complète, munie du marqueur de fin, peut être trouvé dans les bibliothèques standards de Plan 9 ; le code suivant permet de traiter les options de la ligne de commandes :

ARGBEGIN {
case 'a':
        /* Option '-a' spécifiée. */
        /* ... */;
        break;

case 'b':
        /* ... */;
        break;

default:
        usage();
} ARGEND;

Utilisez la concaténation pour simuler la généricité par nom

La concaténation est un mécanisme puissant puisqu’elle permet de générer des identificateurs à partir de fragments, dont certains peuvent être passés en paramètres à vos macros.

Moyennant le respect de quelques conventions dans les noms, vous pouvez écrire du code générique, dont les parties spécifiques sont masquées derrière un espace de nom improvisé passé en argument.

Et encore un exemple bidon pour illustrer le principe de base :

#define RELEASE(name, p) do {                               \
        if (name##_decrref(p) == 0)                         \
                free(p);                                    \
} while (/* CONSTCOND */ 0)

Générez des définitions

Rappelez-vous l’histoire des effets de bord que nous avons rencontrée plus haut. Il n’y a pas de méthode magique, pour éviter les effets de bords, il faut passer par des variables intermédiaires.

Une solution simple et plutôt élégante pour résoudre ce problème est de générer non plus du code directement, mais des fonctions… Mais, mais, me direz-vous, quel intérêt de passer par des macros pour générer des fonctions ? Pourquoi ne pas écrire les fonctions directement ?

Et bien, cette astuce, combinée à la précédente, permet un peu de généricité ! Et un ptit exemple pas très utile, pour la route :

#define ARRAY_FIND_PROTOTYPE(name, type, cmp)                 \
type *name##_ARRAY_FIND(type *, size_t, type *)

#define ARRAY_FIND_GENERATE(name, type, cmp)                  \
type *name##_ARRAY_FIND(type *_a, size_t _n, type *_elm)      \
{                                                             \
        for (; _n > 0; ++_a, --_n) {                          \
                if (cmp(_a, _elm) == 0)                       \
                        return _a;                            \
        }                                                     \
        return NULL;                                          \
}

#define ARRAY_FIND(name, a, n, elm)                           \
        name##_ARRAY_FIND((a), (n), (elm))

Pour des exemples plus complets, je vous invite à jeter un coup d’œil à l’implémentation de `sys/tree.h` (ou localement, dans /usr/include/sys/tree.h si vous avez un BSD sous la main).

Côté performances, vous n’avez guère de soucis à vous faire. Si vous définissez des fonctions statiques, le compilateur s’occupera tout seul comme un grand de les machiner comme il se doit. Et si vous voulez lui forcer un peu la main, inline est là pour ça.^α

Simulez les alternatives avec la concaténation

Nous arrivons ainsi à la dernière astuce accessible avec un préprocesseur à la norme C89.

Vous connaissez certainement les directives #if, #ifdef, et compagnie. Hélas, elles ne peuvent être utilisées à l’intérieur d’une définition de macro.

Dans les cas simples — mais très courants — où vous souhaitez simplement discriminer entre plusieurs valeurs d’une constante passée en paramètre, cependant, vous pouvez vous en sortir en utilisant… la concaténation ! Encore elle !

En effet, il suffit pour cela de définir chaque alternative comme une macro séparée, nommée avec un préfixe commun, et un suffixe dépendant du cas. Illustration :

#define DECL_STATIC_0
#define DECL_STATIC_1 static
#define DECL_STATIC(s) DECL_STATIC_##s

#define SOME_FUNCTION_PROTOTYPE(name, type, s)              \
DECL_STATIC(s) type some_function(type);

Simulez les opérations sur les n-uplets avec les macros variadic (C99)

Avec C99 ont été introduites les macros variadic, c’est-à-dire acceptant un nombre variable d’arguments. Cet ajout, a priori mineur, est en vérité très important, car il permet la manipulation des n-uplets, soit des collections de valeurs.

Pour nous, un n-uplet sera une suite d’éléments séparés par des virgules, entre parenthèses. Par exemple :

(a, b, c)

Pour opérer sur des tuples, le truc de base à remarquer est le suivant :

• les appels de macros respectent l’équilibrage des parenthèses (ce qui permet effectivement de passer des n-uplets comme simples arguments à des macros) ;

• les macros sont développées autant de fois que possibles : si le texte substitué par une macro contient encore des invocations de macros, celles-ci sont traitées (sauf si elles ont déjà été appelées) ;

• en juxtaposant un n-uplet à un nom de macro, on obtient un appel de la macro correspondante, avec en guise d’arguments les éléments du n-uplet !

Il faudrait un billet entier pour explorer en profondeur toutes les possibilités offertes par cette astuce. Je ne vais présenter ici qu’un cas d’utilisation simple, mais sachez qu’il est possible, par exemple de créer une macro qui substitue tout n-uplet par 1 et toute autre construction par 0, par exemple ! Je vous laisse imaginer ce que l’on peut en faire, combinée aux alternatives par concaténation expliquées ci-dessus.

Mais revenons à notre modeste exemple, qui illustre la fonction identité de manière ridiculement complexe :

#define IDENTITY(...) __VA_ARGS__

/*
 * 'IDENTITY' peut en fait servir à supprimer des parenthèses
 * superflues gênantes.
 */
#define CALL_WITH_RESOURCE(name, var, aargs, f, args) do {  \
        name##_type var = name##_alloc aargs;               \
        f(var, IDENTITY args);                              \
        name##_free(var);                                   \
} while (/* CONSTCOND */ 0)

#define FILE_type FILE *
#define FILE_alloc fopen
#define FILE_free fclose

/* ... */
CALL_WITH_RESOURCE (FILE, fp, ("log.txt", "a"),
    fprintf, ("%d\n", 42));

COS contient une bibliothèque entière de macros travaillant sur les n-uplets. Je vous invite à regarder le code source si cela vous intéresse ; il s’agit plus particulièrement du dossier CosBase/include/cos/cpp/, dans l’archive.

Énumérez les cas et déroulez les appels pour émuler la récursion (C99)

Au vu de ce que nous venons de voir, vous êtes en droit de vous demander : « Peut-on faire pire ? » Et la réponse est oui ! :) J’ai gardé cette astuce pour la fin car elle constitue, à mes yeux, une limite que je ne souhaite pas, à titre personnel, franchir.

Un peu plus haut, j’ai dit quelque chose d’important : dans une chaîne de substitutions de macros, une macro déjà substituée ne le sera plus, même si elle apparaît dans le texte produit… il est donc impossible de faire des macros récursives !

L’astuce ici consiste à dire : « L’univers est fini, je vais décrire tout l’univers ! » Aidée de la concaténation, les possibilités sont vraiment (in)finies ! Mais je ne m’étendrai pas davantage sur le sujet. Encore une fois, COS contient toute une panoplie d’exemples, qui, je n’en doute pas, apparaîtront brillants pour certains, et affligeants pour d’autres.

Voilà, en espérant vous avoir appris quelques petits trucs rigolos ! Have fun!

Récemment, on m’a demandé de composer quelques vers pour le Post’IT, le journal de l’école. Et puisque je me suis remis à écrire un peu, je me permets de poster ici un vieux billet, vieux d’octobre dernier !

En octobre dernier donc, dans le sombre hall de l’Ensimag, près de l’endroit qui sent le paté… On me fit remarquer, là, dans un coin, accroché sur le panneau réservé aux associations, un poème. Et quel poème ! « L’amoureux ! » Il fallait réagir ! Ramener à ce micro-monde la Vérité !

Et le lendemain, ce fut chose faite ; encore aujourd’hui, vous pouvez trouver, accroché près de ces vers, les miens, signés de ma vraie fausse signature. Pour ceux qui ne peuvent malheureusement se déplacer, voici tout de même, en guise de consolation, mon œuvre ! :-°

L’infirme

Je suis l’amoureux !
Là, ne vois-tu pas, dans mes yeux ?
Cette larme de mots, invisible,
Demandant à mouiller ton reflet ?
Et là, les chants muets !
N’agonisent-ils pas, à mes lèvres
    suspendus,
Guettant une illusion de ta gorge
    dévêtue ?

Ne suis-je pas l’amoureux ?
Au fond de mon lit, malheureux,
Bercé de désirs impossibles.
Dérivant de fantasme impuni
En crime inassouvi,
Ne devines-tu pas où l’esprit vagabonde,
Égaré par ses propres passions infécondes ?

Suis-je l’amoureux ?
L’aube m’est venue, le cœur creux.
Ma plume est sèche,
Mes pages défigurées ;
J’y parle d’amours éthérées.
Ton image,
    ce doux spectre, toujours me poursuit ;
Mais déjà,
    mon regard se confond dans l’ennui.

Pourrais-je être l’amoureux ?
Tu le sais ! Dis moi ! Je le peux.
Ta chair est fraîche,
Et ma nature invincible.
Je sais que les voix inaudibles
Souffleront à mes sens, quand enfin viendra l’heure,
De m’en faire à nouveau le gardien, le voleur.

Comme promis, voici la seconde partie de mon article traitant de ce sujet ô combien passionant qu’est… mon blog. Finies la conception et les questions programmatiques profondes, et place à l’action, au déploiement, à la publication, au référencement ! Autant de sujets qui pourront surprendre le lecteur habitué de ce blog.

Mais pourquoi s’embêter avec tout ça, me souffle-t-on ? On a développé un produit, à n’en pas douter, technologiquement révolutionnaire… il faut maintenant le vendre ! Et pour un blog, pour un site Internet, pour un projet amateur tel que celui-ci, se vendre, cela signifie avant tout se faire connaître, et plus précisément, dans notre cas, être lu.^α

Dans ce petit billet, je vous propose un tour d’horizon des techniques que j’ai appliquées à mon blog, dans l’optique d’améliorer la navigation, pour les humains, comme pour les robots. Ces optimisations sont adaptées au modèle que j’ai choisi. Elles ne conviendront certainement pas à tout le monde, ou à tous les contextes. Mais si vous aussi vous tenez un blog, ou un petit site à but informatif, que vous êtes jeunes et candides, face à la perversion grandissante du Web, peut-être cet article saura-t-il vous apporter quelques réponses… à des questions que vous ne vous êtes sans doute jamais posées. :)

Vitesse, charge, hébergement

La première question qui se pose, une fois le blog codé, est de savoir où l’héberger. J’ai opté pour un hébergement à la maison, c’est-à-dire sur une de mes machines, derrière ma Freebox. C’est une décision critiquable, étant donné la petite bande passante dont dispose ainsi le site, mais jusqu’à maintenant, la faible fréquentation du blog ne s’est pas révélée être un problème pour ma connexion.

En contrepartie, l’hébergement chez soi permet une grande flexibilité. On configure soi-même la bête, on y déploie la plateforme que l’on veut : serveur HTTP, SSH, langages de script, bibliothèques appropriées, etc.

Mais si le cœur du blog, c’est-à-dire le script de génération des pages HTML, est toujours servi depuis chez moi, un des changements majeurs de cette nouvelle mouture est l’externalisation des ressources statiques. Ainsi, lorsque vous naviguez sur le site, les feuilles de style et les images sont en réalité téléchargées depuis media1.huoc.org, un domaine pointant sur un petit compte gratuit que j’ai pris chez alwaysdata. Le bénéfice est double : d’une part, je me décharge ainsi d’une petite moitié du trafic lié à chaque nouveau visiteur (les anciens ayant déjà ces fichiers en cache), d’autre part, les requêtes HTTP sont réparties entre deux hôtes (de manière certes inégale : plus de données d’un côté, plus de requêtes de l’autre).

De même, le flux Atom principal du site est maintenant réchauffé par FeedBurner, ce qui, au passage, me permet de collecter quelques statistiques.

Bien sûr, avant même de s’occuper de cela, la meilleure optimisation pour gagner un peu de bande passante passe d’abord par la prise en charge de la mise en cache (en-têtes HTTP Last-Modified, If-Modified-Since et Cache-Control) accompagnée d’une compression gzip du contenu textuel.

Une autre astuce que j’utilise, enfin, est l’incrustation d'images dans le CSS pour réduire le nombre de requêtes HTTP.

Tout cela combiné me permet de vous présenter le contenu de la page principale du blog en à peine plus de 50K (dont 10K sont pris par le script JavaScript de Google Analytics…) d’images et de texte compressé, ce qui, entre nous, est mieux que la plupart des blogs que j’ai pu voir ; ceux basés sur Wordpress^β tournent généralement autour de 200K.

Promotion, référencement

Le blog est maintenant en place, on peut y accéder, tout va bien, mais le plus dur reste à faire : le faire connaître. Honnêtement, avec la modeste fréquentation de mon blog, ce n’est probablement pas moi qui vais vous donner des leçons concernant le référencement. Si j’ai retenu une chose de mes lectures et de mes expérimentations, cependant, c’est certainement ceci : présenter du contenu correctement structuré par un HTML simple et sémantique, avec des URL courtes et sympas contenant quelques mots-clés, est agréable à naviguer, et plutôt bien récompensé par Google. Que demande le peuple ?

Ce qu’il demande, généralement, c’est des liens retour, les fameux liens retour… avoir des gens qui font référence à vos articles, si ce n’est pas là un symbole de réussite ! Hélas, il n’est pas aisé de stimuler l’enthousiasme au point que l’on veuille vous citer.

On peut bien sûr faire un peu de publicité par-ci, par-là, en insérant un lien discret dans ses profils, sur les forums, ou autres réseaux sociaux que l’on fréquente, mais les liens ainsi générés risquent d’être relativement médiocres (en revanche, c’est un bon moyen d’amener des visiteurs).

Ou on peut s’inscrire sur des annuaires… Option que j’ai envisagée à plusieurs reprises sans jamais vraiment me décider. J’ai mis longtemps avant de franchir le pas pour dmoz, et c’est pourtant le plus gros annuaire ! Il y a plusieurs raisons à cela. D’une part, la plupart des annuaires que j’ai pu voir (et j’en ai parcouru un rayon) ont un air très amateur. Parmi les rares qui sont visuellement acceptables, il y a souvent le problème du voisinage : certains annuaires ont trop de liens entassés les uns sur les autres sans hiérarchisation, d’autres souffrent de problèmes de modération, ou parfois, on se heurte tout simplement à des fluctuations de la qualité des liens au sein d’une même page ou d’une même catégorie, qui laissent dubitatif (vais-je me retrouver à côté de ce vilain site-là ? ou de celui, qui a l’air plus correct ?).

Conclusion

Voilà qui conclut ma brève non-série d’articles portant sur mon blog. Et après toutes ces semaines de développement Web, je suis impatient de reprendre une activité plus… normale. Il reste certes encore quelques bugs, mais il est grand temps pour moi de changer d’air…

Voilà un petit mois que j’ai commencé mon stage en laboratoire, stage facultatif entrant dans mon cursus Ensimag. Pour les curieux, je suis chez TIMA, un labo en plein centre de Grenoble. Durant ce stage, je suis censé étudier la prise en charge de processeurs VLIW par QEMU, en me basant sur l’exemple du C64x+, un DSP conçu par Texas Instrument. L’objectif est d’établir une méthode convaincante, et un petit prototype qui l’illustre sur le C64x+.

Pour l’heure, je ne peux que constater que j’ai un mal certain à m’adapter à QEMU. Ce n’est pas tant à cause de la documentation interne quasi inexistante, ça, disons, j’ai l’habitude avec le code libre. Mais la structure même du programme est à mon sens quelque peu obscure : de la redondance entre modules similaires, une isolation architecturale qui me paraît douteuse, et des conventions qui semblent au premier abord très peu intuitives.^α

Dans ce premier article, donc, je vous propose simplement une petite présentation de QEMU et de sa technique d’émulation, du moins, ce que j’en ai compris. :)

QEMU is an emulator

Et ouais, QEMU, ce n’est pas WINE. Car QEMU, c’est un émulateur, un programme capable d’exécuter du binaire destiné à d’autres machines. Dans la petite jungle des solutions d’interopérabilité binaire, l’émulateur est sans doute celui qui se place au niveau le plus bas puisqu’il lit et imite une architecture directement au niveau de son jeu d’instructions. QEMU se différencie en cela de logiciels de virtualisation, tels que Xen, dont j’ai déjà parlé dans un billet précédent, dont le but est de faire tourner des systèmes différents mais conçus pour le même CPU, sur une même machine.

Le travail d’un émulateur est donc de lire et d’exécuter un code binaire ; en l’occurrence, il s’agit du codage des instructions d’une machine réelle, mais cela pourrait tout à fait être une machine abstraite. Au final, les techniques possibles sont semblables à celles que l’on peut imaginer pour un compilateur. Simplement, ici, le langage source est binaire (et le langage cible aussi). L’analyseur « syntaxique » se voit donc remplacé par une espèce d’automate dont le rôle est de décoder le binaire en entrée, à la manière du processeur que l’on imite. On y gagne a priori en simplicité : les formes que peuvent prendre les instructions sont généralement assez régulières et limitées. Mais les subtilités guettent ! Pour peu que le jeu d’instructions soit un peu étoffé, les cas particuliers se multiplient rapidement. De plus, il faut prendre en compte l’état de la machine ; en terme de langages, cela se traduirait par un contexte.

Une fois l’instruction identifiée… reste à l’exécuter. Là encore, comme pour les langages de programmation, le choix s’offre à nous, notamment entre interprétation et compilation. Et QEMU a choisi…

Traduction binaire dynamique

… la traduction binaire dynamique.^β En quelques mots, il s’agit d’une compilation à la volée vers du code exécutable par le processeur hôte (faisant tourner QEMU lui-même). Ce code est ensuite directement exécuté. Et hop ! On a un truc pas trop lent. C’est grosso modo le même principe que dans les JIT que l’on trouve dans les machines virtuelles de langages de haut niveau, et dont, il y a quelques années, tout le monde était trop fier.^γ

Plus en détails, QEMU est composé de modules implémentant chacun l’émulation d’un processeur donné, appelé processeur cible (target), en opposition au processeur hôte, sur lequel tourne QEMU, et vers lequel les instructions vont être traduites. La responsabilité d’analyser l’entrée binaire est déléguée au module.

Celui-ci lit l’entrée par blocs qu’il traduit dans un langage intermédiaire, composé d’un jeu de micro-opérations minimal. Un bloc est une suite simple d’instructions, qui s’exécutent linéairement, les unes après les autres. Concrètement, cela signifie que le bloc prend fin au premier saut. Ce code intermédiaire est transmis à TCG, le générateur de code de QEMU, qui se charge de le traduire pour l’hôte. Cela ressemble à s’y méprendre à de la compilation, n’est-ce pas ? Ici, on retrouve les avantages usuellement attribués à l’usage d’un langage intermédiaire : abstraction, uniformité, simplicité.

Et moi, dans tout ça ?

Et bien moi, dans tout ça, je travaille surtout sur la partie analyse et génération du code intermédiaire. L’objectif de mon stage est d’élaborer une méthode de traduction systématique de jeux d’instructions VLIW vers le langage intermédiaire de QEMU. L’idée serait d’automatiser les aspects fastidieux liés à la multitude de cas possibles introduite par le parallélisme. Ainsi, à partir d’une description abstraite du jeu d’instructions, j’espère pouvoir générer le code qui effectue réellement la traduction.

À l’heure où j’écris ces lignes, je commence tout juste à m’attaquer à la partie traduction. J’ai passé ce dernier mois (du moins les jours où je travaillais dessus) à faire connaissance avec QEMU, et, dans une moindre mesure, l’architecture du C64x+. Pour l’heure, je n’ai produit qu’un squelette plus que minimaliste de target C64x+, dont je pense reparler bientôt, dans un prochain article technique consacré au récit de mon (début de) périple dans les entrailles de QEMU !