L'Optimisation De Long.bitCount

Cela semble être l'un de ces problèmes qui est tout simplement parfait pour que le GPU fonctionne. Il devrait être capable de réduire votre temps de quelques ordres de grandeur.

Sinon, je pense que vous devrez peut-être y faire face à un niveau supérieur. Avoir plusieurs threads travaillant sur différents segments de données à la fois (ce que je suis sûr que vous faites déjà), traiter les données pendant que vous les collectez, partager le travail autour de plusieurs systèmes-quelque chose comme ça.

Si votre machine a un entier ALU qui peut traiter des données plus larges que certains multiples de 64 bits (également appelés SIMD, tels que SSE2 ou VMX), vous pouvez calculer le nombre de bits sur plusieurs éléments de 64 bits à la fois.

Malheureusement, cela vous obligera à fournir des implémentations spécifiques à la machine dans un langage de niveau inférieur à Java.

Je soupçonne que votre application est liée à la mémoire plutôt qu'à la CPU, c'est-à-dire qu'elle passe plus de temps à récupérer les valeurs de la mémoire que de compter leurs bits. Dans ce cas, vous devriez essayer de réduire la taille de l'ensemble de travail ou améliorer la localité d'accès pour réduire les échecs de cache (si l'algorithme le permet).

Je ne suis pas expert en la matière, mais au cas où vous n'auriez pas vu ces pages, elles pourraient vous aider:

Http://www.reddit.com/r/programming/comments/84sht/fast_bit_couting_algorithms/

Http://www-graphics.stanford.edu/~seander/bithacks.html

Vous pouvez également fouiller dans les nombreuses bibliothèques graphiques, en particulier celles qui sont de niveau inférieur et / ou parlent directement au matériel.

EDIT: on dirait que vous pouvez utiliser le relativement nouveau introduction de L'instruction POPCNT (disponible sur certains processeurs AMD et Intel récents) pour une augmentation potentielle de la vitesse, si vous avez la possibilité d'écrire du code spécifique à la plate-forme de bas niveau, et pouvez cibler cette architecture spécifique. http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html {[4] } et un autre article avec des repères: http://www.strchr.com/crc32_popcnt

D'après ma compréhension:

J'utiliserais le 33% comme indicateur uniquement car le profilage pour les petites méthodes pourrait vraiment changer la performance globale. Donc, je voudrais exécuter l'algorithme sur un grand ensemble de données et voir le temps total. Et je considérerais les efficacités de mon optimisation en fonction de ces changements de temps totaux. J'inclurais également une phase d'avertissement afin que le JIT puisse faire ses optimisations.

En fait, le comptage des bits semble être l'un des éléments clés de votre algorithme de toute façon... si vous optimisez tout, et parvenez à obtenir 10 temps plus rapide pour tous les éléments clés, vous profilez toujours quelque chose près de 33% pour cette partie. Ce n'est pas mauvais par essence.

Inspirer de ce lien http://bmagic.sourceforge.net/bmsse2opt.html Vous pouvez essayer d'utiliser L'instruction SSE présente dans tous les processeurs intel/AMD maintenant si je me souviens bien (vous pourriez toujours failback à JAVA sinon). Une partie intéressante concernant l'article est... Que la plupart du temps, il est lié à la mémoire de toute façon. Mais je voudrais encore essayer de voir comment cela pourrait fonctionner pour vous.

Un GPU serait un ajustement parfait pour un traitement incroyablement rapide (facile cent fois l'un d'un noyau de CPU) et de la bande passante. Le problème principal serait de pousser les données vers la mémoire dédiée au processeur et d'obtenir le résultat. Mais si vous n'effectuez pas simplement le comptage des bits, mais plus d'opération, cela pourrait apporter d'énormes gains.

Il n'y a pas de raccourci de toute façon, vous devez essayer plusieurs approches et voir ce qui apporte le plus de gain. Ne comptez pas % à travers mais le temps total passé.

J'utilise maintenant cette méthode, qui entrelace quatre opérations popcnt à la fois. Il est basé sur cette implémentation C.

private static final long M0=0x5555555555555555L,
                          M1=0x3333333333333333L,
                          M2=0x0f0f0f0f0f0f0f0fL;
public void store4Tags(long tag0, long tag1, long tag2, long tag3) {
    long count0 = tag0,
         count1 = tag1,
         count2 = tag2,
         count3 = tag3;
    count0 = (count0 & M0) + ((count0 >>> 1) & M0);
    count1 = (count1 & M0) + ((count1 >>> 1) & M0);
    count2 = (count2 & M0) + ((count2 >>> 1) & M0);
    count3 = (count3 & M0) + ((count3 >>> 1) & M0);

    count0 = (count0 & M1) + ((count0 >>> 2) & M1);
    count1 = (count1 & M1) + ((count1 >>> 2) & M1);
    count2 = (count2 & M1) + ((count2 >>> 2) & M1);
    count3 = (count3 & M1) + ((count3 >>> 2) & M1);

    count0 = (count0 + (count0 >>> 4)) & M2;
    count1 = (count1 + (count1 >>> 4)) & M2;
    count2 = (count2 + (count2 >>> 4)) & M2;
    count3 = (count3 + (count3 >>> 4)) & M2;

    count0 += count0 >>> 8;
    count1 += count1 >>> 8;
    count2 += count2 >>> 8;
    count3 += count3 >>> 8;

    count0 += count0 >>> 16;
    count1 += count1 >>> 16;
    count2 += count2 >>> 16;
    count3 += count3 >>> 16;

    count0 += count0 >>> 32;
    count1 += count1 >>> 32;
    count2 += count2 >>> 32;
    count3 += count3 >>> 32;

    storeWithPopCnt(tag0, 0x3f & (int) count0);
    storeWithPopCnt(tag1, 0x3f & (int) count1);
    storeWithPopCnt(tag2, 0x3f & (int) count2);
    storeWithPopCnt(tag3, 0x3f & (int) count3);
}

Cela surpasse légèrement la version de la table de recherche et ne consomme pas de cache.

Plutôt que d'optimiser cette fonction, il est préférable d'optimiser l'utilisation de cette fonction. Par exemple, vous pourriez garder un compteur.

public void set(int n) {
   if(!get(n)) bitCount++;
   // set the bit
}
public void clear(int n) {
   if(get(n)) bitCount--;
   // clear the bit
}
public int bitCount() {
   return bitCount;
}

Cela évite d'analyser les données en gardant une trace du nombre de bits défini. Cela déplace la surcharge à quelle fréquence bits et set ou effacé et rend l'obtention du nombre de bits trivial. Il apparaît dans votre cas, le plus tard est beaucoup plus souvent.