Ответ 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. Поэтому единственная цель состоит в том, чтобы создать дробь, близкую к числителю/деноту, имеющую меньший знаменатель. Самый простой способ сделать это - использовать непрерывные дроби.
Метод продолженных дробей весьма удобен. bestFrac четко работает, если предоставленный интервал содержит целое число: он возвращает наименьшее целое число в интервале более 1. В противном случае он вызывает себя рекурсивно со строго большим интервалом и возвращает m+1/next. Конечным результатом является непрерывная дробь, которая может быть показана индукцией, чтобы иметь правильное свойство: она оптимальна, доля внутри данного интервала с наименьшим знаменателем.
Наконец, мы уменьшаем долю, которую Дарвин передает нам на меньшую, которая будет использоваться при масштабировании mach_absolute_time до наносекунд. Мы можем ввести здесь ошибку, потому что мы не можем уменьшить долю вообще без потери точности. Мы поставили перед собой цель ошибки 0,1% и отметим, что мы сократили долю, достаточную для правильной обработки общих временных интервалов (до десяти лет).
Вероятно, этот метод слишком усложнен для того, что он делает, но он правильно обрабатывает все, что может на него наложить API, и полученный код все еще короткий и очень быстрый (bestFrac обычно повторяется только три или четыре итерации до возвращая знаменатель менее 1000 для случайных интервалов [a,a*1.002]).