Domanda

Non riesco, per la vita a me, a ricordare esattamente cosa ha detto il nostro insegnante quel giorno e spero che tu probabilmente lo saprai.

Il modulo è "Strutture dati e algoritmi" e ci ha detto qualcosa sulla falsariga di:

  

L'istruzione if è la più costosa   [qualcosa]. [qualcosa] registra   [Qualcosa].

Sì, ho un ricordo orribile e mi dispiace davvero tanto, ma ho cercato su google per ore e non è successo nulla. Qualche idea?

È stato utile?

Soluzione

Al livello più basso (nell'hardware), sì, se è costoso. Per capire perché, devi capire come pipeline funzionare.

Le istruzioni correnti da eseguire sono memorizzate in qualcosa che in genere si chiama puntatore istruzioni (IP) o contatore programmi (PC); questi termini sono sinonimi, ma termini diversi sono usati con architetture diverse. Per la maggior parte delle istruzioni, il PC dell'istruzione successiva è solo il PC corrente più la lunghezza dell'istruzione corrente. Per la maggior parte delle architetture RISC, le istruzioni sono tutte di lunghezza costante, quindi il PC può essere incrementato di una quantità costante. Per architetture CISC come x86, le istruzioni possono essere di lunghezza variabile, quindi la logica che decodifica l'istruzione deve capire per quanto tempo l'istruzione corrente deve trovare la posizione dell'istruzione successiva.

Per le istruzioni branch , tuttavia, l'istruzione successiva da eseguire non è la posizione successiva dopo l'istruzione corrente. I rami sono goto: dicono al processore dove si trova la prossima istruzione. I rami possono essere condizionali o incondizionati e la posizione di destinazione può essere fissa o calcolata.

Condizionale vs. incondizionato è facile da capire - un ramo condizionale viene preso solo se una certa condizione è valida (come se un numero è uguale a un altro); se il ramo non viene preso, il controllo procede all'istruzione successiva dopo il ramo come di consueto. Per i rami incondizionati, il ramo viene sempre preso. I rami condizionali vengono visualizzati nelle istruzioni if e nei test di controllo di per e mentre i cicli . I rami incondizionati si presentano in loop infiniti, chiamate di funzione, resi di funzione, istruzioni break e continue , la famigerata istruzione goto e molti altri (questi gli elenchi sono lungi dall'essere esaustivi).

La destinazione del ramo è un altro problema importante. La maggior parte dei rami ha una destinazione di ramo fissa: vanno in una posizione specifica nel codice che viene risolta in fase di compilazione. Ciò include istruzioni if , loop di ogni tipo, chiamate di funzione regolari e molto altro. I rami calcolati calcolano la destinazione del ramo in fase di esecuzione. Ciò include le istruzioni switch (a volte), il ritorno da una funzione, le chiamate di funzione virtuale e le chiamate del puntatore di funzione.

Quindi cosa significa tutto questo per le prestazioni? Quando il processore vede apparire un'istruzione di diramazione nella sua pipeline, deve capire come continuare a riempire la sua pipeline. Per capire quali istruzioni vengono dopo il ramo nel flusso del programma, è necessario conoscere due cose: (1) se il ramo verrà preso e (2) la destinazione del ramo. Capire questo si chiama previsione del ramo ed è un problema impegnativo. Se il processore indovina correttamente, il programma continua alla massima velocità. Se invece il processore indovina in modo errato , ha impiegato poco tempo a calcolare la cosa sbagliata. Ora deve svuotare la pipeline e ricaricarla con le istruzioni dal percorso di esecuzione corretto. In conclusione: un grande successo in termini di prestazioni.

Pertanto, il motivo per cui se le dichiarazioni sono costose è dovuto a previsioni errate sulle filiali . Questo è solo al livello più basso. Se stai scrivendo un codice di alto livello, non devi preoccuparti di questi dettagli. Dovresti preoccuparti di questo solo se stai scrivendo un codice estremamente critico in C o assembly. In tal caso, la scrittura di codice senza rami può spesso essere superiore al codice che si ramifica, anche se sono necessarie più istruzioni. Ci sono alcuni trucchi interessanti che puoi fare per calcolare cose come abs () , min () e

Altri suggerimenti

" costoso " è un termine molto relativo, in particolare in relazione a un " if " dichiarazione poiché è necessario prendere in considerazione anche il costo della condizione. Ciò potrebbe variare da poche brevi istruzioni della CPU al test del risultato di una funzione che chiama un database remoto.

Non me ne preoccuperei. A meno che tu non stia eseguendo una programmazione integrata, probabilmente non dovresti preoccuparti del costo di " if " affatto. Per la maggior parte dei programmatori non sarà mai il fattore trainante delle prestazioni della tua app.

I rami, specialmente sui microprocessori con architettura RISC, sono alcune delle istruzioni più costose. Questo perché su molte architetture, il compilatore prevede quale percorso di esecuzione verrà preso molto probabilmente e inserisce quelle istruzioni nel file eseguibile, quindi saranno già nella cache della CPU quando si verifica il ramo. Se il ramo va dall'altra parte, deve tornare alla memoria principale e recuperare le nuove istruzioni: è piuttosto costoso. Su molte architetture RISC, tutte le istruzioni sono un ciclo tranne per la diramazione (che spesso è di 2 cicli). Non stiamo parlando di un costo importante qui, quindi non preoccuparti. Inoltre, il compilatore ottimizzerà meglio di te il 99% delle volte :) Una delle cose davvero fantastiche dell'architettura EPIC (Itanium è un esempio) è che memorizza nella cache (e inizia l'elaborazione) istruzioni da entrambi i lati del ramo, quindi scarta il set non necessario una volta che si conosce l'esito del ramo. Ciò consente di risparmiare l'accesso alla memoria aggiuntiva di un'architettura tipica nel caso in cui si ramifichi lungo il percorso non previsto.

Consulta l'articolo Migliori prestazioni attraverso l'eliminazione delle filiali sulle prestazioni delle celle . Un altro divertente è questo post sulle selezioni senza rami sul blog di rilevamento delle collisioni in tempo reale.

Oltre alle eccellenti risposte già pubblicate in risposta a questa domanda, vorrei ricordare che sebbene "se" le dichiarazioni sono considerate costose operazioni di basso livello, il tentativo di utilizzare tecniche di programmazione senza filiali in un ambiente di livello superiore, come un linguaggio di scripting o un livello di logica aziendale (indipendentemente dal linguaggio), può essere ridicolmente inappropriato.

La maggior parte delle volte, i programmi dovrebbero essere scritti per chiarezza prima e ottimizzati per le prestazioni in secondo luogo. Esistono numerosi domini problematici in cui le prestazioni sono di primaria importanza, ma il semplice fatto è che la maggior parte degli sviluppatori non sta scrivendo moduli da utilizzare nel profondo di un motore di rendering o una simulazione di fluidodinamica ad alte prestazioni che viene eseguita per settimane consecutive. Quando la massima priorità è che la tua soluzione sia semplicemente "funzionante" l'ultima cosa che dovresti pensare è se puoi salvare o meno il sovraccarico di un'istruzione condizionale nel tuo codice.

Al livello più basso possibile se è costituito da (dopo aver calcolato tutti i prerequisiti specifici dell'app per se ):

  • alcune istruzioni di prova
  • passa a un punto del codice se il test ha esito positivo, altrimenti procedi in avanti.

Costi associati a questo:

  • un confronto di basso livello - di solito 1 operazione CPU, super economico
  • potenziale salto - che può essere costoso

Reson perché i salti sono costosi:

  • puoi saltare al codice arbirary che vive ovunque nella memoria, se si scopre che non è memorizzato nella cache dalla cpu - abbiamo un problema, perché dobbiamo accedere alla memoria principale, che è più lenta
  • le CPU moderne eseguono la previsione del ramo. Provano a indovinare se riusciranno o meno ed eseguiranno il codice in anticipo nella pipeline, quindi accelerate le cose. Se la previsione fallisce, tutti i calcoli effettuati in anticipo dalla pipeline devono essere invalidati. Anche questa è un'operazione costosa

Quindi, per riassumere:

  • Se può essere costoso, se davvero, davvero ti preoccupi molto delle prestazioni.
  • Dovresti preoccupartene se e solo se stai scrivendo raytracer in tempo reale o simulazione biologica o qualcosa di simile. Non c'è motivo di preoccuparsene nella maggior parte del mondo reale.

se in sé è non lento. La lentezza è sempre relativa scommetto per la mia vita che non hai mai sentito il "sovraccarico" di un'istruzione if. Se hai intenzione di creare un codice ad alte prestazioni, potresti comunque voler evitare i rami. Ciò che rende if lento è che il processore sta precaricando il codice dopo il if basato su alcune euristiche e quant'altro. Impedirà inoltre alle pipeline di eseguire il codice direttamente dopo l'istruzione di ramo if nel codice macchina, poiché il processore non sa ancora quale percorso verrà intrapreso (in un processore pipeline, vengono interlacciate più istruzioni e eseguito). Il codice eseguito potrebbe essere eseguito al contrario (se è stato preso l'altro ramo. Si chiama errore nel ramo ), oppure noop deve essere riempito in quei punti in modo che non non succede.

Se if è male, allora anche switch è male, e & amp; & amp; , || pure. Non preoccuparti.

Forse la ramificazione uccide il prefetching delle istruzioni della CPU?

I processori moderni hanno condotte di esecuzione lunghe, il che significa che diverse istruzioni vengono eseguite in varie fasi contemporaneamente. Potrebbero non sempre conoscere l'esito di un'istruzione quando inizia a eseguire la successiva. Quando si imbattono in un salto condizionale (se) a volte devono aspettare fino a quando la pipeline è vuota prima di poter sapere in che direzione dovrebbe andare il puntatore dell'istruzione.

Lo considero un lungo treno merci. Può trasportare molto carico velocemente in linea retta, ma si inclina male.

Il Pentium 4 (Prescott) aveva una conduttura notoriamente lunga di 31 tappe.

Altre informazioni su Wikipedia

L'unica cosa a cui posso immaginare questo potrebbe essere il fatto che un'istruzione if in genere può provocare un ramo. A seconda delle specifiche dell'architettura del processore, i rami possono causare blocchi della pipeline o altre situazioni non ottimali.

Tuttavia, questo è estremamente specifico per la situazione: la maggior parte dei processori moderni ha capacità di previsione delle filiali che tentano di minimizzare gli effetti negativi della ramificazione. Un altro esempio potrebbe essere il modo in cui l'architettura ARM (e probabilmente altri) è in grado di gestire la logica condizionale - ARM ha un'esecuzione condizionale a livello di istruzione, quindi una logica condizionale semplice non provoca ramificazioni - le istruzioni vengono semplicemente eseguite come NOP se le condizioni non sono soddisfatte.

Detto questo, ottieni la tua logica corretta prima di preoccuparti di queste cose. Il codice errato non è ottimizzato come si può ottenere.

Come sottolineato da molti, i rami condizionali possono essere molto lenti su un computer moderno.

Detto questo, ci sono molti rami condizionali in cui non convivono le istruzioni if, non puoi sempre dire che cosa comporrà il compilatore e preoccuparti di quanto tempo impiegheranno le dichiarazioni di base praticamente sempre la cosa sbagliata da fare. (Se riesci a capire cosa genererà il compilatore in modo affidabile, potresti non avere un buon compilatore di ottimizzazione.)

Le CPU sono profondamente pipeline. Qualsiasi istruzione di ramo (if / for / while / switch / etc) significa che la CPU non sa davvero quale istruzione caricare ed eseguire successivamente.

La CPU si blocca in attesa di sapere cosa fare, oppure la CPU fa un'ipotesi. Nel caso di una CPU precedente o se l'ipotesi è errata, dovrai soffrire di uno stallo della pipeline mentre va e carica le istruzioni corrette. A seconda della CPU, questa può arrivare a 10-20 istruzioni per lo stallo.

Le CPU moderne cercano di evitarlo facendo una buona previsione del ramo e eseguendo più percorsi contemporaneamente e mantenendo solo quello effettivo. Questo aiuta molto, ma può andare solo così lontano.

Buona fortuna in classe.

Inoltre, se devi preoccuparti di questo nella vita reale, probabilmente stai facendo progettazione del sistema operativo, grafica in tempo reale, elaborazione scientifica o qualcosa di simile legato alla CPU. Profilo prima di preoccuparti.

Nota anche che all'interno di un loop non è necessariamente molto costoso.

La CPU moderna presuppone alla prima visita di un'istruzione if, che "if-body" deve essere preso (o detto nell'altro modo: presuppone anche che un corpo ad anello sia preso più volte) (*). In occasione di seconde e successive visite, la (CPU) può forse esaminare la Tabella della cronologia delle filiali e vedere come la condizione era l'ultima volta (era vera? Era falsa?). Se l'ultima volta è stato falso, l'esecuzione speculativa procederà a " else " dell'if o oltre il ciclo.

(*) La regola è in realtà " ramo in avanti non preso, ramo indietro preso " ;. In un'istruzione if, c'è solo un salto [in avanti] (al punto dopo l'if-body ) se la condizione è falsa (ricorda: la CPU comunque presuppone di non prendere un ramo / salto), ma in un ciclo, c'è forse un ramo in avanti nella posizione dopo il ciclo (da non prendere) e un ramo all'indietro dopo la ripetizione (da prendere).

Questo è anche uno dei motivi per cui una chiamata a una funzione virtuale o una funzione-pointer-call non è poi così grave come molti ipotizzano ( http://phresnel.org/blog/ )

Scrivi i tuoi programmi nel modo più chiaro, semplice e pulito che non sia ovviamente inefficiente. Quello fa il miglior uso della risorsa più costosa, tu. Sia che si tratti di scrivere o di eseguire il debug (richiede comprensione) del programma. Se le prestazioni non sono sufficienti, misura dove si trovano i colli di bottiglia e scopri come mitigarli. Solo in occasioni estremamente rare dovrai preoccuparti delle istruzioni individuali (fonte) quando lo fai. Le prestazioni riguardano la selezione degli algoritmi e delle strutture dati corretti nella prima riga, un'attenta programmazione, la realizzazione di una macchina abbastanza veloce. Usa un buon compilatore, rimarrai sorpreso quando vedi il tipo di ristrutturazione del codice che fa un compilatore moderno. La ristrutturazione del codice per le prestazioni è una sorta di misura dell'ultima risorsa, il codice diventa più complesso (quindi più buggier), più difficile da modificare e quindi più costoso.

Ho avuto questa discussione con un mio amico una volta. Stava usando un algoritmo di cerchio molto ingenuo, ma affermava che era più veloce del mio (il tipo che calcola solo 1/8 del cerchio) perché il mio usava se. Alla fine, l'istruzione if è stata sostituita con sqrt e in qualche modo è stato più veloce. Forse perché la FPU ha sqrt integrato?

Alcune CPU (come X86) forniscono la previsione del ramo a livello di programmazione per evitare tale latenza di previsione del ramo.

Alcuni compilatori espongono (come GCC) questi come estensione a linguaggi di programmazione di livello superiore (come C / C ++).

Consulta macro probabile () / improbabile () nel kernel Linux - come lavorano? Qual è il loro vantaggio? .

Il più costoso in termini di utilizzo di ALU? Utilizza i registri della CPU per memorizzare i valori da confrontare e richiede tempo per recuperare e confrontare i valori ogni volta che viene eseguita l'istruzione if.

Pertanto, un'ottimizzazione di ciò consiste nel fare un confronto e memorizzare il risultato come variabile prima dell'esecuzione del ciclo.

Sto solo cercando di interpretare le tue parole mancanti.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top