Какой из этих двух методов более эффективен в C? И как насчет:
pow(x,3)
против.
x*x*x // etc?
Что более эффективно? Используя pow для квадрата или просто умножьте его на себя?
Ответ 1
Я тестировал разницу в производительности между x*x*... vs pow(x,i) для небольших i с помощью этого кода:
#include <cstdlib>
#include <cmath>
#include <boost/date_time/posix_time/posix_time.hpp>
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<loops; ++i) \
{ \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
x += expression; \
} \
boost::posix_time::time_duration elapsed = now() - startTime; \
\
std::cout << elapsed << " "; \
\
return x; \
}
TEST(1, b)
TEST(2, b*b)
TEST(3, b*b*b)
TEST(4, b*b*b*b)
TEST(5, b*b*b*b*b)
template <int exponent>
double testpow(double base, long loops)
{
double x = 0.0;
boost::posix_time::ptime startTime = now();
for (long i=0; i<loops; ++i)
{
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
x += std::pow(base, exponent);
}
boost::posix_time::time_duration elapsed = now() - startTime;
std::cout << elapsed << " ";
return x;
}
int main()
{
using std::cout;
long loops = 100000000l;
double x = 0.0;
cout << "1 ";
x += testpow<1>(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";
}
Результаты:
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
Обратите внимание, что я накапливаю результат каждого вычисления pow, чтобы убедиться, что компилятор не оптимизирует его.
Если я использую версию std::pow(double, double) и loops = 1000000l, я получаю:
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
Это на Intel Core Duo под управлением Ubuntu 9.10 64bit. Скомпилирован с использованием gcc 4.4.1 с оптимизацией -o2.
Итак, в C да x*x*x будет быстрее, чем pow(x, 3), потому что перегрузка pow(double, int) отсутствует. В С++ он будет примерно таким же. (Предполагая, что методология в моем тестировании верна.)
Это ответ на комментарий, сделанный An Markm:
Даже если была выпущена директива using namespace std, если второй параметр pow является int, тогда вместо ::pow(double, double) из <math.h> будет вызываться перегрузка std::pow(double, int) из <cmath>.
Этот тестовый код подтверждает это поведение:
#include <iostream>
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;
}
Ответ 2
Это неправильный вопрос. Правильный вопрос: "Какой из них легче понять для читателей моего кода?"
Если скорость имеет значение (позже), не спрашивайте, а измерьте. (И до этого измерьте, будет ли оптимизация этого на самом деле иметь какую-либо заметную разницу.) До тех пор напишите код, чтобы его было легче всего читать.
Edit
Просто, чтобы сделать это ясно (хотя это уже должно было быть): ускорение ускорения обычно происходит от таких вещей, как , используя лучшие алгоритмы, улучшая локальность данных, сокращая использование динамической памяти, результатов предварительного вычисления и т.д. Они редко когда-либо происходят из микрооптимизируемых вызовов одной функции, и там, где они это делают, они делают это в очень мало мест, которые можно найти только тщательный (и отнимающий много времени) профилирование, чаще, чем никогда, их нельзя ускорить делая очень неинтуитивные вещи (например, вставляя операторы noop) и что оптимизация для одной платформы иногда является пессимизацией для другой (поэтому вам нужно измерять, а не спрашивать, потому что мы не полностью знаем/имеем вашей среды).
Позвольте мне еще раз подчеркнуть это: даже в тех немногих приложениях, где такие вещи имеют значение, в большинстве случаев они не имеют значения, а маловероятно, что вы найдете места, где они имеют значение, глядя на код. Вам действительно нужно идентифицировать горячие точки сначала, потому что в противном случае оптимизация кода просто пустая трата времени.
Даже если одна операция (например, вычисление квадрата какого-либо значения) занимает 10% времени выполнения приложения (что IME довольно редко), и даже если оптимизация сохраняет 50% времени, необходимого для этой операции (какой IME еще много, гораздо реже), вы все равно сделали приложение всего на 5% меньше времени.
Вашим пользователям потребуется секундомер, чтобы даже заметить это. (Я думаю, что в большинстве случаев для большинства пользователей ничего не происходит до 20% ускорения, и это четыре таких места, которые вам нужно найти.)
Ответ 3
x*x или x*x*x будет быстрее, чем pow, так как pow должен иметь дело с общим случаем, тогда как x*x является специфическим. Кроме того, вы можете исключить вызов функции и тому подобное.
Однако, если вы обнаружите микрооптимизацию таким образом, вам нужно получить профилировщик и провести серьезное профилирование. Подавляющая вероятность, что вы никогда не заметите никакой разницы между ними.
Ответ 4
Мне также было интересно узнать о проблеме с производительностью, и надеялся, что это будет оптимизировано компилятором на основе ответа от @EmileCormier. Тем не менее, я был обеспокоен тем, что тестовый код, который он показал, все равно позволит компилятору оптимизировать вызов std:: pow(), поскольку каждый раз в этом вызове использовались одни и те же значения, которые позволяли компилятору сохранять результаты и повторно использовать его в цикле - это объясняет почти идентичные времена выполнения для всех случаев. Поэтому я тоже изучил это.
Здесь код, который я использовал (test_pow.cpp):
#include <iostream>
#include <cmath>
#include <chrono>
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::milliseconds>(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;
}
Это было скомпилировано с помощью:
g++ -std=c++11 [-O2] test_pow.cpp -o test_pow
В принципе, разница в аргументе std:: pow() - это счетчик циклов. Как я боялся, разница в производительности выражена. Без флага -O2 результаты в моей системе (Arch Linux 64-bit, g++ 4.9.1, Intel i7-4930) были:
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)
С оптимизацией результаты были одинаково впечатляющими:
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)
Итак, похоже, что компилятор хотя бы попытается оптимизировать случай std:: pow (x, 2), но не случай std:: pow (x, 3) (требуется ~ 40 раз дольше, чем std:: pow (x, 2) случай). Во всех случаях ручное расширение выполнялось лучше - но особенно для случая с мощностью 3 (в 60 раз быстрее). Это определенно стоит иметь в виду, если запустить std:: pow() с целыми степенями больше 2 в узком цикле...
Ответ 5
Наиболее эффективным способом является рассмотрение экспоненциального роста умножений. Проверьте этот код для p ^ q:
template <typename T>
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;
}
Ответ 6
Если показатель постоянный и малый, расширьте его, минимизируя количество умножений. (Например, x^4 не оптимально x*x*x*x, но y*y где y=x*x. И x^5 есть y*y*x где y=x*x. И так далее.) Для константных целочисленных показателей просто напишите уже оптимизированная форма; с небольшими показателями, это стандартная оптимизация, которая должна выполняться независимо от того, был ли код профилирован или нет. Оптимизированная форма будет быстрее в таком большом проценте случаев, что она в основном всегда стоит делать.
(Если вы используете Visual С++, std::pow(float,int) выполняет оптимизацию, на которую ссылаюсь, в которой последовательность операций связана с битовой диаграммой экспоненты. Я не гарантирую, что компилятор будет разворачивать цикл для вас, хотя, поэтому по-прежнему стоит делать это вручную.)
[edit] BTW pow имеет (un) удивительную тенденцию к появлению результатов профилирования. Если вам это совсем не нужно (т.е. Показатель большой или не постоянный), и вас вообще беспокоит производительность, то лучше всего выписать оптимальный код и дождаться, когда профайлер скажет вам об этом (на удивление ) тратить время, прежде чем думать дальше. (Альтернативой является вызов pow и профайлер рассказать вам об этом (неудивительно) тратить время - вы вырезаете этот шаг, делая это разумно.)
Ответ 7
Я был занят с подобной проблемой, и я весьма озадачен результатами. Я вычислял x⁻³/² для ньютоновской гравитации в ситуации с n телами (ускорение от другого тела с массой M, расположенного на векторе расстояния d): a = MG d*(d²)⁻³/² (где d² это точечное (скалярное) произведение d само по себе), и я подумал, что вычисление M*G*pow(d2, -1.5) будет проще, чем M*G/d2/sqrt(d2)
Хитрость заключается в том, что это верно для небольших систем, но по мере увеличения размера систем M*G/d2/sqrt(d2) становится более эффективным, и я не понимаю, почему размер системы влияет на этот результат, потому что повторение операции на разных данных нет. Это как если бы были возможные оптимизации по мере роста системы, но которые невозможны с pow
