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 :