Il modo più veloce per permutare i bit in un array Java

Question

Qual è il modo più rapido per permutare casualmente (ma ripetutamente) tutti i bit all'interno di un array di byte Java? Ho provato a farlo con successo con un BitSet, ma c'è un modo più veloce? Chiaramente il ciclo for consuma la maggior parte del tempo della CPU.

Ho appena fatto un po 'di profilazione nel mio IDE e il ciclo for costituisce il 64% del tempo della CPU all'interno dell'intero metodo permute().

Per chiarire, la matrice (preRound) contiene una matrice esistente di numeri che entrano nella procedura. Voglio che i singoli bit del set di quell'array vengano mescolati in modo casuale. Questo è il motivo per P []. Contiene un elenco casuale di posizioni di bit. Ad esempio, se è impostato il bit 13 di preRound, viene trasferito al posto P [13] di postRound. Questo potrebbe essere nella posizione 20555 di postRound. Il tutto fa parte di una rete di permutazione di sostituzione, e sto cercando il modo più veloce per permutare i bit in arrivo.

Il mio codice finora ...

private byte[] permute(byte[] preRound) { 
    BitSet beforeBits = BitSet.valueOf(preRound); 
    BitSet afterBits = new BitSet(blockSize * 8); 


    for (int i = 0; i < blockSize * 8; i++) { 
     assert i != P[i]; 


     if (beforeBits.get(i)) { 
      afterBits.set(P[i]); 
     } 
    } 


    byte[] postRound = afterBits.toByteArray(); 
    postRound = Arrays.copyOf(postRound, blockSize);  // Pad with 0s to the specified length 
    assert postRound.length == blockSize; 


    return postRound; 
} 

Cordiali saluti, blockSize è di circa 60.000 e P è una tabella di ricerca casuale.

Answer 1

Non ho eseguito alcun test delle prestazioni, ma è possibile prendere in considerazione quanto segue: Per omettere la chiamata a Arrays.copyOf (che copia la copia del long [] utilizzata internamente, che è piuttosto fastidiosa) , basta impostare l'ultimo bit nel caso in cui non sia stato impostato prima e disattivarlo in seguito.

Inoltre, c'è un bel linguaggio per scorrere i bit impostati nella permutazione di input.

private byte[] permute(final byte[] preRound) { 
    final BitSet beforeBits = BitSet.valueOf(preRound); 
    final BitSet afterBits = new BitSet(blockSize*8); 
    for (int i = beforeBits.nextSetBit(0); i >= 0; i = 
      beforeBits.nextSetBit(i + 1)) { 
     final int to = P[i]; 
     assert i != to; 
     afterBits.set(to); 
    } 
    final int lastIndex = blockSize*8-1; 
    if (afterBits.get(lastIndex)) { 
     return afterBits.toByteArray(); 
    } 
    afterBits.set(lastIndex); 
    final byte[] postRound = afterBits.toByteArray(); 
    postRound[blockSize - 1] &= 0x7F; 
    return postRound; 
} 

Se questo non è tagliato, nel caso in cui si utilizza lo stesso P per un sacco di iterazioni, può valere la pena di prendere in considerazione trasformare la permutazione in notazione ciclo ed eseguire la trasformazione sul posto. In questo modo è possibile iterare linearmente su P, che potrebbe consentire di sfruttare meglio il caching (P è 32 volte più grande della matrice di byte, assumendo che sia un array int). Tuttavia, perderai il vantaggio di dover guardare solo 1s e finire spostando ogni singolo bit nell'array di byte, impostato o meno.

Se si vuole evitare di utilizzare il BitSet, si può semplicemente farlo a mano:

private byte[] permute(final byte[] preRound) { 
    final byte[] result = new byte[blockSize]; 
    for (int i = 0; i < blockSize; i++) { 
     final byte b = preRound[i]; 
     // if 1s are sparse, you may want to use this: 
     // if ((byte) 0 == b) continue; 
     for (int j = 0; j < 8; ++j) { 
      if (0 != (b & (1 << j))) { 
       final int loc = P[i * 8 + j]; 
       result[loc/8] |= (1 << (loc % 8)); 
      } 
     } 
    } 
    return result; 
}