что с соискателя спрашивают не real-life задачи, в основном для того, что бы потешить своё ЧСВ за счёт кандидата
Не очень понимаю, к чему вы вообще это написали. Можете заглянуть в статью, на которую я ссылаюсь и которая побудила меня к написанию этого текста. Пример "не real-life задачи, которой тешат ЧСВ" звучит вот так (цититую):
Приходим мы к этому умозаключению после того, как я задаю свой первый вопрос про то, сколько памяти занимает процесс с указанным PID (кандидату демонстрируется скриншот или экран с выводом top). 80% соискателей с опытом администрирования nix систем не знают ответ, теряются или говорят очень странные вещи, 10% без объяснения выбора способны указать на колонку RES, и оставшиеся с разным успехом могут поговорить и порассуждать про виртуальное адресное пространство, разделяемую память, OOM, оверкоммиты, стэки, кучи и так далее.
И вот этого люди не знают. Речь не про решение АСМных задачек на бумажке, а про вполне жизненные и практические вещи.
Нет, конечно, можно сказать "да на хрена мне знать, как работает память/сеть/процессор/операционная система, всё, что мне нужно -- правильно звать библиотечные функции из моего фреймворка". Но это, простите, может делать и обезьянка.
Зачем мне в работе "фундаментальщина"? Где мне её использовать в проектах, которые пилятся для бизнеса по продаже телефонов и бытовой техники?
Давайте про ерунду вроде сортировки пузырьком (да ещё и на Паскале) говорить не будем. Фундаментальщина -- это работа железа, операционки, сети, общие принципы программирования, многопоточность и прочие нетленные знания, которые не меняются от выхода каждого нового модного фреймворка. Её не нужно учить "бегая за ветром". Это база.
И в вакансиях с соискателя трясут кучу знаний, зачастую такое количество, что даже имея стаж в 10-15 лет это всё знать НЕВОЗМОЖНО. Отсюда и вытекает постоянное нытьё о том, что работодатели не могут найти человека-оркестра. Может быть просто надо искать несколько специалистов, а не требовать, к примеру, от программиста знаний девопса, умения в линукс и ещё фронтенд?
Вы правда, на полном серьёзе говорите, что "девопс + линукс + фронтэнд" на уровне "чтобы пройти интервью" -- это непостижимый объём знаний за 10-15 лет стажа, если заниматься этими областями? Ну это я даже не знаю, как комментировать.
Я знаю как минимум одного молодого человека с курсов, кто сделал отличную карьеру примерно через 2 года, обойдя по зарплате и знаниям меня и многих моих коллег. Лично с ним работал. Курсы дали ему основу, дальше его фанатизм и старания сработали.
Не, ну если вы аж ОДНОГО знаете, то тут я под натиском фактов вынужден признать, что написал полную ерунду. :) Скажу больше, я таких знаю человека три. Вы же поняли из текста, что там описывается ситуация в общем и целом, а не формулируется какое-то универсальное правило для каждого отдельного человека? Исключения есть всегда, и они только подтверждают правила.
Это не skillbox виноват - это вы все виноваты.
Все-все? Точно? :) Вы уверены, что про это кричали именно айтишники, а не продавцы курсов?
очень глупо надеяться, что из всего того кол-ва людей, что свичнулись в эту сферу, не найдётся хотя бы процентов 10, которые со временем составят вам конкуренцию. Составят. И ещё зарплаты станут меньше. Медиана вон уже, остановилась на уровне 2-х летней давности.
Слушайте, это было бы прекрасно. Просто потрясающе. Правда, не сарказм. Рынок IT, несмотря на огромное количество кандидатов, всё ещё в состоянии "хорошего специалиста днём с огнём не сыщешь, узких спецов отрывают с руками за любые деньги". Мы даже не близко к тому моменту, чтобы они начали переживать из-за конкуренции.
Проблема в том, что поток людей, которые насыпались в IT, таков, что найти среди них эти самые 10% (думаю, речь о 2-3%, но не суть), которые и впрямь могут составить конкуренцию -- сложно. Для этого приходится отсеивать кучу шлака.
Ну, у меня и не было цели описывать алгоритм SROA (речь ведь о нём?) во всех деталях и тем более доказывать его корректность. Я просто привёл общую схему для понимания того, что происходит.
Что касается полурешёток -- это вкусовщина, но я не люблю описывать графовые алгоритмы в алгебраических терминах, и я бы не стал этого делать даже при формальном изложении. Сходимость следует из того факта, что каждый раз, переходя в новое поддерево доминирования, мы удаляем оттуда все лоады и заменяем их на изначальное значение или какую-то финоду и/или добавляем вход финоде. Число таких поддеревьев всегда конечно, как и число входов у финод (т.е. число таких необработанных поддеревьев -- полуинвариант), поэтому алгоритм точно сойдётся.
UB невозможен, например, в Java (не знаю, насколько это современный язык). Ну то есть, если в компиляторе баг, оно там вылезет, но при правильной работе его нет.
Ну тут всё зависит от того, насколько длинный процесс издания. У книг это год или годы, статья с шансами опубликуется за несколько месяцев (если это научный журнал) или сразу (если это сайт типа хабра), и с шансами ещё не устареет. :) К тому же, академики довольно часто пишут о вещах, которые ещё никто даже не начал реализовывать.
Судя по тому, что видел я, префетчер на х86 одинаково хорошо работает как с итерированием как вперёд, так и назад. Так что проблем с кэшами быть не должно. Что касается предсказателя переходов, то он всегда считает, что backedge - likely taken, независимо от условия цикла. Так что разницы именно по этим причинам я бы не ожидал.
А, понял. Пару советов дать могу, но учтите, что компиляторы разные и ведут себя по-разному. То, о чём я говорю, основано на опыте с компиляторами на основе LLVM:
Чего НЕ обязательно или не нужно делать:
Особо возиться с константами. Это очень базовый класс оптимизаций, и компиляторы это давно умеют, по крайней мере в С++. enum не enum - тоже по большому счёту разницы нет, это всё равно константы. Единственное - могут быть сложности, если константа передаётся через какой-нибудь extern в другой модуль, но это какие-то очень вычурнутые случаи. Пишите как удобно.
Лепить выражения в одну строку вместо разбиения на разные времянки согласно логике. Компилятору всё равно, на уровне IR программа будет, скорее всего, одинаковая. Вы всегда можете в этом убедиться при помощи чудо-сайта https://godbolt.org/. Так что пишите так, как лучше читается человеку.
Применять "хакерские секретики" типа замены "i++" на "++i" в for-циклах или замены умножения/делений на 2 на сдвиги. Наверное, лет 20 назад были компиляторы, которые этого не умели, но современный clang, да и другие современные компиляторы, это делают сами. Если это не помогает читаемости кода, заниматься этим бессмысленно.
Чего НУЖНО делать:
Избегать goto. Особенно в/из циклов. goto может привести к появлению т.н. non-loop cycles в CFG, которые являются циклами (с точки зрения теории графов), но не распознаются как таковые компилятором. На них не применяются цикловые оптимизации.
В сигнатурах функций для параметров-ссылок и указателей писать const везде, где возможно. В случае, если функция не заинлайнится, отсутствие const не позволит компилятору доказать, что никто по этой ссылке ничего не пишет. Это может поломать оптимизации.
Циклы с положительным шагом в целом оптимизируются лучше, чем с отрицательным. Это связано с некоторыми особенностями реализации анализов. В теории разницы нет, но на практике она ещё как есть. Я довольно много времени потратил, чтобы поддержать отрицательные шаги в разных цикловых оптимизациях, но эта работа далека от завершения. Поэтому, если всё равно как бежать по циклу, бегите с положительным шагом.
Всякую сложную дебажную логику (особенно с принтами) лучше уводить под #ifdef, чтобы в релизе её не было. Наличие сложного и развесистого кода с сайд-эффектами может поломать оптимизации много где.
Если сомневаетесь, может ли ваш компилятор сделать то или это, можете проверить в https://godbolt.org/ и зафайлить соотв. issue. Иногда на них кто-то смотрит (но это не точно). :)
Чаще всего floating point реализован по IEEE 754 и не зависит от языка. Но к такому может приводить undefined behavior вообще в другой части кода, а не в какой-нибудь FP-инструкции. Я на фортране не пишу, но гугл говорит, что UB в нём есть.
Похожие симптомы могут быть при наличии неопределённого поведения (UB) в программе. Современные компиляторы стараются по полной использовать его и часто на его основе делают оптимизации в местах, казалось бы, не связанных с той инструкцией, которая непосредственно вызвала UB. Раскапывать такие баги бывает непросто (шаг влево, шаг вправо, добавили принт или дебаг - и эффект пропадает). Пожалуй, это заслуживает отдельного очерка (если доберусь) :)
Скорее всего, не в следующем тексте, но когда-нибудь точно. Думаю, когда я дойду до конкретных оптимизаций, там будет довольно выпукло видно, чем удобен такой IR.
Небольшое замечание по моему определению SSA формы (спасибо читателям, которые это заметили): на самом деле, оно, возможно, слишком уж строгое. Существуют реализации IR на основе SSA, в которых CFG в явном виде не существует, по крайней мере до какого-то момента. Одним из них является IR в Graal VM. Там всё равно есть финоды, и на фундаментальном уровне всё очень похоже, но мне проще объяснять основные принципы на примере LLVM IR, который имеет явный CFG.
В дальнейшем мы будем предполагать наличие явного CFG, а про более сложные вариации, где зависимости по управлению представляются иначе, можете поискать информацию самостоятельно.
Мнения в треде разнятся. Выше высказывалось мнение, что "девопс + линукс + фронтэнд" невозможно освоить за 10-15 лет опыта. :)
Дарю. :)
Не очень понимаю, к чему вы вообще это написали. Можете заглянуть в статью, на которую я ссылаюсь и которая побудила меня к написанию этого текста. Пример "не real-life задачи, которой тешат ЧСВ" звучит вот так (цититую):
И вот этого люди не знают. Речь не про решение АСМных задачек на бумажке, а про вполне жизненные и практические вещи.
Нет, конечно, можно сказать "да на хрена мне знать, как работает память/сеть/процессор/операционная система, всё, что мне нужно -- правильно звать библиотечные функции из моего фреймворка". Но это, простите, может делать и обезьянка.
Давайте про ерунду вроде сортировки пузырьком (да ещё и на Паскале) говорить не будем. Фундаментальщина -- это работа железа, операционки, сети, общие принципы программирования, многопоточность и прочие нетленные знания, которые не меняются от выхода каждого нового модного фреймворка. Её не нужно учить "бегая за ветром". Это база.
Вы правда, на полном серьёзе говорите, что "девопс + линукс + фронтэнд" на уровне "чтобы пройти интервью" -- это непостижимый объём знаний за 10-15 лет стажа, если заниматься этими областями? Ну это я даже не знаю, как комментировать.
Не, ну если вы аж ОДНОГО знаете, то тут я под натиском фактов вынужден признать, что написал полную ерунду. :) Скажу больше, я таких знаю человека три. Вы же поняли из текста, что там описывается ситуация в общем и целом, а не формулируется какое-то универсальное правило для каждого отдельного человека? Исключения есть всегда, и они только подтверждают правила.
Все-все? Точно? :) Вы уверены, что про это кричали именно айтишники, а не продавцы курсов?
Слушайте, это было бы прекрасно. Просто потрясающе. Правда, не сарказм. Рынок IT, несмотря на огромное количество кандидатов, всё ещё в состоянии "хорошего специалиста днём с огнём не сыщешь, узких спецов отрывают с руками за любые деньги". Мы даже не близко к тому моменту, чтобы они начали переживать из-за конкуренции.
Проблема в том, что поток людей, которые насыпались в IT, таков, что найти среди них эти самые 10% (думаю, речь о 2-3%, но не суть), которые и впрямь могут составить конкуренцию -- сложно. Для этого приходится отсеивать кучу шлака.
Ну, у меня и не было цели описывать алгоритм SROA (речь ведь о нём?) во всех деталях и тем более доказывать его корректность. Я просто привёл общую схему для понимания того, что происходит.
Что касается полурешёток -- это вкусовщина, но я не люблю описывать графовые алгоритмы в алгебраических терминах, и я бы не стал этого делать даже при формальном изложении. Сходимость следует из того факта, что каждый раз, переходя в новое поддерево доминирования, мы удаляем оттуда все лоады и заменяем их на изначальное значение или какую-то финоду и/или добавляем вход финоде. Число таких поддеревьев всегда конечно, как и число входов у финод (т.е. число таких необработанных поддеревьев -- полуинвариант), поэтому алгоритм точно сойдётся.
Но вы же то же самое написали, только длиннее. О_о
А чем вам не нравится определение в статье?
"Ты вообще жрать хочешь или нет? Марш на интервью, пока миску риса не отняли!"
Вторая часть про доминирование тут.
UB невозможен, например, в Java (не знаю, насколько это современный язык). Ну то есть, если в компиляторе баг, оно там вылезет, но при правильной работе его нет.
Я пытался сформулировать какой-то ответ, но, наверное, самым лучшим будет "вы вообще о чём?"
Ну тут всё зависит от того, насколько длинный процесс издания. У книг это год или годы, статья с шансами опубликуется за несколько месяцев (если это научный журнал) или сразу (если это сайт типа хабра), и с шансами ещё не устареет. :) К тому же, академики довольно часто пишут о вещах, которые ещё никто даже не начал реализовывать.
Ага, когда джентльмены начали верить друг другу на слово, тут-то мне карта и попёрла. :)
Проблема любых книжек в том, что они устаревают уже на момент публикации. :)
Судя по тому, что видел я, префетчер на х86 одинаково хорошо работает как с итерированием как вперёд, так и назад. Так что проблем с кэшами быть не должно. Что касается предсказателя переходов, то он всегда считает, что backedge - likely taken, независимо от условия цикла. Так что разницы именно по этим причинам я бы не ожидал.
А, понял. Пару советов дать могу, но учтите, что компиляторы разные и ведут себя по-разному. То, о чём я говорю, основано на опыте с компиляторами на основе LLVM:
Чего НЕ обязательно или не нужно делать:
Особо возиться с константами. Это очень базовый класс оптимизаций, и компиляторы это давно умеют, по крайней мере в С++. enum не enum - тоже по большому счёту разницы нет, это всё равно константы. Единственное - могут быть сложности, если константа передаётся через какой-нибудь extern в другой модуль, но это какие-то очень вычурнутые случаи. Пишите как удобно.
Лепить выражения в одну строку вместо разбиения на разные времянки согласно логике. Компилятору всё равно, на уровне IR программа будет, скорее всего, одинаковая. Вы всегда можете в этом убедиться при помощи чудо-сайта https://godbolt.org/. Так что пишите так, как лучше читается человеку.
Применять "хакерские секретики" типа замены "i++" на "++i" в for-циклах или замены умножения/делений на 2 на сдвиги. Наверное, лет 20 назад были компиляторы, которые этого не умели, но современный clang, да и другие современные компиляторы, это делают сами. Если это не помогает читаемости кода, заниматься этим бессмысленно.
Чего НУЖНО делать:
Избегать goto. Особенно в/из циклов. goto может привести к появлению т.н. non-loop cycles в CFG, которые являются циклами (с точки зрения теории графов), но не распознаются как таковые компилятором. На них не применяются цикловые оптимизации.
В сигнатурах функций для параметров-ссылок и указателей писать const везде, где возможно. В случае, если функция не заинлайнится, отсутствие const не позволит компилятору доказать, что никто по этой ссылке ничего не пишет. Это может поломать оптимизации.
Циклы с положительным шагом в целом оптимизируются лучше, чем с отрицательным. Это связано с некоторыми особенностями реализации анализов. В теории разницы нет, но на практике она ещё как есть. Я довольно много времени потратил, чтобы поддержать отрицательные шаги в разных цикловых оптимизациях, но эта работа далека от завершения. Поэтому, если всё равно как бежать по циклу, бегите с положительным шагом.
Всякую сложную дебажную логику (особенно с принтами) лучше уводить под #ifdef, чтобы в релизе её не было. Наличие сложного и развесистого кода с сайд-эффектами может поломать оптимизации много где.
Если сомневаетесь, может ли ваш компилятор сделать то или это, можете проверить в https://godbolt.org/ и зафайлить соотв. issue. Иногда на них кто-то смотрит (но это не точно). :)
Более того, они ещё и UB производят иногда. :) Надеюсь и до этого когда-нибудь добраться.
Чаще всего floating point реализован по IEEE 754 и не зависит от языка. Но к такому может приводить undefined behavior вообще в другой части кода, а не в какой-нибудь FP-инструкции. Я на фортране не пишу, но гугл говорит, что UB в нём есть.
Похожие симптомы могут быть при наличии неопределённого поведения (UB) в программе. Современные компиляторы стараются по полной использовать его и часто на его основе делают оптимизации в местах, казалось бы, не связанных с той инструкцией, которая непосредственно вызвала UB. Раскапывать такие баги бывает непросто (шаг влево, шаг вправо, добавили принт или дебаг - и эффект пропадает). Пожалуй, это заслуживает отдельного очерка (если доберусь) :)
Скорее всего, не в следующем тексте, но когда-нибудь точно. Думаю, когда я дойду до конкретных оптимизаций, там будет довольно выпукло видно, чем удобен такой IR.
Небольшое замечание по моему определению SSA формы (спасибо читателям, которые это заметили): на самом деле, оно, возможно, слишком уж строгое. Существуют реализации IR на основе SSA, в которых CFG в явном виде не существует, по крайней мере до какого-то момента. Одним из них является IR в Graal VM. Там всё равно есть финоды, и на фундаментальном уровне всё очень похоже, но мне проще объяснять основные принципы на примере LLVM IR, который имеет явный CFG.
В дальнейшем мы будем предполагать наличие явного CFG, а про более сложные вариации, где зависимости по управлению представляются иначе, можете поискать информацию самостоятельно.