C'est l'histoire d'une regex...

Si vous n'avez pas suivi le (micro-)feuilleton du moment sur Twitter, voici un résumé rapide.

Tout commence avec un tweet d'Emmanuel Lécharny :

Replacing a 5 lines method by a 140 lines one which is 15 times faster. Don't trust people who claim that less code is better.

La méthode en question est la suivante. Son but est visiblement de supprimer d'une chaîne de caractères les marqueurs de fin de ligne (\r, \n et leurs combinaisons) suivis par un espace.

protected static String unfold2( String s ){
    s = s.replaceAll( "\n\r ", "" );
    s = s.replaceAll( "\r\n ", "" );
    s = s.replaceAll( "\n ", "" );
    s = s.replaceAll( "\r ", "" );
    return s;
}

A la demande de ses followers, que le problème intéresse, Emmanuel poste son nouveau code...

Et c'est là que, naturellement, la machine s'emballe. On n'agite pas un problème sous le nez d'un développeur sans provoquer de réactions !

La solution d'Emmanuel me paraissant compliquée, je propose une alternative qui me semble plus simple. S'ensuit une vidéoconférence impromptu[1] où s'invitent plusieurs développeurs intrigués.

Nos nombreux échanges sur Twitter commencent à attirer l'attention de nos followers respectifs, et le problème gagne rapidement en audience. Pour départager les différentes implémentations, William Delanoue (@twillouer) écrit un benchmark JMH.

Pour le moment, il semblerait que ce soit la version de Cédric Champeau qui remporte la palme. Mais tous les paris sont encore ouverts !

N'hésitez pas à proposer votre solution, l'exercice est amusant et relativement simple. Et c'est pour la bonne cause, puisque ce code sera intégré à Apache Directory Server. A vos claviers !

Edit : Cédric Champeau a carrément officialisé le challenge !

Note

[1] D'où il ressort surtout que, non, le télétravail ne permet pas de s'affranchir d'un certain code vestimentaire :)


Commentaires

1. Le lundi 16 mars 2015, 16:56 par Emmanuel Lécharny

Ce qui est marrant, c'est que c'est en tombant sur cette série de regexp vers minuit que j'ai trouvé ça sale, et que je me suis amusé à pondre un truc que mon cerveau fatigué a réussi à rendre hyper compliqué. cela dit, c'était plus rapide, et c'est tout ce que je cherchais à prouver !

Là dessus, il faut reconnaître que la solution d'Olivier, déjà bien plus rapide, était super élégante : son raisonnement notamment est magnifique : "on doit chercher un espace, le reste, on s'en fout. Quand on tombe sur cet espace, on peut regarder en arrière voir si ce sont des RC ou des NL". Plus besoin d'état !

La solution de Cédric est super simple ! Et en plus, super rapide. Mais il lui a fallu au moins trois tentatives successives pour arriver à ce résultat (avec amélioration des perfs à chaque fois !)

Cela dit, sans l'intégration de JMH, on est carrément à poil : les résultats sont hyper variables d'une machine à l'autre, d'une JVM à l'autre.

Bilan : amusant, challenging, et ça prouve clairement qu'un cerveau fatigué n'est pas efficace, qu'un seul cerveau n'est pas suffisant, et que la collaboration, ça marche, et que c'est encore mieux si c'est Open Source ! Dernier point : l'émulation. C'est quand même un facteur d'amélioration très important. Ceux qui ont les chevilles qui gonflent et le melon trop important, ce n'est pas pour vous ;-)

Merci à tous !

2. Le lundi 16 mars 2015, 16:57 par Emmanuel Lécharny

PS : sur la remarque concernant la tenue vestimentaire : je me suis fait surprendre en slip chez moi...

3. Le lundi 16 mars 2015, 21:09 par Olivier Hubaut

Suis-je le seul à m'inquiéter du fait que toutes les solutions proposées se basent sur des char et que cela peut poser quelques soucis si l'on joue avec de l'unicode ou bien cela fait partie d'un implicite qui n'est pas décrit dans l'énoncé ?

4. Le lundi 16 mars 2015, 21:24 par Olivier Croisier

En mémoire, Java utilise Unicode pour représenter les caractères. Les questions d'encodage (vers ou depuis UTF-8, UTF-16, etc.) ne se posent que lorsque des données doivent être lues depuis, ou écrites vers, le monde extérieur.
Il n'y a donc aucun souci à manipuler des chars.

5. Le lundi 16 mars 2015, 22:51 par Cédric Champeau

J'ajouterais en plus que ça m'a permis de trouver des gros pbs d'optimisation dans le compilateur Groovy. Je savais que Groovy serait plus lent (à cause des accès tableaux qui ne peuvent pas se faire comme en Java), mais j'ai trouvé d'autres trucs qui étaient bien moins évidents...

6. Le mardi 17 mars 2015, 09:30 par Emmanuel Lécharny

Autre résultat intéressant : https://travis-ci.org/melix/lecharn...

Cédric a fait tourner les algos sur différentes JVM. Les résultats sont... surprenants ! On remarque juste qu'en moyenne, Java 8 est plus lent que Java 6, mais plus rapide que Java 7. En moyenne, seulement ! Il y a des cas où ce n'est pas vérifié (au détail près de la précision, comme pour les sondages...)

Reste à faire tourner cela sur différentes plates-formes (OSX, Windows, Linux).

7. Le mardi 31 mars 2015, 14:05 par Olivier Guilloux

Pour avoir déjà fait des tests de performances entre JVM, cela dépend d’énormément de paramètres surtout pour des micro-benchs comme celui-ci (La JVM Oracle a plus de 770 paramètres. Lancer java avec les options -XX:+UnlockDiagnosticVMOptions -XX:+UnlockExperimentalVMOptions -XX:+PrintFlagsFinal pour vous en convaincre)

En général, les JVM 64bit réagissent plus vite que les 32bits (car elles utilisent en standard à minima l'accélération SSE2 des CPU Intel et des registres 64bit utile notamment pour les calculs mathématique).

Je vous renvois à cet article sur le comportement de la JVM également selon la taille des méthodes (en bytecode) => http://www.technologies-ebusiness.c... et les 2 autres uivants

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.