Comments 14
Интересно решили проблему проверки диапазонов в Rust. Там всячески принуждают программиста использовать итераторы вместо ручного цикла со счётчиком. Код с итераторами гарантированно не может выйти за диапазон, так что результирующий код вовсе не содержит проверок.
С таким подходом вся описанная в данной статье оптимизация утрачивает смысл. Ибо там, где обход массива прост, можно использовать итераторы, а там, где доступ к массиву сложноанализируемый (произвольный), оптимизатор всё равно не сможет удалить проверки.
Можно пример? В C++ же всё равно, с итераторами или без, но вам так или иначе надо делать проверки на выход за пределы. Ну, если это не foreach цикл.
Кроме того, тут примеры сложнее, код из линейной алгебры со свёртками и т.д.
В C++ нету штатной проверки на диапазон при обращении к массивам. Так что там в значительной мере всё равно, что через итераторы обращаться, что через цикл со счётчиком и [].
В Rust же есть встроенные типы стандартной библиотеки для итерации, которые вызываются при использовании оператора for. И вот внутри них проверок никаких всё ещё нету. Но вот в штатном операторе [] проверки уже есть.
В вышеизложенной статье в основном все примеры так же выразимы через итераторы - итерация в обратном направлении, итерация с отличным от единицы шагом, итерация с окном и т. д. Так что будь это Rust, то в нём всё ещё использовались бы итераторы и компилятор бы опять же не парился бы с убиранием проверок из циклов.
Ну она не то чтобы утрачивает смысл. Она просто гарантированно сделается на каноническом коде. Или они прямо в парсере не вставляют эти чеки? Код парсера Раста я не читал.
Как всегда, огромное спасибо за цикл! Прочёл с огромным интересом.
А вы можете ещё про MLIR рассказать немного?
И вот в LLVM используется подход одного промежуточного представления между проходами. В этом есть и своя прелесть, и недостатки. А как вы смотрите на подход Nanopass, где промежуточные представления слегка различаются? (недавно пробежала статья о том, как это эффективно реализовывать в OCaml (статически-типизированном языке).
Про MLIR рассказать не могу, так как сам читал только вводные статьи и смотрел пару выступлений Криса, но не особо вникал. Если кто-то популярно это опишет, я сам с радостью почитаю. Насколько я понял, всё это затевалось ради полиэдральных оптимизаций для нейронов изначально, а сейчас там тьма диалектов и непонятно, куда смотреть, чтобы разобраться.
Про Nanopass тоже мало что могу сказать, ибо руками не трогал. Судя по гитхабу, проект мёртв. Думаете, стоит изучить?
Про Nanopass тоже мало что могу сказать, ибо руками не трогал. Судя по гитхабу, проект мёртв. Думаете, стоит изучить?
Nanopass — это Крузенштерн, «человек и пароход». Есть библиотека Nanopass, а есть подход, когда ваш компилятор от начала и до конца — это конвейер из очень простых проходов с разными IR. При этом в не очень оптимизирующем компиляторе их до полусотни. Соседние IR слегка различаются, но хорошо специфицированы как отдельные языки. Вот, собственно, и вся наука.
https://github.com/IUCompilerCourse/Essentials-of-Compilation — вот курс, базирующийся на подходе Nanopass. Там для каждого прохода есть тестирующий интерпретатор (разумееся, похожие IR включены в группы, чтобы писать один интерпретатор для группы)
При исполнении такого кода нельзя ожидать, что случится что-то конкретное. В зависимости от того, что сделает компилятор, вы можете получить:
Ну и пускай. Разве, когда мы что-то делаем, мы не обязаны думать о том что мы делаем? Если выход за пределы диапазона не предусмотрен, то это не имеет значения, а если предусмотрен и может вызвать ошибки, то кодер чудак и сам виноват. Больше смахивает на "линейкой по рукам".
Вроде бы, в старых и уже заброшенных инструкциях x86, или же в каком-то другом процессоре пытались проверять границы аппаратно. Знать бы, почему не взлетело.
Я о таком не слышал, но как минимум если два массива лежат подряд, то нет способа понять, вылезли вы за пределы или нет. Память-то там выделена.
Похоже, это инструкция Bound:
While the
BOUNDinstruction does provide hardware bounds-checking, I understand it indirectly caused performance issues because it breaks the hardware branch predictor (according to a Reddit thread, but I'm unsure why), but also because it requires the bounds to be specified in a tuple in memory - that's terrible for performance - I understand at runtime it's no faster than manually having the instructions to do an "ifindexnot in range[x,y]then signal theBRexception to the program or OS" (so you might imagine theBOUNDinstruction was added for the convenience of people who coded assembly by-hand, which was quite common in the 1980s).The
BOUNDinstruction is still present in today's processors, but it was not included in AMD64 (x64) - likely for the performance reasons I explained above, and also because likely very few people were using it (and compilers could trivially replace it with a manual bounds check, that might have better performance anyway, as that could use registers).
MPX is superior to
BOUNDin that it provides dedicated registers to store the bounds range so the bounds-check should be almost zero-cost compared toBOUNDwhich required a memory access. On the Intel 486 theBOUNDinstruction takes 7 cycles (compare toCMPwhich takes only 2 cycles even if the operand was a memory address). In Skylake the MPX equivalent (BNDMK,BNDCLandBNDCU) are all 1-cycle instructions andBNDMKcan be amortized as it only needs to be called once for each new pointer).I cannot find any information on wherever or not AMD has implemented their own version of MPX yet (as of June 2017).
Поговорим об оптимизирующих компиляторах. Сказ седьмой: борьба с проверками диапазонов