Question

J'ai un programme qui fait un grand nombre d'appels à Long.bitCount (), tant qu'il prend 33% des cycles sur un noyau CPU. Est-il un moyen de mettre en œuvre qui est plus rapide que la version Sun JDK?

J'ai essayé:

  • Cette algorithme (je pense que c'est exactement comment la implémente) JDK
  • tables de consultation de diverses tailles comprises entre 2 8 et 2 22 (en regardant quelques bits à la fois et en ajoutant les résultats)

Mais je ne pouvais pas faire mieux qu'un 2 16 -entrée recherche table avec une boucle manuellement déroulée (environ CPU de 27%.)
Sinon, comment cela pourrait-il être optimisé pour Java?

Remarque : cette question est sur l'optimisation spécifique à Java, mais cette similaire (langue-agnostique) question a beaucoup d'autres algorithmes.

Était-ce utile?

La solution

Si vous êtes sur un processeur récent x86 il y a une instruction pour cela, POPCNT.

Dans les versions récentes de Java, Long.bitCount () utilise cette instruction. Il suffit d'utiliser -XX: + UsePopCountInstruction (valeur par défaut dans les versions récentes)

Cependant, il y a quelques bugs avec elle dans 6.0_u18 par 7.0_u5 JRE: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

Autres conseils

Cela semble être l'un de ces problèmes est tout simplement parfait pour le GPU à travailler. Il devrait être en mesure de réduire votre temps par un ordre de grandeur couple.

Sinon, je pense que vous pourriez avoir à traiter à un niveau supérieur. Plusieurs threads travaillant sur différents segments de données à la fois (que je suis sûr que vous faites déjà), le traitement des données pendant que vous collectez, la 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 connu sous le nom SIMD, comme SSE2 ou VMX), vous pouvez calculer les bits compte sur plusieurs éléments 64 bits à la fois.

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

Je suppose que votre application est la mémoire liée plutôt que liée CPU, à savoir qu'il passe plus de temps aller chercher les valeurs de la mémoire que de compter leurs bits. Dans ce cas, vous devriez essayer de réduire la taille du jeu de travail ou d'améliorer la localité d'accès pour réduire misses cache (si l'algorithme permet).

Je ne suis pas expert en la matière, mais au cas où vous ne l'ai pas vu ces pages, ils peuvent 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 les nombreuses bibliothèques graphiques là-bas, en particulier ceux qui sont de niveau inférieur et / ou de parler directement au matériel.

EDIT: Il semble que vous pouvez utiliser l'instruction POPCNT relativement nouvellement introduit (disponible sur certains processeurs récents AMD et Intel) pour une augmentation de la vitesse potentielle, si vous avez la possibilité de code spécifique à la plate-forme d'écriture de bas niveau, et peut cibler que l'architecture spécifique. http://kent-vandervelden.blogspot.com /2009/10/counting-bits-population-count-and.html et un autre article avec des critères: http : //www.strchr.com/crc32_popcnt

De ma compréhension:

J'utiliserait 33% comme indicateur que le profilage des petites méthodes pourrait vraiment changer la performance globale. Donc, je courrais l'algorithme sur un certain grand ensemble de données et voir le temps total. Et je considérerais les efficiancies de mon optimisation basée sur que les changements de temps total. Je comprend également un avertissement en phase de sorte que le JIT peut faire Optimisations est tout.

En fait, la chose de comptage de bits semble être l'un des éléments clés de votre algorithme quand même ... si vous optimisez tout, et réussi à obtenir 10 fois plus rapide pour tous les éléments clés, vous profil encore quelque chose près de 33% pour cette partie. Ce n'est pas mauvaise par essence.

Authentiques de ce lien http://bmagic.sourceforge.net/bmsse2opt.html pourrait essayer d'utiliser d'instructions SSE présente dans l'ensemble processeur Intel / AMD maintenant, si je me souviens bien (vous pouvez alway failback à JAVA autrement). Une partie interressant en ce qui concerne l'article est ... Que la plupart du temps, il est lié mémoire de toute façon. Mais je voudrais essayer encore de voir comment cela pourrait fonctionner pour vous.

Un GPU serait un ajustement parfait pour le traitement incroyablement rapide (facile une centaine de temps d'un noyau CPU) et la bande passante. Le principal problème serait de pousser des données à la CPU mémoire dédiée et revenir résultat. Mais si vous ne vous contentez pas d'effectuer le comptage des bits, mais plus une opération plus, cela pourrait apporter des gains énormes.

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

Je suis maintenant en utilisant cette méthode, qui entrelace quatre opérations de 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);
}

Cette surclasse la version de table de recherche un peu, et ne consomme pas le cache.

Plutôt que d'optimiser cette fonction, vous êtes susceptible d'être mieux optimiser l'utilisation de cette fonction. Par exemple. vous pouvez 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;
}

On évite ainsi le balayage des données en gardant la trace du nombre du nombre de bits fixés. Cela déplace le plafond à la fréquence de bits et fixe ou effacé et fait d'obtenir le nombre de bits mis trivial. Il apparaît dans votre cas d'utilisation, le plus tard est beaucoup plus souvent.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top