Использование модульной арифметики для избежания проблем переполнения интервалов

Это перевод Using modular arithmetic to avoid timing overflow problems. Автор: Реймонд Чен.

Ранее я показал простой способ избежать переполнений в интервалах времени (таймерах), который, кажется, оказался довольно туманным.

Короткий ответ: способ определить, истёк ли заданный интервал времени по заданному времени старта (start), конечному (текущему) времени (end) и самому интервалу (interval) заключается в использовании выражения end - start >= interval. Наивная реализация вида end >= start + interval может не сработать из-за проблем с переполнением.

Длинный ответ: для упрощения обсуждения, давайте работать с base-100 вместо base-2³². Тут работает та же логика, но, как мне кажется, работая с base-100 будет проще это понять.

Base-100 означает, что мы запоминаем только две последние цифры любого числа. Давайте рассмотрим начальное время start = 90 и интервал interval = 10. Использование ошибочного выражения даёт нам: end >= start + interval = 90+10 = 100 = 0. Другими словами, end >= 0, что всегда истинно, поскольку end лежит в диапазоне 0...99. В результате, ошибочное выражение будет думать, что интервал времени уже истёк, хотя на самом деле это не так.

Используя правильное выражение, мы получаем: end - 90 >= 10. Те из чисел 0..99, что дают нам разность меньше 10, являются числа от 90 до 99. Когда end = 0, результат будет 0 - 90 = 10, что правильно указывает, что когда таймер достигает 0, с момента времени 90 проходит 10 тиков.

Вы можете поработать с этой же ошибкой, используя start = 89, вместо start = 90; в этом случае, ошибочное выражение становится: end >= start + interval = 89 + 10 = 99, или, другими словами, end >= 99. Здесь мы имеем противоположную проблему, а именно: выражение не сможет определить, что интервал истёк, когда таймер переходит к нулю ("переполняется").

Но почему работает выражение end - start? Это очень просто: вам только нужно вспомнить правила арифметики из начальной школы.

(x - c) - (y - c) = x - c - y + c = x - y

Другими словами, вычитание одного и того же значения из обоих частей разности не влияет на окончательный результат. Это правило применимо даже к модульной арифметике (потому что, как любят говорить математики, множество из целых чисел по модулю N формирует аддитивную группу).

Это правило полезно, потому что позволяет вам "откладывать" переполнение на максимально поздний момент, вычитая стартовую точку из всех ваших временных меток. Подумайте, разве не было бы прекрасным, если бы начальное время всегда было равно нулю? Ведь тогда переполнения не случится аж 100 тиков! Ну, вы можете действовать так, "как если бы" начальное время было нулевым: просто вычитая его из временных меток.

Те из вас, кто предпочитают графический подход, могут думать о истёкшем времени как о движении стрелки на часах (которая "переполняется", скажем, каждые 60 минут). Когда вы решите запомнить начальное время, просто поверните циферблат так, чтобы "12" оказалось в точности на том месте, где сейчас стрелка (прим.пер.: видимо, имеются ввиду часы с вращающимся циферблатом). Теперь вы можете узнать прошедшее с момента старта время просто смотря на (повёрнутый) циферблат. Поворот циферблата - это тоже самое, что вычитание (ну или добавление) константы ко всем временным меткам.

Конечно же, этот трюк перестаёт работать, когда вам нужно измерять интервалы, которые приближаются к времени сброса вашего таймера. В нашей модели с 100-тиковым таймером, к примеру, будет довольно сложно измерить интервал в, скажем, 90 тиков: потому что у вас есть окно всего в 10 тиков, где ваше выражение становится истинным. Если вы не сумеете сделать проверку в этом окне - вы пропустите уведомление и вам придётся ждать ещё 90 тиков. По очевидным причинам, вы вообще не сможете измерить интервал больше 99 тиков.

Поэтому: не делайте этого. На практике никогда не используйте GetTickCount для измерения интервалов дольше 15 дней.