Come può l'aritmetica, come un bit shift, evitare la ramificazione?

Questo tipo di microottimizzazione viene solitamente evitato perché danneggia la leggibilità del codice e le microottimizzazioni sono il compito del compilatore. Ma a volte queste tecniche possono essere legittimamente utili.

Spesso, invece di ramificarci, possiamo sfruttare il modo in cui i pattern a bit interagiscono. Per esempio. invece di testare se un booleano è impostato con un condizionale, potremmo forse moltiplicare il valore booleano con un valore. Esempio sciocco:

int some_condition = ...;  // boolean, either 0 or 1
/* if (some_condition) {
 *   return x;
 * } else {
 *   return y;
 * }
 */
return some_condition * x + !some_condition * y;

Se si presuppone che la moltiplicazione sia costosa, nota che -1 è lo schema di bit di tutti su un sistema a due componenti, quindi potremmo utilizzare in modo equivalente:

return (-some_condition & x) | (-!some_condition & y);

A volte è possibile strutturare calcoli più grandi in un modo tale da far propagare qualche schema di bit (ad esempio tutti zeri o tutti). Ciò è particolarmente utile quando abbiamo una lista di condizioni che sono tutte economiche da valutare. Ma ad es. L'operatore || di C è un operatore di ramificazione! Potrebbe quindi essere più veloce sostituire testA() || testB() || testC() con:

int ok = 0;
ok |= testA();
ok |= testB();
ok |= testC();

Se uno di questi aiuti deve essere valutato. Sui sistemi moderni, la risposta è quasi universalmente "no". I rami non sono il problema, è la previsione di falsi rami. Sul tuo sistema, potresti voler guardare il codice assembly e contare i cicli di istruzione (che dovrebbero essere elencati nel manuale della CPU). Puoi quindi avere la sensazione che ulteriori istruzioni salvino qualsiasi ciclo rispetto a un ramo.

But if it returns 0 or -1, wouldn't you still need a branch to check which one it is and execute the according instructions?

Non necessariamente. Come scritto, la spiegazione lascia fuori cosa fare con il valore dell'espressione una volta calcolato. Con un numero in mano, puoi usarlo come indice per un array:

// Return one value for odd inputs and another for even.
int x_factor(int value)
{
  static int factors[] = {
    123,  // For odd values                                                                                                         
    456   // For even values
  };

  int index = (value % 2) == 0;
  return factors[index];
}

... o come parte di un'espressione scritta in modo intelligente:

// Same as above.
int x_factor(int value)
{
  int multiplier = (value % 2) == 0;
  return (456 * multiplier) + (123 * (!multiplier));
}

Come sottolinea correttamente Amon nella sua risposta, trucchi del genere possono ridurre la leggibilità e le ottimizzazioni come questa dovrebbero essere lasciate al compilatore. Il fatto è che non hai sempre un compilatore e, ovviamente, qualcuno deve capire queste cose per scrivere i compilatori in primo luogo.

La prossima domanda logica sarebbe il motivo per cui dovresti fare assolutamente nulla. La risposta a ciò che si trova nei processori delle pipeline viene utilizzata per assicurarsi che ci siano sempre istruzioni da eseguire per eseguire invece di stare inattivi in attesa dell'arrivo di istruzioni.

Alcune architetture sono a pipeline singola, il che significa che continuano a recuperare le istruzioni e ad inserirle nella pipa purché possano sapere con certezza quale sarà il contatore del programma dopo l'esecuzione dell'istruzione. Ciò vale per tutte le classi di istruzioni tranne due: quelle che coinvolgono la ramificazione condizionale e quelle che implicano un salto o una chiamata a un indirizzo memorizzato in una posizione volatile (registro o memoria). L'incontro con una di queste istruzioni significa che la pipeline deve smettere di andare a prendere perché non ha idea di come andranno le cose fino a quando non saranno state eseguite tutte le istruzioni precedenti. Ciò si traduce in una pipeline vuota e in una CPU che deve essere inattiva durante il caricamento delle istruzioni finché non si riempie nuovamente. Se stai cercando di estorcere a ogni bit delle prestazioni il processore o se hai requisiti rigidi in tempo reale che richiedono la prevedibilità dei tempi di esecuzione, questa è l'ultima cosa che vuoi che accada.

Intel e altri hanno aggirato questo problema utilizzando più pipeline che eseguivano il prelievo speculativo di istruzioni da entrambi i possibili risultati del ramo. Una volta determinato il risultato, viene usata la pipa piena di istruzioni sul lato "vero" del ramo e il contenuto della pipa dal lato "falso" viene gettato via. Questa è una soluzione molto intelligente, ma ha un prezzo: ci vogliono più porte per implementare la pipeline aggiuntiva e il processo decisionale. Più porte significa più dimensioni fisiche, più consumo energetico e più calore. Questo è accettabile se stai costruendo processori da inserire nei server ma non tanto per qualcosa che dovrà essere eseguito su una manciata di batterie AA in un piccolo pacchetto.