Почему рекурсивная версия функции будет быстрее, чем итеративная в C?

Question

Я проверяю разницу между двумя реализациями градиентного спуска, я предполагал, что после оптимизации компилятора обе версии алгоритма будут эквивалентны.

Для моего удивления рекурсивная версия была значительно быстрее. Я не отбрасываю фактический дефект ни на одну из версий, ни даже на то, как я измеряю время. Можете ли вы, ребята, рассказать мне, пожалуйста?

Это мой код:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
#include <stdint.h> 

double f(double x) 
{ 
     return 2*x; 
} 

double descgrad(double xo, double xnew, double eps, double precision) 
{ 
//  printf("step ... x:%f Xp:%f, delta:%f\n",xo,xnew,fabs(xnew - xo)); 

     if (fabs(xnew - xo) < precision) 
     { 
       return xnew; 
     } 
     else 
     { 
       descgrad(xnew, xnew - eps*f(xnew), eps, precision); 
     } 
} 

double descgraditer(double xo, double xnew, double eps, double precision) 
{ 
     double Xo = xo; 
     double Xn = xnew; 

     while(fabs(Xn-Xo) > precision) 
     { 
       //printf("step ... x:%f Xp:%f, delta:%f\n",Xo,Xn,fabs(Xn - Xo)); 
       Xo = Xn; 
       Xn = Xo - eps * f(Xo); 
     } 

     return Xn; 
} 

int64_t timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p) 
{ 
    return ((timeA_p->tv_sec * 1000000000) + timeA_p->tv_nsec) - 
      ((timeB_p->tv_sec * 1000000000) + timeB_p->tv_nsec); 
} 

int main() 
{ 
     struct timespec s1, e1, s2, e2; 

     clock_gettime(CLOCK_MONOTONIC, &s1); 
     printf("Minimum : %f\n",descgraditer(100,99,0.01,0.00001)); 
     clock_gettime(CLOCK_MONOTONIC, &e1); 

     clock_gettime(CLOCK_MONOTONIC, &s2); 
     printf("Minimum : %f\n",descgrad(100,99,0.01,0.00001)); 
     clock_gettime(CLOCK_MONOTONIC, &e2); 

     uint64_t dif1 = timespecDiff(&e1,&s1)/1000; 
     uint64_t dif2 = timespecDiff(&e2,&s2)/1000; 

     printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2))); 

     printf("End. \n"); 
} 

Я компиляции с GCC 4.5.2 на Ubuntu 11.04 со следующими параметрами: НКУ grad.c -O3 -lrt -о дг

Выход мой код:

Minimum : 0.000487 
Minimum : 0.000487 
time_iter:127 ms, time_rec:19 ms, ratio (dif1/dif2) :6.68421 
End. 

я прочитал нить, которая также спросить о рекурсивной версии алгоритма был быстрее, чем повторяющийся. Объяснение в том, что, будучи рекурсивной версией, использующей стек, а другая версия с использованием некоторых векторов, доступ к куче замедлял итеративную версию. Но в этом случае (в лучшем смысле) я просто использую стек в обоих случаях.

Я что-то упустил? Что-нибудь очевидное, что я не вижу? Мой способ измерить время не так? Какие-нибудь идеи?

EDIT: Тайна решена в комментарии. Как сказал @TonyK, инициализация printf замедляла первое выполнение. Извините, что я пропустил эту очевидную вещь.

BTW, код компилируется сразу же без предупреждений. Я не думаю, что «возвращение descgrad (..» необходимо, так как условие остановки происходит до того

Answer 1

Я скомпилировал и запустил ваш код локально. Перемещение printf вне временного блока делает обе версии выполняться в ~ 5 мс каждый раз.

Итак, центральная ошибка в вашем времени заключается в том, что вы измеряете сложный зверь printf, и его время выполнения затмевает код, который вы на самом деле пытаетесь измерить.

Мой main() -функции теперь выглядит следующим образом:

int main() { 
    struct timespec s1, e1, s2, e2; 

    double d = 0.0; 

    clock_gettime(CLOCK_MONOTONIC, &s1); 
    d = descgraditer(100,99,0.01,0.00001); 
    clock_gettime(CLOCK_MONOTONIC, &e1); 
    printf("Minimum : %f\n", d); 

    clock_gettime(CLOCK_MONOTONIC, &s2); 
    d = descgrad(100,99,0.01,0.00001); 
    clock_gettime(CLOCK_MONOTONIC, &e2); 
    printf("Minimum : %f\n",d); 

    uint64_t dif1 = timespecDiff(&e1,&s1)/1000; 
    uint64_t dif2 = timespecDiff(&e2,&s2)/1000; 

    printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2))); 

    printf("End. \n"); 
} 

Answer 2

С одной стороны, ваш рекурсивный шаг пропускает return:.

double descgrad(double xo, double xnew, double eps, double precision) 
{ 
    if (fabs(xnew - xo) < precision) 
     return xnew; 
    else 
     descgrad(xnew, xnew - eps*f(xnew), eps, precision); 
} 

Должно быть:

double descgrad(double xo, double xnew, double eps, double precision) 
{ 
    if (fabs(xnew - xo) < precision) 
     return xnew; 
    else 
     return descgrad(xnew, xnew - eps*f(xnew), eps, precision); 
} 

Это упущение приводит возвращаемое значение descgrad быть неопределенным, так что компилятор едва должен генерировать код для него вообще;)

Answer 3

Во многих случаях недостатки современного аппаратного кэша являются ограничивающим фактором производительности для небольших контуров цикла. Рекурсивная реализация с меньшей вероятностью создаст пропуски кэша на пути команд.

Answer 4

Является ли мой способ измерения времени неправильным?

Да. В коротких временных интервалах, которые вы измеряете, планировщик может оказать огромное влияние на вашу программу. Вам нужно либо сделать свой тест намного дольше, чтобы усреднить такие различия, либо использовать CLOCK_PROCESS_CPUTIME_ID вместо этого, чтобы измерить время процессора, используемое вашим процессом.

Answer 5

Для начала, вы были в том числе Printf в то время, когда Вы пытаетесь измерить. Это всегда гигантский нет-нет, потому что он может и, скорее всего, приостановит ваш процесс, выполняя консольный вывод. Фактически выполнение любого системного вызова может полностью исключить такие измерения времени.

И, во-вторых, как упоминалось ранее, в течение этого периода, не превышающего период выборки, прерывания планировщика могут иметь огромное влияние.

Это не идеально, но попробуйте это для вашего основного, и вы увидите, что на самом деле очень мало различий. По мере увеличения числа циклов отношение приближается к 1,0.

#define LOOPCOUNT 100000 
int main() 
{ 
    struct timespec s1, e1, s2, e2; 
    int i; 
    clock_gettime(CLOCK_MONOTONIC, &s1); 
    for(i=0; i<LOOPCOUNT; i++) 
    { 
     descgraditer(100,99,0.01,0.00001); 
    } 
    clock_gettime(CLOCK_MONOTONIC, &e1); 

    clock_gettime(CLOCK_MONOTONIC, &s2); 
    for(i=0; i<LOOPCOUNT; i++) 
    { 
     descgrad(100,99,0.01,0.00001); 
    } 
    clock_gettime(CLOCK_MONOTONIC, &e2); 

    uint64_t dif1 = timespecDiff(&e1,&s1)/1000; 
    uint64_t dif2 = timespecDiff(&e2,&s2)/1000; 

    printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2))); 

    printf("End. \n"); 

}

EDIT: После просмотра разобранного вывода с помощью objdump -dS я заметил несколько вещей:
С -O3 оптимизацией, приведенным выше код оптимизирует вызов функции исчезнет полностью. Тем не менее, он все еще создает код для двух функций, и ни один из них не является фактически рекурсивным.

Во-вторых, с -O0, так что полученный код на самом деле рекурсивный, рекурсивная версия буквально a trillion раз медленнее. Моя догадка заключается в том, что стек вызовов заставляет переменные заканчиваться в памяти, где итеративная версия заканчивается из регистров и/или кеша.

Answer 6

Во-первых, clock_gettime похоже измерение настенные часы время, а не время исполнения. Во-вторых, фактическое время, которое вы измеряете, - это время выполнения printf, а не время выполнения вашей функции. И, в-третьих, при первом вызове printf его нет в памяти, поэтому он должен быть выгружен в с участием значительного дискового ввода-вывода. Обратный порядок запускает тесты, и результаты также будут инвертированы.

Если вы хотите получить некоторые важные измерения, вы должны убедиться, что что

1. только код, который вы хотите измерить в контурах измерения, или, по крайней мере, дополнительный код очень минимальный по сравнению с тем, что вы измерения,
2. вы делаете что-то с результатами, так что компилятор не может оптимизировать весь код из (не проблема, в тестах),
3. вы выполняете код в быть измерено большим числом в раз, беря среднее,
4. вы измеряете время центрального процессора, а не настенные часы время, и
5. вы убедитесь, что все страницы памяти перед началом измерений.

Answer 7

Принимаемый ответ неправильный.

Существует разница во время выполнения итеративной функции и рекурсивная функция, и причина заключается в оптимизации компилятора -foptimize-sibling-calls добавлено -O3.

Во-первых, код:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
#include <stdint.h> 

double descgrad(double xo, double xnew, double eps, double precision){ 
     if (fabs(xnew - xo) <= precision) { 
       return xnew; 
     } else { 
       return descgrad(xnew, xnew - eps*2*xnew, eps, precision); 
     } 
} 

double descgraditer(double xo, double xnew, double eps, double precision){ 
     double Xo = xo; 
     double Xn = xnew; 

     while(fabs(Xn-Xo) > precision){ 
       Xo = Xn; 
       Xn = Xo - eps * 2*Xo; 
     } 
     return Xn; 
} 

int main() { 
     time_t s1, e1, d1, s2, e2, d2; 
     int i, iter = 10000000; 
     double a1, a2; 

     s1 = time(NULL); 
     for(i = 0; i < iter; i++){ 
      a1 = descgraditer(100,99,0.01,0.00001); 
     } 
     e1 = time(NULL); 
     d1 = difftime(e1, s1); 

     s2 = time(NULL); 
     for(i = 0; i < iter; i++){ 
      a2 = descgrad(100,99,0.01,0.00001); 
     } 
     e2 = time(NULL); 
     d2 = difftime(e2, s2); 

    printf("time_iter: %d s, time_rec: %d s, ratio (iter/rec): %f\n", d1, d2, (double)d1/d2) ; 
    printf("return values: %f, %f\n", a1, a2); 
} 

Предыдущие должности были правы, указывая на то, что вам нужно повторять много раз, чтобы усреднить прочь помехи среды. Учитывая это, я отказался от вашей функции дифференцирования в пользу time.hdifftime функции на time_t данных, поскольку в течение многих итераций ничего прекрасного, чем секунда, не имеет смысла. Кроме того, я удалил printfs в тесте.

Я также исправил ошибку в рекурсивной реализации. Исходный код вашего исходного кода проверен на fabs(xnew-xo) < precision, что неверно (или, по крайней мере, отличается от итеративной реализации). Итеративные петли, в то время как fabs()> точность, поэтому рекурсивная функция не должна возвращаться, когда fabs < = точность. Добавление счетчиков «итерации» к обеим функциям подтверждает, что это исправление делает логически эквивалентную функцию.

Составление и работает с -O3:

$ gcc test.c -O3 -lrt -o dg 
$ ./dg 
time_iter: 34 s, time_rec: 0 s, ratio (iter/rec): inf 
return values: 0.000487, 0.000487 

Составление и работает без -O3

$ gcc test.c -lrt -o dg 
$ ./dg 
time_iter: 54 s, time_rec: 90 s, ratio (iter/rec): 0.600000 
return values: 0.000487, 0.000487 

Под без оптимизации, итерации работает лучше, чем рекурсии.

Под -O3 оптимизация, однако, рекурсия запускает десять миллионов итераций в секунду. Причина в том, что он добавляет -foptimize-sibling-calls, что оптимизирует рекурсивные вызовы для сестер и хвостов, что именно то, что использует ваша рекурсивная функция.

Чтобы быть уверенным, я побежал это будет все -O3 оптимизаций КРОМЕ -foptimize-sibling-calls:

$ gcc test.c -lrt -o dg -fcprop-registers -fdefer-pop -fdelayed-branch -fguess-branch-probability -fif-conversion2 -fif-conversion -fipa-pure-const -fipa-reference -fmerge-constants -ftree-ccp -ftree-ch -ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-sra -ftree-ter -funit-at-a-time -fthread-jumps -falign-functions -falign-jumps -falign-loops -falign-labels -fcaller-saves -fcrossjumping -fcse-follow-jumps -fcse-skip-blocks -fdelete-null-pointer-checks -fexpensive-optimizations -fgcse -fgcse-lm -fpeephole2 -fregmove -freorder-blocks -freorder-functions -frerun-cse-after-loop -fsched-interblock -fsched-spec -fschedule-insns -fschedule-insns2 -fstrict-aliasing -ftree-pre -ftree-vrp -finline-functions -funswitch-loops -fgcse-after-reload -ftree-vectorize 
$ ./dg 
time_iter: 55 s, time_rec: 89 s, ratio (iter/rec): 0.617978 
return values: 0.000487, 0.000487 

Рекурсия без оптимизации хвост вызова, выполняет хуже, чем итерации, таким же образом, как при компиляции с NO оптимизации. Read about compiler optimizations here.

EDIT:

В проверке правильности я обновил свой код включает возвращаемые значения. Кроме того, я поставил две статические переменные в 0 и увеличивается каждый рекурсии и итерации для проверки правильности вывода:

int a = 0; 
int b = 0; 

double descgrad(double xo, double xnew, double eps, double precision){ 
     if (fabs(xnew - xo) <= precision) { 
       return xnew; 
     } else { 
       a++; 
       return descgrad(xnew, xnew - eps*2*xnew, eps, precision); 
     } 
} 

double descgraditer(double xo, double xnew, double eps, double precision){ 
     double Xo = xo; 
     double Xn = xnew; 

     while(fabs(Xn-Xo) > precision){ 
       b++; 
       Xo = Xn; 
       Xn = Xo - eps * 2*Xo; 
     } 
     return Xn; 
} 

int main() { 
    time_t s1, e1, d1, s2, e2, d2; 
    int i, iter = 10000000; 
    double a1, a2; 

    s1 = time(NULL); 
    for(i = 0; i < iter; i++){ 
     a1 = descgraditer(100,99,0.01,0.00001); 
    } 
    e1 = time(NULL); 
    d1 = difftime(e1, s1); 

    s2 = time(NULL); 
    for(i = 0; i < iter; i++){ 
     a2 = descgrad(100,99,0.01,0.00001); 
    } 
    e2 = time(NULL); 
    d2 = difftime(e2, s2); 

    printf("time_iter: %d s, time_rec: %d s, ratio (iter/rec): %f\n", d1, d2, (double)d1/d2) ; 
    printf("return values: %f, %f\n", a1, a2); 
    printf("number of recurs/iters: %d, %d\n", a, b); 
} 

Выход:

$ gcc optimization.c -O3 -lrt -o dg 
$ ./dg 
time_iter: 41 s, time_rec: 24 s, ratio (iter/rec): 1.708333 
return values: 0.000487, 0.000487 
number of recurs/iters: 1755032704, 1755032704 

ответы одинаковы, и повторение того же ,

Также интересно отметить, что статическая переменная fetching/incrementing оказывает значительное влияние на оптимизацию хвостового вызова, однако рекурсия по-прежнему выполняется итерацией.