Archives de catégorie : Java

Micro benchmark de convertisseurs de tableaux de bytes vers représentation Hexa avec Java

Contexte

Il y a quelques temps maintenant je suis tombé sur une offre d’emploi de la société ARCA Computing. Cette annonce est intéressante dans sa présentation, car pour pouvoir candidater il fallait résoudre une petite énigme qui consistait à récupérer un projet hébergé sur github, l’exécuter en remplissant quelques trous pour obtenir le contenu de l’annonce depuis le site web d’ARCA.

Bon, j’avoue, j’ai triché car j’ai juste récupéré le bout de code intéressant pour obtenir l’url, mis cela dans mon IDE pour obtenir le lien que j’ai ouvert directement dans un navigateur. Mais bref, là n’est pas le sujet…

Ce qui a piqué ma curiosité, c’est la méthode convertToHex du petit exercice. J’avais souvenir d’avoir déjà utilisé ce genre de méthode, mais pas avec cette implémentation. Je me suis donc demandé si elle était plus intéressante que d’autres qu’on peut trouver ici et là. Après une petite recherche, je suis tombé sur un message de Stack Overflow qui proposait plusieurs implémentations : http://stackoverflow.com/questions/9655181/convert-from-byte-array-to-hex-string-in-java. Cela permettait d’avoir une bonne liste pour faire un petit comparatif à l’arrache.

Le principe est simple :

  • Je fixe une limite de temps d’exécution : EXCLUSION_DELAY (en ms).
  • J’itère sur les convertisseurs en les exécutants LOOPS fois sur une chaine d’entrée qui augmente à chaque itération. La chaine d’entrée est construite par répétition d’une chaine de base autant de fois que le numéro d’itération courante.
  • Lorsqu’un convertisseur dépasse EXCLUSION_DELAY ms pour réaliser ses LOOPS conversions sur la chaine d’entrée, alors il est exclu de la suite du test et j’enregistre le numéro d’itération où il a échoué.
  • Quand tous les convertisseurs sont finalement exclus, le test est terminé. J’affiche donc le résultat c’est à dire le numéro d’itération correspondant à l’exclusion du convertisseur.

Ci-dessous les différentes implémentations que j’ai collectées. J’ai tout placé dans une seule classe pour te faciliter la vie lecteur : si tu veux reproduire, pas besoin de télécharger une archive et tout le bataclan. Créer une nouvelle classe et copier/coller le code qui suit te permettra de tester rapidement et simplement de ton côté. Le “Converter 0” est l’implémentation extraite du code de l’annonce. Les “Converter 1“, “Converter 2“, “Converter 3“, “Converter 5“, “Converter 6“, “Converter 7” (il s’agit d’une légère variante du 6 qui n’apporte rien, j’aurai dû le supprimer),  et “Converter 8” sont extraits de l’article de Stack Overflow ou des articles pointés. Le “Converter 4” est un mélange que j’ai réalisé entre les “Converter 3” et “Converter 5

Le code

package net.ozim;

import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author <a href="mailto:dev@arliguy.net">Bruno ARLIGUY</a>
 */
public class HexaString {

    private interface Converter
    {
        public String execute(final byte[] data);
        public String getName();

        public boolean isExcluded();
        public boolean excluded();
    }

    private static abstract class AbstractConverter implements Converter {
        private int _count = 0;

        @Override
        public boolean isExcluded() {
            return _count > 2;
        }

        @Override
        public boolean excluded() {
            _count ++;

            return this.isExcluded();
        }
    }

    private static class Converter0 extends AbstractConverter {
        @Override
        public final String execute(final byte[] data) {
            final StringBuilder sb = new StringBuilder(2 * data.length);
            for (int i = 0; i < data.length; i++) {
                int halfbyte = (data[i] >>> 4) & 0x0F;
                int two_halfs = 0;
                do {
                    if ((0 <= halfbyte) && (halfbyte <= 9)) {
                        sb.append((char) ('0' + halfbyte));
                    }
                    else {
                        sb.append((char) ('a' + (halfbyte - 10)));
                    }
                    halfbyte = data[i] & 0x0F;
                } while (two_halfs++ < 1);
            }
            return sb.toString();
        }

        @Override
        public final String getName() {
            return "Converter 0";
        }
    }

    private static class Converter1 extends AbstractConverter {
        @Override
        public final String execute(final byte[] data) {
            final StringBuilder sb = new StringBuilder(2 * data.length);
            for(byte b: data) {
                sb.append(String.format("%02x", b&0xff));
            }
            return sb.toString();
        }

        @Override
        public final String getName() {
            return "Converter 1";
        }
    }

    private static class Converter2 extends AbstractConverter {
        @Override
        public final String execute(final byte[] data) {
            final StringBuilder sb = new StringBuilder(2 * data.length);
            for(byte b: data) {
                sb.append(Integer.toString( ( b & 0xff ) + 0x100, 16).substring( 1 ));
            }

            return sb.toString();
        }

        @Override
        public final String getName() {
            return "Converter 2";
        }
    }

    private static class Converter3 extends AbstractConverter {
        private static final String _chars = "0123456789abcdef";

        @Override
        public final String execute(final byte[] data) {
            final StringBuilder sb = new StringBuilder(2 * data.length);
            for (final byte b : data) {
                sb.append(_chars.charAt((b & 0xF0) >>> 4)).append(_chars.charAt((b & 0x0F)));
            }
            return sb.toString();
        }

        @Override
        public final String getName() {
            return "Converter 3";
        }
    }

    /**
     * Un mélange du converter3 et converter5
     */
    private static class Converter4 extends AbstractConverter {
        private static final String _chars = "0123456789abcdef";

        @Override
        public final String execute(final byte[] data) {
            final char[] result = new char[2 * data.length];
            int index = 0;

            for (final byte b : data) {
              result[index++] = _chars.charAt((b & 0xF0) >>> 4);
              result[index++] = _chars.charAt((b & 0x0F));
            }
            return new String(result);
        }

        @Override
        public final String getName() {
            return "Converter 4";
        }
    }

    private static class Converter5 extends AbstractConverter {
        private static final byte[] _chars = {
            (byte)'0', (byte)'1', (byte)'2', (byte)'3',
            (byte)'4', (byte)'5', (byte)'6', (byte)'7',
            (byte)'8', (byte)'9', (byte)'a', (byte)'b',
            (byte)'c', (byte)'d', (byte)'e', (byte)'f'
        };

        @Override
        public final String execute(final byte[] data) {
            final byte[] hex = new byte[2 * data.length];
            int index = 0;

            for (byte b : data) {
              final int v = b & 0xFF;
              hex[index++] = _chars[v >>> 4];
              hex[index++] = _chars[v & 0xF];
            }
            return new String(hex, StandardCharsets.US_ASCII);
        }

        @Override
        public final String getName() {
            return "Converter 5";
        }
    }

    private static class Converter6 extends AbstractConverter {
        private static final char[] _chars = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};

        @Override
        public final String execute(final byte[] data) {
            final char[] hexChars = new char[data.length * 2];
            int v;
            for (int j = 0; j < data.length; j++) {
                v = data[j] & 0xFF;
                hexChars[j * 2] = _chars[v >>> 4];
                hexChars[j * 2 + 1] = _chars[v & 0x0F];
            }
            return new String(hexChars);
        }

        @Override
        public final String getName() {
            return "Converter 6";
        }
    }

    private static class Converter7 extends AbstractConverter {
        private static final String _chars = "0123456789abcdef";

        @Override
        public final String execute(final byte[] data) {
            final char[] hexChars = new char[data.length * 2];
            int v;
            for (int j = 0; j < data.length; j++) {
                v = data[j] & 0xFF;
                hexChars[j * 2] = _chars.charAt(v >>> 4);
                hexChars[j * 2 + 1] = _chars.charAt(v & 0x0F);
            }
            return new String(hexChars);
        }

        @Override
        public final String getName() {
            return "Converter 7";
        }
    }

    /**
     * Note : Using this will remove the leading zeros
     */
    private static class Converter8 extends AbstractConverter {
        @Override
        public final String execute(final byte[] data) {
            return new BigInteger(1, data).toString(16);
        }

        @Override
        public final String getName() {
            return "Converter 8";
        }
    }

    private static class ExclusionStep {
        private final Converter _converter;
        private final int       _step;

        public ExclusionStep(final Converter converter, final int step) {
            _converter = converter;
            _step = step;
        }

        @Override
        public String toString() {
            return String.format("%s at step %4d", _converter.getName(), _step);
        }
    }

    private static long doTest(final Converter c, final byte[] data, final int loops) {
        final long start = System.currentTimeMillis();

        for (int i = loops; i > 0; i--) {
            c.execute(data);
        }

        final long stop = System.currentTimeMillis();

        return (stop - start);
    }

    private final static int LOOPS = 40_000;
    private final static int EXCLUSION_DELAY = 300;

    public static void main(final String[] args) throws NoSuchAlgorithmException {
        final String base = "€€ ma base à mettre en hex string… ";
        final List<Converter> converters = new ArrayList<>();

        converters.add(new Converter0());
        converters.add(new Converter1());
        converters.add(new Converter2());
        converters.add(new Converter3());
        converters.add(new Converter4());
        converters.add(new Converter5());
        converters.add(new Converter6());
        converters.add(new Converter7());
        converters.add(new Converter8());

        final byte[] validation = base.getBytes(StandardCharsets.UTF_8);

        for (Converter c : converters) {
            System.out.println(String.format("validation %s : %s", c.getName(), c.execute(validation)));
        }

        //warmup
        for (Converter c : converters) {
            doTest(c, validation, LOOPS);
        }

        boolean stop;
        int count = 0;
        final List<ExclusionStep> exclusions = new ArrayList<>();
        do {
            //create content to convert, longer at each loop
            final String current = new String(new char[++count]).replace("\0", base);
            final byte[] data = current.getBytes(StandardCharsets.UTF_8);

            System.out.println(String.format("step %d", count));

            int countExcluded = 0;
            for (Converter c : converters) {
                if (c.isExcluded()) {
                    countExcluded ++;
                }
                else {
                    final long duration = doTest(c, data, LOOPS);
                    if (duration > EXCLUSION_DELAY && c.excluded()) {
                        exclusions.add(new ExclusionStep(c, count));
                        System.out.println(String.format("Excluding %s", c.getName()));
                    }
                }
            }

            stop = countExcluded == converters.size();

        } while (! stop);

        for (ExclusionStep exclusion : exclusions) {
            System.out.println(exclusion.toString());
        }
    }
}

Le résultat

Voici ce que j’obtiens sur ma machine :

Converter 1 at step    3
Converter 8 at step    5
Converter 2 at step    6
Converter 3 at step   39
Converter 0 at step   42
Converter 5 at step   78
Converter 4 at step  111
Converter 7 at step  112
Converter 6 at step  113

NB : Attention, cela ne représente que le résultat d’une exécution sur ma machine, il n’est pas garanti qu’ailleurs le résultat soit identique.

Il ressort donc que le “Converter 0” est pile-poile au milieu de la liste. Que le “Converter 4” que j’ai fait en mixant le 3 et le 5 se comporte bien mieux qu’eux et qu’il égale même le plus rapide qui est le “Converter 6” (le 7 étant une variante inutile).

Que conclure de ce petit test ? Que si vous avez besoin de faire plus de 40 000 conversions de tableaux de bytes en représentation hexa en moins de 300 ms sur de gros tableaux de bytes, alors il faut faire attention à l’algo utilisé. Sinon … Il y a peut être une meilleure façon de passer le temps :)

Et je me dis maintenant qu’il faudrait vraiment que j’essaye un framework de micro-benchmarks réalisé par des gens plus compétents que moi pour voir ce que cela donne. J’ai noté comme outils :

 

Projet découverte IP, v1.a

Petites nouvelles sur l’avancement.

J’ai rapidement mis en ligne ce que j’appelle la version 1.a. Il est donc maintenant possible de trouver et d’afficher son adresse IP via ipso.me.

J’ai mis à disposition le code source du projet sur Kenai.com (en). Leur service est vraiment clair et pratique. J’ai ouvert un dépôt Mercurial : http://kenai.com/projects/ipsome/sources/hg/show (en). Je découvre l’utilisation d’un gestionnaire de code décentralisé, je ne suis pas encore 100% à l’aise avec car cela change de SVN, mais c’est assez pratique. Il faudra qu’un jour je prenne le temps de lire Subversion Re-education (en).

Pour l’instant le code est vraiment minimaliste, il y a juste un contrôleur qui récupère l’IP du client et la passe à une vue. Mes premières impressions sur l’utilisation de Play! Framework (en) sont très bonnes. C’est vraiment très simple à mettre en place, très simple pour commencer, le tutoriel de départ est bon. J’ai d’ailleurs fait cette version 1.a directement en suivant le tutoriel “Première application (en)” .

Pour le style, j’ai récupéré un template que j’ai déjà utilisé par ailleurs, il a l’avantage d’utiliser le framework CSS 1140 CSS Grid (en) qui permet de s’adapter à la largeur de l’écran. Le rendu s’adapte jusqu’aux résolutions des smartphones.

Ce qu’il me reste à faire pour avoir une vrai version 1 :

  • Intégrer la licence Apache au projet,
  • Faire une petite doc pour l’installation :
    • en texte dans un fichier install.txt,
    • en html intégré dans une page du projet
  • Nettoyer le code et le template utilisé

Installation de Tomcat et variable d’environment BASEDIR

Si vous installez Tomcat sur un GNU/Linux depuis une archive binaire récupérée d’Apache et lancez tomcat via “./startup.sh” vous risquez d’avoir le message suivant :

The BASEDIR environment variable is not defined correctly
This environment variable is needed to run this program

Pour éviter cela, il faut d’abord vérifier que “JAVA_HOME” et “CATALINA_HOME” soeint bien définis comme cela est spécifié dans le fichier “RUNNING.txt” livré avec l’archive de Tomcat.

Ensuite il faut surtout vérifier que les fichiers “bin/startup.sh” “bin/shutdown.sh” et “bin/setclasspath.sh” soient bien exécutables. Quelque chose du genre :

chmod +x bin/startup.sh
chmod +x bin/shutdown.sh
chmod +x bin/setclasspath.sh

Après cela Tomcat devrait s’exécuter via “./startup.sh“.

Projet découverte IP

Version 0

Le nom

J’ai trouvé un nom qui va avec un domaine disponible : ipso.me. Bon, maintenant, bien entendu le domaine n’est plus disponible. Pourquoi ipso ? Car c’est court, le domaine en .me est libre. Il contient IP qui fait bien référence à l’adresse IP qu’on veut arriver à déterminer. Le so peut faire référence à « solve » ou « solution ».

IP + SOlve = ipso. Le “.me” indiquant qu’il s’agit de résoudre mon adresse ip.

Ça me parait bien. Le projet sera donc nommé « ipso.me » et ce sera à la fois le nom du projet et du domaine.

La forge

Pour la forge, j’ai envie de tester le système de gestion de version Mercurial. Je m’oriente donc vers la plateforme Kenai qui est très bien intégrée à Netbeans, l’IDE que j’utilise couramment. Depuis le rachat de Sun par Oracle, il était question que Kenai disparaisse pour laisser la place à java.net qui utilise maintenant la plateforme Kenai. Mais il semble que les deux sont actifs en simultanés. Donc on verra, il sera toujours temps de changer. Les autres choix possibles pour Mercurial sont :

Projet découverte IP

But du projet

Construire une application web permettant d’afficher l’adresse IP des visiteurs. Afficher le maximum d’informations sur :

  • utilisation d’un proxy,
  • localisation,
  • IP dynamique ou statique

Ce projet sera développé de façon itérative et doit me permettre de tester diverses technologies. Le code sera en Java et open-source sous licence Apache 2.0.

Prévision de versions

  • Version 0 :
    • Trouver un nom au projet,
    • Trouver un nom de domaine pour l’installation publique,
    • Trouver une forge où publier l’application
  • Version 1 :
    • Afficher l’adresse IP du visiteur,
    • Mettre en ligne l’application,
    • Publier le code sur la forge choisie
  • Version 1.1 :
    • Afficher les informations sur l’utilisation de proxy
  • Version 1.2 :
    • Afficher les informations de localisation de l’IP via une base de localisation
  • Version 1.3 :
    • Permettre à l’utilisateur de tracer ses changements d’adresse via un cookie, ainsi depuis un même poste, il pourra déterminer si il a une adresse IP dynamique.
  • Version 1.4 :
    • Si l’utilisateur le permet et si son navigateur le supporte, demander la localisation de l’utilisateur.
  • Version 2.0 :
    • Permettre à l’utilisateur d’avoir un compte sur l’application, proposer plusieurs systèmes d’authentification :
      • Système interne au site,
      • OpenID
      • Facebook
      • Google
    • Avoir un compte permet de :
      • Avoir un historique de ses IP, localisations
      • Supprimer son compte et ainsi effacer toutes les données
    • La collecte d’information va nécessiter une déclaration à la CNIL

Outils utilisés

  • Essayer Java 7, une pré-version est disponible.
  • Utiliser le framework d’application web “Play!“.

Bien entendu, aucune garantie de résultat, juste du best effort