Existe-t-il un moyen de créer un tableau primitif sans initialisation ?

Question

Comme nous le savons, Java initialise toujours les tableaux lors de leur création. C'est-à-dire new int[1000000] retourne toujours un tableau avec tous les éléments = 0. Je comprends que c'est une nécessité pour les tableaux d'objets, mais pour les tableaux primitifs (à l'exception des booléens), dans la plupart des cas, nous ne nous soucions pas des valeurs initiales.

Quelqu'un connaît-il un moyen d'éviter cette initialisation ?

Answer 1

J'ai fait quelques recherches. Il n'y a aucun moyen légal de créer un tableau non initialisé en Java. Même JNI NewXxxArray crée des tableaux initialisés. Il est donc impossible de connaître exactement le coût de la mise à zéro des tableaux. Néanmoins, j'ai fait quelques mesures :

1) Création de tableaux de 1000 octets avec des tailles de tableaux différentes

        long t0 = System.currentTimeMillis();
        for(int i = 0; i < 1000; i++) {
//          byte[] a1 = new byte[1];
            byte[] a1 = new byte[1000000];
        }
        System.out.println(System.currentTimeMillis() - t0);

Sur mon PC, il donne < 1ms pour l'octet [1] et ~500 ms pour l'octet [1000000]. Cela me semble impressionnant.

2) Nous n'avons pas de méthode rapide (native) dans le JDK pour remplir les tableaux, Arrays.fill est trop lent, alors voyons au moins combien il faut pour copier 1000 tableaux de taille 1,000,000 avec la méthode native System.arraycopy.

    byte[] a1 = new byte[1000000];
    byte[] a2 = new byte[1000000];
    for(int i = 0; i < 1000; i++) {
        System.arraycopy(a1, 0, a2, 0, 1000000);
    }

Il est de 700 ms.

Cela me donne des raisons de croire que a) la création de tableaux longs est coûteuse b) elle semble être coûteuse à cause de l'initialisation inutile.

3) Prenons sun.misc.Unsafe http://www.javasourcecode.org/html/open-source/jdk/jdk-6u23/sun/misc/Unsafe.html . Il est protégé de l'usage extérieur, mais pas trop.

    Field f = Unsafe.class.getDeclaredField("theUnsafe");
    f.setAccessible(true);
    Unsafe unsafe = (Unsafe)f.get(null);

Voici le coût du test d'allocation de mémoire

    for(int i = 0; i < 1000; i++) {
        long m = u.allocateMemory(1000000);
    }

Cela prend < 1 ms, si vous vous souvenez, pour new byte[1000000] cela a pris 500ms.

4) Unsafe n'a pas de méthodes directes pour travailler avec des tableaux. Il a besoin de connaître les champs de classe, mais la réflexion ne montre aucun champ dans un tableau. Il n'y a pas beaucoup d'informations sur les internes des tableaux, je suppose que c'est spécifique à la JVM / plateforme. Néanmoins, il s'agit, comme tout autre objet Java, d'un en-tête + des champs. Sur mon PC/JVM, cela ressemble à

header - 8 bytes
int length - 4 bytes
long bufferAddress - 8 bytes

Maintenant, en utilisant Unsafe, je vais créer byte[10], allouer un tampon mémoire de 10 octets et l'utiliser comme éléments de mon tableau :

    byte[] a = new byte[10];
    System.out.println(Arrays.toString(a));
    long mem = unsafe.allocateMemory(10);
    unsafe.putLong(a, 12, mem);
    System.out.println(Arrays.toString(a));

il imprime

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[8, 15, -114, 24, 0, 0, 0, 0, 0, 0]

Vous pouvez voir que les données du tableau ne sont pas initialisées.

Maintenant je vais changer la longueur de notre tableau (bien qu'il pointe toujours vers une mémoire de 10 octets)

    unsafe.putInt(a, 8, 1000000);
    System.out.println(a.length);

il affiche 1000000. C'était juste pour prouver que l'idée fonctionne.

Maintenant, test de performance. Je vais créer un tableau d'octets vide a1, allouer un tampon de 1000000 octets, affecter ce tampon à a1 et définir a1.length = 10000000.

    long t0 = System.currentTimeMillis();
    for(int i = 0; i < 1000; i++) {
        byte[] a1 = new byte[0];
        long mem1 = unsafe.allocateMemory(1000000);
        unsafe.putLong(a1, 12, mem);
        unsafe.putInt(a1, 8, 1000000);
    }
    System.out.println(System.currentTimeMillis() - t0);

cela prend 10ms.

5) Il y a malloc et alloc en C++, malloc alloue juste un bloc de mémoire, calloc l'initialise aussi avec des zéros.

cpp

...
JNIEXPORT void JNICALL Java_Test_malloc(JNIEnv *env, jobject obj, jint n) {
     malloc(n);
} 

java

private native static void malloc(int n);

for (int i = 0; i < 500; i++) {
    malloc(1000000);
}

résultats malloc - 78 ms ; calloc - 468 ms

Conclusions

1. Il semble que la création de tableaux Java soit lente à cause de la mise à zéro inutile des éléments.

2. Nous ne pouvons pas le changer, mais Oracle le peut. Il n'est pas nécessaire de changer quoi que ce soit dans JLS, il suffit d'ajouter des méthodes natives à java.lang.reflect.Array comme

   Public static native xxx[] newUninitialziedXxxArray(int size) ;

pour tous les types numériques primitifs (octet - double) et le type char. Il peut être utilisé partout dans le JDK, comme dans java.util.Arrays.

    public static int[] copyOf(int[] original, int newLength) {
        int[] copy = Array.newUninitializedIntArray(newLength);
        System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
        ...

ou java.lang.String

   public String concat(String str) {
        ...   
        char[] buf = Array.newUninitializedCharArray(count + otherLen);
        getChars(0, count, buf, 0);
        ...

Answer 2

Je vais déplacer cette question vers une réponse parce qu'elle devrait probablement l'être.

Un "tableau" en Java n'est pas ce que vous pensez. Ce n'est pas seulement un pointeur vers un morceau de mémoire contiguë sur la pile ou le tas.

Un tableau en Java est un objet comme tout le reste (sauf les primitives) et se trouve sur le tas. Lorsque vous appelez new int[100000] vous créez un nouvel objet comme tous les autres objets, et il est initialisé, etc.

Le JLS fournit toutes les informations spécifiques à ce sujet :

http://docs.oracle.com/javase/specs/jls/se5.0/html/arrays.html

Donc, non. Vous ne pouvez pas éviter d'"initialiser" un tableau. Ce n'est tout simplement pas comme ça que Java fonctionne. La mémoire de tas non initialisée n'existe tout simplement pas ; beaucoup de gens appellent cela une "fonctionnalité" car elle vous empêche d'accéder à la mémoire non initialisée.

Answer 3

Java 9 commence à exposer cela via jdk.internal.misc.Unsafe.allocateUninitializedArray méthode. Elle nécessiterait en fait le module JDK.Unsupported déclaration .

Answer 4

Je peux imaginer que le coût O(n) du nouveau int[n] pourrait être un fardeau dans certaines structures de données ou algorithmes.

Une façon d'avoir un coût amorti O(1) d'allocation de mémoire en Java pour un tableau primitif de taille n est de recycler les tableaux alloués avec un pool d'objets ou une autre stratégie. Le tableau recyclé peut être considéré comme "non initialisé" pour la prochaine allocation.