为什么函数的递归版本比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");
}

我正在使用以下选项在Ubuntu 11.04上使用gcc 4.5.2进行编译:gcc grad.c -O3 -lrt -o dg

我的代码输出是:

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

我读了一个线程,它也询问算法的递归版本比迭代版本更快.对那里的解释是使用堆栈的递归版本和使用一些向量的其他版本,堆上的访问减慢了迭代版本.但在这种情况下(据我所知),我只是在两种情况下使用堆栈.

我错过了什么吗？有什么明显我没看到的吗？我测量时间的方式错了吗？任何见解？

编辑:在评论中解决了神秘.正如@TonyK所说,printf的初始化减慢了第一次执行的速度.对不起,我错过了那个明显的事情.

顺便说一句,代码编译恰到好处而没有警告.我不认为"返回descgrad(.."是必要的,因为停止条件发生之前.

Answer 1

我已在本地编译和运行您的代码.移动printf定时块的外部使得两个版本每次都在~5ms内执行.

因此,你的计时中的一个核心错误是你测量复杂的野兽,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

我测量时间的方式错了吗？

是.在您测量的短时间范围内,调度程序可能会对您的程序产生巨大影响.您需要更长时间地进行测试以平均这些差异,或者CLOCK_PROCESS_CPUTIME_ID用来衡量流程使用的CPU时间.