Archives de catĂ©gorie : Article

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 :

 

Java et les fuites mémoires

Petite sĂ©rie d’article sur les fuites mĂ©moire (memory leak) en Java :

Les outils :

  • MAT qui se base sur Eclipse, mais dispose d’un client indĂ©pendant pour ceux qui n’utilisent pas Eclipse
  • VisualVM qui se base sur Netbeans, mais dispose d’un client indĂ©pendant pour ceux qui n’utilisent pas Netbeans

Ne pas croire que parce-qu’il y a un garbage collector la gestion de la mĂ©moire doit ĂȘtre ignorĂ©e. Surtout dans un contexte d’applications web oĂč l’empilement des class-loaders rend difficile d’avoir une vision claire.