以毫秒精度测量时间

Question

我将编写一个程序来比较不同的排序算法，包括时间和空间。空间已经解决了，但是测量时间有些困难。以下是运行排序的代码：

void test(short* n, short len) {
  short i, j, a[1024];

  for(i=0; i<2; i++) {         // Loop over each sort algo
    memused = 0;               // Initialize memory marker
    for(j=0; j<len; j++)       // Copy scrambled list into fresh array
      a[j] = n[j];             // (Sorting algos are in-place)
                               // ***Point A***
    switch(i) {                // Pick sorting algo
    case 0:
      selectionSort(a, len);
    case 1:
      quicksort(a, len);
    }
                               // ***Point B***    
    spc[i][len] = memused;     // Record how much mem was used
  }
}

现在，我需要测量排序算法花费的时间。最明显的方法是记录点(a)的时间，然后将其从点(b)的时间中减去。但是，C语言的时间函数都不够好:

time()可以给我秒级时间，但是算法速度比这更快，因此我需要更精确的方法。

clock()给出程序启动以来的CPU时钟周期数，但似乎向最近的10,000舍入，仍然不够小。

time shell命令足够好，但是我需要每个算法运行超过1,000次测试，并且我需要每个算法单独的时间。

我不知道 getrusage()返回什么，但它的时间也太长了。

我需要的是单位时间（如果可能）比排序函数的运行时间小得多的时间：大约为2毫秒。那么我的问题是：我从哪里获取它？

- MegaWidget

---

哪个平台？提到 getrusage() 表明是 POSIX 系统，在这种情况下，适用于 gettimeofday() 或 clock_gettime()（分别具有微秒和纳秒分辨率，但不一定具有所述的准确性）。 - Jonathan Leffler

man 2 clock_gettime，或者如果您可以使用C2011，则为int timespec_get(struct timespec *ts, int base);。 - Daniel Fischer

平台：AMD Athlon 64（运行Debian Linux） - MegaWidget

Answer 1

gettimeofday()函数具有微秒级的分辨率，易于使用。

一对实用的计时器函数：

static struct timeval tm1;

static inline void start()
{
    gettimeofday(&tm1, NULL);
}

static inline void stop()
{
    struct timeval tm2;
    gettimeofday(&tm2, NULL);

    unsigned long long t = 1000 * (tm2.tv_sec - tm1.tv_sec) + (tm2.tv_usec - tm1.tv_usec) / 1000;
    printf("%llu ms\n", t);
}

- user529758

---

@OliCharlesworth 很遗憾，不过至少它通常提供了一个很好的近似值。当然，这10行左右的代码并不适合作为生产代码，但这也不是我的目标。 - user529758

微秒是 µs（使用 ASCII 码 230 - 八进制中的 '\181'），而不是 ms（代表毫秒）。通常用字母 u 而不是希腊字母 μ：us。 - paddy

@paddy 呃...我有反对这个的观点吗？ - user529758

哦，对不起，我看错了，以为你要输出微秒。 - paddy

不要使用“gettimeofday”。它受时间服务器更新和漂移影响。 - TheBuzzSaw

Answer 2

为了测量时间，请使用clock_gettime与CLOCK_MONOTONIC(或CLOCK_MONOTONIC_RAW如果它可用)。在可能的情况下，避免使用gettimeofday。它已被明确弃用，推荐使用clock_gettime，而从中返回的时间受时间服务器的调整影响，这可能会使您的测量失准。

- TheBuzzSaw

Answer 3

您可以使用getrusage如下获取总用户+内核时间（或选择一个）：

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

double get_process_time() {
    struct rusage usage;
    if( 0 == getrusage(RUSAGE_SELF, &usage) ) {
        return (double)(usage.ru_utime.tv_sec + usage.ru_stime.tv_sec) +
               (double)(usage.ru_utime.tv_usec + usage.ru_stime.tv_usec) / 1.0e6;
    }
    return 0;
}

我选择创建一个包含小数秒的double...

double t_begin, t_end;

t_begin = get_process_time();
// Do some operation...
t_end = get_process_time();

printf( "Elapsed time: %.6f seconds\n", t_end - t_begin );

- paddy

Answer 4

时间戳计数器在这里可能会有所帮助：

static unsigned long long rdtsctime() {
    unsigned int eax, edx;
    unsigned long long val;
    __asm__ __volatile__("rdtsc":"=a"(eax), "=d"(edx));
    val = edx;
    val = val << 32;
    val += eax;
    return val;
}

尽管如此，还有一些注意事项需要注意。不同处理器核心的时间戳可能会不同，并且更改时钟速度（由于节能功能等）可能会导致错误的结果。

- Imre Kerr

---

假设您正在使用英特尔/AMD x86_64平台，而不是SPARC、PPC、PA-RISC（可能也不是IA-64）。 - Jonathan Leffler

我相信从Pentium 4开始，TSC与瞬时CPU频率无关（请参阅Intel-64 SDM的第17.12章）。 - Oliver Charlesworth

解决上述原问题并不需要特定于CPU的指令，即使使用基于英特尔的系统也是如此。如果正确执行，则比较排序算法不需要这种粒度（完全没有必要）。 - Randy Howard