Ottimizzazione Long.bitCount

StackOverflow https://stackoverflow.com/questions/4839128

Domanda

Ho un programma che sta compiendo un enorme numero di chiamate al Long.bitCount (), così tanti che sta prendendo 33% dei cicli su un core CPU. C'è un modo per la sua attuazione che è più veloce rispetto alla versione Sun JDK?

ho provato:

  • Questo algoritmo (credo che questo sia esattamente come il JDK implementa it)
  • tabelle di ricerca di varie dimensioni tra 2 8 e 2 22 (guardando alcuni bit alla volta e sommando i risultati)

Ma non ho potuto fare meglio di un 16 -entry ricerca tabella 2 con un ciclo manualmente srotolato (circa il 27% della CPU.)
Come altro potrebbe questo essere ottimizzato per Java?

Nota : questa domanda è di ottimizzazione Java-specifici, ma questo simile domanda (indipendente dal linguaggio) ha molti altri algoritmi.

È stato utile?

Soluzione

Se siete su un recente CPU x86 v'è un'istruzione per questo, POPCNT.

Nelle recenti versioni di Java, Long.bitCount () utilizza questa istruzione. Basta usare -XX: + UsePopCountInstruction (questa è l'impostazione predefinita nelle versioni più recenti)

Tuttavia, ci sono alcuni bug con esso in JRE 6.0_u18 attraverso 7.0_u5: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

Altri suggerimenti

Questo mi sembra uno di quei problemi che è semplicemente perfetta per la GPU su cui lavorare. Dovrebbe essere in grado di ridurre drasticamente il tempo per un paio di ordini di grandezza.

In caso contrario, penso che si potrebbe avere a che fare con esso a un livello superiore. Avendo più thread che lavorano su diversi segmenti di dati alla volta (che sono sicuro che già lo fanno), l'elaborazione dei dati, mentre si stanno raccogliendo esso, condividendo il lavoro intorno più sistemi -. Qualcosa di simile

Se macchina è un numero intero ALU in grado di elaborare i dati di larghezza superiore alcuni multipli di 64 bit (noto anche come SIMD, come SSE2 o VMX), è possibile calcolare i conteggi bit su diversi elementi a 64 bit alla volta.

Purtroppo, questo richiederà di fornire implementazioni di macchine specifiche in un linguaggio di livello inferiore rispetto a Java.

ho il sospetto che la vostra applicazione è la memoria-bound piuttosto che CPU-bound, vale a dire si passa più tempo il recupero dei valori dalla memoria che contare i bit. In tal caso si dovrebbe cercare di ridurre la dimensione del set di lavoro o di migliorare l'accesso località di ridurre cache miss (se l'algoritmo lo permette).

Non sono un esperto in materia, ma nel caso in cui non ho visto queste pagine, che possono aiutare:

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

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

Si potrebbe anche voler cercare un po 'le librerie grafiche molti là fuori, in particolare quelli che sono di livello inferiore e / o parlare direttamente con l'hardware.

EDIT: Sembra che è possibile utilizzare l'istruzione POPCNT relativamente recente introduzione (disponibile su alcuni recenti processori AMD e Intel) per un aumento del potenziale di velocità, se avete la possibilità di scrittura a basso livello di codice specifico per la piattaforma, e possono indirizzare che specifica architettura. http://kent-vandervelden.blogspot.com /2009/10/counting-bits-population-count-and.html e un altro articolo con parametri di riferimento: http : //www.strchr.com/crc32_popcnt

Dalla mia comprensione:

Vorrei utilizzare il 33% come indicatore solo come profiling per i piccoli metodi potrebbe davvero cambiare le prestazioni complessive. Quindi mi sento di eseguire l'algoritmo su alcuni grandi set di dati e vedere il tempo totale. E vorrei prendere in considerazione le efficiancies della mia ottimizzazione basata su quella totale cambio di orario. Vorrei includere anche un avvertimento in fase di modo che il JIT può farlo di ottimizzazioni.

In realtà la cosa conteggio po 'sembra essere una delle parte fondamentale del vostro algoritmo comunque ... se ottimizzate tutto, e riesce a ottenere 10 tempo più veloce per tutta la parte fondamentale, qualcosa che ancora profilo nei pressi del 33% per questo parte. Che non è male per essenza.

Inspiring da questo link http://bmagic.sourceforge.net/bmsse2opt.html voi potrebbero tentare di usare SSE istruzioni presenti in tutti processore Intel / AMD ora se ricordo bene (si può sempre puntuale failback a JAVA altrimenti). Una parte interresting riguardante l'articolo è ... Che la maggior parte del tempo, è la memoria legata comunque. Ma vorrei comunque cercare di vedere come questo potrebbe funzionare per voi.

Una GPU sarebbe una misura perfetta per follemente veloce elaborazione (facile centinaia volta che uno di un nucleo CPU) e larghezza di banda. Il problema principale sarebbe trasmettere i dati alla CPU memoria dedicata e ottenere risultato di nuovo. Ma se non solo di eseguire il conteggio po 'di più, ma di più il funzionamento, questo potrebbe portare enormi guadagni.

non è scorciatoia in ogni caso, è necessario provare diversi approccio e vedere cosa porterà il più guadagno. Non contare% attraverso ma il tempo totale trascorso.

Ora sto usando questo metodo, che intercala quattro operazioni POPCNT alla volta. Si basa su questa implementazione 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);
}

Questa versione lunga il tabella di ricerca un po ', e non consuma cache.

Invece di ottimizzare questa funzione, si rischia di essere meglio ottimizzare l'utilizzo di questa funzione. Per esempio. si potrebbe tenere un contatore. 

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;
}

Ciò evita scansione i dati tenendo traccia del numero del conteggio dei bit impostati. Questo sposta il sovraccarico a quanto spesso i bit e impostare o togliere e fa ottenere il numero di bit impostato banale. Appare nel vostro caso d'uso, il secondo è molto più spesso.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top