Обсуждение принципов работы современных компиляторов

[Absurd]

которые из-зо всех сил пытались оставаться в родной среде и писали циклы на ( i <= N-1 ).

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

Я вас уже три раза наглядно ставил перед фактом: в построении компиляторов вы не понимаете ничерта. Ну чтож, поставлю четвертый раз: что может помешать вынести вычисление выражения N-1 за пределы цикла, если компилятор видит что переменная N внутри цикла заведомо не изменяется никогда?

[Romeo]

Я вас уже три раза наглядно ставил перед фактом: в построении компиляторов вы не понимаете ничерта. Ну чтож, поставлю четвертый раз: что может помешать вынести вычисление выражения N-1 за пределы цикла, если компилятор видит что переменная N внутри цикла заведомо не изменяется никогда?

Да я тоже столько раз уже его тыкал в его необразованность и полное отсутствие гибкости мышления. Всё бесполезно. Как с гуся вода...

[Absurd]

Да я тоже столько раз уже его тыкал в его необразованность и полное отсутствие гибкости мышления

Это слишком общее. Тут речь о том что он допускает одну и ту же ошибку три раза, и даже не считает нужным хотябы заткнуться и больше не заикаться о проблемах которые инженеры IBM решили уже в 70-х/80-х годах прошлого века теми способами которые в данный момент уже вошли в учебники по информатике.

[Сионист]

Я вас уже три раза наглядно ставил перед фактом: в построении компиляторов вы не понимаете ничерта. Ну чтож, поставлю четвертый раз: что может помешать вынести вычисление выражения N-1 за пределы цикла, если компилятор видит что переменная N внутри цикла заведомо не изменяется никогда?

Оптимизация компилятором к делу не относится. Лучше скажи, в чём суперхитрость перекладывать на компилятор даже самую очевидную оптимизацию? Компиляторы и настройки оптимизации бывают разные и вполне можно наткнуться на вариант, который этого не делает. И даже хуже того: инструментальщик-неумеха может такой цикл в самом компиляторе перевести вручную и получить уже гарантию того, что вычитание будет выполняться в самом цикле. Кроме того, хорошо, когда тип хотябы встроенный. А если свой? Вы можете заранее гарантировать, что в любой кривоподелухе ни одно вычитание не будет иметь побочных эффектов? А тогда такая оптимизация меняет алгоритм не на эквивалентный, как в случае целых, а на неэквивалентный, но таких полномочий компилятор не имеет. Но даже если эти эффекты нужны и в цикле, делать так так не нужно, а нужно от побочных эффектов в самом вычитании избавиться, а всё, что надо делать в цикле, но не надо делать при каждом инкременте, запихать или прямо в тело цикла, или в другие функции, возможно инлайновые, а из тела цикла их вызывать.

[Absurd]

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

Компьютер не выполняет программу которую вы написали. Компьютер выполняет программу которая _эквивалентна по наблюдаемому поведению_ той программе которую вы написали. Это общее место в теории и практике компьютерной науки уже несколько десятилетий. На однопоточных программах это не заметно, но на многопоточных программах чтобы быть уверенным в том что переменная a изменится до переменной b нужно поставить fence между присвоениями новых значений a и b.

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

У компиляторов есть пайплайн от исходного кода до непосредственно exe. Обычно он примерно одинаковый, так как это в основном древние как говно мамонта технологии 80-х годов, запатентованные IBM или какими нибудь Silicon Graphics или Cray. Можете показать на картинке место в пайплайне GCC, где может возникнуть подобный дефект?

[Сионист]

У компиляторов есть пайплайн от исходного кода до непосредственно exe.

Компиляторов? Или ассемблеов? Не важно, в каком именно месте исходного текста компилятора попался цикл. Если инструментальщик-неумеха, или инструментальщик-новичок привык, когда был прикладником, полагаться на автоматическую оптимизацию, но в ручной оптимизации на уровне исходного текста ни бум-бум и взялся за разработку по схеме "сначала написать компилятор на языке высокого уровня, а потом вручную перевести его на язык ассемблера", то его цикл в исполняемом коде компилятора будет максимально точно соответствовать тому, что он же напишет на высоком уровне. Без оптимизации. И если там было i<=N-1, то дефект будет проявляться в несколько более медленной компиляции, чем можно было бы сделать с тем же качеством оптимизации компилированного этим поделием кода. И врядли этот компилятор сможет оптизировать таким образом. Да, кстати, N может быть и волотильной, тогда единственная возможная оптимизация будет заменой I<=N-1 на i<N. Но можно хранить количество элементов, а можно адреса крайних элементов. Но речь не о том, может ли эту оптимизацию выполнить компилятор. Дело в том, что она очевидна любому, кто знаком с методами оптимизации кода. А раз она очевидна, то почему бы не сделать её явной? Только и всего. Вот за этим и посылать в библиотеку. Чтоб если когда нибудь возомнит себя компиляторо-писакой, то во-первых хотябы попытался сделать автоматические оптимизации и уже знал, какими они должны быть, а во-вторых смог сам компилятор написать оптимально даже в том случае, если придётся его писать на языке ассемблера. В книгах на тему оптимизации много таких советов. Проанализировать, всегда ли чётно количество итераций и если да, то попробовать сократить его в два раза, но удвоить тело цикла, а потом сравнить. В циклах сравнивать только с величинами, вычисленными до сравнения. Предпочитать сравнение с нолём сравнению с любым другим значением, то есть если счётчик цикла знаковый, а направление перебора не имеет значения, то вместо

Код: Выделить всё

for (i=0; i<N; ++i)

писать

Код: Выделить всё

for (i=N-1; i>=0; --i)

. Попробовать отложенное и преждевременное вычисление и сравнить с вычислением по мере надобности. Везде, где не требуется из инкермента/декрмента обязательно возвращать куда либо именно старое значение переменной, применять только префиксные инкремент/декремент, а не постфиксные. Компилятор способен оптимизировать

Код: Выделить всё

i++

до

Код: Выделить всё

++i

? All complete. Но в книгах эту замену тоже рекомендуется делать вручную и явно. Не я всё это придумал, я это прочитал в книгах на тему оптимизации. Вынос вычитания из сравнения в цикле за цикл даёт положительный эффект всегда, но не усложняет исходный текст, а замена i<=N-1 на i<N даёт положительный эффект не только всегда, но и всегда ещё больший, поэтому такие оптимизации надо делать вручную. Даст ли всё это эффект на конкретном компиляторе с конкретными настойками - это уже другой вопрос, то, что даёт эффект всегда, может быть как раз сделано в обеих сравниваемых версиях программы. Но эти приёмы надо знать. И не перекладывать на компилятор, а применять явно. В противоположность этому замена

Код: Выделить всё

TList::Iterator Iterator;
...
for (TList::Begin(); Iterator!=TList::End(); ++Iterator)

на

Код: Выделить всё

TList::Iterator Iterator=TList::Begin();
...
for (; Iterator!=TList::End(); ++Iterator)

текст усложняет. Но если между декларацией итератора и первым заголовком цикла с этим итератором нет ни одного обращения к итератору, то что помешает компилятору сделать и эту замену тоже? Но почему то меня здесь призывают заменять начальное присваивание инициализацией. Текст должен легко читаться, сопровождающего программиста не следует заставлять листать программу от цикла назад к декларации итератора, а декларация итератора прямо в заголовке может привести к многократному дублированию этой декларации и блокам на пустом месте, то есть уже к однозначной корявости текста. А то, что действительно можно без затрат сделать вручную, почему то выливается в критику моего знания процесса компиляции. Я такие компиляторы видал, что компилированный ими код не мог выиграть по времени исполнения 1-ну секунду из 1423-х у интерпретируемой бейсик-программы.

[Absurd]

Вы не знаете как компилятор компилирует программы. Сначала он делает псевдоассемблер с бесконечным количеством виртуальных регистров, каждому из которых можно присвоить значение ровно один раз. Кроме того, есть Ф-форма, позволяющая присвоить виртуальному регистру значение в зависимости от того по какому маршруту мы пришли к оператору присваивания. Ф-форма может появляться только в начале блока либо после другой Ф-формы. Блок должен заканчиваться условным либо безусловным goto, либо оператором ret

Код: Выделить всё

for (i=0; i<=N-1; ++i)

Превращается в

Код: Выделить всё

block cycle_prologue:
     vreg0 = 0
     vreg1 = sub N, 1
     goto cycle_body

block cycle_body:
     vreg2 = Ф(cycle_prologue: vreg0, cycle_body: vreg3)
     vreg3 = add vreg2, 1
     vreg4 = cmp le vreg3, vreg1
     cond_goto vreg4, true:cycle_body, false:cycle_epilogue

block cycle_epilogue:
     /*то что после тела цикла*/

Здесь виртуальному регистру vreg2 присвоено значение vreg0 или vreg3 в зависимости от того пришли мы к Ф-форме из инициализации либо из тела цикла.
Потом псевдоассемблер конвертируется в реальный ассемблер с реальными регистрами. Это патент IBM от середины 80-х.

Можете мне описать алгоритмическую оправданность генерации двух Ф-форм для N и для i вместо одной Ф-формы для переменной i?

Код: Выделить всё

i++

++i

Оператора инкремента в псевдоассемблере clang вообще нет. ЕМНИП и в gcc тоже нет. Есть add c литералом. Кроме того, поскольку значение присваивается виртуальному регистру один раз и навсегда разницы между постфиксным и префиксным инкрементом тоже нет. Они оба превращаются в "vreg1 = add vreg0, 1". Только когда парсится выражение с постфиксным инкрементом обращение к переменной i заменяется обращением к виртуальному регистру vreg0, а с префиксным - к регистру vreg1.

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


Да и вообще, читаете вы говно.

Для въезда в тему надо прочитать как минимум это

http://newstar.rinet.ru/~goga/sicp/sicp.pdf

[Сионист]

Кстати, у меня Find возвращает значение, если Pointer равен nullptr, ноо получив такой итератор стартовым, не делает ничего полезного, а ограничивается только проверкой и бросает исключение, если nullptr равен Owner. Если же nullptr валяется в Pointer итератора последнего элемента в диапазоне, то ищет до конца списка. И Insert, получив nullptr в Pointer исключение не бросает, а добавляет элемент за конец списка, если же nullptr валяется в Owner, то бросается исключение. И только сравнение и инкремент бросают исключение и если Pointer равен nullptr, и если nullptr равен Owner. Но разные. Под проверками Pointer==nullptr и Owner==nullptr ни где нет одинакового кода.

Можете мне описать алгоритмическую оправданность генерации двух Ф-форм для N и для i вместо одной Ф-формы для переменной i?

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

Это патент IBM от середины 80-х.

Во-первых у меня у самого 4 патента. А сколько у Вас, чтоб говорить, что чистая математика патентуется? Она не патентуется вообще. А во-вторых патент предназначен для защиты идеи от несанкционированного использования: патентообладатель заявляет государству, что именно он хочет сохранить в секрете, а государство требует, чтоб тот, кто даже узнал секрет, но не получил от патентообладателя разрешения на его использование, воздерживался от использования чужого секрета. Таким образом, патент на компилятор прямо противоречит тому, что все компилятору устроены именно так. Сам патент запрещал бы без специального на то разрешения повторять за IBM.

Оператора инкремента в псевдоассемблере clang вообще нет.

1. Оператора в ассемблере, даже псевдо. Не смешно.
2. В системе команд процессорная инструкция инкремента есть и закодирована иначе, чем процессорная инструкция составного сложения и присваивания, а процессорной инструкции обычного сложения нет. Объясни, каким образом компилятор компилирует ++i в операцию именно инкремента и почему i=i+1 для оптимизации до INC требует анализа, без которого в худшем случае получится:

Код: Выделить всё

скопировать через регистр i во временную величину
загрузить её в регистр
сложить этот регистр с 1 инструкцией ADD
сохранить его назад в память
скопировать временную величину через регистр в память

, а в относительно хорошем:

Код: Выделить всё

скопировать i в регистровую временную величину, то есть просто отвести регистр для временного хранения копии i
сложить этот регистр с 1 инструкцией ADD
сохранить его назад в i

. При том, что счётчик цикла уже лежит в регистре и в память каждый раз не сохраняется, даже такой код коряв и его можно ещё улучшить до увеличения i инструкцией ADD, но:
2.1. Даже такая оптимизация уже требует анализа кода.
2.2. ADD требует загрузки второго операнда, из-за чего может выполняться медленнее, чем INC. И на старых камнях загрузка второго операнда выполнялась всегда после расшифровки кода операции, но до начала исполнения, что требовало минимум одного дополнительного такта, из-за чего INC и была введена в систему команд. Инкремент же компилируется просто в INC, которую улучшить уже нельзя.
Если скажешь, что компилятор способен скомпилировать i=i+1 в INC AX, оспаривать не буду, да вопрос не в том.

[Absurd]

Можете мне описать алгоритмическую оправданность генерации двух Ф-форм для N и для i вместо одной Ф-формы для переменной i?

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

Месье, не пора ли вам выйти на свежий воздух?

Про Static Single Assignment Form я вам ранее писал. Этой технологии уже более 20 лет. Ее использует, gcc, clang и MSVC++. Вы проигнорировали эту информацию.

[Сионист]

Про Static Single Assignment Form я вам ранее писал. Этой технологии уже более 20 лет. Ее использует, gcc, clang и MSVC++. Вы проигнорировали эту информацию.

"Технологии"? Или двум Ф-формам вместо одной на конкретном этапе компиляции, перед которым можно воткнуть ещё один?

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

Тест говорит от обратном:

Код: Выделить всё

i=1;
std::cout<<++i<<std::endl;

выводит 2,

Код: Выделить всё

i=1;
std::cout<<i++<<std::endl;

же выводит 1.
Так кто не знает, как работает компилятор? По-Вашему он просто не способен соблюсти стандарт, так что очевидно, что Вы даже не подозреваете, как он работает.