Ottimizzazione del ciclo iterativo con elementi rimossi

In un processo che, se ho compreso correttamente la tua descrizione, implica prendere decisioni in base al tuo campo lost circa 50.000 volte, stai riscontrando un rallentamento di circa 1 secondo a causa di quei controlli (o delle conseguenze di comportamento che cambia dopo di loro).

Una stima errata di un ramo ha un costo che varia in base al processore, ma in genere non supera i 30 cicli del processore. Su una tipica macchina a 2 GHz potreste vedere un rallentamento di almeno 1,5 ms se si verificava una cattiva previsione su ogni iterazione (che avrebbe bisogno di un set di dati davvero bizzarro per ottenere come i processori moderni sono abbastanza buoni per la previsione delle branch).

L'effetto che stai vedendo è di circa 3 ordini di grandezza più alto, quindi l'errore deve essere di origine algoritmica, non un problema di micro-ottimizzazione come la previsione dei rami.

Stai solo supponendo. L'enorme differenza sembra indicare che tu non stavi misurando la stessa cosa, che gli elementi di chiamata [i] sono molto lenti (stai scorrendo attraverso una lista collegata dove gli elementi [i] sono molto lenti?), O che non chiama calc_loads ( ) ha effetti collaterali che non conosci. E 2,7 secondi è un tempo terribile per tutto ciò che non coinvolge almeno decine di milioni di elementi.

Esegui il tuo codice usando un debugger e vedi se succede qualcosa che non ti aspetti. Se questo non produce risultati, usa un profiler. Se non sai come fare, chiedi a un collega. Ma posso garantire che la previsione delle branchie non ha nulla a che fare con il tuo problema e qualsiasi hack che cerchi di risolvere il tuo problema di "branch prediction" percepito renderà il tuo codice più complicato e più lento.

È abbastanza probabile che l'uso di un iteratore C ++ faccia andare via il problema. E hai attivato l'ottimizzazione nel compilatore? C ++ si basa spesso sull'ottimizzazione del compilatore.

L'esecuzione condizionale può interferire con il predittore di ramo dell'hardware, che è noto per avere il potenziale per rallentare notevolmente le cose.

Potresti considerare di avere due raccolte: una per il perso & uno per non perso. Piuttosto che taggare un oggetto come perso (o forse in aggiunta): spostalo da una raccolta all'altra. Questo avrà due effetti benefici: non troverai oggetti persi nella traversata, quindi ci sono meno oggetti da attraversare e, non avrai bisogno della logica condizionale che interferisce con il predittore del ramo.

Richiederà comunque due raccolte, quindi YMMV.

(Se si utilizza solo il meccanismo di raccolta per identificare la perdita, è possibile anche rimuovere il metodo is_lost() e qualsiasi stato associato rendendo gli oggetti altrettanto più piccoli.)

Se la dimensione della raccolta non cambia durante l'elaborazione, è possibile anche memorizzare nella cache la dimensione della raccolta in una variabile locale. Inoltre, calcolerei questo- > gli articoli [i] solo una volta ogni iterazione, memorizzandone il caching in una variabile locale.

A meno che l'ordine degli elementi nella raccolta sia importante (che non sembra essere, almeno in uno qualsiasi dei codici che hai mostrato), dividerei la raccolta in due gruppi, quindi opererò su quello:

auto part = std::partition(items.begin(), items.end(), 
    [&](item const *a) { return a->force <= force_x_max; });

std::for_each(items.begin(), part, 
    [](item *i) { i->calc_loads(...); });

Se calc_loads modifica gli articoli mentre esegue i calcoli su di essi, potresti stare meglio con std::transform anziché std::for_each .

Inoltre, se l'ordine degli elementi in items è rilevante, non sembra che questo sia un problema grave: items apparentemente contiene solo 12 puntatori, quindi la copia non richiede quasi del tempo. Possiamo quindi partizionare la copia dei puntatori senza influenzare l'ordine degli elementi originali o l'ordine dei puntatori originali su di essi. In alternativa, possiamo combinare i due passaggi utilizzando std::copy_if :

std::vector<item *> temp;
std::copy_if(items.begin(), items.end(), std::back_inserter(temp),
             [&](item const *a) { return i->force <= force_x_max; });

std::for_each(temp.begin(), temp.end(),
              [](item *i) { i->calc_loads(...); });

In entrambi i casi, ciò che hai in questo momento è attraversare i dati una volta per impostare la bandiera, quindi prendere decisioni basate sulla bandiera durante il ciclo interno. Tramite il partizionamento dell'array, possiamo evitare di effettuare tali controlli nel ciclo interno.

È comunque possibile che ciò non sia di aiuto. In particolare, il codice originale potrebbe avere un modello altamente prevedibile di caricamento di ogni articolo a turno. La maggior parte delle moderne CPU tenterà di rilevare i modelli di lettura e precaricare i dati basati su di essi. Può essere che semplicemente avendo alcuni oggetti che vengono elaborati e altri che non lo fanno (da soli) impediscono il funzionamento del precaricamento, quindi i tentativi di ottimizzazione in questa direzione falliranno sempre - ma penso che sia probabilmente utile almeno provare partizionamento per vedere se funziona meglio per i tuoi scopi.

Poiché chiaramente sta succedendo qualcosa di strano: potrebbe essere che il compilatore abbia richiamato la chiamata calc_loads. Ma con "continua", la chiamata potrebbe non essere eseguita affatto, quindi il compilatore decide che l'inlining non vale la pena. Controllare il codice assemblatore se si ha una chiamata di funzione e l'altra no.

Penso davvero che dovresti prendere un bel profiler che ti mostri statistiche come previsioni sbagliate dei rami e mancate cache. Fatto. Puoi ottenere la risposta esatta immediatamente senza indovinare.

Detto questo, dal momento che mi sto godendo le congetture, offrirò uno che non si riferisce alla previsione del ramo. Se i tuoi dati di load_item erano, in assenza di questo membro lost (e suppongo che il metodo is_lost() sia un semplice accorgimento), un multiplo della dimensione di una linea di cache (ad esempio un multiplo di 64 byte), come così:

struct loads_item
{
    ...        // 64 bytes of data
    bool lost; // extra byte
};

... che potrebbe gonfiare la dimensione di una struttura da, diciamo, 64 byte a 72 o giù di lì (a seconda dei requisiti di allineamento del primo campo dati), allora questa sarebbe una possibile spiegazione. Offro questa congettura se è corretta o meno in questo caso, perché tale consapevolezza può aiutarti a diventare un po 'più consapevole dei possibili hotspot orientati ai dati.

In questo caso, se combinato con il modo in cui stai memorizzando i puntatori a questi elementi di carico (rendendo irrilevante un campo così freddo per quanto manca la cache se non è accessibile se gli elementi non sono archiviati in modo contiguo), accedendo a lost membro nel ciclo raddoppierà efficacemente i mancati messaggi di cache relativi all'accesso a questi pointees loads_item , mentre l'omissione dell'accesso a lost li ridurrebbe a metà.

Questa è in realtà la più "intuizione" per me dopo anni di profilazione di tale codice e di concentrazione su una mentalità orientata ai dati in contesti così importanti dal punto di vista delle prestazioni, forniti i tuoi dati hanno effettivamente queste caratteristiche e calc_loads non è un metodo banale da chiamare (altrimenti la ramificazione potrebbe costare molto di più anche senza troppe previsioni), anche se ovviamente le mie intuizioni non sono ancora molto affidabili (ma almeno più di prima ho acquisito un po 'di esperienza misurare queste cose per anni).

Una cosa che posso dire è che spesso ogni intuizione che avevo in relazione con le previsioni errate delle filiali era molto, molto più spesso sbagliata che corretta quando ho iniziato a prestare attenzione alle statistiche di profilazione dettagliate in VTune. Molto più spesso se qualcosa di strano stava succedendo sotto il cofano che sembrava molto contro-intuitivo, in realtà era legato al layout della memoria e all'accesso con la cache della CPU. Occasionalmente l'ottimizzatore stava facendo qualcosa di strano per quanto riguarda la selezione delle istruzioni o l'assegnazione del registro. Ma raramente è un caso nella mia esperienza (anche se potrebbe essere dovuto alla natura del codice con cui lavoro), in relazione alla previsione del ramo.