如何以微秒为单位测量执行时间？

Question

我编写了以下代码来测量排序任何数据所需的时间。但是，我得到一些奇怪的结果，例如在某些情况下出现负时间，并且对于相同的数据集没有得到任何一致的结果（我明白它不会完全相同）。请告诉我问题在哪里或如何正确测量时间。

#include<stdio.h>
#include<sys/time.h>

void bubble(int a[],int n)
{
    int i,j,flag,temp;
    for(i=0;i<n-1;i++)
    {
        flag=0;
        for(j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                flag=1;
                a[j]=a[j]+a[j+1];
                a[j+1]=a[j]-a[j+1];
                a[j]=a[j]-a[j+1];
            }
        }
        if(flag==0)
            break;
    }
}

int main()
{
    int n,a[100000],i;
    printf("Enter the size of array:");
    scanf("%d",&n);
    for(i=0;i<n;i++)
        a[i]=rand()%100000;     //average case
        //a[i]=i;               //best case
        //a[i]=n-1-i;           //worst case
    /*
    printf("The UNsorted array is:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n\n");
    */

    int st,et;
    struct timezone tz;
    struct timeval tv;
    gettimeofday(&tv,NULL);
    st=tv.tv_usec;
    bubble(a,n);
    gettimeofday(&tv,NULL);
    et=tv.tv_usec;
    printf("Sorting time: %d micro seconds\n",et-st);
    /*
    printf("\nThe sorted array is:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    */
    return 0;
}

- Naitik Parekh

---

当微秒达到1000000时，您认为会发生什么？ - EOF

在哪个系统上？请编辑问题。 - Lundin

Answer 1

gettimeofday所填充的struct timeval定义如下：

struct timeval {
    time_t      tv_sec;     /* seconds */
    suseconds_t tv_usec;    /* microseconds */
};

tv_sec和tv_usec字段一起包含自历元以来的秒数和微秒数。微秒部分仅包含小数秒，即0到999999之间的值。

您需要减去秒数和微秒数。

struct timeval st, et;

gettimeofday(&st,NULL);
bubble(a,n);
gettimeofday(&et,NULL);

int elapsed = ((et.tv_sec - st.tv_sec) * 1000000) + (et.tv_usec - st.tv_usec)
printf("Sorting time: %d micro seconds\n",elapsed);

如果总运行时间非常短，您可以进行多次运行并将它们平均：

struct timeval st, et;
int i, num_runs = 5;

gettimeofday(&st,NULL);
for (i=0; i<num_runs; i++) {
    bubble(a,n);
}
gettimeofday(&et,NULL);

int elapsed = (((et.tv_sec - st.tv_sec) * 1000000) + (et.tv_usec - st.tv_usec)) / num_runs;

- dbush

---

这对于平均情况和最坏情况分析效果很好，但是我仍然在测量非常小的时间时遇到问题。当我运行冒泡排序的最佳情况时，我得到了不一致的输出。相同数据集的时间在0到1000微秒之间变化。我正在测试10000-90000范围内的数据。 - Naitik Parekh

@NaitikParekh 看一下我的修改。进行多次运行并取平均值。 - dbush

抖动（时间变化）是由于系统中发生的其他事情将您的进程执行推离CPU：中断、I/O和优先级更高的进程。如果您在算法中调用printf()或访问文件，请将它们移至第二个gettimeofday()之后。关于进程优先级，尝试使用sudo nice -19运行程序，并将进程的亲和性设置为特定的CPU（例如使用sched_setaffinity或numa程序）。这将尽可能地防止缓存崩溃。 - Eric

如果您想知道最佳情况，即没有任何系统中断，则将代码放置在关键部分内的内核模块中：它将在整个执行时间内获得不间断的CPU，没有任何中断。使用此方法可以获得一致的时间测量结果，但也存在限制，因为调用C标准库将无法正常工作。内核中有printf（实际上是printk）。 - Eric