Измерение времени с наносекундной точностью05.10.2018 00:47

Пару месяцев назад для меня наступил исторический момент. Мне перестало хватать стандартных средств операционной системы для измерения времени. Понадобилось измерять время с наносекундной точностью и с наносекундными накладными расходами.

Я решил написать библиотеку, которая решала бы эту задачу. На первый взгляд казалось, что и делать-то особо нечего. Но при более детальном рассмотрении, как всегда, выяснилось, что есть много интересных проблем, с которыми предстояло разобраться. В этой статье я расскажу и о проблемах, и о том, как они были решены.

Так как на компьютере можно измерять много разных типов времени, сразу уточню, что здесь речь пойдет о «времени по секундомеру». Или wall-clock time. Оно же real time, elapsed time и т.п. То есть простое «человеческое» время, которое мы засекаем в начале исполнения задачи и останавливаем в конце.

Микросекунда — почти вечность

Разработчики высокопроизводительных систем за последние несколько лет уже привыкли к микросекундному масштабу времени. За микросекунды можно прочитать данные с NVMe-диска. За микросекунды данные можно переслать по сети. Не по всякой, конечно, но по InifiniBand-сети — запросто.

При этом у микросекунды появилась еще и структура. Полный стек ввода-вывода состоит из нескольких программных и аппаратных компонент. Задержки, вносимые некоторыми из них, лежат на суб-микросекундном уровне.

Для измерения задержек такого масштаба микросекундная точность уже недостаточна. Однако важна не только точность, но еще и накладные расходы на измерение времени. Линуксовый системный вызов clock_gettime () возвращает время с наносекундной точностью. На машине, которая вот прямо сейчас у меня под рукой (Intel® Xeon® CPU E5–2630 v2 @ 2.60GHz), этот вызов отрабатывает примерно за 120 нс. Очень неплохая цифра. К тому же clock_gettime () работает достаточно предсказуемо. Это позволяет учесть накладные расходы на его вызов и в действительности делать измерения с точностью порядка десятков наносекунд. Однако обратим теперь внимание вот на что. Чтобы измерить интервал времени, нужно сделать два таких вызова: в начале и в конце. Т.е. потратить 240 нс. Если измеряются плотно расположенные промежутки времени порядка 1–10 мкс, то в некоторых таких случаях сам процесс измерения будет значительно искажать наблюдаемый процесс.

Я начал этот раздел с того, как ускорился IO-стек в последние годы. Это новая, однако далеко не единственная причина хотеть измерять время быстро и точно. Такая необходимость была всегда. Например, всегда существовал код, который хотелось ускорить хотя бы на 1 такт микропроцессора. Или вот еще пример, из оригинальной статьи про нашумевшую уязвимость Spectre:

Здесь в строках 72–74 измеряется время исполнения одной-единственной операции обращения к памяти. Правда, Spectre не интересуют наносекунды. Время может быть измерено в «попугаях». К попугаям и секундам мы еще вернемся.

Time-stamp counter

Ключ к быстрому и точному измерению времени — специальный счетчик микропроцессора. Значение этого счетчика обычно хранится в отдельном регистре и обычно –, но не всегда — доступно из пользовательского пространства. На разных архитектурах счетчик называется по-разному:

1. time-stamp counter на x86
2. time base register на PowerPC
3. interval time counter на Itanium
4. и т.п.

Ниже я везде буду использовать название «time-stamp counter» или TSC, хотя на деле буду иметь в виду любой такой счетчик, независимо от архитектуры.
Прочитать значение TSC обычно –, но опять же не всегда — можно с помощью одной-единственной инструкции. Вот пример для x86. Строго говоря, это не чистая ассемблерная инструкция, а inline-ассемблер GNU:

uint32_t eax, edx;

__asm__ __volatile__( "rdtsc" : "=a" (eax), "=d" (edx));

Инструкция «rdtsc» помещает две 32-битных половинки регистра TSC в регистры eax и edx. Из них можно «склеить» единое 64-битное значение.

Еще раз отмечу: эту (и подобные) инструкции в большинстве случаев можно вызвать прямо из пользовательского пространства. Никаких системных вызовов. Минимум накладных расходов.
Что теперь нужно сделать, чтобы измерить время?

1. Исполнить одну такую инструкцию в начале интересующего нас промежутка времени. Запомнить значение счетчика
2. Исполнить одну такую инструкцию в конце. Мы считаем, что значение счетчика от первой инструкции ко второй вырастет. Иначе зачем он нужен? Запоминаем второе значение
3. Считаем разницу двух сохраненных значений. Это и есть наше время

Выглядит просто, но…

Время, измеренное по описанной процедуре, выражено в «попугаях». Оно не в секундах. Но иногда попугаи — это именно то, что нужно. Бывают ситуации, когда важны не абсолютные значения интервалов времени, а то, как различные интервалы соотносятся друг с другом. Приведенный выше пример со Spectre демонстрирует ровно такую ситуацию. Длительность каждого отдельного обращения к памяти значения не имеет. Важно только, что обращения по одним адресам будут исполнены значительно быстрее, чем по другим (в зависимости о того, хранятся ли данные в кеше или основной памяти).

А что если нужны не попугаи, а секунды/микросекунды/наносекунды и т.п.? Тут можно выделить два принципиально разных случая:

1. Наносекунды нужны, но потом. То есть допустимо сначала сделать все необходимы замеры в попугаях и сохранить их где-то для последующей обработки (например, в памяти). И лишь после того, как измерения закончены, не спеша конвертировать собранных попугаев в секунды
2. Наносекунды нужны «на лету». Например, у вашего процесса измерения есть какой-то «потребитель», которого вы не контролируете и который ожидает время именно в «человеческом» формате

Первый случай простой, второй — требует изворотливости. Конвертация должна быть максимально эффективной. Если она будет потреблять много ресурсов, то может сильно исказить процесс измерения. Про эффективную конвертацию мы поговорим ниже. Здесь же мы пока обозначили эту проблему и переходим к другой.

Time-stamp counter-ы не так просты, как нам хотелось бы. На некоторых архитектурах:

1. не гарантируется, что TSC обновляется с высокой частотой. Если TSC обновляется, допустим, раз в микросекунду, то наносекунды с его помощью фиксировать не получится
2. частота, с которой обновляется TSC, может меняться во времени
3. на различных CPU, присутствующих в системе, TSC могут обновляться с разной частотой
4. может существовать сдвиг между TSC, тикающими на разных CPU

Вот пример, иллюстрирующий последнюю проблему. Допустим, у нас есть система с двумя CPU: CPU1 и CPU2. Предположим, что TSC на первом CPU отстает от второго на количество тиков, которое эквивалентно 5 секундам. Допустим далее, что в системе запущен поток, который измеряет время вычислений, которые сам же и делает. Для этого поток сначала считывает значение TSC, затем делает вычисления, и потом считывает второе значение TSC. Если во время всей своей жизни поток остается только на одном CPU — на любом — то нет никаких проблем. Но что если поток стартовал на CPU1, там же измерил первое значение TSC, и потом в середине вычислений был перемещен операционной системой на CPU2, где прочел второе значение TSC? В этом случае вычисления будут казаться на 5 секунд длиннее, чем они есть в действительности.

Из-за перечисленных выше проблем TSC не может служить надежным источником времени на некоторых системах. Однако на других системах, «страдающих» от тех же проблем, TSC все же можно использовать. Это становится возможным благодаря специальным архитектурным фишкам:

1. аппаратура может генерировать специальное прерывание каждый раз, когда изменяется частота, с которой обновляется TSC. При этом аппаратура также предоставляет возможность узнать текущую частоту. Как альтернативный вариант, частота обновления TSC может быть отдана под контроль операционной системы (см. «Power ISA Version 2.06 Revision B, Book II, Chapter 5»)
2. аппаратура наряду со значением TSC может также предоставлять ID того CPU, на котором это значение прочитано (см. интеловскую инструкцию RDTSCP, «Intel 64 and IA-32 Architectures Software Developer’s Manual», Volume 2)
3. на некоторых системах можно программным образом скорректировать значение TSC для каждого CPU (см. интеловскую инструкцию WRMSR и регистр IA32_TIME_STAMP_COUNTER, «Intel 64 and IA-32 Architectures Software Developer’s Manual», Volume 3)

Вообще тема того, как счетчики времени реализованы на разных архитектурах, увлекательна и обширна. Если у вас есть время и интерес, рекомендую погрузиться. Среди прочего, вы узнаете, например, что некоторые системы позволяют программным образом выяснить, может ли TSC служить надежным источником времени.

Итак, существует множество архитектурных реализаций TSC, каждая со своими особенностями. Но интересно, что во всем этом зоопарке установился общий тренд. Современные железо и операционные системы стремятся гарантировать, что:

1. TSC тикает на одной и той же частоте на каждом CPU в системе
2. эта частота не меняется во времени
3. между TSC, тикающими на разных CPU, нет сдвига

При дизайне своей библиотеки я решил исходить из этой посылки, а не из винегрета аппаратных реализаций.

Библиотека

Я не стал закладываться на аппаратные фишки кучи разных архитектур. Вместо этого я решил, что моя библиотека будет ориентирована на современный тренд. У нее чисто эмпирический фокус:

1. она позволяет экспериментальным путем проверить надежность TSC как источника времени
2. также позволяет экспериментально вычислить параметры, необходимые для быстрой конвертации «тиков» в наносекунды
3. естественным образом, библиотека предоставляет удобные интерфейсы для чтения TSC и конвертации тиков в наносекунды «на лету»

Код библиотеки доступен здесь: https://github.com/AndreyNevolin/wtmlib
Компилироваться и исполняться он будет только на Линуксе.
В коде можно посмотреть детали реализации всех методов, о которых далее пойдет речь.

Оценка надежности TSC

Библиотека предоставляет интерфейс, который возвращает две оценки:

1. максимальный сдвиг между счетчиками, принадлежащими различным CPU. Рассматриваются только CPU, доступные процессу. Например, если процессу доступно три CPU, и в один и тот же момент времени TSC на этих CPU равны 50, 150, 20, то максимальный сдвиг будет 150–20=130. Естественно, экспериментальным путем библиотека реальный максимальный сдвиг получить не сможет, но она выдаст оценку, в которую этот сдвиг будет укладываться. Что с оценкой делать дальше? Как использовать? Это уже решает клиентский код. Но смысл примерно следующий. Максимальный сдвиг — это максимальная величина, на которую может быть искажено измерение, которое делает клиентский код. Допустим, в нашем примере с тремя CPU клиентский код начал измерять время на CPU3 (где TSC был 20), а закончил на CPU2 (где TSC был 150). Получается, что в измеренный интервал закрадется лишних 130 тиков. И никогда больше. Разница между CPU1 и CPU2 была бы только 100 тиков. Имея оценку в 130 тиков (на деле она будет сильно консервативнее) клиент может решить, устраивает его такая величина искажения или нет
2. возрастают ли значения TSC, измеренные последовательно на одном и том же или разных CPU. Здесь идея следующая. Допустим, у нас есть несколько CPU. Допустим, их часы синхронизированы и тикают с одной и той же частотой. Тогда если сначала измерить время на одном CPU, а потом измерить снова — уже на любом из доступных CPU — то вторая цифра должна быть больше первой.
   Эту оценку я ниже буду называть оценкой монотонности TSC
   

Посмотрим теперь, как можно получить первую оценку:

1. один из доступных процессу CPU объявляется «базовым»
2. далее перебираются все остальные CPU, и для каждого из них вычисляется сдвиг: TSC_на_текущем_CPU – TSC_на_базовом_CPU. Делается это следующим образом:
   
   • a) берутся три последовательно (одно за другим!) измеренные значения: TSC_base_1, TSC_current, TSC_base_2. Здесь current указывает на то, что значение было измерено на текущем CPU, а base — на базовом
   • b) сдвиг TSC_на_текущем_CPU – TSC_на_базовом_CPU обязан лежать в интервале [TSC_current – TSC_base_2, TSC_current – TSC_base_1]. Это в предположении, что TSC тикают с одной и той же частотой на обоих CPU
   • c) шаги a)-b) повторяются несколько раз. Вычисляется пересечение всех интервалов, полученных на шаге b). Результирующий интервал принимается за оценку сдвига TSC_на_текущем_CPU – TSC_на_базовом_CPU
   
   
3. после того, как получена оценка сдвига для каждого CPU относительно базового, легко получить оценку максимального сдвига между всеми доступными CPU:
   
   • a) вычисляется минимальный интервал, который включает в себя все результирующие интервалы, полученные на шаге 2
   • b) ширина этого интервала принимается за оценку максимального сдвига между TSC, тикающими на разных CPU
   
   

Для оценки монотонности в библиотеке реализован следующий алгоритм:

1. Допустим, процессу доступно N CPU
2. Измеряем TSC на CPU1
3. Измеряем TSC на CPU2
4. …
5. Измеряем TSC на CPUN
6. Снова измеряем TSC на CPU1
7. Проверяем, что измеренные значения монотонно увеличиваются от первого к последнему

Здесь важно, что первое и последнее значения измеряются на одном и том же CPU. И вот почему. Допустим, у нас есть 3 CPU. Предположим, что TSC на CPU2 сдвинут на +100 тиков по отношению к TSC на CPU1. Также предположим, что TSC на CPU3 сдвинут на +100 тиков по отношению к TSC на CPU2. Рассмотрим следующую цепочку событий:

• Прочитать TSC на CPU1. Пусть было получено значение 10
• Прошло 2 тика
• Прочитать TSC на CPU2. Должно быть 112
• Прошло 2 тика
• Прочитать TSC на CPU3. Должно быть 214

Пока что часы выглядят синхронизированными. Но давайте снова измерим TSC на CPU1:

• Прошло 2 тика
• Прочитать TSC на CPU1. Должно быть 16

Опа! Монотонность нарушена. Получается, что измерение первого и последнего значения на одном и том же CPU позволяет обнаруживать более-менее большие сдвиги между часами. Следующий вопрос, конечно же: «Насколько большие сдвиги?» Величина сдвига, который можно обнаружить, зависит от времени, которое проходит между последовательными измерениями TSC. В приведенном примере это всего 2 тика. Сдвиги между часами, превышающие 2 тика, будут обнаружены. Если говорить в общем, то сдвиги, которые меньше, чем время, проходящее между последовательными измерениями, обнаружены не будут. Значит, чем плотнее во времени расположены измерения, тем лучше. От этого зависит точность обеих оценок. Чем плотнее делаются замеры:

• тем ниже оценка максимального сдвига
• тем больше доверия к оценке монотонности

В следующем разделе поговорим о том, как делать плотные замеры. Здесь же добавлю, что во время вычисления оценок надежности TSC библиотека делает еще множество простых проверок «на вшивость», например:

• ограниченную проверку того, что TSC на разных CPU тикают с одинаковой скоростью
• проверку того, что счетчики действительно изменяются во времени, а не просто показывают одно и то же значение

Два метода сбора значений счетчиков

В библиотеке я реализовал два метода сбора значений TSC:

1. Переключение между CPU. В этом методе все данные, необходимые для оценки надежности TSC, собираются одним-единственным потоком, который «прыгает» с одного CPU на другой. Оба алгоритма, описанные в предыдущем разделе, подходят именно для этого метода и не подходят для другого.
   Практической пользы «переключение между CPU» не имеет. Метод был реализован просто ради «поиграться». Проблема метода в том, что время, необходимое для того, чтобы «перетащить» поток с одного CPU на другой, очень велико. Соответственно, между последовательными измерениями TSC проходит уйма времени, и точность оценок получается очень низкой. Например, типичная оценка для максимального сдвига между TSC получается в районе 23000 тиков.
   Тем не менее, у метода есть пара достоинств:
   
   • он абсолютно детерминированный. Если нужно последовательно измерить TSC на CPU1, CPU2, CPU3, то мы просто берем и делаем это: переключаемся на CPU1, читаем TSC, переключаемся на CPU2, читаем TSC, и наконец, переключаемся на CPU3, читаем TSC
   • предположительно, если количество CPU в системе очень быстро растет, то время переключения между ними должно расти гораздо медленнее. Поэтому в теории, видимо, может существовать система — очень большая система! — в которой использование метода будет оправдано. Но все же это маловероятно
   
   
2. Замеры, упорядоченные с помощью CAS. В этом методе данные собираются параллельно множеством потоков. На каждом доступном CPU запускается один поток. Измерения, сделанные разными потоками, упорядочиваются в единую последовательность с помощью операции «compare-and-swap». Ниже будет кусок кода, который показывает, как это делается.
   Идея метода позаимствована из fio, популярного инструмента генерации I/O-нагрузок.
   Оценки надежности, получаемые с мощью этого метода, выглядят уже очень неплохо. Например, оценка максимально сдвига получается уже на уровне нескольких сотен тиков. А проверка монотонности позволяет поймать рассинхронизацию часов в пределах сотни тиков.
   Однако алгоритмы, приведенные в предыдущем разделе, не подходят для этого метода. Для них важно, чтобы значения TSC были измерены в заранее определенном порядке. Метод «замеров, упорядоченных с помощью CAS» не позволяет этого сделать. Вместо этого, сначала собирается длинная последовательность случайных измерений, и затем алгоритмы (уже другие) пытаются найти в этой последовательности значения, прочитанные на «подходящих» CPU.
   Я не буду приводить здесь эти алгоритмы, чтобы не злоупотреблять вашим вниманием. Их можно посмотреть в коде. Там много комментариев. Идейно эти алгоритмы те же самые. Принципиально новый момент — это проверка того, насколько статистически «качественными» являются случайно набранные последовательности TSC. Также возможно задать минимально приемлемый уровень статистической значимости для оценок надежности TSC.
   Теоретически, на ОЧЕНЬ больших системах метод «замеров, упорядоченных с помощью CAS» может давать плохие результаты. Метод требует, чтобы процессоры состязались за доступ к общей ячейке памяти. Если процессоров очень много, то состязание может получиться очень напряженным. В результате, будет сложно создать последовательность измерений с хорошими статистическими свойствами. Однако на данный момент такая ситуация выглядит маловероятной.
   

Я обещал немного кода. Вот как выглядит выстраивание замеров в единую цепочку с помощью CAS.

    for ( uint64_t i = 0; i < arg->probes_count; i++ )
    {
        uint64_t seq_num = 0;
        uint64_t tsc_val = 0;

        do
        {
            __atomic_load( seq_counter, &seq_num, __ATOMIC_ACQUIRE);
            __sync_synchronize();
            tsc_val = WTMLIB_GET_TSC();
        } while ( !__atomic_compare_exchange_n( seq_counter, &seq_num, seq_num + 1, false, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED));

        arg->tsc_probes[i].seq_num = seq_num;
        arg->tsc_probes[i].tsc_val = tsc_val;
    }

Этот код исполняется на каждом доступном CPU. Все потоки имеют доступ к общей переменной seq_counter. Перед тем, как прочитать TSC, поток считывает значение этой переменной и сохраняет его в переменной seq_num. Затем читает TSC. Затем пытается атомарно увеличить seq_counter на единицу, но только в том случае, если значение переменной не изменилось с момента чтения. Если операция проходит успешно, то это означает, что потоку удалось «застолбить» за измеренным значением TSC порядковый номер, сохраненный в seq_num. Следующий порядковый номер, который удастся застолбить (возможно, уже в другом потоке) будет на единицу больше. Ибо этот номер берется из переменной seq_counter, а каждый успешный вызов __atomic_compare_exchange_n() увеличивает эту переменную на единицу.

Еще один момент, о котором стоит здесь упомянуть — это забота о том, чтобы все потоки, занимающиеся измерениями, стартанули более-менее одновременно. Мы заинтересованы в том, чтобы значения TSC, прочитанные на разных CPU, были как можно лучше перемешаны между собой. Нас не устроит ситуация, когда, например, сначала запустится один поток, закончит свою работу, и только потом запустятся все остальные. У результирующей последовательности TSC будут никудышные свойства. Из нее не получится извлечь никаких оценок. Одновременный старт всех потоков важен — и для этого в библиотеке приняты меры.

Конвертация тиков в наносекунды «на лету»

После проверки надежности TSC, второе большое назначение библиотеки — это конвертация тиков в наносекунды на лету. Идею этой конвертации я позаимствовал из уже упомянутого fio. Однако мне пришлось внести несколько существенных улучшений, потому что как показал мой анализ, в самом fio процедура конвертации работает недостаточно хорошо. Там получается низкая точность.

Сразу начну с примера.
В идеале, конвертировать тики в наносекунды хотелось бы вот так:
ns_time = tsc_ticks / tsc_per_ns
Мы хотим, чтобы время, затрачиваемое на конвертацию, было минимальным. Поэтому мы нацелены на использование исключительно целочисленной арифметики. Посмотрим, чем это может нам грозить.
Если tsc_per_ns = 3, то простое целочисленное деление, с точки зрения точности, работает прекрасно: ns_time = tsc_ticks / 3.
Но что, если tsc_per_ns = 3.333? Если это число будет округлено до 3, то точность конвертации будет очень низкой. Преодолеть эту проблему можно следующим образом:
ns_time = (tsc_ticks * factor) / (3.333 * factor)
Если множитель factor достаточно большой, то и точность будет хорошей. Но кое-что останется плохим. А именно, накладные расходы на конвертацию. Целочисленное деление — это очень дорогая операция. Например, на x86 она требует 10+ тактов. Плюс к тому, операции целочисленного деления не всегда конвейеризуются.

Перепишем нашу формулу в эквивалентной форме:
ns_time = (tsc_ticks * factor / 3.333) / factor

Первое деление — не проблема. Мы можем предвычислить (factor / 3.333) заранее. А вот второе деление — по-прежнему боль. Чтобы избавиться от нее, давайте выберем factor равным степени двойки. После этого второе деление можно будет заменить на битовый сдвиг — простую и быструю операцию.

Насколько большим можно выбрать factor? К сожалению, factor не может быть сколь угодно большим. Он ограничен тем условием, что умножение, находящееся в числителе, не должно приводить к переполнению 64-битного типа. Да, мы хотим использовать только «родные» типы. Опять же, чтобы держать накладные расходы на конвертацию на минимальном уровне.

Посмотрим теперь, насколько большим может быть factor в нашем конкретном примере. Допустим, мы хотим работать с временными интервалами вплоть до одного года. За год TSC тикнет следующее количество раз: 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000. Разделим максимальное значение 64-битного типа на это число: 18446744073709551615 / 105109488000000000 ~ 175.5. Таким образом, выражение (factor / 3.333) не должно быть больше, чем это значение. Тогда имеем: factor <= 175.5 * 3.333 ~ 584.9. Самая большая степень двойки, которая не превосходит этого числа, равна 512. Следовательно, наша формула конвертации принимает вид:
ns_time = (tsc_ticks * 512 / 3.333) / 512

Или:
ns_time = tsc_ticks * 153 / 512

Прекрасно. Давайте теперь посмотрим, что у этой формулы с точностью. В одном году содержится 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000 наносекунд. Наша же формула дает: 105109488000000000 * 153 / 512 = 31409671218750000. Разница с настоящим значением составляет 126328781250000 наносекунд, или 126328781250000 / 1000000000 / 60 / 60 ~ 35 часов.

Это большая ошибка. Мы хотим лучшей точности. Что если мы будем измерять интервалы времени не более часа? Я опущу выкладки. Они совершенно идентичны только что проделанным. Окончательная формула будет:
ns_time = tsc_ticks * 1258417 / 4194304 (1)

Ошибка конвертации составит лишь 119305 наносекунд на 1 час (что меньше 0.2 миллисекунды). Очень и очень неплохо. Если же максимальное конвертируемое значение будет еще меньше, чем час, то и точность будет еще лучше. Но как нам это использовать? Не ограничивать же измерения времени одним часом?

Обратим внимание на следующий момент:
tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

Если мы предвычислим tsc_ticks_per_1_hour, то сможем извлечь number_of_hours из tsc_ticks. Далее, мы знаем, сколько наносекунд содержится в одном часе. Поэтому нам не составит труда перевести в наносекунды ту часть tsc_ticks, которая соответствует целому количеству часов. Чтобы закончить конвертацию, нам останется перевести в наносекунды tsc_ticks_remainder. Однако мы знаем, что это количество тиков натикало меньше, чем за час. А значит, чтобы преобразовать его в наносекунды, мы можем воспользоваться формулой (1).

Готово. Такой механизм конвертации нас устраивает. Давайте теперь его обобщим и оптимизируем.
Прежде всего, мы хотим иметь гибкий контроль над ошибками конвертации. Мы не хотим привязывать параметры конвертации к интервалу времени в 1 час. Пусть это будет произвольный интервал времени:
tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

Еще раз вспомним, как конвертировать остаток в наносекунды:
ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

Вычислим параметры конвертации (мы знаем, что tsc_ticks_remainder < modulus):
modulus * (factor / tsc_per_nsec) <= UINT64_MAX
factor <= (UINT64_MAX / modulus) * tsc_per_nsec
2 ^ shift <= (UINT64_MAX / modulus) * tsc_per_nsec

Занудства ради, надо отметить, что последнее неравенство не эквивалентно первому в рамках целочисленной арифметики. Но я не буду на этом надолго останавливаться. Скажу только, что последнее неравенство более жесткое, чем первое, и поэтому безопасно для использования.

После того, как из последнего неравенства получен shift, мы вычисляем:
factor = 2 ^ shift
mult = factor / tsc_per_nsec

И дальше эти параметры используются для конвертации остатка в наносекунды:
ns_per_remainder = (tsc_ticks_remainder * mult) >> shift

Итак, с конвертацией остатка разобрались. Следующая проблема, которую надо решить — это извлечение tsc_ticks_remainder и number_of_moduli_periods из tsc_ticks. Как всегда, мы хотим делать это быстро. Как всегда, мы не хотим использовать деление. Поэтому просто выбираем modulus равным степени двойки:
modulus = 2 ^ remainder_bit_length
Тогда:
number_of_moduli_periods = tsc_ticks >> remainder_bit_length
tsc_ticks_remainder = tsc_ticks & (modulus - 1)

Отлично. Мы теперь знаем, как извлечь из tsc_ticks number_of_moduli_periods и tsc_ticks_remainder. И знаем, как конвертировать tsc_ticks_remainder в наносекунды. Осталось понять, как конвертировать в наносекунды ту часть тиков, которая кратна modulus. Но тут все просто:
ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_modulus можно вычислить заранее. Причем по той же формуле, по которой мы конвертируем остаток. Эту формулу можно использовать для промежутков времени, которые не длиннее, чем modulus. Сам modulus, естественно, не длиннее, чем modulus.
ns_per_modulus = (modulus * mult) >> shift

Все! Мы смогли предвычислить все параметры, необходимые для конвертации тиков в наносекунды «на лету». Суммируем теперь кратенько процедуру конвертации:

1. имеем tsc_ticks
2. number_of_moduli_periods = tsc_ticks >> remainder_bit_length
3. tsc_ticks_remainder = tsc_ticks & (modulus - 1)
4. ns = ns_per_modulus * number_of_moduli_periods + (tsc_ticks_remainder * mult) >> shift

В этой процедуре параметры remainder_bit_length, modulus, ns_per_modulus, mult и shift предвычислены заранее.

Если вы все еще читаете этот пост, то вы большой или большая молодец. Возможно даже, что вы performance-аналитик или разработчик высокопроизводительного софта.
Так вот. Оказывается, мы еще не закончили :)

Помните, как мы вычислили параметр mult? Это было вот так:
mult = factor / tsc_per_nsec

Вопрос: откуда берется tsc_per_nsec?
Количество тиков в одной наносекунде — это очень маленькая величина. В действительности в моей библиотеке вместо tsc_per_nsec используется (tsc_per_sec / 1000000000). Т.е.:
mult = factor * 1000000000 / tsc_per_sec

И тут есть два интересных вопроса:

1. Почему tsc_per_sec, а не tsc_per_msec, например?
2. Откуда взять эти tsc_per_sec?

Начнем с первого. В fio сейчас действительно используется количество тиков в миллисекунде. И с этим есть проблемы. На машине, параметры которой я называл выше, tsc_per_msec = 2599998. В то время как tsc_per_sec = 2599998971. Если привести эти числа к одному масштабу, то их отношение будет очень близко к единице: 0.999999626. Но если мы будем использовать первое, а не второе, то на каждую секунду у нас будет ошибка 374 наносекунды. Поэтому — tsc_per_sec.

Далее… Как посчитать tsc_per_sec?
Делается это на основе прямого измерения:
start_sytem_time = clock_gettime()
start_tsc = WTMLIB_GET_TSC()
подождать сколько-то времени
end_system_time = clock_gettime()
end_tsc = WTMLIB_GET_TSC()

«сколько-то времени» — это конфигурируемый параметр. Он может быть больше, меньше или равен одной секунде. Допустим, это полсекунды. Допустим далее, что реальная разница между end_system_time и start_system_time оказалась равна 0,6 секунды. Тогда tsc_per_sec = (end_tsc – start_tsc) / 0,6.

Библиотека считает таким способом несколько значений tsc_per_sec. А затем стандартными методами «очищает» их от статистического шума и получает одно-единственное значение tsc_per_sec, которому можно доверять.

В схеме измерения времени, приведенной выше, важен порядок вызовов clock_gettime() и WTMLIB_GET_TSC(). Важно, чтобы между двумя вызовами WTMLIB_GET_TSC() прошло то же самое время, что и между двумя вызовами clock_gettime(). Тогда можно будет легко соотнести системное время с тиками TSC. И тогда разброс значений tsc_per_sec действительно можно будет считать случайным. При такой схеме измерений значения tsc_per_sec будут отклоняться от среднего значения в любую сторону с одинаковой вероятностью. И к ним можно будет применить стандартные методы фильтрации.

Заключение

Пожалуй, все.

Но тема эффективного измерения времени на этом не исчерпывается. Есть много нюансов. Заинтересованным предлагаю самостоятельно проработать следующие вопросы:

• хранение параметров конвертации в кеше или — еще лучше — на регистрах
• до каких пределов можно уменьшать modulus (тем самым повышая точность конвертации)?
• как мы видели, на точность конвертации влияет не только modulus, но еще и величина интервала времени, который соотносится с тиками (tsc_per_msec или tsc_per_sec). Как сбалансировать влияние обоих факторов?
• TSC на виртуальной машине. Можно ли использовать?
• использование стандартных структур операционной системы для хранения времени. Например, fio сохраняет свои наносекунды в стандартном линуксовом формате timespec. Вот как это происходит:
  tp->tv_sec = nsecs / 1000000000ULL;
  Получается, что сначала TSC тики конвертируются в наносекунды с помощью быстрой и эффективной процедуры. А потом весь выигрыш нивелируется за счет целочисленного деления, которое нужно, чтобы из наносекунд выделить секунды
  

Рассмотренные в этой статье методы позволяют измерять время масштаба секунды с точностью порядка нескольких десятков наносекунд. Это та точность, которую я реально наблюдаю при использовании своей библиотеки.

Интересно, что fio, из которого я позаимствовал некоторые методы, на масштабе секунды теряет в точности порядка 700–900 наносекунд (и тому есть целых три причины). Плюс теряет в скорости конвертации из-за хранения времени в стандартном линуксовом формате. Однако спешу успокоить фанатов fio. Я отправил разработчикам описание всех проблем с конвертацией, которые обнаружил: github.com/axboe/fio/issues/695. Люди уже работают, скоро исправят.

Желаю всем много приятных наносекунд!

© Habrahabr.ru