Cosa è più efficiente? Usando pow per quadrare o semplicemente moltiplicarlo con se stesso?

Quale di questi due metodi è più efficace in C? E che dire:

pow(x,3) 

vs.

 x*x*x // etc? 

Ho provato la differenza di prestazioni tra x*x*... vs pow(x,i) per i piccoli usando questo codice:

 #include  #include  #include  inline boost::posix_time::ptime now() { return boost::posix_time::microsec_clock::local_time(); } #define TEST(num, expression) \ double test##num(double b, long loops) \ { \ double x = 0.0; \ \ boost::posix_time::ptime startTime = now(); \ for (long i=0; i double testpow(double base, long loops) { double x = 0.0; boost::posix_time::ptime startTime = now(); for (long i=0; i(rand(), loops); x += test1(rand(), loops); cout < < "\n2 "; x += testpow<2>(rand(), loops); x += test2(rand(), loops); cout < < "\n3 "; x += testpow<3>(rand(), loops); x += test3(rand(), loops); cout < < "\n4 "; x += testpow<4>(rand(), loops); x += test4(rand(), loops); cout < < "\n5 "; x += testpow<5>(rand(), loops); x += test5(rand(), loops); cout < < "\n" << x << "\n"; } 

I risultati sono:

 1 00:00:01.126008 00:00:01.128338 2 00:00:01.125832 00:00:01.127227 3 00:00:01.125563 00:00:01.126590 4 00:00:01.126289 00:00:01.126086 5 00:00:01.126570 00:00:01.125930 2.45829e+54 

Nota che accumulo il risultato di ogni calcolo del Pow per assicurarmi che il compilatore non lo ottimizzi.

Se uso la versione std::pow(double, double) e loops = 1000000l , ottengo:

 1 00:00:00.011339 00:00:00.011262 2 00:00:00.011259 00:00:00.011254 3 00:00:00.975658 00:00:00.011254 4 00:00:00.976427 00:00:00.011254 5 00:00:00.973029 00:00:00.011254 2.45829e+52 

Questo è su un Intel Core Duo con Ubuntu 9.10 a 64 bit. Compilato usando gcc 4.4.1 con l'ottimizzazione di -o2.

Quindi in C, sì x*x*x sarà più veloce di pow(x, 3) , perché non c'è sovraccarico di pow(double, int) . In C ++, sarà più o meno lo stesso. (Supponendo che la metodologia nei miei test sia corretta).


Questo è in risposta al commento fatto da An Markm:

Anche se è stata emessa una direttiva using namespace std , se il secondo parametro di pow è un int , allora il sovraccarico std::pow(double, int) da verrà chiamato invece di ::pow(double, double) da

.

Questo codice di test conferma questo comportamento:

 #include  namespace foo { double bar(double x, int i) { std::cout < < "foo::bar\n"; return x*i; } } double bar(double x, double y) { std::cout << "::bar\n"; return x*y; } using namespace foo; int main() { double a = bar(1.2, 3); // Prints "foo::bar" std::cout << a << "\n"; return 0; } 

Questo è il tipo sbagliato di domanda. La domanda giusta sarebbe: “Qual è più facile da capire per i lettori umani del mio codice?”

Se la velocità conta (più tardi), non chiedere, ma misurare. (E prima di questo, valuta se l’ottimizzazione di questo effettivamente farà una differenza evidente.) Fino ad allora, scrivi il codice in modo che sia più facile da leggere.

modificare
Giusto per renderlo chiaro (anche se avrebbe dovuto essere già stato): gli speed-through di solito provengono da cose come l’ utilizzo di algoritmi migliori , il miglioramento della localizzazione dei dati , la riduzione dell’uso della memoria dynamic , i risultati pre-calcolo , ecc. Raramente provengono da micro -ottimizzare le chiamate a singola funzione , e dove lo fanno, lo fanno in pochissimi posti , che potrebbero essere trovati solo con una profilazione attenta (e dispendiosa in termini di tempo), più spesso che mai possono essere accelerati facendo cose non intuitive (come l’inserimento di istruzioni noop ), e ciò che è un’ottimizzazione per una piattaforma a volte è una pessimizzazione per un’altra (motivo per cui è necessario misurare, invece di chiedere, perché non conosciamo pienamente / l’ambiente).

Vorrei sottolineare ancora una volta: anche nelle poche applicazioni in cui queste cose sono importanti, non contano nella maggior parte dei posti in cui vengono utilizzate, ed è molto improbabile che troviate i luoghi in cui contano osservando il codice. Hai davvero bisogno di identificare prima i punti caldi , perché altrimenti l’ottimizzazione del codice è solo una perdita di tempo .

Anche se una singola operazione (come il calcolo del quadrato di un certo valore) occupa il 10% del tempo di esecuzione dell’applicazione (il quale è piuttosto raro), e anche se l’ottimizzazione consente di risparmiare il 50% del tempo necessario per tale operazione (quale IME è anche molto, molto più raro), hai comunque reso l’applicazione solo il 5% in meno di tempo .
I tuoi utenti avranno bisogno di un cronometro per accorgersene. (Suppongo che nella maggior parte dei casi qualsiasi aumento del 20% non passi inosservato per la maggior parte degli utenti. E questo è quattro di questi punti che devi trovare.)

x*x o x*x*x sarà più veloce di pow , dato che pow deve occuparsi del caso generale, mentre x*x è specifico. Inoltre, puoi scegliere la chiamata alla funzione e simili.

Tuttavia, se ti ritrovi a micro-ottimizzare in questo modo, devi ottenere un profiler e fare una seria profilazione. La schiacciante probabilità è che non noterai mai alcuna differenza tra i due.

Mi stavo anche chiedendo il problema delle prestazioni, e speravo che questo sarebbe stato ottimizzato dal compilatore, basato sulla risposta di @ EmileCormier. Tuttavia, ero preoccupato che il codice di test che mostrava permettesse al compilatore di ottimizzare la chiamata std :: pow (), poiché ogni volta venivano utilizzati gli stessi valori nella chiamata, il che avrebbe consentito al compilatore di memorizzare i risultati e riutilizzarlo nel ciclo – questo spiegherebbe i tempi di esecuzione quasi identici per tutti i casi. Quindi ho dato un’occhiata anche a questo.

Ecco il codice che ho usato (test_pow.cpp):

 #include  #include  #include  class Timer { public: explicit Timer () : from (std::chrono::high_resolution_clock::now()) { } void start () { from = std::chrono::high_resolution_clock::now(); } double elapsed() const { return std::chrono::duration_cast(std::chrono::high_resolution_clock::now() - from).count() * 1.0e-6; } private: std::chrono::high_resolution_clock::time_point from; }; int main (int argc, char* argv[]) { double total; Timer timer; total = 0.0; timer.start(); for (double i = 0.0; i < 1.0; i += 1e-8) total += std::pow (i,2); std::cout << "std::pow(i,2): " << timer.elapsed() << "s (result = " << total << ")\n"; total = 0.0; timer.start(); for (double i = 0.0; i < 1.0; i += 1e-8) total += i*i; std::cout << "i*i: " << timer.elapsed() << "s (result = " << total << ")\n"; std::cout << "\n"; total = 0.0; timer.start(); for (double i = 0.0; i < 1.0; i += 1e-8) total += std::pow (i,3); std::cout << "std::pow(i,3): " << timer.elapsed() << "s (result = " << total << ")\n"; total = 0.0; timer.start(); for (double i = 0.0; i < 1.0; i += 1e-8) total += i*i*i; std::cout << "i*i*i: " << timer.elapsed() << "s (result = " << total << ")\n"; return 0; } 

Questo è stato compilato utilizzando:

 g++ -std=c++11 [-O2] test_pow.cpp -o test_pow 

Fondamentalmente, la differenza è l'argomento per std :: pow () è il contatore del ciclo. Come temevo, la differenza nelle prestazioni è pronunciata. Senza il flag -O2, i risultati sul mio sistema (Arch Linux 64-bit, g ++ 4.9.1, Intel i7-4930) erano:

 std::pow(i,2): 0.001105s (result = 3.33333e+07) i*i: 0.000352s (result = 3.33333e+07) std::pow(i,3): 0.006034s (result = 2.5e+07) i*i*i: 0.000328s (result = 2.5e+07) 

Con l'ottimizzazione, i risultati sono stati ugualmente sorprendenti:

 std::pow(i,2): 0.000155s (result = 3.33333e+07) i*i: 0.000106s (result = 3.33333e+07) std::pow(i,3): 0.006066s (result = 2.5e+07) i*i*i: 9.7e-05s (result = 2.5e+07) 

Quindi sembra che il compilatore cerchi almeno di ottimizzare il caso std :: pow (x, 2), ma non il caso std :: pow (x, 3) (ci vogliono circa 40 volte di più rispetto a std :: pow (x, 2) caso). In tutti i casi, l'espansione manuale ha funzionato meglio, ma in particolare per il caso power 3 (60 volte più veloce). Questo vale sicuramente la pena di tenere presente se esegui std :: pow () con potenze intere maggiori di 2 in un loop stretto ...

Il modo più efficace è considerare la crescita esponenziale delle moltiplicazioni. Controlla questo codice per p ^ q:

 template  T expt(T p, unsigned q){ T r =1; while (q != 0) { if (q % 2 == 1) { // if q is odd r *= p; q--; } p *= p; q /= 2; } return r; } 

Se l’esponente è costante e piccolo, espanderlo, riducendo al minimo il numero di moltiplicazioni. (Ad esempio, x^4 non è ottimamente x*x*x*x , ma y*y dove y=x*x . E x^5 è y*y*x dove y=x*x . E così via. ) Per gli esponenti interi costanti, scrivi già la forma ottimizzata; con piccoli esponenti, questa è una ottimizzazione standard che dovrebbe essere eseguita indipendentemente dal fatto che il codice sia stato profilato o meno. La forma ottimizzata sarà più veloce in una percentuale così ampia di casi che in pratica vale sempre la pena farlo.

(Se si utilizza Visual C ++, std::pow(float,int) esegue l’ottimizzazione a cui alludo, per cui la sequenza di operazioni è correlata al modello di bit dell’esponente. Non garantisco che il compilatore srotolerà il ciclo per tu, però, quindi vale comunque la pena farlo a mano.)

[modifica] BTW pow ha una tendenza (non) sorprendente a spuntare sui risultati del profiler. Se non ne hai assolutamente bisogno (cioè, l’esponente è big o non costante), e sei del tutto preoccupato per le prestazioni, quindi meglio scrivere il codice ottimale e attendere che il profiler ti dica che è (sorprendentemente ) perdere tempo prima di pensare ulteriormente. (L’alternativa è chiamare pow e pow al profiler di dirti che è (non sorprendentemente) perdere tempo – stai tagliando questo passaggio facendolo in modo intelligente.)