Come ottimizzare un ciclo?

Question

Ho la seguente funzione collo di bottiglia.

typedef unsigned char byte; 
void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3) 
{ 
    const byte b1 = 128-30; 
    const byte b2 = 128+30; 
    for (const byte * p1 = p1Start; p1 != p1End; ++p1, ++p2, ++p3) { 
     *p3 = (*p1 < *p2) ? b1 : b2; 
    } 
} 

voglio sostituire C++ codice con SSE2 funzioni intinsic. Ho provato _mm_cmpgt_epi8 ma ha usato il confronto firmato. Ho bisogno di confrontare senza firma.

C'è qualche trucco (SSE, SSE2, SSSE3) per risolvere il mio problema?

Nota: Non voglio usare multi-threading in questo caso.

Answer 1

Invece di compensare i tuoi valori con segno per renderli non firmato, un modo un po 'più efficace sarebbe quella di effettuare le seguenti operazioni:

• uso _mm_min_epu8 per ottenere il minimo senza segno di p1, p2
• confronta min per l'uguaglianza con p2 utilizzando _mm_cmpeq_epi8
• la maschera risultante sarà ora 0x00 per gli elementi in cui p1 < P2 e 0xff per gli elementi in cui p1> p2 =
• è ora possibile utilizzare questa maschera con _mm_or_si128 e _mm_andc_si128 per selezionare i valori di b2/B1 appropriate

Si noti che questo è di 4 istruzioni in totale, rispetto al 5 utilizzando il + approccio confronto firmato offset.

Answer 2

Sì, SSE non funzionerà qui. È possibile migliorare questa performance di codice sul computer multi-core utilizzando OpenMP:

 
void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3) 
{ 
    const byte b1 = 128-30; 
    const byte b2 = 128+30; 

    int n = p1End - p1Start; 
    #pragma omp parallel for 
    for (int i = 0; i < n; ++p1, ++i) 
    { 
     p3[i] = (p1[i] < p2[i]) ? b1 : b2; 
    } 
} 

Answer 3

uso pcmpeqb e essere il potere con voi.

Answer 4

È possibile sottrarre 127 da numeri, e quindi utilizzare _mm_cmpgt_epi8

Answer 5

Sì, questo può essere fatto in SIMD, ma ci vorrà qualche passo per rendere la maschera.

Ruslik ha ragione, penso. Si desidera xor ogni componente con 0x80 per capovolgere il senso del confronto firmato e senza segno. _mm_xor_si128 (PXOR) è quello che ti serve: dovrai creare la maschera come array statico di char da qualche parte prima di caricarla in un registro SIMD. Quindi _mm_cmpgt_epi8 ti fa una maschera e puoi usare un AND bit a bit (es. _mm_and_si128) per eseguire uno spostamento mascherato.

Answer 6

Sfortunatamente, molte delle risposte precedenti non sono corrette. Assumiamo una parola di 3 bit:

non firmato: 4 5 6 7 0 1 2 3 == firmato: -4 -3 -2 -1 0 1 2 3 (bit: 100 101 110 111 000 001 010 011)

Il metodo di Paul R non è corretto. Supponiamo di voler sapere se 3> 2. min (3,2) == 2, che suggerisce sì, quindi il metodo funziona qui. Ora supponiamo di voler sapere se 7> 2. Il valore 7 è -1 nella rappresentazione firmata, quindi min (-1,2) == -1, il che suggerisce erroneamente che 7 non sia maggiore di 2 non firmati.

Anche il metodo di Andrey non è corretto. Supponiamo di voler sapere se 7> 2, o a = 7, e b = 2. Il valore 7 è -1 nella rappresentazione firmata, quindi il primo termine (a> b) fallisce e il metodo suggerisce che 7 non sia maggiore di 2.

Tuttavia, il metodo di BJobnh, come corretto da Alexey, è corretto. Sottrarre appena 2^(n-1) dai valori, dove n è il numero di bit. In questo caso, sottraiamo 4 per ottenere nuovi valori corrispondenti:

vecchio firmato: -4 -3 -2 -1 0 1 2 3 => nuovo firmato: 0 1 2 3 -4 -3 -2 -1 == nuovo non firmato 0 1 2 3 4 5 6 7.

In altre parole, unsigned_greater_than (a, b) è equivalente a signed_greater_than (a - 2^(n-1), b - 2^(n-1)).