Простой цикл for () занимает то же время, что и любой цикл

#include <iostream>
#include <ctime>

using namespace std;

int main () {
int start_s=clock();

int i;
for(i=0;i<5000;i++){
i*434243;
}

int stop_s=clock();
cout << "time: "<< (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000;

return 0;
}

i*434243;

int a = i*434243;

int a = i * i;
cout << a << "\n";

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

int foo() {
int x = 0;
for (int i=0;i<1000;i++){
x += i;
}
return 42;
}

int bar() {
return 42;
}

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

Насколько агрессивно компилятор оптимизирует ваш код, контролируется -O флаг. типично -O0 для отладочных сборок (потому что он компилируется быстрее) и -O2 или же -O3 для релизных сборок.

Временной код может быть сложным, потому что вы должны убедиться, что вы действительно что-то измеряете. За foo Вы можете убедиться, что цикл выполняется (*), написав это:

int foo() {
int x = 0;
for (int i=0;i<1000;i++){
x += i;
}
return x;
}

(*) = Даже это не приведет к выполнению цикла на большинстве компиляторов, так как этот тип цикла является настолько распространенным шаблоном, что он обнаруживается и приводит к чему-то по линии x = 1000*1001/2;,

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

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

Если вы хотите продолжить, один из вариантов — объявить переменную как volatile и присвоить ей свой ответ.

volatile int a = i * 434243;

Другой — создать функцию и вернуть значение. Возможно, вам придется отключить встраивание.

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

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

Я немного изменил ваш код, чтобы он был следующим:

#include <iostream>
#include <ctime>

using namespace std;

int main() {
for (long long int j = 10000000; j <= 10000000000; j = j * 10) {

int start_s = clock();

for (long long int i = 0; i < j; i++) {
i * 434243;
}

int stop_s = clock();

cout << "time: " << (stop_s - start_s) / double(CLOCKS_PER_SEC) * 1000 << endl;
}

int k;
cin >> k;
return 0;
}

Вывод: (что выглядит прекрасно для меня.)

time: 23
time: 224
time: 2497
time: 21697

Есть одна вещь, о которой нужно знать. поскольку i целое число, оно никогда не будет равно 49058349083. В вашем случае верхняя граница преобразуется в int что соответствует чему-то между -2 147 483 648 и 2 147 483 647, поэтому цикл выполняется в диапазоне от 0 до 2 147 483 647 раз, что не так много для простой операции умножения. (1813708827 в случае 49058349083).

Попробуйте использовать long long int который может быть между -2 ^ 63 и 2 ^ 63-1

Кстати, если бы вы на самом деле сделали i<49058349083, gcc и clang создают бесконечный цикл в системах с 32-битным int (включая x86 и x86-64). 49058349083 больше чем INT_MAX, Большие литеральные числа неявно переводятся в тип, достаточно большой для их хранения, так что вы эффективно сделали (int64_t)i < 49058349083LL, что верно для любого возможного значения int i,

Переполнение со знаком является неопределенным поведением в C ++, равно как и бесконечный цикл без побочных эффектов внутри цикла (например, системный вызов), поэтому Я проверил на проводнике компилятора Godbolt чтобы увидеть, как это действительно компилируется с включенной оптимизацией. Интересный факт: MSVC все еще оптимизирует пустой цикл (включая i*10 ничего не присваивается), когда условие является всегда истинным сравнением, а не ненулевой константой, такой как 42,

---

Такая петля довольно в корне ошибочна.

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

Если это звучит намного сложнее, чем вы надеялись, это очень плохо, и для этого есть все основания.

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

---

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

Оптимизирующие компиляторы предназначены для создания исполняемого файла, который дает те же результаты, что и ваш исходный код C ++, но который работает максимально быстро. Производительность не является наблюдаемым результатом, поэтому всегда законно делать программу более эффективной. Это правило «как будто»: Что именно "как будто" править?

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

Помните, что вы пишете для абстрактной машины C ++, но задача вашего компилятора — перевести это на язык ассемблера (или машинный код) для вашего процессора. Язык ассемблера сильно отличается от C ++. (И современные высокопроизводительные ЦП также могут выполнять инструкции не по порядку, следуя своему собственному правилу «как если бы», чтобы сохранить иллюзию сгенерированного компилятором кода, работающего в программном порядке. Но ЦП не могут отбрасывать работу, только перекрываются Это.)

Вы не может микробенчмарк int * int бинарный оператор в C ++ в общем случае, даже только для вашего собственного рабочего стола (не обращайте внимания на другое оборудование / другие компиляторы). Разное использование в разных контекстах будет компилироваться в разный код. Даже если бы вы могли создать какую-то версию вашего цикла, которая измерила бы что-то полезное, это не обязательно расскажет вам много о том, как дорого foo = a * b находится в другой программе. Другая программа может стать узким местом при задержке умножения вместо пропускной способности или объединить это умножение с какой-либо другой близлежащей операцией a или же bили любое количество вещей.

---

Вы можете подумать, что было бы полезно просто отключить оптимизацию (лайк gcc -O0 вместо gcc -O3). Но единственный способ сделать это также вводит антиоптимизации, такие как сохранение каждого значения обратно в память после каждого оператора C ++, и перезагрузка переменных из памяти для следующего оператора. Это позволяет вам изменять значения переменных при отладке скомпилированной программы или даже переходить на новую строку в той же функции, и при этом получать результаты, которые вы ожидаете получить, глядя на исходный код C ++.

Поддержка этого уровня помех налагает огромную нагрузку на компилятор. Store / reload (store-forwarding) имеет примерно 5 циклов задержки на типичном современном x86. Это означает, что антиоптимизированный цикл может в лучшем случае выполнять только одну итерацию в течение ~ 6 тактов против 1 цикла для узкого цикла, например looptop: dec eax / jnz looptop где счетчик цикла находится в регистре.

Среднего положения не так много: у компиляторов нет опций для создания asm, который «похож на» исходный код C ++, но сохраняет значения в регистрах между операторами. В любом случае это не будет полезным или значимым, потому что они не компилируются с включенной полной оптимизацией. (gcc -Og может быть немного так.)

Тратить время на изменение вашего C ++, чтобы он работал быстрее с -O0 это пустая трата времени: Помощь по оптимизации цикла C для окончательного назначения.

Заметка: антиоптимизированный режим отладки (-O0) по умолчанию для большинства компиляторов. Это также режим «быстрой компиляции», так что он хорош для проверки того, что ваш код компилируется / работает вообще, но он бесполезен для тестирования производительности. Полученный asm, сгенерированный компилятором, работает с той скоростью, с которой он работает по причинам, зависящим от аппаратного обеспечения, но ничего не говорит вам о том, как быстро будет работать оптимизированный код. (например, ответ на Добавление избыточного назначения ускоряет код при компиляции без оптимизации Это довольно тонкое поведение задержки пересылки хранилищ в семействе Intel Sandybridge, напрямую вызванное хранением / перезагрузками и наличием узкого места в цикле на счетчике циклов в памяти.
Обратите внимание, что первая версия вопроса спрашивала о том, почему это сделало C быстрее, что было справедливо понижено, потому что бенчмаркинг -O0 глупо Он превратился в интересный вопрос, только когда я отредактировал его в вопрос о x86-ассемблере, который интересен из-за большего, но более быстрого асма, а не потому, что он возник из gcc -O0 с любыми конкретными изменениями источника.)

И это даже не упоминает стандартные функции библиотеки C ++, такие как std::sort или же std::vector::push_back, которые зависят от оптимизатора, чтобы встроить множество вложенных вызовов в крошечные вспомогательные / упаковочные функции.

---

(Я собираюсь показать преобразования кода C ++. Помните, что компилятор фактически преобразовывает внутреннее представление логики вашей программы и затем создает asm. Вы можете думать о преобразованном C ++ как о псевдокоде для asm, где i++ представляет x86 inc eax инструкция или что-то. Большинство операторов C / C ++ Можно сопоставьте с 1 или парой машинных инструкций. Так что это полезный способ описания логики того, что мог бы делать фактический сгенерированный компилятором ассемблер без фактического написания его в ассемблере.)

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

// int gsink;  is a global.
// "sink" is the opposite of a source: something we dump results into.
for (int i=0 ; i<n ; i++) {
gsink = i*10;
}

эквивалентно этому коду, поскольку это касается оптимизирующего компилятора:

if (! (0 < n)) {     // you might not have noticed that your loop could run 0 times
gsink = n*10;    // but the compiler isn't allowed to do gsink=0 if n<1
}

Если gsink вместо этого были локальные или с файловой областью static ничего не читая, компилятор может полностью оптимизировать его. Но компилятор не может «видеть» код вне текущего исходного файла C ++ («модуль компиляции») во время компиляции функции, содержащей его, поэтому он не может изменить наблюдаемый побочный эффект, который когда функция возвращает, gsink = n*10;,

Ничто не читает промежуточные значения gsink потому что нет вызовов функции для не встроенной функции. (Потому что это не atomic<int>компилятор может предположить, что никакие другие потоки или обработчики сигналов не читают его; Это было бы неопределенным поведением гонки данных.)

---

Если бы это было глобально volatile int gsink, фактическое хранилище, которое помещает значение в память было бы быть наблюдаемым побочным эффектом (это то что volatile значит в C ++). Но значит ли это, что мы можем тестировать умножение таким образом? Нет, это не так. Побочным эффектом, который должен сохранить компилятор, является только размещение окончательного значения в памяти. Если он может рассчитать это дешевле, чем с i * 10 каждый раз через цикл, он будет делать это.

Этот цикл также будет производить ту же последовательность результатов присваиваний gsinkи, следовательно, является допустимой опцией для оптимизирующего компилятора. Преобразование независимых умножений в перенос, переносимый циклом, называется оптимизация «снижение силы».

volatile int gsink;

int i10 = 0;   // I could have packed this all into a for() loop
int i=0;       // but this is more readable
while (i<n) {
gsink = i10;
i10 += 10;
i++;
}

Может ли компилятор сбросить i в целом и использовать i10 < n*10 как условие цикла? (Конечно поднимать upperbound = n*10 расчет из цикла.)

Это не всегда дает одинаковое поведение, потому что n*10 может переполниться, поэтому цикл может выполняться не более INT_MAX/10 раз, если реализовано таким образом. Но переполнение со знаком в C ++ — неопределенное поведение, и i*10 в теле цикла переполнится в любой программе, где n*10 переполнен, поэтому компилятор может безопасно ввести n*10 без изменения поведения любой легальной / четко определенной программы. Увидеть Что каждый программист C должен знать о неопределенном поведении.

(На самом деле, i*10 оценивается только для i вплоть до n-1 максимум, и n*10 может переполниться в то время как (n-1)*10 не делает. Что за GCC на самом деле делает больше похоже while(i10 != n*10) используя unsigned math при компиляции для x86. x86 — машина дополнения до 2, поэтому неподписанные и подписанные являются одной и той же двоичной операцией, и проверка на != вместо подписанного менее чем безопасно, даже если (unsigned)n*10UL == 0x8000000UL, который является INT_MIN.)

Для получения дополнительной информации о просмотре вывода asm компилятора и ознакомлении с новичком в x86 asm, см. выступление Мэтта Годболта на CppCon2017 «Что мой компилятор сделал для меня в последнее время? Откручиваем крышку компилятора ». (И связанные: Как убрать "шум" из вывода сборки GCC / clang?). Увидеть http://agner.org/optimize/ для получения дополнительной информации о том, как работают текущие процессоры x86.

Вывод компилятора для этой функции из gcc7.3 -O3, компилирование для x86-64, в проводнике компилятора Godbolt:

volatile int gvsink;

void store_n(int n) {
for(int i=0 ; i<n; i++) {
gvsink = i*10;
}
}

store_n(int):          # n in EDI  (x86-64 System V calling convention)
test    edi, edi
jle     .L5                   # if(n<=0) goto end

lea     edx, [rdi+rdi*4]      # edx = n * 5
xor     eax, eax              # tmp = 0
add     edx, edx              # edx = n * 10

.L7:                                   # do {
mov     DWORD PTR gvsink[rip], eax   # gvsink = tmp
add     eax, 10                      # tmp += 10
cmp     eax, edx
jne     .L7                        # } while(tmp != n*10)
.L5:
rep ret

Оптимальная / идиоматическая структура асм цикла do{}while(), так компиляторы всегда пытаются сделать такие циклы. (Это не означает, что вы должны писать свой исходный код таким образом, но вы можете позволить компилятору избегать проверки на нулевые итерации в таких случаях, когда он не может этого доказать.)

Если бы мы использовали unsigned intпереполнение было бы хорошо определено как перенос, так что нет UB, который компилятор может использовать в качестве предлога для компиляции вашего кода способом, который вы не ожидали. (Современный C ++ не прощающий язык. Оптимизация компиляторов довольно враждебна программистам, которые не стараются избегать UB, и это может быть довольно тонким, потому что много вещи неопределенного поведения. Компиляция C ++ для x86 не похожа на написание сборки x86. Но, к счастью, есть варианты компилятора, такие как gcc -fsanitize=undefined который будет обнаруживать и предупреждать о UB во время выполнения. Вы все еще должны проверить все возможные входные значения, которые вас интересуют.)

void store_n(unsigned int n) {
for(unsigned int i=0 ; i<n; i++) {
gvsink = i*10;
}
}

store_n(unsigned int):
test    edi, edi
je      .L9            # if (n==0) return;
xor     edx, edx       # i10 = 0
xor     eax, eax       # i = 0
.L11:                      # do{
add     eax, 1         #    i++
mov     DWORD PTR gvsink[rip], edx
add     edx, 10        #    i10 += 10
cmp     edi, eax
jne     .L11           # } while(i!=n)
.L9:
rep ret

Clang компилирует с двумя отдельными счетчиками для подписанного и неподписанного. Код Clang больше похож

i10 = 0;
do {
gvsink = i10;
i10 += 10;
} while(--n != 0);

Так что отсчитывает n зарегистрироваться на ноль, избегая отдельного cmp инструкция, потому что инструкции add / sub также устанавливают флаги кода условия, по которым ЦП может переходить. (Clang разворачивает небольшие циклы по умолчанию, генерируя i10, i10 + 10, i10 + 20, вплоть до i10 + 70 в регистрах он может храниться из, при этом выполняя только инструкции цикла-заголовка один раз. Однако, разворачиваясь на типичных современных процессорах, вы ничего не получите. Узким местом является одно хранилище за такт, а также 4 мопа за такт (на процессорах Intel), выводимые из внешнего интерфейса в неупорядоченную часть ядра.

---

Получение компилятора для умножения:

Как мы можем остановить эту оптимизацию снижения прочности? Замена *10 с * variable не работает, тогда мы просто получаем код, который добавляет регистр вместо добавления немедленной константы.

Мы могли бы превратить его в цикл над массивами, как a[i] = b[i] * 10;, но тогда мы также будем зависеть от пропускной способности памяти. Кроме того, это может автоматически векторизовать с помощью SIMD-инструкций, которые мы можем или не хотим тестировать.

Мы могли бы сделать что-то вроде tmp *= i; (с unsigned, чтобы избежать UB со знаком переполнения). Но это делает вывод умножения на каждой итерации входом для следующей. Таким образом, мы будем умножать бенчмаркинг задержка, не пропускная способность. (Процессоры конвейерны, и, например, могут начинать новое умножение каждый такт, но результат однократного умножения не готов до 3 тактов позже. Так что вам нужно по крайней мере tmp1*=i, tmp2*=i, а также tmp3*=i сохранить целочисленное умножение на процессоре семейства Intel Sandybridge, насыщенном работой.

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

Если этот ответ у вас над головой, придерживайтесь расписания всех функций! На самом деле невозможно сказать много об одном арифметическом операторе C или выражении, не понимая окружающий контекст и то, как он работает в asm.

Если вы понимаете кеширование, вы можете понять доступ к памяти и массивы по сравнению со связанными списками довольно прилично, не вдаваясь в подробности на уровне asm. Можно понять производительность C ++ на некотором уровне детализации, не зная много об asm (помимо того факта, что он существует и что компиляторы сильно оптимизируются). Но чем больше вы знаете об asm, настройке производительности процессора и о том, как работают компиляторы, тем больше становится смысла.

---

PS:

Любое вычисление, основанное на значениях постоянной времени компиляции, может (и, надеюсь, так) выполнено во время компиляции.. Это называется «постоянное распространение». Скрытие констант от оптимизатора (например, путем ввода их в качестве аргументов командной строки (atoi(argv[1])или с другими приемами) может сделать сгенерированный компилятором код для микробенчмарка больше похожим на реальный вариант использования, если этот вариант использования также не может видеть константы во время компиляции. (Но обратите внимание, что константы, определенные в других файлах, становятся видимыми с оптимизацией во время компоновки, что очень хорошо для проектов с множеством небольших функций, которые вызывают друг друга через границы исходного файла и не определяются в заголовках (.h) где они могут встраиваться нормально.)

Умножение на 16 (или любая другая степень 2) будет использовать сдвиг, потому что это более эффективно, чем фактическая инструкция умножения. Это особенно важно для деления. Увидеть Почему этот код C ++ быстрее, чем моя рукописная сборка для проверки гипотезы Коллатца?, а также Почему GCC использует умножение на странное число при реализации целочисленного деления?.

Другие константы умножения с парой битов, установленных в их двоичном представлении, могут быть выполнены с помощью метода shift + add, часто с меньшей задержкой, чем универсальная инструкция умножения. Смотри например Как умножить регистр на 37, используя только две последовательные инструкции в x86?.

Ни одна из этих оптимизаций невозможна с a * b или же a / b если ни один из входных данных не известен во время компиляции.

---

Смотрите также: Как я могу измерить производительность кода C ++?, особенно ссылки на Доклад Чандлера Каррута о CppCon 2015: «Настройка C ++: тесты, процессоры и компиляторы! О, Боже!».

И потому что стоит упомянуть дважды: CppCon2017 разговор Мэтта Годболта «Что мой компилятор сделал для меня в последнее время? Откручиваем крышку компилятора ». Это достаточно деликатное введение, что новичок, вероятно, может достаточно хорошо его изучить, чтобы посмотреть, как скомпилирован их цикл, и посмотреть, оптимизирован ли он или нет.