Conto alla rovescia per i for-loop

StackOverflow https://stackoverflow.com/questions/804777

  •  03-07-2019
  •  | 
  •  

Domanda

Credo (da alcune letture di ricerca) che il conto alla rovescia nei for-loop sia effettivamente più efficiente e più veloce in fase di esecuzione. Il mio codice software completo è C ++

Al momento ho questo: 

for (i=0; i<domain; ++i) {

la mia 'i' non è firmata resgister int, anche 'domain' è unsigned int

nel for-loop i viene utilizzato per passare attraverso un array, ad esempio 

array[i] = do stuff

convertendolo per il conto alla rovescia incasina l'output previsto / corretto della mia routine.

Posso immaginare che la risposta sia piuttosto banale, ma non riesco a girarci intorno.

AGGIORNAMENTO: 'fare cose' non dipende dall'iterazione precedente o successiva. I calcoli all'interno del for-loop sono indipendenti per quella iterazione di i. (Spero che abbia un senso).

AGGIORNAMENTO: Per ottenere una velocità di runtime con il mio for-loop, conto alla rovescia e in tal caso rimuovo la parte non firmata durante il delcaring del mio int o quale altro metodo?

Per favore aiutate.

È stato utile?

Soluzione

Immagino che il tuo backward per loop assomigli a questo: 

for (i = domain - 1; i >= 0; --i) {

In tal caso, poiché i è non firmato , sarà sempre maggiore o uguale a zero. Quando decrementi una variabile senza segno che è uguale a zero, si avvolgerà su un numero molto grande. La soluzione è o rendere i firmato, o modificare la condizione nel ciclo for in questo modo: 

for (i = domain - 1; i >= 0 && i < domain; --i) {

Oppure conta da dominio a 1 anziché da domain - 1 a 0 : 

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

Altri suggerimenti

Esiste un solo metodo corretto per eseguire il looping all'indietro utilizzando un contatore senza segno: 

for( i = n; i-- > 0; )
{
    // Use i as normal here
}

C'è un trucco qui, per l'ultima iterazione del loop avrai i = 1 nella parte superiore del loop, i-- > 0 passa perché 1 > 0, quindi i = 0 nel corpo del loop. Alla prossima iterazione i-- > 0 fallisce perché i == 0, quindi non importa che il decremento postfix sia passato sul contatore.

Lo so non molto ovvio.

Questa non è una risposta al tuo problema, perché sembra che tu non abbia un problema.

Questo tipo di ottimizzazione è completamente irrilevante e dovrebbe essere lasciato al compilatore (se fatto affatto).

Hai profilato il tuo programma per verificare che il tuo for-loop sia un collo di bottiglia? In caso contrario, non è necessario passare il tempo a preoccuparsi di questo. Ancora di più, avendo " i " come "registro" int, mentre scrivi, non ha alcun senso dal punto di vista delle prestazioni.

Anche senza conoscere il tuo dominio problematico, ti posso garantire che sia la tecnica di reverse-loop che il "registro" Il contatore int avrà un impatto trascurabile sulle prestazioni del programma. Ricorda, "l'ottimizzazione prematura è la radice di tutti i mali".

Detto questo, il tempo di ottimizzazione impiegato meglio sarebbe pensare alla struttura generale del programma, alle strutture dati e agli algoritmi utilizzati, all'utilizzo delle risorse, ecc.

Controllare se un numero è zero può essere più veloce o più efficiente di un confronto. Ma questo è il tipo di micro-ottimizzazione di cui non dovresti davvero preoccuparti: alcuni cicli di clock saranno notevolmente sminuiti da qualsiasi altro problema di perf.

Su x86: 

dec eax
jnz Foo

Invece di: 

inc eax
cmp eax, 15
jl Foo

Se hai un compilatore decente, ottimizzerà " contando " altrettanto efficacemente come "contare alla rovescia". Prova alcuni benchmark e vedrai.

Quindi " leggi " che il downgrade è più efficiente? Lo trovo molto difficile da credere se non mi mostri alcuni risultati del profiler e il codice. Posso acquistarlo in alcune circostanze, ma nel caso generale, no. Mi sembra che questo sia un classico caso di ottimizzazione prematura.

Il tuo commento su " registrati int i " è anche molto significativo. Al giorno d'oggi, il compilatore sa sempre meglio di te come allocare i registri. Non preoccuparti di usare la parola chiave register a meno che tu non abbia profilato il tuo codice.

Quando esegui il looping di strutture di dati di qualsiasi tipo, gli errori nella cache hanno un impatto molto maggiore rispetto alla direzione in cui stai andando. Preoccupati di avere un quadro più ampio del layout della memoria e della struttura dell'algoritmo invece di banali microottimizzazioni.

Non ha nulla a che fare con il conteggio su o giù . Ciò che può essere più veloce è contare verso zero . La risposta di Michael mostra perché & # 8212; x86 ti offre un confronto con zero come effetto collaterale implicito di molte istruzioni, quindi dopo aver regolato il tuo contatore, devi solo ramificare in base al risultato invece di fare un confronto esplicito. (Forse lo fanno anche altre architetture; non lo so.)

I compilatori Pascal di Borland sono noti per eseguire tale ottimizzazione. Il compilatore trasforma questo codice: 

for i := x to y do
  foo(i);

in una rappresentazione interna più simile a questa: 

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

(dico notoriamente non perché l'ottimizzazione influisce sull'esito del ciclo, ma perché il debugger visualizza la variabile del contatore in modo errato. Quando il programmatore controlla i , il debugger può visualizzare il valore di tmp invece, senza provocare confusione e panico per i programmatori che pensano che i loro loop stiano procedendo all'indietro.)

L'idea è che anche con le istruzioni extra Inc o Dec , è ancora una vittoria netta, in termini di tempo di esecuzione, rispetto a un confronto esplicito. Se puoi effettivamente notare che la differenza è in discussione.

Ma nota che la conversione è qualcosa che il compilatore farebbe automaticamente , a seconda che ritenesse utile la trasformazione. Il compilatore di solito è più bravo nell'ottimizzare il codice di te, quindi non spendere troppo sforzo per competere con esso.

Comunque, hai chiesto di C ++, non di Pascal. C ++ "per" i loop non sono altrettanto facili da applicare a quell'ottimizzazione come Pascal "per" i loop sono perché i limiti dei loop di Pascal sono sempre calcolati completamente prima dell'esecuzione del loop, mentre i loop C ++ a volte dipendono dalla condizione di arresto e dal contenuto del loop. I compilatori C ++ devono eseguire una certa quantità di analisi statiche per determinare se un determinato ciclo può soddisfare i requisiti per il tipo di trasformazione per cui i loop di Pascal sono idonei incondizionatamente. Se il compilatore C ++ esegue l'analisi, potrebbe eseguire una trasformazione simile.

Non c'è niente che ti impedisce di scrivere i tuoi loop in questo modo da solo: 

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

In questo modo potrebbe velocizzare l'esecuzione del codice. Come ho detto prima, però, probabilmente non te ne accorgerai. Il costo maggiore che paghi organizzando manualmente i tuoi loop in questo modo è che il tuo codice non segue più i modi di dire stabiliti. Il tuo loop è un " per " perfettamente ordinario loop, ma non sembra come uno & # 8212; ha due variabili, contano in direzioni opposte e una di esse non è nemmeno usata nel corpo del loop & # 8212; quindi chiunque legga il tuo codice (incluso te, una settimana, un mese o un anno da quando hai dimenticato la "ottimizzazione" che speravi di ottenere) dovrà fare uno sforzo extra per dimostrare a se stesso che il ciclo è davvero un normale ciclo sotto mentite spoglie.

(Hai notato che il mio codice sopra utilizzava variabili senza segno senza il pericolo di andare a zero? L'uso di due variabili separate lo consente.)

Tre cose da togliere a tutto questo:

  1. Lascia che l'ottimizzatore faccia il suo lavoro; nel complesso è meglio di te.
  2. Rendi il codice ordinario un aspetto ordinario in modo che il codice speciale non debba competere per attirare l'attenzione delle persone che lo revisionano, eseguono il debug o lo mantengono.
  3. Non fare nulla di speciale in nome della performance fino a quando il test e la profilazione lo dimostrano necessario.

Puoi provare quanto segue, che il compilatore ottimizzerà in modo molto efficiente: 

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

Ora puoi usarlo: 

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

Puoi iterare in qualsiasi direzione: 

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

Il ciclo 

for_range (unsigned,i,b,a)
{
   // body of the loop
}

produrrà il seguente codice: 

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1

Difficile dirlo con le informazioni fornite ma ... invertire l'array e fare il conto alla rovescia?

Jeremy Ruten ha giustamente sottolineato che l'uso di un contatore di loop senza segno è pericoloso. È anche inutile, per quanto ne so.

Altri hanno anche sottolineato i pericoli dell'ottimizzazione prematura. Hanno assolutamente ragione.

Detto questo, ecco uno stile che ho usato durante la programmazione di sistemi embedded molti anni fa, quando ogni byte e ogni ciclo contavano qualcosa. Questi moduli mi sono stati utili su particolari CPU e compilatori che stavo usando, ma il tuo chilometraggio può variare. 

// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
     *p-- = (... whatever ...)
}

Questo modulo sfrutta il flag di condizione impostato su alcuni processori dopo operazioni aritmetiche - su alcune architetture, il decremento e il test per la condizione di diramazione possono essere combinati in un'unica istruzione. Nota che usare predecrement ( --i ) è la chiave qui - usare postdecrement ( i-- ) non avrebbe funzionato altrettanto bene.

In alternativa, 

// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
     *(--p) = (... whatever ...)
}

Questa seconda forma sfrutta l'aritmetica del puntatore (indirizzo). Raramente vedo il modulo (pointer - int) in questi giorni (per una buona ragione), ma la lingua garantisce che quando sottrai un int da un puntatore, il puntatore viene decrementato di (int * sizeof (* pointer)) .

Sottolineerò di nuovo che se questi moduli sono una vittoria per te dipende dalla CPU e dal compilatore che stai utilizzando. Mi hanno servito bene su architetture Motorola 6809 e 68000.

In alcuni successivi arm armes, decrementa e confronta richiede solo una singola istruzione. Ciò rende i loop decrescenti più efficienti di quelli incrementali.

Non so perché non ci siano anche istruzioni per confrontare gli incrementi.

Sono sorpreso che questo post sia stato votato -1 quando è un vero problema.

Tutti qui si stanno concentrando sulle prestazioni. Esiste effettivamente un motivo logico per scorrere verso lo zero che può risultare in un codice più pulito.

L'iterazione prima dell'ultimo elemento è utile quando si eliminano elementi non validi scambiando con la fine dell'array. Per elementi danneggiati non adiacenti all'estremità, possiamo passare alla posizione finale, ridurre il limite finale dell'array e continuare a ripetere. Se dovessi iterare verso la fine, lo scambio con la fine potrebbe comportare lo scambio male in male. Con iterando end su 0 sappiamo che l'elemento alla fine dell'array si è già dimostrato valido per questa iterazione.

Per ulteriori spiegazioni ...

Se:

  1. Elimina gli elementi danneggiati scambiando con un'estremità dell'array e modificando i limiti dell'array per escludere gli elementi errati.

Quindi ovviamente:

  1. Dovresti scambiare con un buon elemento, cioè uno che è già stato testato in questa iterazione.

Quindi questo implica:

  1. Se eseguiamo iterazioni lontano dal limite della variabile, gli elementi tra il limite della variabile e il puntatore dell'iterazione corrente si sono dimostrati validi. Se il puntatore all'iterazione ottiene ++ o - non importa. Ciò che conta è che stiamo iterando lontano dal limite della variabile, quindi sappiamo che gli elementi adiacenti sono buoni.

Quindi finalmente:

  1. L'iterazione verso 0 ci consente di utilizzare solo una variabile per rappresentare i limiti dell'array. Se questo è importante è una decisione personale tra te e il tuo compilatore.

Ciò che conta molto di più se si sta aumentando o diminuendo il contatore è se si va o meno nella memoria. La maggior parte delle cache sono ottimizzate per aumentare la memoria, non la memoria. Poiché il tempo di accesso alla memoria è il collo di bottiglia che la maggior parte dei programmi oggi deve affrontare, ciò significa che cambiare il programma in modo da aumentare la memoria può comportare un aumento delle prestazioni anche se ciò richiede il confronto del contatore con un valore diverso da zero. In alcuni dei miei programmi, ho visto un miglioramento significativo delle prestazioni modificando il mio codice per aumentare la memoria anziché scaricarla.

Scettico? Ecco l'output che ho ottenuto: 

sum up   = 705046256
sum down = 705046256
Ave. Up Memory   = 4839 mus
Ave. Down Memory =  5552 mus
sum up   = inf
sum down = inf
Ave. Up Memory   = 18638 mus
Ave. Down Memory =  19053 mus

dall'esecuzione di questo programma: 

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
  std::random_device rnd_device;
  std::mt19937 generator(rnd_device());
  std::uniform_int_distribution<T> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
  std::random_device rnd_device;
  std::mt19937_64 generator(rnd_device());
  std::uniform_real_distribution<double> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = one_past_last;
  do {
    it--;
    sum += *it;
  } while (it != first);
  total += sum;
}

template<class T> std::chrono::nanoseconds TimeDown(
                      std::vector<T> &vec, const std::vector<T> &vec_original,
                      std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_down(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class T> std::chrono::nanoseconds TimeUp(
                      std::vector<T> &vec, const std::vector<T> &vec_original,
                      std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_up(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  {
  typedef int ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  {
  typedef double ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  return 0;
}

Sia sum_abs_up che sum_abs_down fanno la stessa cosa e sono cronometrati allo stesso modo con l'unica differenza che sum_abs_up va in memoria mentre < code> sum_abs_down si esaurisce la memoria. Passo persino vec in modo che entrambe le funzioni accedano alle stesse posizioni di memoria. Tuttavia, sum_abs_up è costantemente più veloce di sum_abs_down . Provalo tu stesso (l'ho compilato con g ++ -O3).

FYI vec_original è lì per la sperimentazione, per farmi cambiare facilmente sum_abs_up e sum_abs_down in un modo che li fa cambiare < code> vec senza consentire a queste modifiche di influire sui tempi futuri.

È importante notare quanto sia stretto il loop che sto programmando. Se il corpo di un ciclo è grande, probabilmente non importerà se il suo iteratore sale o scende, poiché il tempo necessario per eseguire il corpo del ciclo probabilmente dominerà completamente. Inoltre, è importante ricordare che con alcuni loop rari, a volte la memoria è più veloce che salirla. Ma anche con tali loop raramente succede che salire sia sempre più lento di scendere (diversamente dai loop che vanno in memoria, che molto spesso sono sempre più veloci degli equivalenti loop di memoria insufficiente; una manciata di volte erano addirittura 40 +% più veloce).

Il punto è, come regola empirica, se hai l'opzione, se il corpo del loop è piccolo, e se c'è poca differenza tra il fatto che il tuo loop salga la memoria invece che verso il basso, allora dovresti aumentare la memoria.

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