вы большой компилятор что это значит
Что такое компилятор
Dec 7, 2020 · 7 min read
Если вы программист, то наверняка слышали слово “компилятор”. Но знаете ли вы, что это такое на самом деле? Вы когда-нибудь задумывались, что происходит под капотом, когда вы запускаете команду javac (если у вас код на Java)? Вы когда-нибудь хотели создать свой собственный язык программирования? — и просто заводили бесполезный репозиторий GitHub, где все равно есть только один readme.md, потому что вы даже не знаете, с чего начать. Я думаю, что начинать стоит с этого: узнать больше о компиляторе.
Итак, в этой статье мы разберёмся, что представляет собой компилятор. Если вы опытный программист, который знает про компилятор каждую мелочь, то извините, эта статья не для вас. Но если вы — тот самый парень из абзаца выше, то вперёд за мной, в кроличью нору. На протяжении статьи я буду обсуждать следующие подтемы:
Вступление
Компилятор — это не что иное, как переводчик исходного кода.
Задача компилятора — перевести исходный код с одного языка на другой. Это означает, что если вы скормите компилятору исходный код Java, то сможете получить исходный код Python (не самый лучший пример, просто для понимания сути. На самом деле вы получите байт-код Java, который можно запустить на JVM). Для выполнения этого процесса у компилятора есть несколько взаимосвязанных компонентов.
Типы компиляторов
Мы можем классифицировать компиляторы по-разному. В этой статье я расскажу о двух способах классификации компиляторов, однако особенно углубляться в это не буду.
Классификация компиляторов в соответствии с этапами компиляции
Здесь мы рассмотрим количество этапов, которые проходит компилятор. Некоторые компиляторы непосредственно преобразуют высокоуровневый исходный код в машинный код, а некоторые — сначала преобразуют высокоуровневый исходный код в промежуточное представление перед преобразованием в машинный код.
Таким образом, в соответствии с этой классификацией можно выделить три типа компиляторов:
Если вы хотите узнать больше об этой классификации компиляторов, посмотрите сюда.
Классификация компиляторов в соответствии с исходным кодом и целевым кодом
Для преобразования исходного кода в целевой применяются разные подходы. Некоторые компиляторы преобразуют код на высокоуровневом языке в машинный. Некоторые компиляторы преобразуют с одного языка высокого уровня на другой язык высокого уровня. Таким образом, здесь выделяются следующие типы:
Архитектура компилятора
Когда компилятор компилирует (переводит) исходный код, он проходит несколько этапов:
Мы можем разделить все эти этапы на две фазы, примерно как фронтенд и бэкенд. Эти фазы включают в себя следующие этапы:
Фронтенд
Бэкенд
В следующем разделе я кратко опишу, что происходит на каждой фазе. Если вы не программируете компиляторы, то нормально иметь о них лишь поверхностное представление, но если вы хотите разработать компилятор сами, то вам стоит подробно изучить их работу.
Лексический анализ
Теперь вы знаете, что компилятор — это программа, которая преобразует исходный код в другой исходный код. Компилятор получает исходный код в виде файла. Этот файл содержит код в текстовом формате, но компилятор не может работать с этим текстом. Необходимо преобразовать этот текст в некоторый другой формат, понятный компилятору. Для этого компилятор разбивает текст по маркерам. Помните, что эти маркеры заранее определены в грамматике языка. Маркеры пригодятся на следующих этапах процесса компиляции:
KEYWORD, BRACKET, IDENTIFIER, OPERATOR, NUMBER на приведенной выше диаграмме — это и есть маркеры. Компилятор использует лексический анализ для идентификации маркеров, и если он получает маркер, который не определен заранее в грамматике языка, то это будет считаться ошибкой.
Синтаксический анализ (парсинг)
На этом этапе компилятор проверяет, расположены ли идентифицированные ранее маркеры в правильном порядке. Для этого в каждом языке есть набор правил, называемый грамматикой. Во-первых, компилятор пытается построить структуру данных — дерево синтаксического анализа. Если компилятор смог успешно построить дерево синтаксического анализа в соответствии с заранее определенными правилами грамматики, то в исходном коде нет синтаксических ошибок. В противном случае возникают ошибки и компилятор их покажет.
Здесь мы сначала определили грамматику. Затем компилятор пытается построить дерево синтаксического анализа для исходного кода 2 + 3 * 3. В этом случае компилятору удается построить дерево синтаксического анализа (с правой стороны) в соответствии с грамматикой, следовательно в этой программе нет синтаксических ошибок.
Семантический анализ
Просто потому, что программа не содержит синтаксических ошибок, код еще не может считаться правильным. Рассмотрим предложение ниже.
Компилятор при анализе синтаксиса может решить, что в этом предложении нет синтаксических ошибок, потому что маркеры (слова) расположены в правильном порядке.
Теперь рассмотрим предложение ниже.
Предположим, что eat — правильный маркер в соответствии с грамматикой. Таким образом, предложение признается правильным на этапе лексического и синтаксического анализа, поскольку слова расположены в правильном порядке. Но в этом предложении нет никакого смысла — никто не может есть компиляторы.
Итак, согласно этапу семантического анализа, эта программа содержит ошибку. Мы называем эту разновидность ошибок семантическими ошибками. Взгляните на этот простой Java-код:
Здесь нет синтаксических ошибок. Все маркеры упорядочены правильно. Но на пятой строке int total = c + d — не имеет никакого значения, так как идентификаторы c и d не определены. Это и есть семантическая ошибка.
Генерация промежуточного кода
Любой компилятор может непосредственно генерировать машинный код из исходного. Так зачем же тогда нужна фаза генерации промежуточного кода?
Существуют различные типы машин. Таким образом, машинный код зависит от системы, а высокоуровневый исходный код — нет. Если компилятор непосредственно генерирует машинный код из исходного кода, то каждая машина нуждается в полной компиляции от фронта к бэку. Но когда компилятор генерирует промежуточный код ( промежуточное представление), он уже может генерировать машинный код для каждой машины с его помощью, без повторения лексического анализа и парсинга для каждой машины.
Существует два основных типа промежуточных представлений:
Существует также несколько способов представления промежуточного представления.
Оптимизация кода
Этап оптимизации кода выполняет две основные задачи: минимизация времени или минимизация ресурсов. Что все это значит? Когда пользователь пишет код, нет ничего, кроме инструкций. Когда процессор выполняет эти инструкции, требуют время и ресурсы памяти. Таким образом, целью этапа оптимизации кода становится сокращение времени выполнения и ресурсов, потребляемых программой. Оптимизатор кода всегда следует трем правилам:
Существует два способа оптимизации кода:
Машинно-независимая оптимизация принимает промежуточное представление относительно входных данных и не заботится ни о каких регистрах процессора и ячейках памяти. Она происходит после генерации промежуточного кода.
При машинно-зависимой оптимизации кода компилятор заботится о регистрах процессора, расположениях памяти и архитектуре машины. Она происходит после генерации машинного кода.
Генерация кода
Генерация кода — это последний этап процесса компиляции. Да, после может следовать машинно-зависимая оптимизация кода. Но мы можем рассматривать и то, и другое вместе как генерацию кода. На этом этапе компилятор генерирует машинно-зависимый код. Генератор кода должен иметь представление о среде выполнения целевой машины и ее наборе команд.
На этом этапе компилятор выполняет несколько основных задач:
Итоговый машинный код, сгенерированный генератором кода, может быть выполнен на целевой машине. Именно так высокоуровневый исходный код, который мы пишем в нашем любимом редакторе кода, преобразуется в формат, который можно запустить на любой целевой машине.
В этой статье я предоставляю только краткое описание. Если вам хочется углубиться в эти концепции, к вашим услугам миллионы ресурсов в интернете.
Что такое компилятор
Если вы программист, то наверняка слышали слово “компилятор”. Но знаете ли вы, что это такое на самом деле? Вы когда-нибудь задумывались, что происходит под капотом, когда вы запускаете команду javac (если у вас код на Java)? Вы когда-нибудь хотели создать свой собственный язык программирования? — и просто заводили бесполезный репозиторий GitHub, где все равно есть только один readme.md, потому что вы даже не знаете, с чего начать. Я думаю, что начинать стоит с этого: узнать больше о компиляторе.
Итак, в этой статье мы разберёмся, что представляет собой компилятор. Если вы опытный программист, который знает про компилятор каждую мелочь, то извините, эта статья не для вас. Но если вы — тот самый парень из абзаца выше, то вперёд за мной, в кроличью нору. На протяжении статьи я буду обсуждать следующие подтемы:
Вступление
Компилятор — это не что иное, как переводчик исходного кода.
Задача компилятора — перевести исходный код с одного языка на другой. Это означает, что если вы скормите компилятору исходный код Java, то сможете получить исходный код Python (не самый лучший пример, просто для понимания сути. На самом деле вы получите байт-код Java, который можно запустить на JVM). Для выполнения этого процесса у компилятора есть несколько взаимосвязанных компонентов.
Типы компиляторов
Мы можем классифицировать компиляторы по-разному. В этой статье я расскажу о двух способах классификации компиляторов, однако особенно углубляться в это не буду.
Классификация компиляторов в соответствии с этапами компиляции
Здесь мы рассмотрим количество этапов, которые проходит компилятор. Некоторые компиляторы непосредственно преобразуют высокоуровневый исходный код в машинный код, а некоторые — сначала преобразуют высокоуровневый исходный код в промежуточное представление перед преобразованием в машинный код.
Таким образом, в соответствии с этой классификацией можно выделить три типа компиляторов:
Если вы хотите узнать больше об этой классификации компиляторов, посмотрите сюда.
Классификация компиляторов в соответствии с исходным кодом и целевым кодом
Для преобразования исходного кода в целевой применяются разные подходы. Некоторые компиляторы преобразуют код на высокоуровневом языке в машинный. Некоторые компиляторы преобразуют с одного языка высокого уровня на другой язык высокого уровня. Таким образом, здесь выделяются следующие типы:
Архитектура компилятора
Когда компилятор компилирует (переводит) исходный код, он проходит несколько этапов:
Мы можем разделить все эти этапы на две фазы, примерно как фронтенд и бэкенд. Эти фазы включают в себя следующие этапы:
Фронтенд
Бэкенд
В следующем разделе я кратко опишу, что происходит на каждой фазе. Если вы не программируете компиляторы, то нормально иметь о них лишь поверхностное представление, но если вы хотите разработать компилятор сами, то вам стоит подробно изучить их работу.
Лексический анализ
Теперь вы знаете, что компилятор — это программа, которая преобразует исходный код в другой исходный код. Компилятор получает исходный код в виде файла. Этот файл содержит код в текстовом формате, но компилятор не может работать с этим текстом. Необходимо преобразовать этот текст в некоторый другой формат, понятный компилятору. Для этого компилятор разбивает текст по маркерам. Помните, что эти маркеры заранее определены в грамматике языка. Маркеры пригодятся на следующих этапах процесса компиляции:
KEYWORD, BRACKET, IDENTIFIER, OPERATOR, NUMBER на приведенной выше диаграмме — это и есть маркеры. Компилятор использует лексический анализ для идентификации маркеров, и если он получает маркер, который не определен заранее в грамматике языка, то это будет считаться ошибкой.
Синтаксический анализ (парсинг)
На этом этапе компилятор проверяет, расположены ли идентифицированные ранее маркеры в правильном порядке. Для этого в каждом языке есть набор правил, называемый грамматикой. Во-первых, компилятор пытается построить структуру данных — дерево синтаксического анализа. Если компилятор смог успешно построить дерево синтаксического анализа в соответствии с заранее определенными правилами грамматики, то в исходном коде нет синтаксических ошибок. В противном случае возникают ошибки и компилятор их покажет.
Здесь мы сначала определили грамматику. Затем компилятор пытается построить дерево синтаксического анализа для исходного кода 2 + 3 * 3. В этом случае компилятору удается построить дерево синтаксического анализа (с правой стороны) в соответствии с грамматикой, следовательно в этой программе нет синтаксических ошибок.
Семантический анализ
Просто потому, что программа не содержит синтаксических ошибок, код еще не может считаться правильным. Рассмотрим предложение ниже.
I love compilers
Компилятор при анализе синтаксиса может решить, что в этом предложении нет синтаксических ошибок, потому что маркеры (слова) расположены в правильном порядке.
Теперь рассмотрим предложение ниже.
I eat compilers
Предположим, что eat — правильный маркер в соответствии с грамматикой. Таким образом, предложение признается правильным на этапе лексического и синтаксического анализа, поскольку слова расположены в правильном порядке. Но в этом предложении нет никакого смысла — никто не может есть компиляторы.
Итак, согласно этапу семантического анализа, эта программа содержит ошибку. Мы называем эту разновидность ошибок семантическими ошибками. Взгляните на этот простой Java-код:
Здесь нет синтаксических ошибок. Все маркеры упорядочены правильно. Но на пятой строке int total = c + d — не имеет никакого значения, так как идентификаторы c и d не определены. Это и есть семантическая ошибка.
Генерация промежуточного кода
Любой компилятор может непосредственно генерировать машинный код из исходного. Так зачем же тогда нужна фаза генерации промежуточного кода?
Существуют различные типы машин. Таким образом, машинный код зависит от системы, а высокоуровневый исходный код — нет. Если компилятор непосредственно генерирует машинный код из исходного кода, то каждая машина нуждается в полной компиляции от фронта к бэку. Но когда компилятор генерирует промежуточный код (промежуточное представление), он уже может генерировать машинный код для каждой машины с его помощью, без повторения лексического анализа и парсинга для каждой машины.
Существует два основных типа промежуточных представлений:
Существует также несколько способов представления промежуточного представления.
Оптимизация кода
Этап оптимизации кода выполняет две основные задачи: минимизация времени или минимизация ресурсов. Что все это значит? Когда пользователь пишет код, нет ничего, кроме инструкций. Когда процессор выполняет эти инструкции, требуют время и ресурсы памяти. Таким образом, целью этапа оптимизации кода становится сокращение времени выполнения и ресурсов, потребляемых программой. Оптимизатор кода всегда следует трем правилам:
Существует два способа оптимизации кода:
Машинно-независимая оптимизация принимает промежуточное представление относительно входных данных и не заботится ни о каких регистрах процессора и ячейках памяти. Она происходит после генерации промежуточного кода.
При машинно-зависимой оптимизации кода компилятор заботится о регистрах процессора, расположениях памяти и архитектуре машины. Она происходит после генерации машинного кода.
Генерация кода
Генерация кода — это последний этап процесса компиляции. Да, после может следовать машинно-зависимая оптимизация кода. Но мы можем рассматривать и то, и другое вместе как генерацию кода. На этом этапе компилятор генерирует машинно-зависимый код. Генератор кода должен иметь представление о среде выполнения целевой машины и ее наборе команд.
На этом этапе компилятор выполняет несколько основных задач:
Итоговый машинный код, сгенерированный генератором кода, может быть выполнен на целевой машине. Именно так высокоуровневый исходный код, который мы пишем в нашем любимом редакторе кода, преобразуется в формат, который можно запустить на любой целевой машине.
В этой статье я предоставляю только краткое описание. Если вам хочется углубиться в эти концепции, к вашим услугам миллионы ресурсов в интернете.
Война с компилятором и собой: об оптимизациях вещественной арифметики на Эльбрусе
Недавно в процессе выполнения учебного задания мне потребовалось реализовать метод конечных разностей для нахождения приближённого решения краевой задачи. По сути, я впервые столкнулся с вычислениями с плавающей точкой и не мог не попробовать запустить свою программу на Эльбрусе, зная о его больших возможностях и заточенности под вычисления такого рода. Хотите удивиться? Отправляйтесь со мной в увлекательное путешествие!
Вкратце о математике
Для понимания происходящего математическая постановка задачи не является принципиально важной, так что её подробный разбор я позволю себе пропустить и ограничусь коротким описанием.
Итак, рассматривается дифференциальное уравнение Пуассона в прямоугольной области [0; 4] x [0; 3]:
Для данного уравнения рассматривается краевая задача, причём на каждом отрезке границы заданы граничные условия третьего типа:
где 
— единичная внешняя нормаль к границе.
Решение 
будем искать с помощью разностной схемы, которая может быть представлена в виде конечно-разностной операторной задачи
. Вычисления представляют из себя итерационный метод, на каждом шаге 
вычисляется новое приближение сеточной функции 
, где невязка 
, а итерационный параметр
Для проверки условия остановки вычисляется норма разности между новым и старым приближением. За более подробным описанием отправляю читателя к профильной литературе, например, книге А.А. Самарского [1].
В результате основные вычисления на каждом шаге представляют из себя несколько запусков пары вложенных циклов с классической характерной структурой: несколько чтений данных из матриц, арифметические операции и запись в выходную матрицу и/или накопление результата в промежуточной переменной. С производительностью исполнения этих циклов мы и будем разбираться. Вот так выглядит один из них:
Стоит отметить, что постановка учебной задачи подразумевает реализацию параллельной MPI+OpenMP программы, а также (при желании) дополнение программы MPI+CUDA реализацией. Необходимость разбивки области вычислений на домены вносит небольшую специфику в организацию программы, которую я решил здесь сохранить, несмотря на то, что статья посвящена только оптимизации последовательных вычислений и не касается вопросов распараллеливания на несколько процессов.
Дедлайн был вчера: самая обычная программа
За основу для исследований возьмём реализацию, которую легко может написать студент для выполнения учебной задачи: она не самая шустрая, но укладывается в ограничение по времени работы и удовлетворяет требуемым свойствам. Примерно такой же вид будет у программы, которую писали без оглядки на производительность вычислений, ведь сложно думать об оптимизациях, когда время поджимает, а размеры данных в задаче не велики или её надо запустить всего лишь раз. Признаюсь, я сразу писал не так и мне пришлось изрядно подпортить свою программу, чтобы продемонстрировать распространённые проблемы.
Полная реализация лежит на github [3]. Основные шаги, проделанные в статье, можно отследить по истории коммитов. Например, вот начальная версия.
Для тестовых замеров будем смотреть на время выполнения 1000 шагов итерационного метода на одном ядре процессора на сетке размером 1000×1000. За эффектом от оптимизаций будем следить на трёх платформах:
«целевой вычислительный кластер» — IBM POWER8 @ 4.0 ГГц и компилятор IBM XL C/C++ 13.1.6, базовые флаги оптимизации «-O5» (именно на таких процессорах требовалось запускать задачу; с удовольствием бы взял более новую систему, но доступа к свежим процессорам IBM у меня нет);
Итак, для тестов на Эльбрусе мы взяли наиболее производительный на данный момент процессор (инженерные образцы 6 поколения архитектуры не рассматриваем). У данного процессора есть аппаратная поддержка циклов, векторные регистры, возможности программной конвейеризации циклов, механизм подкачки массивов (APB) и вообще 6 «двухэтажных» АЛУ для вычислений с плавающей точкой, а мы взяли достаточно свежий компилятор и хорошие опции оптимизации. Несмотря на то, что для векторизации требуется соблюдение выравнивания данных, мы надеемся получить хороший результат.
Смотрим на результаты запуска и немного огорчаемся: Эльбрус отстаёт в 5-16 раз от Intel и IBM, впрочем, последние тоже не радуют скоростью. Здесь можно отправиться читать Руководство по эффективному программированию на платформе «Эльбрус» [2], а я просто воспользуюсь опытом, полученным при реализации криптографических примитивов.
И всё-таки линейкой по пальцам: подстановка «горячих» функций компилятором
Давайте просто посмотрим, как изменится время выполнения программы, если перенести определения функций q(x, y) и F(x, y) из отдельного файла (куда они могли попасть из соображений удобства) поближе к месту их вызова.
№1 — возможен inline
Примечательно, что на Эльбрусе, который имеет фиксированные и относительно большие штрафы за вызов функций, ускорение составляет 2.2 раза, а на Intel и IBM — 2.9 и 1.5 раза, соответственно. Так что на предсказатель переходов и внеочередное исполнение надейся, а сам не плошай.
Удар ниже пояса: правильный тип для счётчика цикла
Так вышло, что использовать сейчас в качестве счётчика цикла на Эльбрусе любой тип, существенно отличающийся от long — крайне неудачная идея. Связано это с тем, что компилятору необходимо следовать стандарту языка Си, а также с рядом особенностей в реализации компилятора.
В Руководстве нет подробных комментариев, только сказано, что рекомендуется использовать тип long (знаковый). Наверное, идеологически более правильно было бы рекомендовать ssize_t, но тут надо уточнить наличие определения ssize_t на других платформах. Да и с точки зрения компилятора конкретно на Эльбрусе отличий нет: это всё знаковый 64-битный тип.
Что ж, заменяем все границы и счётчики на ssize_t (определение через my_int для удобства экспериментов) и получаем ускорение в 5.4 раза: на 1000 итераций теперь требуется 18.8 секунд вместо 102. В зависимости от ряда факторов, ускорение от подобной замены может быть как почти незаметным, так и более весомым.
Так чем плохи другие типы? Для успешного применения механизма подкачки массивов APB необходимо гарантировать линейность изменения адресов элементов массива в цикле. К сожалению, это сразу отрезает возможность эффективного использования беззнакового типа: в нём допустимо переполнение, а значит на этапе компиляции невозможно гарантировать условие i + 1 > i. Так что привычный многим беззнаковый size_t отпадает. Хотя конкретно в данном примере size_t немного выигрывает, при дальнейших оптимизациях, как правило, проявляется небольшая просадка времени выполнения на беззнаковом типе. Впрочем, разница не так велика и можно продолжать спокойно использовать size_t.
А у меня всё в int, что я делаю не так? Это пример ситуации, когда формально проблемы нет, но есть некоторые сложности в реализации компилятора. Оптимизации применяются на разных стадиях работы компилятора и не всегда успешно согласуются друг с другом. В нашем случае компилятор на более раннем этапе видит цикл и расширяет счётчик до естественного для процессора 64-битного типа. Затем при попытке применить APB внутри цикла происходит вычисление смещения с использованием другой переменной типа int — run_config->domain_n. Получается несогласованность типов переменных, необходимо преобразование, что и приводит к вопиющему снижению производительности. Интересно, что можно вынести из внутреннего цикла чтение domain_n в локальную int переменную и тоже получить ускорение, так как в этом случае расширение переменной до 64 бит происходит в более ранней фазе компиляции.
Просадка производительности с типом int на этом примере была признана недоработкой компилятора, так что в светлом будущем такого сюрприза не будет. Пока же можно дать простую рекомендацию: при возможности, основные переменные лучше дублировать в виде локальных — это даёт компилятору больше информации о независимости данных и простор для оптимизаций.
Наконец, таблица с замерами этого раздела. Хотя на Intel и IBM лучший результат показывает тип int, мы остановимся на ssize_t, чтобы не плодить платформозависимых изменений.
№1 + локальные int переменные
№1 + size_t счётчики
№2 — ssize_t счётчики
Галопом по Европам: несколько алгоритмических оптимизаций
Этот раздел посвящён традиционным оптимизациям, которые приходят с опытом и обычно дают положительный эффект.
Во-первых, это предвычисления значений функций q(x, y) и F(x, y). На протяжении всего итерационного процесса они не меняются, так что нет смысла тратить время на лишнюю арифметику, тем более, эти функции на практике могут быть более сложными, чем в рассматриваемом примере. Вообще говоря, может оказаться, что считать эти функции будет быстрее, чем загружать значения из памяти, но я не уверен, что такое поведение сохранится после применения дальнейших оптимизаций.
Во-вторых, это уменьшение количества проходов по массиву. В данном случае очевидно, что при вычислении итерационного параметра можно совместить вычисление скалярного произведения для числителя и нормы для знаменателя. Чуть менее заметно второе место: вычисление текущего значения итерационной ошибки можно делать вместе с обновлением сеточной функции. Заметим, что полагаться на компилятор здесь не получается, так как циклы попадают в разные функции, вызываемые из другой единицы трансляции.
В-третьих, это обмен указателей вместо копирования матрицы для перехода к новой итерации. Копирование матрицы вместо обмена указателей увеличивает время работы программы на всех рассматриваемых платформах на 3-8%.
В сумме указанные оптимизации дают ускорение на всех платформах от нескольких процентов до нескольких разов. Заметно выбивается Intel, на котором проявляется замедление при переходе к предвычислениям функций. Это место неплохо бы происследовать, но мы пока удовлетворимся хорошим ускорением на Эльбрусе и IBM.
+ предвычисления q, F
+ меньше проходов по массиву
+ отказ от memcpy — №3
Панки грязи не боятся: читаем на языке ассемблера
Возьмём, например, последний вложенный цикл (из функции update_w_calc_partial_error). Так как компилятор делает ряд оптимизаций по конвейеризации циклов, расщеплению по условиям и создаёт участки компенсирующего кода, то нас прежде всего интересуют вхождения нашей строки в широкие команды (ШК) с меткой loop_mode. Таких оказывается 2, второй выглядит получше, но начнём с первого:
В этом отдельном куске только арифметика с выдерживанием задержек от инструкций, так что вернёмся к анализу первой части. Замечаем, что загрузки из памяти делаются инструкцией ldd с тегами mas=0x4 и mas=0x3. Ага, замечательно, это у нас применился динамический механизм разрыва зависимостей с использованием аппаратной таблицы DAM (Memory Access Disambiguator). Секундочку.
Соблюдаем социальную дистанцию: разрыв зависимостей
При реализации подобных численных методов (да и вообще при решении многих других задач) обычно удобно соблюдать простое правило: участки памяти по разным указателям не пересекаются. В действительности, при написании функций я уже держал эту информацию в голове и полагался на независимость указателей. Только вот почему бы не рассказать об этом компилятору, раз мы обладаем такой информацией?
О необходимости разрыва зависимостей очень легко забыть, но нельзя недооценивать важность этой информации для эффективной оптимизации. В случае суперскалярных процессоров эффект может быть заметен не всегда, но он тоже присутствует, как будет видно из замеров. Пожалуй, основное проблемное место — это возможности автовекторизации. Действительно, как можно считать одновременно 2 соседние итерации цикла с помощью векторных регистров, если нет уверенности, что результат следующей итерации не зависит от записи на текущей?
В случае Эльбруса проявляется ещё и другая особенность: из-за статического планирования без информации о независимости итераций мы не можем начать исполнять следующую итерацию до окончания текущей. Это сразу лишает нас важнейшего способа быстрого исполнения циклов в условиях статического планирования — программной конвейеризации цикла.
В lcc 1.25 впервые появилась поддержка прагмы ivdep, предназначенной для игнорирования возможных зависимостей в цикле. Можно попробовать воспользоваться ею, но я предпочитаю вариант с копированием нужных указателей и явным добавлением модификатора restrict. На мой взгляд, такой вариант самый прозрачный и даже немного упрощает код программы. Вот так, например, будет выглядеть начало одной из 3 подправленных функций:
В результате небольшой модификации мы добились ускорения на 33-80% на всех платформах. Подчеркну, что наша оптимизация является общей, а не специфической для Эльбруса. Более того, наиболее выраженный эффект от её применения наблюдается на IBM.