Eigen: как это работает: библиотека, которая умнее компилятора
Содержание:
1. Проект Eigen;
2. Документация и сторонние модули;
3.Как это работает: библиотека, которая умнее компилятора (Вы читаете данный раздел).
Перед тем, как перейти непосредственно к коду, нужно сделать отступление и объяснить, как Eigen умудряется генерировать код, сравнимый по скорости с написанным вручную в оптимизированных под конкретное «железо» библиотеках BLAS и LAPACK.
Любимое упражнение в учебниках по С++ - это создание класса, инкапсулирующего векторы и матрицы. Таких классов созданы сотни, но все они имеют крайне низкую производительность и никогда не используются для серьезных задач. Компилятор С++, в отличие от Fortran, даже не подозревает, что векторы и матрицы надо обрабатывать поэлементно. В результате, в сумме матриц:
сначала будет вычислена правая часть и присвоена временному объекту. Затем временный объект будет скопирован в mat1 и разрушен. Ясно, что вызов конструктора и деструктора временного объекта и копирование данных совершенно излишни.
Оказывается, что компилятору можно помочь, сделав за него часть работы с помощью метапрограммирования и шаблонов выражений (expression templates). Классы, использующие шаблоны выражений, преобразуют порядок действий в выражениях путем рекурсивной подстановки шаблонов на этапе компиляции.
Скажем, сложение объектов обрабатывается перегруженным оператором «+», который сам по себе ничего не делает с данными, а возвращает особый шаблонный класс «операция сложения».
Этот класс в свою очередь имеет перегруженные операторы и может участвовать в более сложных выражениях и т.п. На выходе получается абстрактное синтаксическое дерево правой части исходного выражения в виде шаблонных объектов, известных на стадии компиляции. Это дерево «раскручивается» в реальный код только при срабатывании оператора присваивания (обработке левой части выражения), поэтому говорят, что шаблоны выражений являются «ленивыми» (lazy).
Дерево шаблонов содержит только ссылки на реальные массивы данных и порядок их обработки, а оператор присваивания пробегает массивы поэлементно в цикле и формирует результирующий массив. По сути шаблоны выражений сами компилируют сложную формулу в некое промежуточное представление и выдают «глупому» компилятору «полупереваренный» код в виде явных циклов, которые уже без проблем компилируются в оптимальный машинный код.
Раз уж мы делаем за компилятор половину работы, то можно помочь ему и с оптимизацией. Современные процессоры оказываются гораздо изощрённее, чем предполагают и программист, и компилятор. Например, такой код кажется оптимальным, и улучшить в нем вроде бы нечего:
Тем не менее, он использует лишь малую долю вычислительной мощи процессора! Дело в том, что современные процессоры имеют специальные наборы инструкций (Intel SSE, ARM NEON) для обработки данных пакетами по 128 бит. Это 4 числа типа float, т.е. процессор может за один такт «прожевать» сразу 4 числа (это называют векторизацией). Обрабатывая наш код, компилятор последовательно перебирает элементы массива по 32 бита (размер типа float), а остальные 96 бит числового конвейера никак не используются. Чтобы включить векторизацию и загрузить числовой конвейер на все 100%, нужно, во-первых, расположить элементы массивов с 128-битным выравниванием, а во-вторых, вручную вызывать в цикле низкоуровневые ассемблерные SSE-инструкции для пакетов из 4 элементов массива.
Компилятор Fortran сам умеет векторизовать операции с массивами, а библиотеки BLAS и LAPACK либо используют возможности Fortran, либо содержат ассемблерный код, оптимизированный под конкретную процессорную архитектуру. В С++ все нужно делать вручную, а ассемблер - это совсем не то, с чем хочет работать современный прикладной программист...
К счастью, Eigen содержит нужные ассемблерные вставки для разных типов процессоров и вызывает их внутри шаблонов выражений. Благодаря этому, операции с объектами Eigen векторизуются и используют всю вычислительную мощность процессора.
Нужно сказать, что векторизация происходит в пределах одного ядра процессора. Eigen не распараллеливает вычисления по разным ядрам, оставляя программисту право использовать многопоточность по своему усмотрению.
Если вы до конца не поняли, как все это работает, то знайте, что не одиноки. Детали реализации шаблонов выражений крайне сложны - это высший пилотаж программирования на С++. Хорошее представление о сложности реального кода дает пример из документации Eigen http://eigen.tuxfamily.org/dox/TopicInsideEigenExample.html, описывающий, что происходит «под капотом».
К счастью, программисту совершенно не обязательно разбираться в этих деталях - внешний API у Eigen чрезвычайно прост. В следующей части статьи я приведу примеры кода и опишу специфику работы с библиотекой.
Eigen достаточно часто обновляется, так что, если Вам необходим высокоскоростной мобильный интернет в Швейцарии (http://cellhire.ru/ru/business/Switzerland_USB_modem_rental.html) для поддержания актуальной версии библиотеки, то стоит подобрать хорошего оператора. Ну а я Вам, в свою очередь, советую остановить свой выбор на Cellhire LLC, который предлагает самые гибкие тарифные планы!
1. Проект Eigen;
2. Документация и сторонние модули;
3.
Перед тем, как перейти непосредственно к коду, нужно сделать отступление и объяснить, как Eigen умудряется генерировать код, сравнимый по скорости с написанным вручную в оптимизированных под конкретное «железо» библиотеках BLAS и LAPACK.
Любимое упражнение в учебниках по С++ - это создание класса, инкапсулирующего векторы и матрицы. Таких классов созданы сотни, но все они имеют крайне низкую производительность и никогда не используются для серьезных задач. Компилятор С++, в отличие от Fortran, даже не подозревает, что векторы и матрицы надо обрабатывать поэлементно. В результате, в сумме матриц:
matl = mat2 + mat3
сначала будет вычислена правая часть и присвоена временному объекту. Затем временный объект будет скопирован в mat1 и разрушен. Ясно, что вызов конструктора и деструктора временного объекта и копирование данных совершенно излишни.
Оказывается, что компилятору можно помочь, сделав за него часть работы с помощью метапрограммирования и шаблонов выражений (expression templates). Классы, использующие шаблоны выражений, преобразуют порядок действий в выражениях путем рекурсивной подстановки шаблонов на этапе компиляции.
Скажем, сложение объектов обрабатывается перегруженным оператором «+», который сам по себе ничего не делает с данными, а возвращает особый шаблонный класс «операция сложения».
Этот класс в свою очередь имеет перегруженные операторы и может участвовать в более сложных выражениях и т.п. На выходе получается абстрактное синтаксическое дерево правой части исходного выражения в виде шаблонных объектов, известных на стадии компиляции. Это дерево «раскручивается» в реальный код только при срабатывании оператора присваивания (обработке левой части выражения), поэтому говорят, что шаблоны выражений являются «ленивыми» (lazy).
Дерево шаблонов содержит только ссылки на реальные массивы данных и порядок их обработки, а оператор присваивания пробегает массивы поэлементно в цикле и формирует результирующий массив. По сути шаблоны выражений сами компилируют сложную формулу в некое промежуточное представление и выдают «глупому» компилятору «полупереваренный» код в виде явных циклов, которые уже без проблем компилируются в оптимальный машинный код.
Раз уж мы делаем за компилятор половину работы, то можно помочь ему и с оптимизацией. Современные процессоры оказываются гораздо изощрённее, чем предполагают и программист, и компилятор. Например, такой код кажется оптимальным, и улучшить в нем вроде бы нечего:
std::vector
for (int i=0; i
for (int i=0; i
Тем не менее, он использует лишь малую долю вычислительной мощи процессора! Дело в том, что современные процессоры имеют специальные наборы инструкций (Intel SSE, ARM NEON) для обработки данных пакетами по 128 бит. Это 4 числа типа float, т.е. процессор может за один такт «прожевать» сразу 4 числа (это называют векторизацией). Обрабатывая наш код, компилятор последовательно перебирает элементы массива по 32 бита (размер типа float), а остальные 96 бит числового конвейера никак не используются. Чтобы включить векторизацию и загрузить числовой конвейер на все 100%, нужно, во-первых, расположить элементы массивов с 128-битным выравниванием, а во-вторых, вручную вызывать в цикле низкоуровневые ассемблерные SSE-инструкции для пакетов из 4 элементов массива.
Компилятор Fortran сам умеет векторизовать операции с массивами, а библиотеки BLAS и LAPACK либо используют возможности Fortran, либо содержат ассемблерный код, оптимизированный под конкретную процессорную архитектуру. В С++ все нужно делать вручную, а ассемблер - это совсем не то, с чем хочет работать современный прикладной программист...
К счастью, Eigen содержит нужные ассемблерные вставки для разных типов процессоров и вызывает их внутри шаблонов выражений. Благодаря этому, операции с объектами Eigen векторизуются и используют всю вычислительную мощность процессора.
Нужно сказать, что векторизация происходит в пределах одного ядра процессора. Eigen не распараллеливает вычисления по разным ядрам, оставляя программисту право использовать многопоточность по своему усмотрению.
Если вы до конца не поняли, как все это работает, то знайте, что не одиноки. Детали реализации шаблонов выражений крайне сложны - это высший пилотаж программирования на С++. Хорошее представление о сложности реального кода дает пример из документации Eigen http://eigen.tuxfamily.org/dox/TopicInsideEigenExample.html, описывающий, что происходит «под капотом».
К счастью, программисту совершенно не обязательно разбираться в этих деталях - внешний API у Eigen чрезвычайно прост. В следующей части статьи я приведу примеры кода и опишу специфику работы с библиотекой.
Eigen достаточно часто обновляется, так что, если Вам необходим высокоскоростной мобильный интернет в Швейцарии (http://cellhire.ru/ru/business/Switzerland_USB_modem_rental.html) для поддержания актуальной версии библиотеки, то стоит подобрать хорошего оператора. Ну а я Вам, в свою очередь, советую остановить свой выбор на Cellhire LLC, который предлагает самые гибкие тарифные планы!
