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

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