C Questo hack senza branch è in realtà più veloce?

Question

Sto provando a bloccare un valore compreso tra -127 e 127 su un sistema Cortex-M microcontroller.

Ho due funzioni concorrenti, uno usa condizionali l'altro usa un attacco senza ramo che ho trovato here.

// Using conditional statements 
int clamp(int val) { return ((val > 127) ? 127 : (val < -127) ? -127 : val); } 

// Using branchless hacks 
int clamp(int val) { 
    val -= -127; 
    val &= (~val) >> 31; 
    val += -127; 
    val -= 127; 
    val &= val >> 31; 
    val += 127; 

    return val; 
} 

Ora so in alcuni casi uno di questi metodi potrebbe essere più veloce rispetto agli altri, e vice-versa, ma in generale è la pena di utilizzare la tecnica branchless visto che in realtà non mi importa che uso, entrambi funzioneranno bene nel mio caso?

Un piccolo background sul microcontrollore, è un microcontrollore basato su ARM in esecuzione a 90 MIPS con pipeline a 3 stadi, fetch, decodifica ed esecuzione e sembra avere una sorta di predittore di ramo ma non sono riuscito a trovare dettagli.

Answer 1

codice ARM (GCC 4.6.3 con -O3):

clamp1: 
    mvn r3, #126 
    cmp r0, r3 
    movlt r0, r3 
    cmp r0, #127 
    movge r0, #127 
    bx lr 

clamp2: 
    add r0, r0, #127 
    mvn r3, r0 
    and r0, r0, r3, asr #31 
    sub r0, r0, #254 
    and r0, r0, r0, asr #31 
    add r0, r0, #127 
    bx lr 

codice Thumb:

clamp1: 
    mvn r3, #126 
    cmp r0, r3 
    it lt 
    movlt r0, r3 
    cmp r0, #127 
    it ge 
    movge r0, #127 
    bx lr 

clamp2: 
    adds r0, r0, #127 
    mvns r3, r0 
    and r0, r0, r3, asr #31 
    subs r0, r0, #254 
    and r0, r0, r0, asr #31 
    adds r0, r0, #127 
    bx lr 

Entrambi sono senza rami grazie alla struttura esecuzione condizionale di ARM. Scommetto che sono sostanzialmente comparabili in termini di prestazioni.

Answer 2

Qualcosa da realizzare è che le architetture ARM e x86 sono molto diverse quando si tratta di istruzioni di derivazione. Facendo un salto si libera la pipeline che può comportare la spesa di un numero di cicli di clock solo per "tornare al punto in cui eri" in termini di velocità effettiva.

Per citare un pdf che ho scaricato l'altro giorno (PG14 di http://simplemachines.it/doc/arm_inst.pdf),

Esecuzione condizionale

• maggior istruzione imposta consentono solo rami da eseguire in modo condizionale.
• Tuttavia, riutilizzando l'hardware di valutazione delle condizioni, ARM aumenta effettivamente il numero di istruzioni.
• Tutte le istruzioni contengono un campo delle condizioni che determina se la CPU le eseguirà.
• Le istruzioni non eseguite assorbono 1 ciclo. - È ancora necessario completare il ciclo in modo da consentire il recupero e la decodifica delle seguenti istruzioni.
• Ciò elimina la necessità di molti rami, che bloccano la tubazione (3 cicli da riempire).
• Consente il codice in linea molto denso, senza diramazioni.
• La penalità di tempo di non esecuzione di più istruzioni condizionate è spesso inferiore al sovraccarico del ramo o della chiamata di subroutine che altrimenti sarebbe necessaria.

Answer 3

No. Il linguaggio C non ha velocità; Questo è un concetto introdotto dalle implementazioni di C. Un compilatore perfettamente ottimale tradurrebbe entrambi quelli con lo stesso codice macchina.

I compilatori C hanno maggiori probabilità di essere in grado di ottimizzare il codice conforme agli stili comuni ed è ben definito. La seconda funzione non è ben definita.

Tali aggiunte e sottrazioni possono causare overflow di interi. Gli overflow integer sono comportamenti indefiniti, quindi potrebbero causare il malfunzionamento del programma. Ottimisticamente, il tuo hardware potrebbe implementare il wrapping o la saturazione. Un po 'meno ottimisticamente, il tuo sistema operativo o il compilatore potrebbero implementare segnali o rappresentazioni di trap per overflow interi. La rilevazione di overflow integer potrebbe influire sulla performance percepita della modifica di una variabile. Il caso peggiore è che il tuo programma perda la sua integrità.

Gli operatori & e >> hanno aspetti definiti dall'implementazione per i tipi firmati. Possono risultare in uno zero negativo, che è un esempio di una rappresentazione trap. Usare una rappresentazione trap è un comportamento indefinito, quindi il tuo programma potrebbe perdere la sua integrità.

Forse il vostro sistema operativo o compilatore implementa controlli di bit di parità per gli oggetti int. In questo caso, prova a immaginare di ricalcolare i bit di parità ogni volta che una variabile cambia e verifica i bit di parità ogni volta che una variabile viene letta. Se un controllo di parità fallisce, il tuo programma potrebbe perdere la sua integrità.

Utilizzare la prima funzione. Almeno è ben definito. Se il tuo programma sembra funzionare lentamente, l'ottimizzazione di questo codice probabilmente non accelera significativamente il tuo programma; Utilizzare un profiler per trovare ottimizzazioni più significative, utilizzare un sistema operativo o un compilatore più ottimizzato o acquistare hardware più veloce.