Câu hỏi Làm thế nào tôi có thể sử dụng mach_absolute_time mà không bị tràn?


Ở Darwin, tiêu chuẩn POSIX clock_gettime(CLOCK_MONOTONIC) hẹn giờ không có sẵn. Thay vào đó, bộ định thời monotonic có độ phân giải cao nhất thu được thông qua mach_absolute_time chức năng từ mach/mach_time.h.

Kết quả trả về có thể là một số đếm không được điều chỉnh từ bộ xử lý, trong trường hợp đó các đơn vị thời gian có thể là một bội số lạ. Ví dụ, trên một CPU với số lượng đếm 33MHz, Darwin trả về 1000000000/33333335 làm các đơn vị chính xác của kết quả trả về (ví dụ, nhân mach_absolute_time theo phân số đó để thu được giá trị nano giây).

Chúng tôi thường muốn chuyển đổi từ các ve chính xác sang các đơn vị "chuẩn" (thập phân), nhưng thật không may, việc nhân thời gian tuyệt đối bằng phần nhỏ sẽ tràn ngay cả trong số học 64 bit. Đây là lỗi mà tài liệu duy nhất của Apple về mach_absolute_time rơi vào (Hỏi đáp kỹ thuật QA1398).1

Làm thế nào tôi nên viết một hàm sử dụng chính xác mach_absolute_time?


  1. Lưu ý rằng đây không phải là một vấn đề lý thuyết: mã mẫu trong QA1398 hoàn toàn không hoạt động trên Mac dựa trên PowerPC. Trên máy Mac Intel, mach_timebase_info luôn luôn trả về 1/1 làm hệ số chia tỷ lệ vì số lượng đánh dấu thô của CPU không đáng tin cậy (bước tăng tốc động), do đó API thực hiện mở rộng quy mô cho bạn. Trên máy Mac PowerPC, mach_timebase_info trả về 1000000000/33333335 hoặc 1000000000/25000000, vì vậy mã được Apple cung cấp chắc chắn sẽ tràn mỗi vài phút. Rất tiếc.

10
2018-04-30 01:18


gốc


Apple đã cập nhật định dạng URL cho tài liệu, do đó, liên kết mới cho QA1398 là developer.apple.com/library/content/qa/qa1398/_index.html - Dan Waylonis
Cảm ơn Dan, đã cập nhật. - Nicholas Wilson


Các câu trả lời:


Câu trả lời chính xác nhất (tốt nhất)

Thực hiện số học ở độ chính xác 128 bit để tránh tràn!

// 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);
}

Một câu trả lời có độ phân giải thấp đơn giản

// 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;
}

Một giải pháp khó sử dụng số học chính xác thấp nhưng sử dụng phân số liên tục để tránh mất độ chính xác

// 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;
}

Đạo hàm

Chúng tôi muốn giảm phân số được trả về bởi mach_timebase_info đến một bản chất giống nhau, nhưng với một mẫu số nhỏ. Kích thước của khoảng thời gian mà chúng ta có thể xử lý bị giới hạn bởi kích thước của mẫu số, không phải là tử số của phân số chúng ta sẽ nhân với:

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;
}

Nếu denom=33333335 như được trả lại bởi mach_timebase_info, chúng tôi có thể xử lý sự khác biệt lên đến 18 giây chỉ trước khi nhân bằng số tràn. Như getExpressibleSpan cho thấy, bằng cách tính toán giới hạn dưới thô cho điều này, kích thước của numer không quan trọng: giảm một nửa numer đôi maxDiffWithoutOverflow. Mục tiêu duy nhất do đó là tạo ra một phần nhỏ gần số / denom có ​​mẫu số nhỏ hơn. Phương pháp đơn giản nhất để làm điều này là sử dụng các phân số liên tục.

Phương pháp phân số tiếp tục khá thuận tiện. bestFrac rõ ràng hoạt động chính xác nếu khoảng thời gian được cung cấp chứa một số nguyên: nó trả về số nguyên nhỏ nhất trong khoảng trên 1. Nếu không, nó sẽ tự động gọi đệ quy với khoảng thời gian lớn hơn và trả về m+1/next. Kết quả cuối cùng là một phần tiếp theo có thể được hiển thị bằng cảm ứng để có thuộc tính chính xác: tối ưu, phần nhỏ bên trong khoảng thời gian đã cho với mẫu số nhỏ nhất.

Cuối cùng, chúng ta giảm phân số Darwin chuyển chúng ta sang một phần nhỏ hơn để sử dụng khi rescaling mach_absolute_timeđến nano giây. Chúng tôi có thể giới thiệu một lỗi ở đây vì chúng tôi không thể giảm phần nói chung mà không làm mất độ chính xác. Chúng tôi đặt mục tiêu của mình là sai số 0,1% và kiểm tra xem chúng tôi đã giảm phân số đủ cho các khoảng thời gian thông thường (tối đa mười năm) để được xử lý đúng cách.

Có thể cho rằng phương pháp này quá phức tạp với những gì nó làm, nhưng nó xử lý chính xác mọi thứ API có thể ném vào nó, và mã kết quả vẫn ngắn và cực kỳ nhanh (bestFrac thường chỉ đệ trình ba hoặc bốn lần lặp lại sâu trước khi trả về mẫu số nhỏ hơn 1000 cho khoảng thời gian ngẫu nhiên [a,a*1.002]).


21
2018-04-30 01:18



Điều đó có vẻ đầy hứa hẹn, thật không may là tôi dường như không thể làm cho trình biên dịch của tôi hoạt động với những trình biên dịch đó (sử dụng một cách đơn giản clang foo.c) (có lẽ là static struct Data {Data(uint64_t bias_) : bias(bias_) { một phần mà tôi chưa bao giờ nhìn thấy) bạn có thể cho tôi bất kỳ đầu mối? - Romuald Brunet
Đó là C ++ (ObjC ++), không C. Có nói rằng, tôi thực sự nên cập nhật câu trả lời này bởi vì tôi sử dụng một kỹ thuật khác bây giờ - chỉ cần làm số học ở độ chính xác cao :) - Nicholas Wilson
Cảm ơn :) Tôi đã đưa ra một giải pháp khác nhau quá (nhưng không có PowerPC để kiểm tra nó thực sự hoạt động: p) - Romuald Brunet
Tôi đã cập nhật với giải pháp chính xác hơn của tôi ngay bây giờ. Chúng tôi đã giảm hỗ trợ cho PPC tại công ty của tôi một năm trước đây, vì vậy bây giờ tất cả chúng ta đều được bảo đảm rằng chúng tôi được bảo đảm khá nhiều không bao giờ thấy bất kỳ điều gì khác ngoài 1/1 trở về từ mach_timebase_info(). - Nicholas Wilson