Не очень понял, как связано спекулятивное исполнение и несколько ядер. Для этого бы пришлось задействовать (как минимум) протоколы когерентности кэша, а это довольно дорого. Насколько я понимаю, процессоры спекулируют на одном ядре.
А что мешает процессору, который умеет спекулировать обе ветки, делать это на неразмотанном цикле?
Ну насколько я понимаю, эта оптимизация основана на том, что вычисления в unsigned происходят в кольце вычетов по 2^32, и поэтому там есть обратный элемент. В signed так не получится, во всяком случае в лоб (не работает для отрицательных). Другое дело, что тут компилятор всё равно мог бы доказать, что при отрицательном индексе у него будет UB, при условии, что этот индекс когда-то станет меньше -6. В общем, попробовать поприседать можно, но в данном случае от деления избавиться довольно трудно.
Я имел в виду, что если вы хотите повторить на C++ что-то типа перехвата sigsegv для корректной обработки таких ситуаций (не "кодер чудак", а "эй, чудак, ты в такой-то массив полез по такому-то индексу"), то сделать этого вот так в лоб нельзя. Придётся вставлять ручные проверки.
Про MLIR рассказать не могу, так как сам читал только вводные статьи и смотрел пару выступлений Криса, но не особо вникал. Если кто-то популярно это опишет, я сам с радостью почитаю. Насколько я понял, всё это затевалось ради полиэдральных оптимизаций для нейронов изначально, а сейчас там тьма диалектов и непонятно, куда смотреть, чтобы разобраться.
Про Nanopass тоже мало что могу сказать, ибо руками не трогал. Судя по гитхабу, проект мёртв. Думаете, стоит изучить?
Ну она не то чтобы утрачивает смысл. Она просто гарантированно сделается на каноническом коде. Или они прямо в парсере не вставляют эти чеки? Код парсера Раста я не читал.
Ну да, есть всякие способы сообщить что-то про алиасинг, но пока что я ограничиваюсь формулировкой "всё сложно", имея в виду, что их реально много и там хватит на отдельную статью.
Дело в том, что в LLVM (да и большинстве других компиляторов) каждая оптимизация отвечает только за одну часть работы. LICM не умеет сокращать сумму прогрессий, GVN не умеет дуплицировать циклы, а векторизатор не пытается решать квадратные уравнения. Если оптимизации на вход пришёл какой-то IR, она будет пытаться с ним сделать то, что умеет она, поскольку каждая отдельная оптимизация не знает (да и не может знать) всего, что ещё можно с ним сделать.
Я намеренно привожу простые примеры, чтобы в них не было лишнего кода, который мешает понять, что происходит и как работает наша оптимизация. Да, их обычно можно оптимизировать сотней других способов. Например, превратив в сумму ряда или векторизовав. Но не надо забывать, что цель статьи -- рассказать про конкретный класс преобразований, а не про то, как заоптимизировать до максимума какой-нибудь игрушечный пример. :)
Если речь не про вынос ветвлений и не про память, то практически любой LLVM-ный компилятор всё вынесет (в режиме -O2 и выше). В таких случаях я бы рекомендовал не приносить читаемость в жертву.
С памятью и ветвлениями всё сложнее. Например, если для выноса ветвления нужно продублировать код, компилятор может отказаться это делать из соображений экономии размера бинарника или времени компиляции, даже если докажет, что трансформация легальна. Что касается памяти, то там вообще всё сложно и нужно доказывать всякие aliasing-факты. Конечно, чем дальше, тем компиляторы в этом смысле умнее, но бывает всякое, и иногда даже относительно простые случаи не оптимизируются.
К тому же, у человека может быть знание, которого у компилятора нет в принципе. Если вы посмотрите на пример про load/store по двум разным указателям, то у компилятора нет способа доказать, что они разные. Но если вы по какой-то причине знаете, что эту функцию вызывают только таким образом, что p1 и p2 никогда не перекрываются, то вы можете соптимизировать её вручную, используя это знание.
В любой ситуации можно использовать чудо-сайт https://godbolt.org/, чтобы посмотреть, что на самом деле происходит.
Это так, но оптимизации, которые к этому приводят, мы в рамках этой статьи не рассматриваем. Это игрушечные примеры, которые нужны только чтобы показать, как идёт работа с инвариантами. Я же не ставил цели показать, как именно эти программы заоптимизировать до максимума.
Я что-то пропустил или что-то не понял? Почему нельзя было посчитать в виде:
Пропустили.
Данный пример можно было бы оптимизировать и иначе, заметив, что обе суммы -- это знакомые нам со школы формулы квадрата суммы и квадрата разности, но об этом классе оптимизаций мы поговорим потом.
Так можно, но речь не об этом. Этим примером я хотел продемонстрировать совсем другую оптимизацию. Это нормально, что один и тот же код можно оптимизировать разными способами, и обычно компилятор работает по принципу "какая оптимизация первая туда пришла, так и работает".
Потом, в чем польза рефакторинга который из ТРЕХ строчек кода делает десять, причем позволяет растащить эти строчки хоть в разные файлы, так что потом чтобы проверить арифметику вам придется ползать по всему проекту.
В том, что этот пример приводится для того, чтобы объяснить работу данной компиляторной оптимизации, а не в том, чтобы научить вас правильно рефакторить код и организовывать проект. Я это уже объяснял в самой первой статье про SSA-форму:
Просто всякий раз, когда нам нужно было переприсвоить переменную (чего мы теперь не можем делать) мы должны определить новую переменную и в дальнейшем пользоваться ей. С точки зрения С++, выглядит довольно многословно и бредово, и ни один человек в здравом уме так не будет писать. Но ведь мы стараемся не для человека, а для компилятора!
В любых целых типах можно, даже если переполнения работают на кольце. В дробных - тут действительно может получиться другой результат, потому что будут другие округления, но если вы компилируете без StrictFP, то всё равно можно.
В случае коллизии проверяется на эквивалентность. В зависимости от затейливости имплементации, она может банально сравнивать опкод + аргументы и полагаться на каноническую форму, либо кривляться на тему сложных проверок эквивалентности. LLVM следует первому подходу (https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/GVN.cpp#L147).
В целом, реально существующие имплементации реализуют достаточно простой вариант, без [сложного] символьного анализа.
Компании, где я работал, старались набирать не джунов, а интернов. Платят им немного, зато есть возможность научить всему необходимому перед получением титула. Это, как правило, были студенты очного отделения, совсем без опыта работы, желательно с какими-нибудь достижениями (годились как олимпиады, так и самостоятельное программирование для себя).
В самом лучшем случае (если человека брали уже на старшем курсе и он был очень толковым), интернатура занимала месяцев 6-8 (в режиме ежедневной практики примерно 20-32 часов в неделю). Обычно -- год-полтора. Только после этого можно было ставить вопрос, чтобы назвать человека джуном.
Выпускникам трёхмесячных курсов, которым сказали, что они джуны, могу только посочувствовать. Их обманули. Продавцам курсов не интересно продавать историю о том, что "после наших курсов вы можете пойти куда-то стажироваться, где вас ещё будут учить", потому что за это мало кто заплатит, видимо. Да и зарплаты интернов не такие вкусные, чтобы ими можно было манить людей.
Объективно, человек без опыта, прошедший трёхмесячные курсы -- функциональный аналог студента, который чего-то там программировал для себя. Точнее, он, скорее всего, сильно уступает студенту по части теоретической базы. Так что таких людей, с оговорками, можно брать на интернов. На джунов -- точно нет. Ну если только это не совсем какая-то галимая галера, где нужно копать от забора до обеда, не включая голову.
Или смысл в том, что в do-while в блок внутри } while (...) нельзя попасть мимо блока перед закрывающей фигурной скобкой, и компилятор сливает оба эти блока?
Практической разницы между тем, чтобы иметь 2 разных блока, между которыми единственное ребро, или один блок -- нет, компилятор при первой же возможности склеит их в один. Наверное, для чистоты можно было бы нарисовать два, я об этом как-то не думал.
Набор взаимно рекурсивных функций?
Можете объяснить, откуда там вообще цикл и non-loop в частности? Мне на ум приходят только какие-то вариации на уровне хвостовой рекурсии, которая после инлайнинга действительно порождает цикл, но обычный.
Циклом называется максимальный по включению сильно связный подграф, в котором одна из его вершин доминирует над всеми остальными.
Факапа нет, прочитайте определение ещё раз. Подграф максимальный при условии, что он всё ещё доминируется одной из его вершин. Если мы берём вершину 3, то максимальный по включению сильно связный подграф, который ей доминируется -- это {3, 4}.
Возможно, мне стоит как-то это переформулировать, чтобы было ясно, что свойство максимальности по включению вторично по отношению к свойству доминирования.
У джавы в числодробилках (т.е. когда в бенче не создаются объекты, не выделяется активно память и не собирается gc и т.п.) нет никаких других дополнительных проблем. Перфоманс у неё будет плюс-минус как у раста (если речь о Зинге используется одна версия LLVM)
Примеры на расте строятся банально (достаточно заюзать что угодно с UB). Ну например:
Проверки на 0 честно делаются и никуда не выкашиваются, поэтому в цикле сложный CFG, против одного блока в С++. Я это не бенчмаркал, потому что мне лень, но перфоманс тут и так понятен.
Я бы сказал, что сложно построить пример, где возможны в теории (но не происходят на практике) какие-то исключительные ситуации (которые в С++ ведут к UB, а в rust -- к panic), и при этом перфоманс будет одинаковый. Если сможете это сделать, можете покидать примеры, очень интересно.
Я понимаю, что для авторов идеи UB выдавать warning на каждую арифметическую операцию со знаковыми (после promotion) целыми числами было бы всё же слишком палевно, они на это не пойдут. Сликом открыто была бы видна их злобная сущность. Примерно как авторы законов о money laundering, тем не менее, не решились до сих пор открыто изъять все деньги со всех банковских счетов населения.
Я всё жду, когда авторов идеи UB начнут сравнивать с нацистами или даже конкретно с Гитлером. :)
Давайте я сразу пошлю в лес все инсинуации на тему "чего можно было бы сделать". clang и LLVM -- открытые продукты. Вы можете пойти и написать соответствующие ворнинги там, где хотите. Если вы сможете обосновать ревьюерам их необходимость, ваши правки примут. Честно. Никакой магии нет.
Я рассказываю о том, как оно работает сейчас, и объясняю, почему. Это не значит, что это лучший или единственно возможный способ делать то или это, но жизнь такова и более никакова. Вы можете 125 раз быть несогласны со вторым началом термодинамики или с правилами навигации кораблей в полярных водах, но разглагольствовать об этом здесь -- бесполезно.
Не очень понял, как связано спекулятивное исполнение и несколько ядер. Для этого бы пришлось задействовать (как минимум) протоколы когерентности кэша, а это довольно дорого. Насколько я понимаю, процессоры спекулируют на одном ядре.
А что мешает процессору, который умеет спекулировать обе ветки, делать это на неразмотанном цикле?
Ну насколько я понимаю, эта оптимизация основана на том, что вычисления в unsigned происходят в кольце вычетов по 2^32, и поэтому там есть обратный элемент. В signed так не получится, во всяком случае в лоб (не работает для отрицательных). Другое дело, что тут компилятор всё равно мог бы доказать, что при отрицательном индексе у него будет UB, при условии, что этот индекс когда-то станет меньше -6. В общем, попробовать поприседать можно, но в данном случае от деления избавиться довольно трудно.
Но наблюдение отличное!
Я о таком не слышал, но как минимум если два массива лежат подряд, то нет способа понять, вылезли вы за пределы или нет. Память-то там выделена.
Я имел в виду, что если вы хотите повторить на C++ что-то типа перехвата sigsegv для корректной обработки таких ситуаций (не "кодер чудак", а "эй, чудак, ты в такой-то массив полез по такому-то индексу"), то сделать этого вот так в лоб нельзя. Придётся вставлять ручные проверки.
Про MLIR рассказать не могу, так как сам читал только вводные статьи и смотрел пару выступлений Криса, но не особо вникал. Если кто-то популярно это опишет, я сам с радостью почитаю. Насколько я понял, всё это затевалось ради полиэдральных оптимизаций для нейронов изначально, а сейчас там тьма диалектов и непонятно, куда смотреть, чтобы разобраться.
Про Nanopass тоже мало что могу сказать, ибо руками не трогал. Судя по гитхабу, проект мёртв. Думаете, стоит изучить?
Ну она не то чтобы утрачивает смысл. Она просто гарантированно сделается на каноническом коде. Или они прямо в парсере не вставляют эти чеки? Код парсера Раста я не читал.
Ну да, есть всякие способы сообщить что-то про алиасинг, но пока что я ограничиваюсь формулировкой "всё сложно", имея в виду, что их реально много и там хватит на отдельную статью.
Дело в том, что в LLVM (да и большинстве других компиляторов) каждая оптимизация отвечает только за одну часть работы. LICM не умеет сокращать сумму прогрессий, GVN не умеет дуплицировать циклы, а векторизатор не пытается решать квадратные уравнения. Если оптимизации на вход пришёл какой-то IR, она будет пытаться с ним сделать то, что умеет она, поскольку каждая отдельная оптимизация не знает (да и не может знать) всего, что ещё можно с ним сделать.
Я намеренно привожу простые примеры, чтобы в них не было лишнего кода, который мешает понять, что происходит и как работает наша оптимизация. Да, их обычно можно оптимизировать сотней других способов. Например, превратив в сумму ряда или векторизовав. Но не надо забывать, что цель статьи -- рассказать про конкретный класс преобразований, а не про то, как заоптимизировать до максимума какой-нибудь игрушечный пример. :)
Если речь не про вынос ветвлений и не про память, то практически любой LLVM-ный компилятор всё вынесет (в режиме -O2 и выше). В таких случаях я бы рекомендовал не приносить читаемость в жертву.
С памятью и ветвлениями всё сложнее. Например, если для выноса ветвления нужно продублировать код, компилятор может отказаться это делать из соображений экономии размера бинарника или времени компиляции, даже если докажет, что трансформация легальна. Что касается памяти, то там вообще всё сложно и нужно доказывать всякие aliasing-факты. Конечно, чем дальше, тем компиляторы в этом смысле умнее, но бывает всякое, и иногда даже относительно простые случаи не оптимизируются.
К тому же, у человека может быть знание, которого у компилятора нет в принципе. Если вы посмотрите на пример про load/store по двум разным указателям, то у компилятора нет способа доказать, что они разные. Но если вы по какой-то причине знаете, что эту функцию вызывают только таким образом, что
p1иp2никогда не перекрываются, то вы можете соптимизировать её вручную, используя это знание.В любой ситуации можно использовать чудо-сайт https://godbolt.org/, чтобы посмотреть, что на самом деле происходит.
Это так, но оптимизации, которые к этому приводят, мы в рамках этой статьи не рассматриваем. Это игрушечные примеры, которые нужны только чтобы показать, как идёт работа с инвариантами. Я же не ставил цели показать, как именно эти программы заоптимизировать до максимума.
Пропустили.
Так можно, но речь не об этом. Этим примером я хотел продемонстрировать совсем другую оптимизацию. Это нормально, что один и тот же код можно оптимизировать разными способами, и обычно компилятор работает по принципу "какая оптимизация первая туда пришла, так и работает".
В том, что этот пример приводится для того, чтобы объяснить работу данной компиляторной оптимизации, а не в том, чтобы научить вас правильно рефакторить код и организовывать проект. Я это уже объяснял в самой первой статье про SSA-форму:
В любых целых типах можно, даже если переполнения работают на кольце. В дробных - тут действительно может получиться другой результат, потому что будут другие округления, но если вы компилируете без StrictFP, то всё равно можно.
В случае коллизии проверяется на эквивалентность. В зависимости от затейливости имплементации, она может банально сравнивать опкод + аргументы и полагаться на каноническую форму, либо кривляться на тему сложных проверок эквивалентности. LLVM следует первому подходу (https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/GVN.cpp#L147).
В целом, реально существующие имплементации реализуют достаточно простой вариант, без [сложного] символьного анализа.
Компании, где я работал, старались набирать не джунов, а интернов. Платят им немного, зато есть возможность научить всему необходимому перед получением титула. Это, как правило, были студенты очного отделения, совсем без опыта работы, желательно с какими-нибудь достижениями (годились как олимпиады, так и самостоятельное программирование для себя).
В самом лучшем случае (если человека брали уже на старшем курсе и он был очень толковым), интернатура занимала месяцев 6-8 (в режиме ежедневной практики примерно 20-32 часов в неделю). Обычно -- год-полтора. Только после этого можно было ставить вопрос, чтобы назвать человека джуном.
Выпускникам трёхмесячных курсов, которым сказали, что они джуны, могу только посочувствовать. Их обманули. Продавцам курсов не интересно продавать историю о том, что "после наших курсов вы можете пойти куда-то стажироваться, где вас ещё будут учить", потому что за это мало кто заплатит, видимо. Да и зарплаты интернов не такие вкусные, чтобы ими можно было манить людей.
Объективно, человек без опыта, прошедший трёхмесячные курсы -- функциональный аналог студента, который чего-то там программировал для себя. Точнее, он, скорее всего, сильно уступает студенту по части теоретической базы. Так что таких людей, с оговорками, можно брать на интернов. На джунов -- точно нет. Ну если только это не совсем какая-то галимая галера, где нужно копать от забора до обеда, не включая голову.
Вы правы, это ошибка, спасибо! Сейчас переделаю.
Практической разницы между тем, чтобы иметь 2 разных блока, между которыми единственное ребро, или один блок -- нет, компилятор при первой же возможности склеит их в один. Наверное, для чистоты можно было бы нарисовать два, я об этом как-то не думал.
Можете объяснить, откуда там вообще цикл и non-loop в частности? Мне на ум приходят только какие-то вариации на уровне хвостовой рекурсии, которая после инлайнинга действительно порождает цикл, но обычный.
Я попробовал, но с разбегу со свитчами у меня не получилось. Они не дают ставить лейблы внутри циклов. Если будет пример, скиньте, очень интересно!
Факапа нет, прочитайте определение ещё раз. Подграф максимальный при условии, что он всё ещё доминируется одной из его вершин. Если мы берём вершину 3, то максимальный по включению сильно связный подграф, который ей доминируется -- это
{3, 4}.Возможно, мне стоит как-то это переформулировать, чтобы было ясно, что свойство максимальности по включению вторично по отношению к свойству доминирования.
Пожалуйста, перестаньте писать мне, что "курощение" -- это опечатка. Это не опечатка, а отсылка к Карлсону. Стыдно классику не знать, товарищи! :)
У джавы в числодробилках (т.е. когда в бенче не создаются объекты, не выделяется активно память и не собирается gc и т.п.) нет никаких других дополнительных проблем. Перфоманс у неё будет плюс-минус как у раста (если речь о Зинге используется одна версия LLVM)
Примеры на расте строятся банально (достаточно заюзать что угодно с UB). Ну например:
С++: https://godbolt.org/z/z6dxvrE13
Rust: https://godbolt.org/z/nK19aWMYE
Проверки на 0 честно делаются и никуда не выкашиваются, поэтому в цикле сложный CFG, против одного блока в С++. Я это не бенчмаркал, потому что мне лень, но перфоманс тут и так понятен.
Я бы сказал, что сложно построить пример, где возможны в теории (но не происходят на практике) какие-то исключительные ситуации (которые в С++ ведут к UB, а в rust -- к panic), и при этом перфоманс будет одинаковый. Если сможете это сделать, можете покидать примеры, очень интересно.
Я всё жду, когда авторов идеи UB начнут сравнивать с нацистами или даже конкретно с Гитлером. :)
Давайте я сразу пошлю в лес все инсинуации на тему "чего можно было бы сделать". clang и LLVM -- открытые продукты. Вы можете пойти и написать соответствующие ворнинги там, где хотите. Если вы сможете обосновать ревьюерам их необходимость, ваши правки примут. Честно. Никакой магии нет.
Я рассказываю о том, как оно работает сейчас, и объясняю, почему. Это не значит, что это лучший или единственно возможный способ делать то или это, но жизнь такова и более никакова. Вы можете 125 раз быть несогласны со вторым началом термодинамики или с правилами навигации кораблей в полярных водах, но разглагольствовать об этом здесь -- бесполезно.