Почему я это написал, и как читать статью
Недавно получил от друга такое сообщение:
Знаешь, какая статья была бы реально интересна? Если бы в ней было показано, что именно происходит с твоим кодом в результате оптимизаций.
Я сразу же подумал: «Ну конечно, я знаю тысячу статей и видеороликов на эту тему», но вскоре осознал, что практически во всех таких источниках от читателя требуется знать компьютерный жаргон, внутреннее устройство, промежуточные представления, т.д. Вот какая проблема здесь возникает: те, кто пользуется компиляторами (как, например, мой друг), всем этим не заморачиваются. Их не волнует, каково именно промежуточное представление LLVM, или что такое φ-узел, или какой проход и почему называется «ротацией циклов». Нет, их интересуют (в порядке убывания приоритета) ответы на вопросы: (1) что, (2) почему, (3) как.
Что. Прежде всего, пользователи хотят знать, что может и чего не может компилятор, то есть, какие аспекты требуется оптимизировать программисту, а какие оптимизации компилятор может выполнить самостоятельно.
Почему. После этого интересно узнать, почему компилятор оптимизировал наш код именно так, как это получилось (например, почему он предпочёл одну инструкцию, а не другую).
Как. Этот вопрос касается того, как именно компилятор достигает поставленных целей, то есть, каков он с технологической точки зрения. Но это наименее приоритетный для человека вопрос, и обычно этим вопросом интересуются только из любопытства, а не ради выполнения поставленной задачи.
В этой статье на нескольких примерах я объясню различные оптимизации компилятора. В основном я сосредоточусь на вопросе «что», а о «как» и «почему» буду говорить только в тех случаях, когда сочту какие-то детали важными или очень интересными. Чтобы статья не получилась чрезмерно длинной, я написал к ней приложение, в котором разобраны некоторые пространные ответы — в том числе, даются ответы на некоторые вопросы «почему» и «как».
Немаловажно, что в примерах я буду использовать язык C, а временами ассемблер x86-64 (если для выражения некоторой концепции язык C окажется слишком высокоуровневым). Я не буду пользоваться промежуточным представлением LLVM, постараюсь не говорить о внутренностях компилятора и не пользоваться связанным с ними жаргоном.
Наконец, отмечу, что я постарался подобрать на все случаи реалистичные примеры, но именно из-за этого их иногда сложно понять. Поэтому о каждом рассмотренном примере лучше судить в отдельности.
Краткая благодарность: Спасибо Андре Синцоффу за то, что вычитал и поправил эту статью.
Арифметика
Начнём с простого и рассмотрим следующую функцию:
int times2(int n) { return n*2; }В принципе, компиляторы умеют достаточно эффективно оптимизировать арифметические, логические и прочие скалярные операции. В случае с векторными операциями всё несколько сложнее, об этом мы поговорим позже. Даже в этом примере, когда компилятору, казалось бы, негде развернуться, при помощи -O1 (godbolt) удалось сгенерировать следующий код:
times2(int): lea eax, [rdi+rdi] retПрактически, компилятор превратил эту функцию в:
int times2(int n) { return n+n; }В Приложении рассмотрено, почему компилятор из всех возможных вариантов решил сгенерировать именно этот.
Теперь рассмотрим близкий реалистичный пример, на котором удобно проиллюстрировать границы возможностей компилятора при выполнении арифметических операций. Пример составлен на основе этого поста. Вот код из оригинала (godbolt), который я немного упростил:
typedef struct Float2 { float x, y; } Float2; Float2 ProjectSphere(float x, float z, float r, float t, float ResultScale) { float tz = t*z; float rx = r*x; float tx = t*x; float rz = r*z; float A = (tz + rx); float B = (tz - rx); float Min = (tx - rz) / A; float Max = (tx + rz) / B; Float2 Res = {Min*ResultScale, Max*ResultScale}; return Res; }Позвольте детально описать, какие именно изменения я внёс в оригинальный код. Чтобы сократить пример, я удалил из него вычисление sqrt; иными словами, эта операция не нужна нам, чтобы передать суть примера. Во-вторых, я вынес распространённые подвыражения (такие, которые встречаются многократно) в собственные переменные, так как полагаю, что в таком виде читать код гораздо удобнее. Мы к этому вернёмся, когда будем обсуждать удаление общих подвыражений.
Далее в этом посте займёмся оптимизацией вышеприведённого кода и попытаемся обойтись без двух операций деления, поскольку такие операции обычно идут медленно на любой аппаратной платформе. Оптимизация базируется на следующем математическом факте:
xy=xy×z×zКонечно же, предполагается, что z != 0. Имеем два значения, одно из которых хотим разделить на A, а другое на B. Оптимизация заключается в том, что мы будем делить оба этих значения на A * B, а затем умножим одно на A (оставив B в знаменателе), а второе на B (оставив A в знаменателе). Таким образом:
Float2 ProjectSphere(float x, float z, float r, float t, float ResultScale) { float tz = t*z; float rx = r*x; float tx = t*x; float rz = r*z; float A = (tz + rx); float B = (tz - rx); // Было: ничего ResultScale /= (A * B); // Было: float Min = (tx - rz) / A; float Min = (tx - rz) * B; // Было: float Max = (tx + rz) / B; float Max = (tx + rz) * A; Float2 Res = {Min*ResultScale, Max*ResultScale}; return Res; }Вот как можно сформулировать наш вопрос: способен ли компилятор выполнить такую оптимизацию самостоятельно? Правдоподобно, что да, поскольку эта оптимизация хоть и странновата, но не слишком. Попробуем выполнить наш -O3 в разных компиляторах. GCC даёт две операции деления, и это нехорошо. Clang чуть-чуть умнее и немного векторизует код. В принципе, он создаёт один вектор: X = {(tx -rz), (tx + rz)}. Затем создаёт другой вектор: Y = {A, B}. После этого делит X / Y. Поэтому в одну команду деления укладываются две операции деления.
С ICX особый случай. Ему удалось сгенерировать код, вообще не содержащий операций деления… ну почти. Вот что, в сущности, у него получилось:
Float2 ProjectSphere(float x, float z, float r, float t, float RS) { float tz = t*z; float rx = r*x; float tx = t*x; float rz = r*z; float A = t*z + r*x; float B = t*z - r*x; float v = {A, B, A, B}; float rec_v = {1/A, 1/B, 1/A, 1/B}; float Min_s = tx - rz; float Max_s = tx + rz; float MinMax = {Min_s, Max_s, Min_s, Max_s}; float RS_v = {RS, RS, RS, RS}; // Отсюда и далее сосредоточимся на первых двух элементах. // В любом случае, только их мы и возвращаем. float MinMaxRS = MinMax*RS_v; // = {Min_s*RS, Max_s*RS} float Div = MinMaxRS*rec_v; // = {Min_s*RS/A, Max_s*RS/B} float Clear = v*Div; // = {Min_s*RS, Max_s*RS} float res = MinMaxRS - Clear; // = {0, 0} res = res*rec_v; // = {0, 0} res = res + Div; // = {Min_s*RS/A, Max_s*RS/B} return res; }В Приложении приводится эта же версия на C, аннотированная исходными ассемблерными инструкциями.
Так что ICX, фактически, вычислил обратную величину, а затем умножил число на неё. Это хороший компромисс, так как rcpps обычно гораздо быстрее, чем divss и divps.
Но компилятор, по-видимому, немного затупил. В строке 21 у нас, по-видимому, уже готов результат! Почему же мы не возвращаемся к этой строке, а проделываем оставшиеся бессмысленные операции, только чтобы получить тот же результат в строке 25? Что ж, напомню, что мы работаем с числами с плавающей точкой. Поэтому нули в строке 24 — на самом деле не нули. Короче говоря, всё, что ICX делает после этой строки, делается для сокращения ошибок в вычислениях. В Приложении показан код на C, вызывающий обе функции и проверяющий ошибку.
Вот что ещё интереснее: ICX смог это сделать только по той причине, что, в отличие от GCC и Clang, у этого компилятора по умолчанию выставлена не максимальная точность при вычислениях с плавающей точкой. Иными словами, сгенерированный код не обязательно приводит ровно к тому же результату, к которому привёл бы оригинальный. Кстати, то же наблюдается и при оптимизации вручную. Оптимизация не учитывает семантику операций с плавающей точкой.
С другой стороны, при работе с GCC и Clang приходится явно сообщать компилятору, что он может использовать «быструю математику», т.е., такие оптимизации, при которых могут вкрасться какие-то ошибки. Это делается при помощи флага -ffast-math. Компилятор GCC с этим почти ничего не мог поделать, а Clang справился! В принципе, он сгенерировал ту же версию, что и ICX.
Суть истории в том, что компиляторы могут проделывать с вашим кодом просто сумасшедшие вещи, и вам приходится сообщать компиляторам, что именно вы делаете, и какие вещи вас не волнуют.
Удаление общих подвыражений
Вернёмся к примеру с ProjectSphere. Вот каким код был сначала:
Float2 ProjectSphere(float x, float z, float r, float t, float ResultScale) { float Min = (t * x - r * z) / (t * z + r * x); float Max = (t * x + r * z) / (t * z - r * x); Float2 Res = {Min * ResultScale, Max * ResultScale}; return Res; }А вот какой код написал я:
Float2 ProjectSphere(float x, float z, float r, float t, float scale) { float tz = t*z; float rx = r*x; float tx = t*x; float rz = r*z; float A = (tz + rx); float B = (tz - rx); float Min = (tx - rz) / A; float Max = (tx + rz) / B; Float2 Res = {Min*scale, Max*scale}; return Res; }У меня в коде я выполнил (на уровне компилятора) оптимизацию, которая называется «удаление общих подвыражений» (CSE). Из названия, в целом, понятно, что при этом делается. В принципе, мы берём выражения, которые многократно встречающиеся в коде, например, t*z в вышеприведённом примере, и помещаем их в переменные. Это должно принести пользу, так как предположительно нам не придётся несколько раз вычислять одно и то же. На практике — здесь есть нюансы. Как правило, при CSE возрастает давление на регистры, эта проблема подробнее объяснена в Приложении.
Принято считать, что нам не требуется самим выполнять CSE, так как компилятор сделает это за нас. На самом деле, всё ещё сложнее: ситуация даже не зависит от того, выполним мы CSE или нет! Компилятор должен уметь видеть переменные насквозь. Иными словами, с точки зрения компилятора такие переменные как tz должны быть сродни макросам. То есть, например, tz и t*z — это, в принципе, одно и то же, независимо от того, как мы напишем код. Но насколько всё это истинно?
При использовании Clang -O1 получаем от двух версий принципиально одинаковый код (одни и те же инструкции, но идущие в разном порядке). То же самое получаем для GCC под -O1. При -O2 и -O3 ситуация с GCC немного меняется. В обоих случаях вы получаете один и тот же код, с той оговоркой, что в моей версии до ret становится ещё одна movdqa, поэтому код работает немного медленнее. В Clang различия между двумя версиями гораздо значительнее при использовании -O2. В данном случае моя версия немного лучше, поскольку в ней применяется две subss, а в оригинальной — две shufps (операции перетасовки). Согласно грубой оценке, subss (здесь) сильно превосходит по пропускной способности shufps (здесь).
Суть в следующем: мнение «не важно, как именно вы пишете арифметические выражения, компилятор о них позаботится» просто неточное. Хуже того, нет такого золотого правила, руководствуясь которым можно было бы предпочесть одну версию другой. В то же время, такой выбор должен волновать вас только в том случае, если вы хотите выжать всю производительность до последней капли. Да, компилятор в 90% случаев обработает ваш код одинаково, независимо от того, как вы его напишете.
Неоптимизированные сборки
Чтобы лучше понять, что именно делает компилятор, когда вы включаете оптимизации — посмотреть, чего он не делает, когда оптимизации отключены. Рассмотрим простой пример с times2, но слегка изменим, чтобы в нём использовалась одна локальная переменная:
int times2(int n) { int x = n*2; return x; }Посмотрим, что сгенерирует Clang без применения оптимизаций (godbolt).
times2: push rbp mov rbp, rsp mov dword ptr [rbp - 4], edi mov eax, dword ptr [rbp - 4] shl eax mov dword ptr [rbp - 8], eax mov eax, dword ptr [rbp - 8] pop rbp retДаже особо не вникая в код, вполне ясно понимаем, что rbp бесполезна. Мы сохраняем её значение, проталкивая её в стек. Затем копируем значение rsp в rbp. Затем, после того, как мы всё сделаем при помощи rbp, мы просто выталкиваем значение rbp из стека. Так что rbp постоянно использует значение rsp. Следовательно, чтобы было проще, стоит просто вообще избавиться от rbp, воспользовавшись -fomit-frame-pointer (godbolt). Если вы не знаете, что такое указатель кадра, то будьте уверены, что (в рамках данной статьи) этого знать и необязательно. Об этом всегда можно подробнее почитать в Интернете. Вот как выглядит код, в котором используется только rsp:
times2: ; Сохраняем в стек аргумент `n`, значение которого находится в `edi`. ; Следующая доступная позиция — `rsp - 4`. mov dword ptr [rsp - 4], edi ; Загружаем `n` в регистр, чтобы затем выполнять над ним операции mov eax, dword ptr [rsp - 4] ; n << 1 shl eax ; `x` также получает позицию в стеке. Следующая доступная позиция ; `rsp - 8`. Там сохраняем результат вычисления, выполненного выше. mov dword ptr [rsp - 8], eax ; Загружаем `x` в `eax`, так как именно это мы и возвращаем. mov eax, dword ptr [rsp - 8] retЯ подробно объясню, что происходит в ассемблере, но следует постоянно иметь в виду следующую вещь: при неоптимизированных сборках компилятор придерживается повторяющегося, бесхитростного и простого метода. Этот метод сводится примерно к такой последовательности. Сначала каждая переменная ассоциируется ровно с одной позицией в стеке, и, соответственно, каждая позиция в стеке ассоциируется ровно с одной переменной. Это касается всех локальных временных переменных, а также аргументов функций. Поэтому в начале функции мы просто копируем все аргументы функции в стек. Далее, всякий раз, когда мы хотим воспользоваться значением переменной, мы загружаем эту переменную из стека в регистр. Отчасти это делается потому, что при вычислениях невозможно напрямую оперировать локациями в стеке – большинство инструкций работает с регистрами. Естественно, при каждой операции присваивания переменной происходит сохранение локации стека в этой переменной.
Сейчас может казаться, что нет ничего глупее, так как в данном случае у нас достаточно неиспользуемых регистров, чтобы вообще обойтись без использования стека. Честно говоря, так и есть. Но понимать неоптимизированные сборки нужно так, что компилятору вообще не приходится о них «задумываться». Если вы поступите так, как описано выше, то у вас получится корректный код, независимо от того, каким количеством переменных вам приходится оперировать. В свою очередь, более изощрённый метод, связанный с использованием регистров, требует держать в уме: «буду пользоваться регистрами до тех пор, пока останется такая возможность, а когда израсходую все регистры — перейду к работе со стеком». Но сам такой подход — это уже оптимизация компилятора: выделение регистров (вы сами решаете, как именно будете задействовать регистры и хранить в них значения). Если захотите — можете включить оптимизации. Существует несколько уровней сложности в зависимости от того, насколько активно значения загоняются в регистры. В некоторых компиляторах при сниженных уровнях оптимизации используются более простые стратегии выделения регистров.
Кроме того, при применении вышеописанного метода упрощается работа отладчика. Поскольку переменная ассоциирована с местоположением в стеке, и этот участок стека больше ни для чего не используется, получается так: если вы хотите посмотреть значение переменной в любой точке выполнения функции, то просто проверяете, какое значение записано в данной точке. Напротив, в оптимизированных сборках значение переменной не ассоциировано ни с какой конкретной точкой в каком-либо регистре. Значение постоянно перемещается. Поэтому компилятор вынужден сообщать об этих промежуточных изменениях, а отладчик — отслеживать эту информацию. Опять же, для простых функций, наподобие той, что рассмотрена выше, компилятор найдёт по регистру на каждую переменную, поэтому каждая переменная будет ассоциирована ровно с одним регистром. Разумеется, никак не обойтись без случаев, когда в некоторый момент времени значение конкретной переменной будет записано более чем в одном регистре. Допустим, компилятор определяет, что значение x будет находиться в edx. Но, всё-таки, если вы хотите вернуть x, то должны скопировать значение edx в eax, и в этот момент значение x будет одновременно находиться и в eax, и в edx. Но в интересующем нас контекcте это не важно, так как если вы спросите у отладчика значение x, он просто посмотрит его в edx, не волнуясь о том, где еще может быть значение x.
Но инструментарий, с которым мы работаем, не оптимизирован для таких «промежуточных» случаев. И нам как мантру повторяют, что третьего не дано — либо у вас будут совершенно тупые отладочные/неоптимизированные сборки, либо оптимизированные сборки, с которыми приходится полагаться на «авось».
Наконец, отмечу, что Clang при умножении использует сдвиг влево даже при работе с неоптимизированными сборками. Аналогично, используемая в GCC версия похожа на одну из рассмотренных выше, где мы заменили умножение сложением (godbolt).
Встраивание функций
Сам себя не похвалишь – никто не похвалит. Вот вам шестиминутная выдержка из моего доклада на одном митапе по компиляторам, сделанного пару лет назад. Это одно из немногих моих выступлений, которыми я до сих пор могу гордиться, так что не стесняйтесь. Всего за шесть минут я объясняю достоинства и недостатки встраивания функций, а также некоторые сопутствующие подводные камни (например, когда встраивание допустимо). Далее я подробнее рассказываю о том, что именно происходит в компиляторе.
Одна деталь, которой нет в видео, и которую я хотел бы здесь добавить — это реализация встраивания в LLVM от Криса Латтнера, примеру уже 20 лет.
Снижение стоимости операций
Допустим, у нас есть такая функция:
void init_scaled(int *array, int n, int scale) { for (int i = 0; i < n; i++) { array[i] = i * scale; } }Чтобы обойтись без умножения внутри цикла, можно написать код, например, вот так:
void init_scaled(int *array, int n, int scale) { int tmp = 0; for (int i = 0; i < n; i++) { array[i] = tmp; tmp += scale; } }Итак, мы заменили умножение сложением, и можно сказать, что на этом выиграли, поскольку, как правило, сложение целых чисел быстрее перемножения целых чисел. Такая оптимизация относится к более широкой категории снижения стоимости операций (strength reduction), где фрагмент кода заменяется эквивалентным, но таким, в котором используются более «дешёвые» инструкции. Clang (и большинство компиляторов) прибегают к такой оптимизации даже в -O1 (godbolt).
Есть более изощрённый вариант снижения стоимости операций: вынос инвариантов цикла (LICM). Вот пример, похожий на вышеприведённый:
void scale_array(float *array, int n, float multiplier) { const float pi = 3.14159; for (int i = 0; i < n; i++) { float scale = pi * multiplier; array[i] = array[i] * scale; } }Вероятно, вы заметили, что значение scale одинаково на всех итерациях цикла. Поэтому можно вынести его из цикла, так, чтобы умножение происходило всего однажды:
void scale_array(float *array, int n, float multiplier) { const float pi = 3.14159; float scale = pi * multiplier; for (int i = 0; i < n; i++) { array[i] = array[i] * scale; } }Clang (и большинство компиляторов) поступят так (godbolt) даже при -O1. Вот сокращённый и аннотированный код на ассемблере:
.LCPI0_0: ; Это число пи .long 0x40490fd0 scale_array: ... ; scale = множитель * пи mulss xmm0, dword ptr [rip + .LCPI0_0] ... .LBB0_2: ; float tmp = array[i]; movss xmm1, dword ptr [rdi + 4*rcx] ; float tmp2 = tmp * scale mulss xmm1, xmm0 ; array[i] = tmp2; movss dword ptr [rdi + 4*rcx], xmm1 ...Оптимизации во время компиляции
Возможно, вас это удивит, но в большинстве компиляторов обычно предусмотрено несколько подсистем, вычисляющих код во время компиляции. Самый очевидный случай — все те механизмы, которые применяются при вычислении constexpr. Например, в Clang реализован интерпретатор constexpr.
Но среди подсистем для вычислений во время компиляции есть и неочевидные. Возьмём, к примеру, обычную последовательность Коллатца (godbolt):
static int collatz(int n) { int its = 0; while (n != 1) { its++; if (n % 2 == 0) { n /= 2; } else { n = 3 * n + 1; } } return its; } int main(void) { return collatz(6); }Посмотрим на ассемблер:
main: mov eax, 8 retСначала я целенаправленно пометил функцию collatz как static, так, чтобы компилятор оставил только функцию main. Подробнее расскажу об этом в разделе об отсечении мёртвых веток кода.
Теперь компилятор, в сущности, сгенерировал следующее:
int main(void) { return 8; }Иными словами, он выполнил функцию во время компиляции и заменил вызов возвращаемым значением collatz. Напомню, уже упоминал в этой статье, что иногда компилятор может превращать циклы в вычисления констант, если цикл сводим к одному этапу. Но широко известно, что последовательность Коллатца не из таких функций. Поэтому компилятор обязательно выполнял цикл во время компиляции.
В сущности, компилятору неоткуда узнать, завершится ли когда-нибудь данный цикл (в особенности в случае с последовательностью Коллатца). Поэтому возникает вопрос: может ли компилятор застрять в бесконечном цикле? Строго говоря, нет, поскольку в компиляторе заложено ограничение на количество итераций. Например, если мы передаём число 27, на обработку которого требуется 111 итераций, компилятор сгенерирует следующее: (godbolt):
main: mov ecx, 27 xor eax, eax .LBB0_1: inc eax mov edx, ecx sar edx test cl, 1 lea ecx, [rcx + 2*rcx + 1] cmove ecx, edx cmp ecx, 1 jne .LBB0_1 retЦикл определённо на месте (обратите внимание на jne вплоть до .LBB0_1). На момент подготовки оригинала статьи максимальное количество итераций, предусмотренных в используемой здесь подсистеме, составляло 100. Здесь пояснено, почему. Можно увеличить это число до 111, передав аргумент командной строки -mllvm --scalar-evolution-max-iterations=111 (godbolt):
main: mov eax, 111 retПочему аргумент называется именно так — уже другая история. Также можете почитать об этом в другой статье автора оригинала на тему анализа возможных значений скалярных выражений (scalar evolution).
Обратите внимание: компиляция протекает достаточно медленно (на самом деле, даже слишком, учитывая, что речь идёт всего о 111 итерациях). Это свидетельствует о медленности систем, зашитых в сами компиляторы. С другой стороны, при их проектировании и не было расчёта на высокую производительность. При этом, когда я недавно знакомился с языком программирования Jai, он генерировал байт-код для вычислений во время компиляции, так что теоретически он должен работать быстрее.
Наконец, не все компиляторы вычисляют циклы во время компиляции. Например, ни GCC (godbolt), ни ICX (godbolt) не будут делать этого в примерах с последовательностями Коллатца.
Отсечение мёртвых веток кода
«Мёртвым» называется в целом такой код, без которого можно обойтись, а в частности — бесполезный/неиспользуемый/избыточный. Пожалуй, основная операция, выполняемая в рамках отсечения мёртвого кода (DCE) — это удаление неиспользуемого кода, ранее включённого директивами #include. Например, если добавить #include в пример с times2 (godbolt), то заметно, что код не изменяется — как раз потому, что компилятор уже выбросил всё ненужное. Это было сделано по двум причинам. Во-первых, потому, что код, содержащийся в файлах .h, большей частью не является исполняемым. Например, struct не исполняется. Он нужен лишь для того, чтобы сообщить компилятору, как сгенерировать код, который использует структуры. Но в C++ в файлах.h также могут содержаться определения функций, например, внутри классов. Если они не используются, то также будут выброшены.
Но бывают и более тонкие случаи. Выше была описана функция для работы с последовательностями Коллаца (godbolt), помеченная как static. Таким образом, функция локальна в пределах данного модуля и не может использоваться ни одним другим модулем (и поэтому не используется). В своём же модуле она вызывается только в одном месте, но этот вызов встраивается. Поэтому теперь в данной функции нет необходимости, поэтому компилятор её удалил.
Большинство из нас, впервые услышав об отсечении мёртвых веток кода, задаются вопросом: «позвольте, весь код, который я пишу, чем-то занят, поэтому как же компилятор находит бесполезный код?». Выше я привёл пример. В целом, большей частью мёртвый код возникает именно в результате компиляторных оптимизаций.
При удалении мёртвого кода возможны сюрпризы. Например, давайте вернёмся к вышеприведённому примеру с collatz. Но на этот раз вместо количества итераций будем возвращать n (godbolt):
static int collatz(int n) { int its = 0; while (n != 1) { its++; if (n % 2 == 0) { n /= 2; } else { n = 3 * n + 1; } } //////////////////////////////////////// // ИМЕННО ЗДЕСЬ ПРОИЗОШЛИ ИЗМЕНЕНИЯ /// //////////////////////////////////////// return n; } int main(void) { return collatz(27); }Рассмотрим код ассемблера:
main: mov eax, 1 retВ принципе, компилятор превратил код в:
int main(void) { return 1; }Но как? Обратите внимание: в данном случае мы не передавали аргумент, который увеличивал бы для движка предельную длительность времени выполнения. Как же компилятору удалось исключить цикл? Посмотрите на условие цикла: while (n != 1). Следовательно, компилятору известно, что по завершении цикла n должно быть равно 1, в противном случае цикл не завершится. Поэтому компилятор обязательно возвращает 1.
Но откуда компилятору известно, что цикл завершится? В конце концов, гипотеза Коллаца — всего лишь гипотеза… Известно из стандарта C… В сущности, бесконечные циклы, не дающие побочных эффектов (напр., вывод в консоль или запись в указатели volatile) — это примеры неопределённого поведения. Компилятор всегда исходит из того, что неопределённого поведения не произойдёт и, следовательно, что цикл завершится.
ссылка на оригинал статьи https://habr.com/ru/articles/868600/
Добавить комментарий