как считать циклы?

Question

Я пытаюсь найти относительные достоинства двух маленьких функций в C. Одна, которая добавляет по циклу, другая, которая добавляет по явным переменным.Функции сами по себе не имеют значения, но я бы хотел, чтобы кто-то научил меня считать циклы, чтобы сравнивать алгоритмы.Таким образом, для f1 потребуется 10 циклов, а для f2 - 8. Я бы хотел так рассуждать.Никаких измерений производительности (например, gprof эксперименты) на данный момент, просто старый добрый подсчет команд.

Есть ли хороший способ сделать это?Есть ли инструменты?Документация?Я пишу C, компилируя с gcc на архитектуре x86.

Answer 1

http://icl.cs.utk.edu/papi/

PAPI_get_real_cyc (3) - вернуть общее количество циклов с некоторой произвольной начальной точкой

Answer 2

Инструкция ассемблера rdtsc (чтение счетчика меток времени) повторная установка в EDX: EAX регистрирует текущее число тактов ЦП, начатое при сбросе ЦП. Если ваш процессор работает на частоте 3 ГГц, то один такт составляет 1/3 ГГц.

EDIT: В MS Windows вызов API QueryPerformanceFrequency возвращает количество тактов в секунду.

Answer 3

К сожалению, синхронизация кода так же подвержена ошибкам, как визуальный подсчет команд и тактов.Будь то отладчик или другой инструмент, или повторная компиляция кода с повторным запуском 10000000 раз и время, когда вы что-то делаете, вы меняете место попадания в строку кэша, частоту попаданий и пропаданий кэша и т. Д.смягчить некоторые из них, добавив или удалив некоторый код вверх по потоку из модуля тестируемого кода (чтобы несколько добавленных и удаленных инструкций изменили выравнивание вашей программы, а иногда и ваших данных).

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

Answer 4

Как писал GJ в другом ответе, я также рекомендую использовать инструкцию "rdtsc" (вместо вызова некоторой функции операционной системы, которая выглядит правильно).

Я написал довольно много ответов на эту тему.Rdtsc позволяет вам вычислять истекшие тактовые циклы в «естественной» среде выполнения кода, а не прибегать к его вызову десять миллионов раз, что может быть неосуществимо, поскольку не все функции являются черными ящиками.чтобы рассчитать истекшее время, вы можете отключить энергосбережение на процессорах.Если это только вопрос тактов, то в этом нет необходимости.

Answer 5

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

Answer 6

Если вы пытаетесь сравнить производительность, самый простой способ - это поместить свой алгоритм в цикл и запустить его 1000 или 1000000 раз.

Как только вы запустите его достаточно раз, чтобы увидеть небольшие различия, запустите time ./my_program, который даст вам количество процессорного времени, которое он использовал.

Сделайте это несколько раз, чтобы получить выборку и сравнить результаты.

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

Answer 7

Это не совсем тривиальный вопрос.Позвольте мне попытаться объяснить:

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

Я не могу дать вам однозначный ответ, потому что мне не хватаетданные, по которым я могу судить, но я работаю на IBM в области баз данных, и мы используем инструменты для измерения циклов и инструкций для нашего кода, и эти трассы действительны только для фактического процессора, на котором была скомпилирована и выполнялась программа.В зависимости от внутренней структуры конвейера вашего процессора и эффективности вашего компилятора, результирующий код, скорее всего, все еще будет иметь ошибки в кеше и другие области, о которых вам придется беспокоиться.(В этом случае вы, возможно, захотите взглянуть на FDPR ...)

Если вы хотите узнать, сколько циклов требуется вашей программе для запуска на вашем ЦП (который был скомпилирован вашим компилятором), вы должны понимать,как работает процессор и как компилятор генерировал код.

Извините, если ответа было недостаточно для решения вашей проблемы под рукой.Вы сказали, что используете gcc для арки x86.Я хотел бы работать с получением кода сборки, сопоставленного с вашим процессором.Я уверен, что вы найдете некоторые области, где gcc мог бы работать лучше ...

Answer 8

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

Answer 9

Используйте gcc -S your_program.c.-S говорит gcc сгенерировать листинг сборки, который будет называться your_program.s.