image

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

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

Так как на компьютере можно измерять много разных типов времени, сразу уточню, что здесь речь пойдет о «времени по секундомеру». Или 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:

image

Здесь в строках 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 и конвертации тиков в наносекунды «на лету»

Код библиотеки доступен здесь. Компилироваться и исполняться он будет только на Линуксе.

В коде можно посмотреть детали реализации всех методов, о которых далее пойдет речь.

Оценка надежности 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() увеличивает эту переменную на единицу.

__atomic вместе с __sync???
Занудства ради, надо отметить, что использование встроенных функций семейства __atomic совместно с функцией из устаревшего семейства __sync выглядит некрасиво. __sync_synchronize() использована в коде для того, чтобы избежать переупорядочения операции чтения TSC с вышележащими операциями. Для этого нужен полный барьер по памяти. В семействе __atomic формально нет функции c соответствующими свойствами. Хотя по факту есть: __atomic_signal_fence(). Эта функция упорядочивает вычисления потока с обработчиками сигналов, исполняющимися в том же потоке. По сути, это и есть полный барьер. Тем не менее прямо это не заявлено. А я предпочитаю код, в котором нет скрытой семантики. Отсюда __sync_synchronize() – стопудовый полный барьер по памяти.

Еще один момент, о котором стоит здесь упомянуть – это забота о том, чтобы все потоки, занимающиеся измерениями, стартанули более-менее одновременно. Мы заинтересованы в том, чтобы значения 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. Я отправил разработчикам описание всех проблем с конвертацией, которые обнаружил. Люди уже работают, скоро исправят.

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

Комментарии (26)


  1. c0f04
    05.10.2018 07:28
    -2

    А для чего понадобилась собственная система измерения времени, почему не взять из существующих ОС? В Linux, например, есть стандартная функция POSIX.1-2001 clock_gettime(). Возвращает время с учётом наносекунд. Умеет работать с CLOCK_MONOTONIC. Т. к. POSIX, другие ОС тоже могут поддерживать эту функцию.


    1. nfw
      05.10.2018 08:23
      +1

      Вы статью-то дальше заголовка читали?

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


      1. c0f04
        05.10.2018 19:02

        Прошу прощения. Просматривал кусками, но делал Ctrl+F, «linux», поэтому не нашёл. Не привык я, чтобы на русском сие название писали.

        Собственно, это и есть ответ на мой вопрос, спасибо.


  1. alexey_prokopyev
    05.10.2018 11:02

    Интересно узнать, для каких практических задач автору понадобилась точность и дискретизация до наносекунд


    1. TimsTims
      05.10.2018 13:16

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


      1. maxzhurkin
        06.10.2018 15:32

        Но такие измерения будут актуальны только для системы, на которой производятся эти измерения (в широком трактовании понимания системы, разумеется)


  1. paradox072
    05.10.2018 11:02

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


    1. tangro
      05.10.2018 11:10

      Более того, измерение серий ещё и ближе к реальному использованию. На практике чаще всего не важно, насколько быстро отработает данный конкретный код одноразово, но важно, чтобы миллион выполнений выполнился как-можно быстрее.

      Единственное, что приходит в голову — какой-то очень высокочастотный трейдинг. Т.е. если код выполнился за 1 наносекунду, то надо поднять ставку на 1 цент, а если за 3 наносекунды — то уже на 3 цента.


      1. JediPhilosopher
        05.10.2018 13:21

        Ну в теории оно может пригодиться во всяких микробенчмарках для тех, кто делает оптимизации для компилятора. Я таким в своем дипломе занимался, когда генетичекими алгоритмами оптимизировал байткод для джавы (даже статью на хабре писал).
        Тут проблема в том, что если считать в цикле миллион вызовов какой-то инструкции, то сам цикл (увеличение счетчиков, проверка условий) может занимать больше времени, чем проверяемая инструкция, и в итоге очень сильно усложнять оценку результата. Вообще микробенчмаркинг та еще боль, так как на результаты начинают ощутимо влиять всякие случайные погрешности, запущенный на компьютере софт и ОС и чуть ли не погода на Марсе. Ну и неточные счетчики в том числе.
        При этом выигрыш одной конкретной оптимизации действительно может быть микроскопическим (кто там будет считать нынче выигрыш от какой-нибудь классической замены mov eax 0 на xor eax eax?). Но множество различных подобных оптимизаций в масштабах целой программы уже дают значительный эффект.


        1. kmu1990
          05.10.2018 17:11

          Чтобы оптимизация какой-то индивидуальной строки которая сама по себе выполняется доли секунд приносила эффект, эта строка должна выполниться много раз а иначе откуда выигрышу взяться?
          В этом случае если реализация самого цикла занимает настолько значительное время, что на фоне этого оптимизация кода который выполняется в цикле не приносит измеримого выигрыша, то какой собственно толк от такой оптимизации?


  1. multiadmin
    05.10.2018 11:02

    … аппаратура наряду со значением TSC может также предоставлять ID того CPU, на котором это значение прочитано (см. интеловскую инструкцию RDTSCP, «Intel 64 and IA-32 Architectures Software Developer's Manual», Volume 2)...

    Какое-то странное пояснение. Как я понимаю, фишка RDTSCP — инвариантность:

    ...The invariant TSC will run at a constant rate in all ACPI P-, C-. and T-states. This is the architectural behavior moving forward. On processors with invariant TSC support, the OS may use the TSC for wall clock timer services (instead of ACPI or HPET timers)...

    ...The invariant TSC means that the TSC continues at a fixed rate regardless of the C-state or frequency of the processor...

    кроме этого:

    ...The RDTSCP instruction waits until all previous instructions have been executed before reading the counter. However, subsequent instructions may begin execution before the read operation is performed...

    в отличии от:

    ...The RDTSC instruction is not a serializing instruction. It does not necessarily wait until all previous instructions have been executed before reading the counter...


    1. radiolok
      05.10.2018 16:53

      Возвращаемое значение в EDX:EAX там будет лежать тоже самое что и после RDTSC
      Отличие как вы верно заметили в ожидании выполнения некоторых инструкций.
      Плюс возвращается TSC_AUX, который согласно Intel-SDM:Chapter 17.17.2 позволит оценить разницу значений TSC разных CPU.



      А что до инвариантности — либо TSC инвариантен в целом(CPUID.80000007H:EDX[8] == 1), либо ее нет в процессоре в принципе(SDM:Chapter:17.17.1).


      1. multiadmin
        05.10.2018 17:20

        Да, извиняюсь, изначально ввел в заблуждение. Еще ответил здесь: habr.com/post/425237/#comment_19197589


      1. multiadmin
        05.10.2018 17:35

        А что до инвариантности — либо TSC инвариантен в целом(CPUID.80000007H:EDX[8] == 1), либо ее нет в процессоре в принципе(SDM:Chapter:17.17.1).

        Кстати, посмотрел, на моем ноутбучном i3 2014 года этот бит стоит, т.е. у меня в системе инвариантный TSC.


  1. Jenix
    05.10.2018 12:00

    Измерять интервалы с помощью программы, время исполнения которой в сотни раз больше интервала? )) Ну такое. Для этого существуют аппаратные решения уже давно.

    Для одного из первых рыночных решений на i8080 интел сделала i8253 — интервальный таймер.
    Его минимальный интервал — 0,5 мкс — 1 тик. А например время выполнение простой команды для i8080 — 4 тика синхры — т.е. 2 мкс.

    При этом всё удобно читается из программы, а время создания этого решения 1974 год. Но нет — надо ведь помучится и получить приблизительный результат аж через 44 года. Программисты, такие программисты. )))


    1. 8street
      05.10.2018 12:50

      А мне в голову еще один вариант пришел. Взять высокостабильный генератор, счетчик, возможно еще и МК. Правда, придется немного попаять.


      1. Alexeyslav
        05.10.2018 13:30

        Задача ради задачи? Извлечь значение с МК будет вечностью по меркам процессора. Команды старт-стоп будут запаздывать на микросекунды… так себе решение. И едва ли им измеришь выполнение кода на основном процессоре величиной в 20...50 инструкций, переключение контекста для передачи команд займет неймоверно много времени.
        Высокостабильность генератора вообще перпендикулярное требование, оно может накладываться на задачу а может быть не важным. Более того, высокостабильные генераторы обычно очень прихотливы и долго выходят на режим — например такой генератор как ГИАЦИНТ-М, выходит на рабочий режим ЧАСЫ!


        1. 8street
          05.10.2018 14:31

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


  1. Alexeyslav
    05.10.2018 13:18

    Интересно. Именно из-за проблемы рассинхронизации счетчиков на разных ядрах лет 5 назад у меня переставал работать пульт от ТВ-тюнера через пол часа работы компьютера. Оказалось, что это была проблема исключительно для AMD-процессоров. А я-то думал что пульт обрабатывается в тюнере аппаратно…


  1. balexa
    05.10.2018 13:25

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


  1. acckiitvar
    05.10.2018 16:03
    -1

    Я в какой-то момент окунулся в этот процесс высокоточных измерений, но умный человек посоветовал использовать HPET и не париться, точность у меня получилась порядка 600нс и она была ограничена временем доступа к HPET. Использовать RDTSC я не стал из-за того, что на разных ядрах у него ТОЧНО разные значения и частота его инкрементации зависит от частоты процессора. А так как все процессоры имеют авторазгон и прочие возможности поменять в динамике частоту, преобразование тики -> секунды стало не тривиальным.
    Для тех кому интересно зачем это надо: современная высокоскоростная периферия требует таких скоростей, ты обязан подать или считать данные через малый интервал времени, а Винда может отсечь не менее 15 микросекунд с вероятностью что это значение сильно возрастет.


    1. multiadmin
      05.10.2018 16:07
      -1

      Использовать RDTSC я не стал из-за того, что на разных ядрах у него ТОЧНО разные значения и частота его инкрементации зависит от частоты процессора

      Я выше в комментарии уже упомянул, что есть RDTSCP — инвариантная версия RDTSC, у которой такой зависимости нет. Так же, RDTSCP выполнится не раньше, чем все предыдущие команды, стоящие до него.

      Только в статье про это почему-то не написано.


      1. acckiitvar
        05.10.2018 16:22

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


        1. multiadmin
          05.10.2018 17:15

          Но она как-то решает проблему изменения частоты ядер?

          Извиняюсь, ввел в заблуждение.

          RDTSCP — это выполнение LFENCE (или в какой-то мере аналог) + чтение TSC (то же, что дает RDTSC) + чтение ID

          И инвариантный TSC — это отдельная фича, проверяется CPUID.80000007H:EDX[8].

          Если эта фича есть, то что RDTSC, что RDTSCP дают значения, которые не зависят от изменения частоты ядер.


  1. radiolok
    05.10.2018 16:11

    Аппаратный метод для тех случаев когда время выполнения нужно «потом»:

    В процессорах Intel (начиная со Skylake и Goldmont) есть технология Processor Trace. Аппаратная фича для записи всего потока выполения приложения, в том числе с временными метками.

    Без инструментации приложения, с помощью simple-pt собирается трасса (главное не забыть включить генерацию CYC пакетов) и с минимальным оверхедом в рантайме, можно получать точность в единицы клоктиков процессора для линейного блока кода (итерации цикла например). Linux perf тоже умеет собирать PT, но там нет поддержки CYC-пакетов.


  1. janatem
    05.10.2018 19:35

    Для пересчета тиков в секунды можно попробовать всё-таки использовать FPU, только вместо деления делать умножение на обратную величину. (Будем считать, что перекалибровка частоты, после которой нужно делить, происходит очень редко.) То есть на критическом участке кода имеем одно FPU-умножение (обычно 3 такта), конверсию integer -> float и обратно (еще два раза примерно по одному такту).