Ours & Hippy — le blog [gsoc]

So the Summer of Code ends soon and it’s time to report what has been done, and what is still lacking. Obviously, everybody can see there is no xmlsed yet in the repository, so what have I been doing since I completed xmlgrep one month ago? What went wrong?

Well, if you ask me, nothing really went wrong, I have just deviated somewhat from my original goals and taken the time to do some things that weren’t part of the initial plan. And even though I am disappointed not to have finished, this has brought its share of good additions. Most of these modifications stem from discussions with David (Young) about features we’d like to see in my xmltools. Also in all these three months, I’ve spent about three weeks optimizing the matcher code.

What we have

Let’s talk about the good stuff first. Of course, the visible part of my work is the existence of xmlgrep, but most of the code actually lives in a common static library. It provides:

• definitions for patterns and trees;
• utilities: (tree) buffers, bit vectors, symbol look-up, state and transition caching;
• a string to pattern parser (that I often just call "pattern compiler");
• an XML parser (which can handle fragments and multi-roots documents, or work as an interface to Expat, for strict XML parsing);
• an XML pretty printer;
• the code for the matcher itself;
• and a higher-level API used to build the tools themselves.

The library has managed to remain reasonably small, with less than 5k lines of code, counting comments and everything, and the core matching algorithm fits in less than 1.5k lines or so (compare this to the 15k-line xpath.c from libxml2). It is stream-oriented and care has been taken so it eats as little memory as possible while remaining efficient.

The pattern matching code

The matcher is undeniably the most important and sensible piece of code in there. It is a blend of a kind-of-NFA and a backtracking machine, which processes one node at the time (NFA) but is able to do unlimited look-ahead (backtracking). Recent work has involved adding new advanced constructs to the matcher (besides forward and look-ahead mechanisms, which were already implemented) and improving its performances when look-ahead is in use.

Performances

On the performance side, the main addition is that of a state cache and pre-computed states created by the pattern compiler (instead of the matching code itself).

The state cache (implemented as a hash table) operates at two levels :

• propagation (from parent to child and sibling to sibling);
• and filtering (deciding whether based on local properties, states match or not).

One effect of using a cache is that bit vectors need not be pooled anymore and a lot of copying has disappeared in favor of pointer swapping. Also, relying on states pre-computed by the pattern compiler has shifted the focus from looping bit by bit through bit vectors to whole-vector operations, most of which can be auto-vectorized by a sufficiently smart compiler (ICC on Linux can vectorize a dozen of these in the whole xmlgrep code, but as I’ve pointed before, GCC auto-vectorizer seems to lag behind its non-use, at least on my code and setup).

With these optimizations merged in, xmlgrep now outperforms xmlstarlet both in terms of speed and memory consumption on my silly little benchmark (for those who have not been there, it consists in grepping for a word and its definition in a 50M XML-formatted English dictionary, and yes, it’s simple-minded), even when using suboptimal look-ahead subpatterns.

Indeed, knowledge of the XML format often enables us to write optimized patterns by anchoring a more costly part with a basic predicate. In our case, instead of searching for p[hw/.="somestring"] (the suboptimal case), we could search for body/p[hw/.="somestring"] since p can only occur inside body. This is an improvement since the p[] part, being a look-ahead subpattern, is sensibly slower than a forward pattern, so reducing the number of tentative matches is essential.

Compared to benchmarks done at the time of the release of xmlgrep, handling of this suboptimal case is about three times faster now.

Features

On the feature side, which is probably more interesting for casual would-be users, I have added grouping, Kleene-like operators, and subpattern negation, as well as reworked some of the old syntax.

Subpattern negation is the simplest extension, algthough it’s fairly powerful. It can be achieved because of backtracking so it’s only available on (look-ahead) subpatterns, not groups (see below). Negation lets you write something like {a}!{a/b} which selects all elements a that do not have a b element. This can’t be done with regular patterns because a node can have many children, and thus, unlike with regexes, something like a/!b (would-be syntax) would match some a node with a child which is not a b, but there can be many other children.

For example:

$ xmlgrep -x '{dict}!{dict/@id}/key/.' test.plist

will extract only keys from unnamed dictionaries.

The second addition is Kleene-like operators. Well, sorry about the name, but it’s just what comes to mind when I use these. They are, as the name implies, somewhat like their regex counter part, the Kleene star, in that they match zero or more repetitions of the preceding predicate. E.g. a*%b matches <a/><a/><a/>...<b/> but not, say, <a/><c/><d/>...<b/>. The %% and // operators have now become special cases of the Kleene operators. a%%b can be written a%**%b and a//b is really a/**/b, where the first star stands for "any node" and the second is part of the operator.

But having these repetition operators limited to repeating a single node predicate would have been quite boring, and so groups were born. Groups, written inside parentheses () (notice these have replaced the old subpattern syntax which has been moved back to being {} from its first days), well, group a pattern fragment, so that it can be repeated. They also accept alternation so you can write a%(b|c)*%d, which just seems natural.

Let’s take an example:

$ cat test.xml
<B/><a/><b/><a/><b/><a/><b/><a/><b/><a/><b/><E/>
$ xmlgrep 'B%(a|b)*%E' test.xml
<E/>

Groups are implemented without backtracking so using a group is not much more costly than using plain forward patterns, and is faster than using look-ahead subpatterns.

Yet, that is only true of normal groups. When you use a selection operator (+, #, - or =) on a group, it becomes a capturing group, a.k.a. look-ahead group. A look-ahead group is really a look-ahead subpattern combined with a group and has a somewhat subtle behavior. It behaves like a group, with the following difference: any selection operator inside a look-ahead group will only apply if the whole group matches. This can be used to bind selectors together. Thus we can revisit the classical key/value pair example: how do we match a key/pair with some properties on the key and some other on the value? You can always do that with simple look-ahead subpatterns combined with forward patterns, but groups just make it more convenient.

Imagine you want to match all key/value pairs where the key contains the letter a and the value is a string. Easy, with a capturing group:

$ xmlgrep -x '(key[.~"a"]#%string#)+' test.plist

Other components, reusability

Some people have discussed with me the possibility of making the library reusable. As it is now, it is not yet ready for wider exposure, but a lot of work has gone into rationalizing its API, in order to prepare for that. The API needs to be stabilized and the various components need to be better segregated.

Currently, the data structures in use are tightly integrated. For instance, the parser actually builds a tree with nodes able to hold matching states. Somehow, I would need to break that dependency, so that the matcher depends on the parser, but not the opposite, so you could use the XML parser as a stand-alone component (it has a nice hybrid design). Other parts are less affected, though.

What’s left to do

Now for the bitter part. Obviously, there are still a lot of things left to do, and I intend to continue working on this project, but whether it will be integrated into NetBSD at some point in the future is not for me to decide, though I really hope it will.

In short, here is the plan:

1. write support for xmlsed templates in the library;
2. write xmlsed proper;
3. change the/add a high-level API to the library to make it possible to write xmljoin (because the high level framework only accepts one input file at this point in time);
4. see what more needs to be adjusted for xmljoin to fit into the framework;
5. write xmljoin proper;
6. see what needs to be done for xmlsort to fit into the framework;
7. write xmlsort.

Of course, I have given some thoughts to the "see what needs to be done" phases, but now is not right time to talk about that.

Also, at some point, I’ll need to address several shortcomings of the current code base:

• add locale support;
• convert my bunch of "regression shell scripts" to proper test suites (ATF, probably);
• add non-NetBSD build support (currently, I have to hand-compile it on my Linux box).

And I will also want to:

• clean-up the API and release the core components as a stand-alone library;
• write documentation on the internals to accompany that library;
• and of course, integrate it into NetBSD, if I am given permission. :)

Lastly, about xmlsed, though you can see no xmlsed directory in the repository, I can say it is pretty close to completion since the pieces needed are almost all there in the library (the only one missing is the template support, and that’s not the hard part).

Conclusion

The Google Summer of Code is nearing its end, but my summer vacations are not over yet. I won’t have classes until September, so I plan to carry on as if nothing much happened at least till the end of August. After that, I won’t have nearly as much free time, but I’ll do what I can; let’s not be hasty and wait till then to see how far the project has gone.

I will continue to update this blog and the code will be available at my Git repository, as usual. (Anyway, I have just recently added comments to my blog so feel free to drop by and give me your opinion.)

Un peu de sérieux, pour une fois. Parlons peu, parlons bien, parlons du Google Summer of Code, du mien, pour être plus précis. C’est l’histoire de comment tout semblait vachement bien parti et puis finalement s’est pas si bien terminé. Ce que je vais raconter ici ne concerne très probablement pas que le GSoC, ni même le libre en général, en fait pas du tout, c’est juste le récit d’un jeune programmeur « inexpérimenté » devant son premier « vrai » projet.

Mais tout d’abord, quelques faits. Sur mon projet, xmltools, une initiative destinée à produire des outils de manipulation de fichiers XML en ligne de commandes, et sur moi, jeune programmeur de vingt-et-un ans, principalement autodidacte. C’était également mon premier « boulot », si l’on peut appeler cela un emploi. Un profil faible, me direz-vous ? Peut-être, mais je n’ai trompé personne quand j’ai posé ma candidature, et par ailleurs, je n’ai pas l’intention de feinter le débutant victimisé : sur le plan technique, je ne me considère plus comme un novice depuis bien des années, en général, et plus particulièrement dans le domaine qui nous concerne (l’analyse syntaxique, l’interprétation, et assimilés).

Des faits, plus de faits : à ce jour, quels sont donc les résultats de mon projet ? xmlgrep est fonctionnel depuis juillet… mais aucun autre outil n’est utilisable encore ! Il me manque bien au moins la moitié des objectifs listés dans mon cahier des charges ! Pourtant, mon projet n’a pas échoué, si l’on s’en tient aux documents officiels. J’ai été payé. Mais je ne suis pas satisfait, et sans doute si l’on s’y penche d’un point de vue extérieur, il y a lieu de se demander à quoi j’ai été payé ! Le malheur tient en cela : j’ai fait des choses, certes, j’ai même investi beaucoup de temps dans ce projet, mais au final, je n’ai pas rempli les termes de mon contrat. Résultat des courses : aux yeux de tout le monde, c’est l’incompréhension, et je passe pour un idiot ou un incompétent.

Question naturelle : qu’ai-je donc fait ? Et bien figurez-vous que j’ai passé mon temps à étoffer et refactoriser le code existant, en fonctionnalités diverses et variées. Mais pour en comprendre les raisons, il faut remonter à juillet, l’évaluation de mi-parcours, xmlgrep était prêt, annoncé, emballé, tout semblait bien se dérouler. J’ai même eu droit à quelques critiques favorables, notamment de la part des gros ours du GCU. Après ça, j’ai rien glandé… est la conclusion vers laquelle on se sent intuitivement guidé, et disons, durant peut-être deux semaines, c’était plus ou moins le cas, ou plutôt, je ne glandais rien de concret. L’origine de ce glandage est en fait liée à un désaccord entre mon mentor et moi-même sur l’interface et les fonctions d’xmlsed. Le sujet du débat ? Une histoire de syntaxe XML ou non. Du moins, c’est ce qui est apparu en surface. Mais cette confrontation m’a fait prendre conscience d’un problème bien plus profond : mon mentor et moi-même étions partis depuis le départ sur des idées très différentes de ce que devaient offrir les outils que nous pensions tous deux que j’allais développer. Là où les choses se sont effectivement compliquées, c’est que ma vision des objectifs était sensiblement plus simpliste que la sienne. En d’autres mots : le modèle que j’avais conçu, les algorithmes que j’avais écrits, et l’interface que j’avais programmée, qui devaient servir de base commune à tous mes outils, ne convenaient plus aux nouvelles contraintes qui m’étaient imposées.

À partir de là, deux choix s’offraient à moi : finir ce que j’avais entrepris, de la manière dont je l’avais envisagé, ou retravailler les fondations pour avancer dans la direction qui m’était donnée. Comme vous vous en doutez à présent, j’ai choisi la seconde option, et je ne le regrette pas. Le code a grandement gagné en complexité depuis ce temps-là et supporte maintenant des fonctionnalités que je me refusais au départ à inclure (et donc pour lesquels je n’avais rien prévu dans mon algorithme). La version d’xmlsed sur laquelle je travaille aura une interface proche de ce que mon mentor souhaitait et permettra en peu de lignes ce qui aurait pris le triple, voire aurait été impossible, si j’avais continué sur ma lancée.

Cela signifie-t-il que j’avais tort en premier lieu ? C’est une question difficile, mais je ne crois pas. Mes choix étaient différents. Tels que je me les imaginais, mes outils devaient être plus limités, plus simples, plus proches de l’implémentation. Je pensais qu’ils seraient complémentés par du scripting, de la programmation, pour compenser le manque d’expressivité du langage de motifs. Pour cela, j’avais commencé par élaborer ma propre variante vaguement issue d’XPath, mais aujourd’hui, j’en suis à penser que mon choix s’explique de moins en moins (il demeure que le langage est plus concis, donc utilisable en ligne de commandes, par exemple) et qu’il me faudra sans doute un jour implémenter XPath comme alternative, ou il me sera reproché de ne pas l’avoir fait (et à cet effet, hop, j’en profite pour glisser un lien vers ma version modifiée du yacc NetBSD qui supporte la génération d’analyseurs réentrants et prenant les symboles un à un, en argument, au lieu d’appeler yylex, bref, des trucs que j’aimerais voir intégrés à NetBSD d’une manière ou d’une autre, ça m’arrangerait…).

Suis-je pour autant mécontent du détour effectué ? Fondamentalement, non. Le challenge technique apporté n’était pas déplaisant, tout au contraire, et de ce point de vue, j’ai su venir à bout de problèmes que je pensais hors de ma portée directe. Et je fais confiance à mon mentor pour mieux définir les besoins des utilisateurs que moi ; j’ai sans doute trop valorisé le critère « possède une implémentation simple et cool » par rapport à l’aspect « confort d’utilisation ».

Le problème est plus dans l’apparence des choses : j’ai continuellement le sentiment inconfortable de ne pas avoir réalisé mon travail correctement, de ne pas avoir rempli les objectifs que je m’étais fixés (alors que tout le monde à côté semble avoir fait du bon boulot). Et j’ai bien peur que la communauté le voie de cette manière, également, et il serait difficile de lui en vouloir, d’autant plus qu’avec la reprise de la vie étudiante, l’avancement du projet est nettement ralentie (je n’y travaille, à tout casser pas plus de deux jours par semaine — plus d’infos sur l’avancement « bientôt », c’est-à-dire quand je serai assez fier de ce que j’ai fait pour en parler). Mais, comme dirait l’autre, on n’y peut rien, c’est la vie. :)