macos - 如何使用 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 位算术中，天真地将绝对时间乘以分数也会溢出。这是Apple在mach_absolute_time上的唯一文档中的一个错误。落入 ( Technical Q&A 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;
}

如果 decom=33333335 由 mach_timebase_info 返回，我们只能在乘以数字溢出之前处理最多 18 秒的差异。正如 getExpressibleSpan 所示，通过计算其粗略下限，numer 的大小并不重要:将 numer 减半使 maxDiffWithoutOverflow 翻倍。因此，唯一的目标是产生一个接近分母较小的数字/分母的分数。最简单的方法是使用连分数。

连分数法相当方便。如果提供的间隔包含整数，bestFrac 显然可以正常工作:它返回间隔中超过 1 的最小整数。否则，它以严格更大的间隔递归调用自身并返回 m+1/下一个。最终结果是一个连分数，可以通过归纳法证明它具有正确的性质:它是最优的，即给定区间内分母最小的分数。

最后，我们将 Darwin 传递给我们的分数减少到一个较小的分数，以便在将 mach_absolute_time 重新调整为纳秒时使用。我们可能会在这里引入一个错误，因为我们通常无法在不损失准确性的情况下减少分数。我们为自己设定了 0.1% 错误率的目标，并检查我们是否已将这个分数减少到足以正确处理常见时间跨度(最多十年)。

可以说，该方法的功能过于复杂，但它可以正确处理 API 可以向其抛出的任何内容，并且生成的代码仍然简短且速度极快(bestFrac 通常仅递归三个或在随机间隔返回小于 1000 的分母之前进行四次迭代[a,a*1.002])。