2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:01 


23/04/18
143
Добрый день!
Пытаюсь измерить среднее время, затрачиваемое на выполнение различного рода операторов в Си, при условии, что компьютер, на фоне сильно колебающихся по величине затрат на фоновые процессы, работает максимально эффективно (поэтому 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 кратно дольше? Может я вообще неправильно интерпретирую результаты, а если так то в чём загвоздка?
Прошу объяснить относительно популярно, так как с железом ниже высокоуровневых языков никогда не работал.
(вообще если кто-то знает, где можно посмотреть таблицу временных затрат на простейшие операторы с точки зрения пропорционального отношения, то буду очень благодарен, если поделитесь, потому что мне гугл, к сожалению, не помог)
Спасибо.

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:07 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Paul Ivanov, компилируете без оптимизаций? Ассемблер умеете смотреть?

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:09 


23/04/18
143
Да, без. К сожалению, не умею.

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:13 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Paul Ivanov в сообщении #1500111 писал(а):
К сожалению, не умею.

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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:19 


23/04/18
143
Понял, буду пробовать.
Спасибо

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 19:56 
Аватара пользователя


23/05/20
336
Беларусь
Paul Ivanov в сообщении #1500109 писал(а):
Пытаюсь измерить среднее время, затрачиваемое на выполнение различного рода операторов в Си


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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 21:19 
Аватара пользователя


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

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

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

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

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

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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение10.01.2021, 22:09 


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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение12.01.2021, 08:47 


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

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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение12.01.2021, 19:32 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Mihaylo в сообщении #1500392 писал(а):
Компилятор оптимизирует. И этой оптимизацией можно управлять. По умолчанию компилятор оптимизирует хорошо, но это не самая маниакальная оптимизация.

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

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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение18.01.2021, 22:42 


11/08/18
363
Вставлю свои пять копеек:

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

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

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

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

 Профиль  
                  
 
 Re: сравнение временных затрат на простейшие операторы
Сообщение24.02.2021, 02:52 
Аватара пользователя


07/02/12
1403
Питер
Paul Ivanov в сообщении #1500111 писал(а):
К сожалению, не умею
А стоит.
Во-первых, избежите взаимонепонимания с компилятором (это когда вы расчитывали на 20 операций, а оказалась одна).
Во-вторых, начнете замечать корреляцию секундомерных результатов с типом машинных команд - когда идет работа с регистрами, когда с математическими конвеерами, когда с памятью. Узнаете, что такое кеш-промахи и буфер записи, потом - как работают мультипроцессорные системы с памятью, а затем, чем плохи interlocked-операции и где они в быту повсеместно явно и неявно используются.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group