Il modo più veloce per vedere quanti byte sono uguali tra array a lunghezza fissa

Question

Ho 2 matrici di 16 elementi (caratteri) di cui ho bisogno per "confrontare" e vedi quanti elementi sono uguali tra i due.

Questa routine verrà utilizzata milioni di volte (una corsa normale è di circa 60 o 70 milioni di volte), quindi ho bisogno che sia il più veloce possibile. Sto lavorando su C ++ (C ++ Builder 2007, per la cronaca)

In questo momento, ho un semplice:

matches += array1[0] == array2[0];

ripetuto 16 volte (poiché la profilazione sembra essere il 30% più veloce rispetto a un ciclo for)

Esiste un altro modo per lavorare più velocemente?

Alcuni dati sull'ambiente e sui dati stessi:

• Sto usando C ++ Builder, che non ha ottimizzazioni di velocità da tenere in considerazione. Proverò alla fine con un altro compilatore, ma in questo momento sono bloccato con questo.
• I dati saranno diversi il più delle volte. Il 100% di dati uguali è di solito molto raro (forse meno dell'1%)

Answer 1

AGGIORNAMENTO: questa risposta è stata modificata per far corrispondere i miei commenti al codice sorgente fornito di seguito.

È disponibile un'ottimizzazione se si ha la possibilità di utilizzare le istruzioni SSE2 e popcnt.

16 byte si adattano perfettamente a un registro SSE. Utilizzando c ++ e assembly / intrinsics, caricare le due matrici da 16 byte nei registri xmm e cmp. Questo genera una maschera di bit che rappresenta la condizione vero / falso del confronto. Quindi utilizzare un'istruzione movmsk per caricare una rappresentazione di bit della maschera di bit in un registro x86; questo diventa quindi un campo di bit in cui puoi contare tutti gli 1 per determinare quanti valori reali hai avuto. Un'istruzione popcnt hardware può essere un modo rapido per contare tutti gli 1 in un registro.

Ciò richiede la conoscenza dell'assembly / intrinsics e SSE in particolare. Dovresti essere in grado di trovare risorse Web per entrambi.

Se si esegue questo codice su una macchina che non supporta SSE2 o popcnt, è necessario scorrere le matrici e contare le differenze con l'approccio del ciclo non srotolato.

Buona fortuna

Modifica: Dato che hai indicato di non conoscere assembly, ecco un codice di esempio per illustrare la mia risposta:

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

Alcune note: questa funzione utilizza istruzioni SSE2 e un'istruzione popcnt introdotte nel processore Phenom (questa è la macchina che uso). Credo che anche i più recenti processori Intel con SSE4 abbiano popcnt. Questa funzione non verifica il supporto delle istruzioni con CPUID; la funzione non è definita se utilizzata su un processore che non ha SSE2 o popcnt (probabilmente otterrai un'istruzione opcode non valida). Tale codice di rilevamento è un thread separato.

Non ho cronometrato questo codice; la ragione per cui penso che sia più veloce è perché confronta 16 byte alla volta, senza diramazioni. Dovresti modificarlo per adattarlo al tuo ambiente, e cronometra te stesso per vedere se funziona per te. L'ho scritto e testato su VS2008 SP1.

SSE preferisce i dati allineati su un limite naturale di 16 byte; se puoi garantire che dovresti ottenere ulteriori miglioramenti della velocità e puoi modificare le istruzioni _mm_loadu_si128 in _mm_load_si128, che richiede l'allineamento.

Answer 2

La chiave è fare i confronti usando il registro più grande supportato dalla CPU, quindi ricadere in byte se necessario.

Il codice seguente mostra l'uso di numeri interi a 4 byte, ma se si esegue un'architettura SIMD (qualsiasi chip Intel o AMD moderno) è possibile confrontare entrambi gli array in un'istruzione prima di ricorrere a un ciclo basato su numeri interi. La maggior parte dei compilatori in questi giorni ha il supporto intrinseco per i tipi a 128 bit, quindi NON richiederà ASM

(Nota che per i confronti SIMD i tuoi array dovrebbero essere allineati a 16 byte e alcuni processori (ad esempio MIPS) richiederebbero che gli array siano allineati a 4 byte per i confronti basati su int.

per es.

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

Non ricordo cosa supporti esattamente il compilatore MSVC per SIMD, ma potresti fare qualcosa del genere;

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}

Answer 3

Se si ha la possibilità di controllare la posizione degli array, mettendoli uno dopo l'altro in memoria, ad esempio, è possibile che vengano caricati nella cache della CPU al primo accesso.

Dipende dalla CPU e dalla sua struttura cache e varierà da una macchina all'altra.

Puoi leggere la gerarchia della memoria e la cache in Henessy & amp; L'architettura informatica di Patterson: un approccio quantitativo

Answer 4

Se hai bisogno di un footprint minimo assoluto, sceglierei il codice assembly. Non lo faccio da un po ', ma scommetto che MMX (o più probabilmente SSE2 / 3) ha istruzioni che possono permetterti di fare esattamente questo in pochissime istruzioni.

Answer 5

Se le corrispondenze sono il caso comune, prova a caricare i valori come 32 bit ints anziché 16 in modo da poter confrontare 2 in una volta (e contarlo come 2 corrispondenze).

Se i due valori a 32 bit sono non uguali, dovrai provarli separatamente (E fuori dai valori superiore e inferiore a 16 bit).

Il codice sarà più complesso, ma dovrebbe essere più veloce.

Se stai prendendo di mira un sistema a 64 bit potresti fare lo stesso trucco con ints a 64 bit, e se vuoi davvero spingere il limite, allora guarda cadere nell'assemblatore e usare le varie istruzioni basate su vettori che ti permetterebbero di lavorare con 128 bit contemporaneamente.

Answer 6

Le opzioni del compilatore magico varieranno notevolmente il tempo. In particolare, far sì che generi la vettorializzazione di SSE ti farà ottenere un enorme aumento di velocità.

Answer 7

Deve essere indipendente dalla piattaforma o questo codice verrà sempre eseguito sullo stesso tipo di CPU? Se ti limiti alle moderne CPU x86, potresti essere in grado di utilizzare le MMX , che dovrebbe consentire di operare su un array di 8 byte in un quadrante di clock. AFAIK, gcc ti consente di incorporare assembly nel tuo codice C e il compilatore Intel (icc) supporta intrinseci, che sono wrapper che ti consentono di chiamare direttamente specifiche istruzioni di assembly. Altri set di istruzioni SIMD, come SSE, possono anche essere utili per questo.

Answer 8

Esiste una connessione tra i valori negli array? È più probabile che alcuni byte siano gli stessi di altri? Potrebbe esserci un ordine intrinseco nei valori? Quindi potresti ottimizzare il caso più probabile.

Answer 9

Se spieghi cosa rappresentano effettivamente i dati, allora potrebbe esserci un modo completamente diverso di rappresentare i dati in memoria che renderebbe inutile questo tipo di forza bruta. Cura di elaborare cosa rappresentano effettivamente i dati ??

Answer 10

È più veloce come un'istruzione?

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;

Answer 11

Se scrivere 16 volte è più veloce di un semplice ciclo, allora il tuo compilatore fa schifo o non hai attivato l'ottimizzazione.

Risposta breve: non c'è modo più veloce, a meno che non si eseguano operazioni vettoriali su hardware parallelo.

Answer 12

Prova a utilizzare i puntatori anziché le matrici:

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

Ovviamente devi misurarlo con altri approcci per vedere quale è il più veloce.

E sei sicuro che questa routine sia un collo di bottiglia nella tua elaborazione? Acceleri davvero le prestazioni della tua applicazione nel suo insieme ottimizzandola? Ancora una volta, solo la misurazione lo dirà.

Answer 13

Esiste un modo per modificare il modo in cui sono archiviate le matrici? Il confronto di 1 byte alla volta è estremamente lento considerando che probabilmente si sta utilizzando un compilatore a 32 bit. Invece, se hai archiviato i tuoi 16 byte in 4 numeri interi (32 bit) o ??2 lunghi (64 bit), dovrai solo eseguire rispettivamente 4 o 2 confronti.

La domanda da porsi è quanto costa la memorizzazione dei dati come array a 4 numeri interi o 2 lunghi. Con quale frequenza devi accedere ai dati, ecc.

Answer 14

C'è sempre la buona vecchia istruzione REPNE CMPS x86.

Answer 15

Un'ulteriore ottimizzazione possibile: se ti aspetti che la maggior parte delle volte gli array siano identici, potrebbe essere leggermente più veloce fare un memcmp () come primo passo, impostando '16' come risposta se il test ritorna vero . Se, naturalmente, se non ti aspetti che gli array siano identici molto spesso, ciò rallenterebbe solo le cose.