Benchmarking Java – Tableaux contre Vecteurs

Java fait partie de ces langages de programmation qui offrent beaucoup d’outils d’aide au développement sensés faciliter et améliorer nos productions. Cependant, certains d’entre eux sont parfois utilisés de manière contre-productive.

Les Vecteurs

Un « vecteur » désigne un ensemble d’éléments stockés de manière contigüe les uns à la suite des autres. On appelle également les vecteurs des « tableaux ». Les tableaux sont des types primitifs des langages de programmation et n’offrent souvent en eux-mêmes que peu d’outils aidant à leur gestion. Il faut en général passer par des fonctions spécifiques.

Java intègre une autre approche en proposant des classes utilitaires (dans le package java.util) dont la classe Vector qui reproduit l’illusion d’un vecteur en ajoutant tout en tas de fonctionnalités améliorées (réallocation dynamique de la taille du tableau, insertion en milieu de tableau, …).

Mais comme nous allons le voir, tout cela a un coût.

Le test

Pour évaluer les performances des Vector Java contre les tableaux primitifs du langage, je procède à l’addition des 100 000 premiers entiers (0 inclus) et ce 10 000 fois successives.

Les résultats sont sans appel :

Entiers directs - Compteur classique :
======================================
Somme obtenue : 4999950000
Durée totale : 339 ms
Durée moyenne d'une itération : 0,033900 ms

Entiers directs - Boucle Java :
======================================
Somme obtenue : 4999950000
Durée totale : 601 ms
Durée moyenne d'une itération : 0,060100 ms

Vecteur - Compteur classique :
======================================
Somme obtenue : 4999950000
Durée totale : 41245 ms
Durée moyenne d'une itération : 4,124500 ms

Vecteur - Itérateur :
======================================
Somme obtenue : 4999950000
Durée totale : 41500 ms
Durée moyenne d'une itération : 4,150000 ms

Vecteur - Boucle Java :
======================================
Somme obtenue : 4999950000
Durée totale : 41874 ms
Durée moyenne d'une itération : 4,187400 ms

Les Vector sont jusqu’à 122 fois plus lents que les tableaux primitifs.

Mais pourquoi ?

Les tableaux primitifs sont capables de stocker l’ensemble des types proposés par Java, des entiers primitifs aux Object. On accède donc directement à l’élément primitif sans conversion de type et sans appel de fonction superflu.

En revanche, les classes génériques comme Vector n’acceptent que des Object ou leurs dérivés (dans notre cas, des objets de la classe Integer). Notre addition provoque donc des allocations d’objets et des conversions vers les types primitifs du langage qui sont très coûteux en temps, et cela réduit donc considérablement les performances.

Mais cela n’est pas tout, la classe Vector effectue tout un tas de vérification lors de l’accès aux éléments et c’est cette étape qui est très gourmande en ressource de calcul. En effet, en reproduisant le test dans notre tableau en remplaçant des entiers primitifs par des objets Integer, les Vector sont toujours 30 fois plus lents.

Conclusion

  • Si votre programme nécessite des performances très élevées, privilégiez des tableaux classiques
  • Si votre programme nécessite des variations fréquentes dans la taille du tableau alloué, envisagez éventuellement des Vector si la première règle n’est pas contredite.

Code du test

import java.util.Iterator;
import java.util.Vector;

public class Benchmark {

    public static final int NB_INTS = 100000;
    public static final int NB_PASS = 10000;
    
    public static void main(String[] args) {
        int[] directInts = new int[NB_INTS];
        Vector<Integer> intVector = new Vector<Integer>(NB_INTS);
        
        // Remplissage
        for (int i = 0; i < NB_INTS; i++) {
            directInts[i] = i;
            intVector.add(i);
        }
        
        // Parcours du tableau en utilisant un compteur classique
        long start = System.currentTimeMillis();
        long sum = 0;
        for (int i = 0; i < NB_PASS; i++) {
            sum = 0;
            for (int c = 0; c < directInts.length; c++)
                sum += directInts[c];
        }
        long elapsed = System.currentTimeMillis() - start;
        
        System.out.println("Entiers directs - Compteur classique :");
        System.out.println("======================================");
        System.out.format("Somme obtenue : %d\n", sum);
        System.out.format("Durée totale : %d ms\n", elapsed);
        System.out.format("Durée moyenne d'une itération : %f ms\n", (double) (elapsed / (double) NB_PASS));
        System.out.println("");
        
        // Parcours du tableau en utilisant la boucle Java
        start = System.currentTimeMillis();
        sum = 0;
        for (int i = 0; i < NB_PASS; i++) {
            sum = 0;
            for (int c : directInts)
                sum += c;
        }
        elapsed = System.currentTimeMillis() - start;
        
        System.out.println("Entiers directs - Boucle Java :");
        System.out.println("======================================");
        System.out.format("Somme obtenue : %d\n", sum);
        System.out.format("Durée totale : %d ms\n", elapsed);
        System.out.format("Durée moyenne d'une itération : %f ms\n", (double) (elapsed / (double) NB_PASS));
        System.out.println("");
        
        // Parcours du vecteur en utilisant un compteur classique
        start = System.currentTimeMillis();
        sum = 0;
        for (int i = 0; i < NB_PASS; i++) {
            sum = 0;
            for (int c = 0; c < intVector.size(); c++)
                sum += intVector.elementAt(c);
        }
        elapsed = System.currentTimeMillis() - start;
        
        System.out.println("Vecteur - Compteur classique :");
        System.out.println("======================================");
        System.out.format("Somme obtenue : %d\n", sum);
        System.out.format("Durée totale : %d ms\n", elapsed);
        System.out.format("Durée moyenne d'une itération : %f ms\n", (double) (elapsed / (double) NB_PASS));
        System.out.println("");
        
        // Parcours du vecteur en utilisant un itérateur
        start = System.currentTimeMillis();
        sum = 0;
        for (int i = 0; i < NB_PASS; i++) {
            sum = 0;
            Iterator<Integer> it = intVector.iterator(); 
            while (it.hasNext())
                sum += it.next();
        }
        elapsed = System.currentTimeMillis() - start;
        
        System.out.println("Vecteur - Itérateur :");
        System.out.println("======================================");
        System.out.format("Somme obtenue : %d\n", sum);
        System.out.format("Durée totale : %d ms\n", elapsed);
        System.out.format("Durée moyenne d'une itération : %f ms\n", (double) (elapsed / (double) NB_PASS));
        System.out.println("");
        
        // Parcours du vecteur en utilisant une boucle Java
        start = System.currentTimeMillis();
        sum = 0;
        for (int i = 0; i < NB_PASS; i++) {
            sum = 0;
            for (int c : intVector)
                sum += c;
        }
        elapsed = System.currentTimeMillis() - start;
        
        System.out.println("Vecteur - Boucle Java :");
        System.out.println("======================================");
        System.out.format("Somme obtenue : %d\n", sum);
        System.out.format("Durée totale : %d ms\n", elapsed);
        System.out.format("Durée moyenne d'une itération : %f ms\n", (double) (elapsed / (double) NB_PASS));
        System.out.println("");
    }

}
Publicités

Test de performances Java

Afin de valider une approche de développement pour un projet personnel, j’ai réalisé un petit test de performances en Java. Le but était de savoir quel mécanisme serait le plus rapide pour différencier des signaux d’événements. Les challengers étaient instanceof et le polymorphisme, les chaînes de caratères et les enums.

Le procédure utilisée est la suivante :

  • Remplir aléatoirement un tableau pour chaque mécanisme tout en gardant le même ordre des éléments pour tous les mécanismes
  • Tester successivement le parcours intégral de chaque tableau et évaluer la durée

Voilà les résultats du test :

Instances :
    A: 500537 - B: 500534 - C: 499560 - D: 499369 - Temps: 32
Strings (avec equals) :
    A: 500537 - B: 500534 - C: 499560 - D: 499369 - Temps: 58
Strings (avec ==) :
    A: 500537 - B: 500534 - C: 499560 - D: 499369 - Temps: 27
Enums (avec ==) :
    A: 500537 - B: 500534 - C: 499560 - D: 499369 - Temps: 26
Enums (switch) :
    A: 500537 - B: 500534 - C: 499560 - D: 499369 - Temps: 34

Les grands gagnants sont donc les enums et les chaînes de caractères évalués grâce à l’opérateur == .

Voici le code source utilisé pour le test :

import java.util.Random;

public class Test {
    public static class A { }
    public static class B { }
    public static class C { }
    public static class D { }

    public static int count = 2000000;

    public static enum TestEnum { A, B, C, D };

    public static void main(String[] args) {
        Random rng = new Random();

        Class<?>[] classValues = { A.class, B.class, C.class, D.class };
        Object[] instances = new Object[count];

        String aStr = "AAA";
        String bStr = "BBBBBB";
        String cStr = "CCCCCCCCC";
        String dStr = "DDDDDDDDDDDD";
        String[] stringValues = { "AAA", "BBBBBB", "CCCCCCCCC", "DDDDDDDDDDDD" };
        String[] strings = new String[count];

        TestEnum[] enumValues = { TestEnum.A, TestEnum.B, TestEnum.C, TestEnum.D };
        TestEnum[] enumRefs = new TestEnum[count];

        for (int i = 0; i < count; i++)
        {
            int rand = rng.nextInt(4);

            Class<?> c = classValues[rand];
            try {
                instances[i] = c.newInstance();
            } catch (Exception e) {
                e.printStackTrace();
            }

            strings[i] = stringValues[rand];
            enumRefs[i] = enumValues[rand];
        }

        int a = 0, b = 0, c = 0, d = 0;
        long start = System.currentTimeMillis();
        for (Object o : instances)
        {
            if (o instanceof A)
                a++;
            else if (o instanceof B)
                b++;
            else if (o instanceof C)
                c++;
            else if (o instanceof D)
                d++;
         }
         long elapsed = System.currentTimeMillis() - start;

         System.out.println("Instances :");
         System.out.println(String.format("\tA: %d - B: %d - C: %d - D: %d - Temps: %d", a, b, c, d, elapsed));
         System.out.println();

         a = b = c = d = 0;
         start = System.currentTimeMillis();
         for (String s : strings)
         {
             if (s.equals(aStr))
                 a++;
             else if (s.equals(bStr))
                 b++;
             else if (s.equals(cStr))
                 c++;
             else if (s.equals(dStr))
                 d++;
         }
        elapsed = System.currentTimeMillis() - start;

        System.out.println("Strings (avec equals) :");
        System.out.println(String.format("\tA: %d - B: %d - C: %d - D: %d - Temps: %d", a, b, c, d, elapsed));
        System.out.println();

        a = b = c = d = 0;
        start = System.currentTimeMillis();
        for (String s : strings)
        {
            if (s == aStr)
                a++;
            else if (s == bStr)
                b++;
            else if (s == cStr)
                c++;
            else if (s == dStr)
                d++;
         }
         elapsed = System.currentTimeMillis() - start;

         System.out.println("Strings (avec ==) :");
         System.out.println(String.format("\tA: %d - B: %d - C: %d - D: %d - Temps: %d", a, b, c, d, elapsed));
         System.out.println();

         a = b = c = d = 0;
         start = System.currentTimeMillis();
         for (TestEnum e : enumRefs)
         {
             if (e == TestEnum.A)
                 a++;
             else if (e == TestEnum.B)
                 b++;
             else if (e == TestEnum.C)
                 c++;
             else if (e == TestEnum.D)
                 d++;
         }
         elapsed = System.currentTimeMillis() - start;

         System.out.println("Enums (avec ==) :");
         System.out.println(String.format("\tA: %d - B: %d - C: %d - D: %d - Temps: %d", a, b, c, d, elapsed));
         System.out.println();

         a = b = c = d = 0;
         start = System.currentTimeMillis();
         for (TestEnum e : enumRefs)
         {
             switch (e) {
                 case A:
                     a++;
                     break;
                 case B:
                     b++;
                     break;
                 case C:
                     c++;
                     break;
                 case D:
                     d++;
                     break;
             }
         }
         elapsed = System.currentTimeMillis() - start;

         System.out.println("Enums (switch) :");
         System.out.println(String.format("\tA: %d - B: %d - C: %d - D: %d - Temps: %d", a, b, c, d, elapsed));
         System.out.println();
    }
}