如何在不溢出的情况下使用mach_absolute_time？

Question

在Darwin上,POSIX标准clock_gettime(CLOCK_MONOTONIC)计时器不可用.相反,最高分辨率的单调计时器是通过mach_absolute_time函数获得的mach/mach_time.h.

返回的结果可能是来自处理器的未调整的滴答计数,在这种情况下,时间单位可能是奇怪的倍数.例如,在具有33MHz滴答计数的CPU上,Darwin返回1000000000/33333335作为返回结果的确切单位(即,乘以该mach_absolute_time分数以获得纳秒值).

我们通常希望将精确刻度转换为"标准"(十进制)单位,但不幸的是,即使在64位算术中,绝对时间乘以分数也会溢出.这是苹果公司唯一的文件归属mach_absolute_time于(技术问答QA1398).¹

我该如何编写正确使用的函数mach_absolute_time？

---

1. 请注意,这不是一个理论问题:QA1398中的示例代码完全无法在基于PowerPC的Mac上运行.在Intel Mac上,mach_timebase_info始终返回1/1作为缩放因子,因为CPU的原始滴答计数不可靠(动态速度步进),因此API会为您进行缩放.在PowerPC Mac上,mach_timebase_info返回1000000000/33333335或1000000000/25000000,因此Apple提供的代码每隔几分钟就会溢出一次.哎呀.

Answer 1

最精确(最好)的答案

以128位精度执行算法以避免溢出!

// Returns monotonic time in nanos, measured from the first time the function
// is called in the process.
uint64_t monotonicTimeNanos() {
  uint64_t now = mach_absolute_time();
  static struct Data {
    Data(uint64_t bias_) : bias(bias_) {
      kern_return_t mtiStatus = mach_timebase_info(&tb);
      assert(mtiStatus == KERN_SUCCESS);
    }
    uint64_t scale(uint64_t i) {
      return scaleHighPrecision(i - bias, tb.numer, tb.denom);
    }
    static uint64_t scaleHighPrecision(uint64_t i, uint32_t numer,
                                       uint32_t denom) {
      U64 high = (i >> 32) * numer;
      U64 low = (i & 0xffffffffull) * numer / denom;
      U64 highRem = ((high % denom) << 32) / denom;
      high /= denom;
      return (high << 32) + highRem + low;
    }
    mach_timebase_info_data_t tb;
    uint64_t bias;
  } data(now);
  return data.scale(now);
}

一个简单的低分辨率答案

// Returns monotonic time in nanos, measured from the first time the function
// is called in the process.  The clock may run up to 0.1% faster or slower
// than the "exact" tick count.
uint64_t monotonicTimeNanos() {
  uint64_t now = mach_absolute_time();
  static struct Data {
    Data(uint64_t bias_) : bias(bias_) {
      kern_return_t mtiStatus = mach_timebase_info(&tb);
      assert(mtiStatus == KERN_SUCCESS);
      if (tb.denom > 1024) {
        double frac = (double)tb.numer/tb.denom;
        tb.denom = 1024;
        tb.numer = tb.denom * frac + 0.5;
        assert(tb.numer > 0);
      }
    }
    mach_timebase_info_data_t tb;
    uint64_t bias;
  } data(now);
  return (now - data.bias) * data.tb.numer / data.tb.denom;
}

使用低精度算法但使用连续分数以避免精度损失的繁琐解决方案

// This function returns the rational number inside the given interval with
// the smallest denominator (and smallest numerator breaks ties; correctness
// proof neglects floating-point errors).
static mach_timebase_info_data_t bestFrac(double a, double b) {
  if (floor(a) < floor(b))
  { mach_timebase_info_data_t rv = {(int)ceil(a), 1}; return rv; }
  double m = floor(a);
  mach_timebase_info_data_t next = bestFrac(1/(b-m), 1/(a-m));
  mach_timebase_info_data_t rv = {(int)m*next.numer + next.denum, next.numer};
  return rv;
}

// Returns monotonic time in nanos, measured from the first time the function
// is called in the process.  The clock may run up to 0.1% faster or slower
// than the "exact" tick count. However, although the bound on the error is
// the same as for the pragmatic answer, the error is actually minimized over
// the given accuracy bound.
uint64_t monotonicTimeNanos() {
  uint64_t now = mach_absolute_time();
  static struct Data {
    Data(uint64_t bias_) : bias(bias_) {
      kern_return_t mtiStatus = mach_timebase_info(&tb);
      assert(mtiStatus == KERN_SUCCESS);
      double frac = (double)tb.numer/tb.denom;
      uint64_t spanTarget = 315360000000000000llu; // 10 years
      if (getExpressibleSpan(tb.numer, tb.denom) >= spanTarget)
        return;
      for (double errorTarget = 1/1024.0; errorTarget > 0.000001;) {
        mach_timebase_info_data_t newFrac =
            bestFrac((1-errorTarget)*frac, (1+errorTarget)*frac);
        if (getExpressibleSpan(newFrac.numer, newFrac.denom) < spanTarget)
          break;
        tb = newFrac;
        errorTarget = fabs((double)tb.numer/tb.denom - frac) / frac / 8;
      }
      assert(getExpressibleSpan(tb.numer, tb.denom) >= spanTarget);
    }
    mach_timebase_info_data_t tb;
    uint64_t bias;
  } data(now);
  return (now - data.bias) * data.tb.numer / data.tb.denom;
}

推导

我们的目标是将返回的分数减少mach_timebase_info到一个基本相同但分数较小的分数.我们可以处理的时间跨度的大小仅受分母的大小限制,而不是我们将乘以的分数的分子:

uint64_t getExpressibleSpan(uint32_t numer, uint32_t denom) {
  // This is just less than the smallest thing we can multiply numer by without
  // overflowing. ceilLog2(numer) = 64 - number of leading zeros of numer
  uint64_t maxDiffWithoutOverflow = ((uint64_t)1 << (64 - ceilLog2(numer))) - 1;
  return maxDiffWithoutOverflow * numer / denom;
}

如果denom=33333335返回mach_timebase_info,我们可以在乘以数字溢出之前处理最多18秒的差异.作为getExpressibleSpan显示,通过计算这一个粗略的下界,大小numer并不重要:减半numer双打maxDiffWithoutOverflow.因此,唯一的目标是产生一个接近于数字/ denom的分数,它具有较小的分母.最简单的方法是使用连续分数.

连续分数法非常方便.bestFrac如果提供的间隔包含一个整数,它可以清楚地正常工作:它返回的间隔中的最小整数大于1.否则,它会以一个严格更大的间隔递归调用自身并返回m+1/next.最终结果是一个连续的分数,可以通过归纳显示具有正确的属性:它是最优的,给定区间内具有最小分母的分数.

最后,我们将Darwin传递给我们的分数减少到一个较小的分数,以便在重新缩放mach_absolute_time到纳秒时使用.我们可能会在这里引入错误,因为我们不能在不失去准确性的情况下减少分数.我们为自己设定了0.1%误差的目标,并检查我们是否已经足够减少了普通时间(最多十年)的分数,以便正确处理.

可以说这个方法过于复杂,但它可以正确处理API可以抛出的任何内容,结果代码仍然很短而且非常快(bestFrac通常只返回三到四次迭代,然后返回小于1000的分母随机间隔[a,a*1.002]).

Answer 2

您担心与结构中的值相乘/除时溢出mach_timebase_info，该结构用于转换为纳秒。因此，虽然它可能不符合您的确切需求，但有更简单的方法可以获取以纳秒或秒为单位的计数。

以下所有解决方案均在内部使用mach_absolute_time（而不是挂钟）。

使用double而不是uint64_t

^{（受 Objective-C 和 Swift 支持）}

double tbInSeconds = 0;
mach_timebase_info_data_t tb;
kern_return_t kError = mach_timebase_info(&tb);
if (kError == 0) {
    tbInSeconds = 1e-9 * (double)tb.numer / (double)tb.denom;
}

（1e-9如果需要纳秒，请删除）

用法：

uint64_t start = mach_absolute_time();
// do something
uint64_t stop = mach_absolute_time();
double durationInSeconds = tbInSeconds * (stop - start);

使用 ProcessInfo.processInfo。系统正常运行时间

^{（受 Objective-C 和 Swift 支持）}

它直接在几秒钟内完成工作double：

CFTimeInterval start = NSProcessInfo.processInfo.systemUptime;
// do something
CFTimeInterval stop = NSProcessInfo.processInfo.systemUptime;
NSTimeInterval durationInSeconds = stop - start;

作为参考，systemUptime 的源代码 仅执行与之前的解决方案类似的操作：

struct mach_timebase_info info;
mach_timebase_info(&info);
__CFTSRRate = (1.0E9 / (double)info.numer) * (double)info.denom;
__CF1_TSRRate = 1.0 / __CFTSRRate;
uint64_t tsr = mach_absolute_time();
return (CFTimeInterval)((double)tsr * __CF1_TSRRate);

使用 QuartzCore。CA当前媒体时间()

^{（受 Objective-C 和 Swift 支持）}

与 相同systemUptime，但不是开源的。

使用调度。调度时间.now()

^{（仅支持 Swift）}

另一个包装纸mach_absolute_time()。基本精度为纳秒，支持UInt64.

DispatchTime start = DispatchTime.now()
// do something
DispatchTime stop = DispatchTime.now()
TimeInterval durationInSeconds = Double(end.uptimeNanoseconds - start.uptimeNanoseconds) / 1_000_000_000

作为参考，源代码DispatchTime.now()表示它基本上只是返回一个 struct DispatchTime(rawValue: mach_absolute_time())。计算为uptimeNanoseconds：

(result, overflow) = result.multipliedReportingOverflow(by: UInt64(DispatchTime.timebaseInfo.numer))
result = overflow ? UInt64.max : result / UInt64(DispatchTime.timebaseInfo.denom)

因此，如果乘法无法存储在 UInt64 中，它只会丢弃结果。