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 :

• japex : https://japex.java.net (Licence Apache 2.0),
• jmh : http://openjdk.java.net/projects/code-tools/jmh (Licence GPL 2.0) avec un petit article d’un blog qui donne quelques explications,
• jetm : http://jetm.void.fm (Licence BSD),
• caliper : http://code.google.com/p/caliper (Licence Apache 2.0). Cela semble être un projet d’origine Google,
• d’autres à ajouter ?