сравнение временных затрат на простейшие операторы

[Paul Ivanov]

Добрый день!
Пытаюсь измерить среднее время, затрачиваемое на выполнение различного рода операторов в Си, при условии, что компьютер, на фоне сильно колебающихся по величине затрат на фоновые процессы, работает максимально эффективно (поэтому min - минимум).
У меня стоит windows 10 64-bit.
Написал код, часть которого выглядит так:

(int N=1000, C=100000) (при изменении этих параметров результат меняется примерно пропорционально изменению N)
На моём компьютере QueryPerformanceCounter тикает раз в 100 наносекунд. На выходе у меня получается 45 (плюс-минус 1) тиков. Если же я все s=1; заменяю на s++;, то получается 205 тиков (плюс-минус 10). Причём такое кардинальное отличие сохраняется при увеличении количества операторов s=1;/s++; (в коде выше их тринадцать) и даже увеличивается до 6-7 раз и примерно стабилизируется (если усреднять вполне естественные колебания).
К сожалению я имею слабое представление о том, как именно реализуются данные операции на машинном уровне, но знаю, например, что время присваивания практически не зависит от того, какое число присваевается и всегда имел наивную веру в то, что инкремент на деле должен выполняться на порядок быстрее присваивания и вообще является одним из самых быстрых операторов.
Почему же тогда выходит, что инкремент выполняется 5-6 кратно дольше? Может я вообще неправильно интерпретирую результаты, а если так то в чём загвоздка?
Прошу объяснить относительно популярно, так как с железом ниже высокоуровневых языков никогда не работал.
(вообще если кто-то знает, где можно посмотреть таблицу временных затрат на простейшие операторы с точки зрения пропорционального отношения, то буду очень благодарен, если поделитесь, потому что мне гугл, к сожалению, не помог)
Спасибо.

[StaticZero]

Paul Ivanov, компилируете без оптимизаций? Ассемблер умеете смотреть?

[Paul Ivanov]

Да, без. К сожалению, не умею.

[StaticZero]

Paul Ivanov в сообщении #1500111 писал(а):

К сожалению, не умею.

gcc main.c -S, файлик main.s будет его содержать. Только если хотите, чтобы можно было что-то посмотреть, вам желательно будет прилепить и исходный код тоже, не только ассемблер. Ну и программу упростить до нельзя тоже желательно, чтобы не замусоривать суть вопроса.

[Paul Ivanov]

Понял, буду пробовать.
Спасибо

[StaticZero]

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

[StepV]

Paul Ivanov в сообщении #1500109 писал(а):

Пытаюсь измерить среднее время, затрачиваемое на выполнение различного рода операторов в Си

Знаете, этим до вас пробовали заниматься очень многие. Все новые фирмы разработчики ПО, когда создаются, начинают с этого, а потом бросают. Потому что программист может снизить выполнение программ улучшением алгоритма, когда дело идет о часах, минутах, секундах.
Разобраться с исполнением отдельных операций в естественной программной среде современных OS невозможно. Есть данные от фирм по производительности операций их железа в тактах синхронизатора, вот, пожалуй и все.
Для вашей программы могу выделить несколько пунктов.
1. Сначала много оптимизировал транслятор. Например, все тринадцать идентичных операторов заменил одним.
2. Когда вы поставили инкремент, то первый инкремент занял в тактах процессора максимальное время, т.к. была выработка адреса ячейки, операция одновременного считывания в регистр ЦП и КЭШ, выполнение арифметической операции, а затем запись в кэш. Следующие операции инкремента производились с кешем. И иногда перезаписью этих значений в память.
3. В середине цикла программа могла несколько раз прерываться системным таймером и диспетчер OS производил системные работы. Это тоже удлиняет некоторые циклы.
Теперь к общему случаю исполнения, но не именно конкретно вашей программы. Еще особенности, у процессора имеется регистр команд, в которые подкачивается ваш код перед исполнением. Если код длинный, то на середине исполнения программы, она может быть снята с ЦП для загрузки в процессор новой порции исполняемого кода.
Каждой ваше обращение за системными ресурсами тоже убивает кучу времени, которую трудно предсказать. Например, заказ памяти, снимает ваш процесс с процессора и в следующем такте программы управления памятью компьютера выделяют кусок и после этого ваша программа продолжит исполнение.
Каждый ввод- вывод тоже снимает вашу программу с процессора для выполнения системных работ.
Для этих общих случаев тоже имеется куча тонкостей зависящих от загрузки ЦП, памяти и OS.
В мире есть несколько солидных фирм, которые занимаются измерением производительности, но это очень серьезно. Нужно делать программу резидентной, нужно все массивы создавать неперемещаемые прямо в системной памяти и т.д.

[B@R5uk]

Paul Ivanov, вы поставили перед собой неимоверную задачу, как уже упомянули выше. Дело тут в двух моментах: 1) в том, как компилятор преобразует текст программы в код; 2) в том, как устроен и работает современный процессор. Когда-то лет 30-40 назад ещё можно было написать код, который отключает прерывания засекает время и крутит тестовый образец в цикле на несколько сот тысяч итераций. Такой подход ещё работает на самых простых микроконтроллерах. Но в целом, это время ушло.

Как вам уже заметили, ваш код на ассемблере может выглядеть совсем не так, как текст программы. Я бы даже сказал, что он будет совершенно неузнаваем, если не иметь натренированный глаз. Поэтому нет смысла измерять время отдельных операндов, они весьма эфемерны. В различных условиях одни и те же операнды могут компилироваться в совершенно различный машинный код. Гораздо разумнее сосредоточиться на измерении времени работы отдельных блоков кода, выполняющих определённую задачу. И если есть возможность, то смотрите на выданный компилятором ассмеблер. Это по первому пункту.

По поводу второго. Современные процессоры невероятно умные. Иногда даже слишком. У них есть такая вещь, как внеочередное выполнение (out-of-order execution). Пересказывать вики я вам не буду, сами почитаете. В двух словах: последовательные инструкции могут выполнятся параллельно и в произвольном порядке. Как это повлияет на ваше измеряемое время, попробуйте себе представить.

Затем, есть такая фича, как спекулятивное исполнение (Speculative execution, русской статьи в вики нет), о которой я сам узнал только сегодня в соседней теме. Смысл в том, что иногда процессор натыкается на условный переход, условие которого он ещё не знает и узнает не скоро. Чтобы не тупить и не бездельничать он берёт и угадывает как этот переход может разрешиться, а затем исполняет угаданную ветвь. Когда условие перехода становится известным, процессор сморит, верно ли он угадал или нет. Если нет, то все действия после перехода, которые он выполнил, отбрасываются, если да — вступают в законную силу.

Почему процессор может стоять и тупить ведёт нас к следующему моменту: процессор работает невероятно быстрее памяти (на порядки). По этой причине, если условие является проверкой какой-то редко используемой ячейки памяти, то потребуется значительное время, чтобы её достать. Чтобы побороть эту проблему медленной памяти используется технология кэширования. Процессор имеет встроенную очень быструю память, называемой кэшем, в которой он хранит часто используемые куски оперативной памяти. Кэш бывает первого, второго и (иногда) последнего уровней. Они отличаются быстродействием, размером и принадлежностью ядру процессора. Кэш хранит как код программ, так и данные. Когда процессор обрабатывает большие объёмы данных, то он пытается подгружать их в кэш упредительно: следующую порцию, пока обрабатывает текущую. Для этого используются всякие эвристические приёмы, а так же специальные команды процессора, которые умный компилятор может вставлять в код. Но они не всегда срабатывают, это называется кэш-промахом. Код программ можно и нужно оптимизировать, чтобы таких промахов было как можно меньше, или, во всяком случае, они не сильно снижали быстродействие. Так что дерзайте! К сожалению, на этом мои познания пока заканчиваются. Я сам ещё в процессе изучения всех этих тонкостей.

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

[Paul Ivanov]

StepV, B@R5uk. Огромное спасибо за такой полный ответ, до сегодняшнего дня даже не догадывался, что есть такие тонкости. Буду теперь знать, что моя "лошадка" трепыхается в столь сложной агонии.

[Mihaylo]

В частности компилятор увидит несколько подряд идущих s=1 и уберет все, кроме одного. Даже прятание в цикле не поможет.

Компилятор оптимизирует. И этой оптимизацией можно управлять. По умолчанию компилятор оптимизирует хорошо, но это не самая маниакальная оптимизация.

[StaticZero]

Mihaylo в сообщении #1500392 писал(а):

Компилятор оптимизирует. И этой оптимизацией можно управлять. По умолчанию компилятор оптимизирует хорошо, но это не самая маниакальная оптимизация.

Paul Ivanov в сообщении #1500111 писал(а):

Да, без

По идее, с -O0 ничего не должен делать. Но в более сложных случаях приходится иногда смотреть asm, что он там начудил...

[ilghiz]

Вставлю свои пять копеек:

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

Скорость выполнения стандартного умножения + сложения, если они разбросаны по арифметическим устройствам процессоров, по сравнению со скоростью закачки операндов из общей памяти и сохранения результатов в общую память, особенно при случайном блуждании по банкам памяти отличается примерно в 100 тысяч раз, то есть без учета того, как лежат у Вас данные в памяти Вы будете измерять погоду на Марсе и реально не понимать почему все так плохо.

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

Хорошим примером проверки производительности являются несколько простых, вроде бы школьных задач, а именно сумма элементов массива (скалярное произведение), умножение матрицы на вектор, умножение матрицы на матрицу, и какая-нибудь сортировка (можно взять тот пример, что я выложил в топике по соседству). А потом сравнить все это с IntelMathKernel Library и долго рыдать над тем, что самопально написанное умножение матриц работает в сотни раз медленнее, чем из MKL, хоть, вроде бы и случайного доступа по памяти нет.

[bondkim137]

Paul Ivanov в сообщении #1500111 писал(а):

К сожалению, не умею

А стоит.
Во-первых, избежите взаимонепонимания с компилятором (это когда вы расчитывали на 20 операций, а оказалась одна).
Во-вторых, начнете замечать корреляцию секундомерных результатов с типом машинных команд - когда идет работа с регистрами, когда с математическими конвеерами, когда с памятью. Узнаете, что такое кеш-промахи и буфер записи, потом - как работают мультипроцессорные системы с памятью, а затем, чем плохи interlocked-операции и где они в быту повсеместно явно и неявно используются.