Спасибо за ваш комментарий.
Подстановка — одна из главных межпроцедурных оптимизаций (Inter-Procedural Optimization). Все скалярные и цикловые оптимизации страдают от наличия вызовов в коде. Векторизация циклов с вызовами не выполняется (кроме случаев векторных функций), Для того, чтобы протянуть в вызываемую функцию константный аргумент нужно выполнять клонирование функций, что не всегда является возможным. Можно провести массу примеров, когда подстановка улучшает производительность. Поэтому не понял вашу первую мысль.
От PGO достаточно много толку. Некоторые оптимизации выполняются только с PGO, например, трансформации данных. Благодаря примерному представлению о размерах массивов эффективней выполняются цикловые оптимизации. Мой эксперимент показывает, что с PGO эффективней выполняются подстановки. Т.е. PGO мало используется потому, что не все программисты представляют какие PGO решает задачи + не все заинтересованы в получении высокой производительности. Смысл вашего посыла о порядке условий от меня ускользнул. Какой порядок условий вы имеете в виду и почему от него перестала зависеть скорость выполнения программы?
Компиляторы и gcc и icc занимаются тем, что выносят в специальные области «холодный» код. Аналогом является вынос холодного кода в функции и запрет их подстановки. Мне кажется вы не поняли, о чем идет речь, поскольку непонятно, что вы имеете в виду под «убиранием фрейма вызова функции» в этом контексте.
Не совсем понятна мысль про то что архитектура компенсирует нехватку регистров. В x86 в случае нехватки регистров для размещения всех живых объектов на регистрах кодогенератор вставляет работу со стеком. Т.е. возникает register spilling и появляются дополнительные операции работы с памятью. Т.е. есть приложения, для которых 32-битные версии заметно проигрывают по производительности 64-битным именно из-за того что в 64 битных меньше работы со стеком (больше доступных регистров). Понятно, что «железо» не может решить эту проблему, хотя она действительно кажется грузом совместимости.
Очень сильно.
Наверное, компилятор мог бы сам векторизовать такие случаи и использовать последовательный доступ к массиву А, но делать маскированные вычисления, т.е. через элемент. И это было бы красивее и выгоднее, разве только в реальных вычислениях такой доступ редко случается и тратить на такой изыск время разработчики не захотят.
Оценочный механизм icc не считает векторизацию выгодной. #pragma vector always помогает и векторизация выглядит вполне разумно. Возможно оценочный механизм не прав.
test.c(2): (col. 3) remark: LOOP WAS VECTORIZED
test.c(9): (col. 3) remark: LOOP WAS VECTORIZED
test.c(17): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient
Автовекторизатору не очень нравится конечный вариант. Взятие остатка от деления дорогущая операция, которую векторизация вряд ли будет в состоянии окупить.
Возможно, вы ошиблись в примере. Остаток от деления не участвует в вычислении индекса для массива A. Здесь у вас скалярное выражение с i. И автовекторизатору нужно скалярную переменную преобразовать в векторную. Автовекторизатор создаст вектор [i:i+N] и будет его векторно делить и получать векторный результат для остатка от деления. Причем, перед векторным циклом будет создан вектор [0:N] и каждый последующий будет вычисляться на каждой итерации сложением с вектором [N,..,N]. Наверное, для автовекторизатора это не сложно. Проблема именно в заполнении векторных регистров из памяти.
Тут проблема в непоследовательном доступе к массиву a. Из-за того, что i+=2 на первой итерации используется a[0], на второй a[2] и т.д. Поэтому считать данные из памяти за одну операцию не получается и приходится их записывать в регистр поэлементно. Поэтому с первым и вторым циклом векторизатору нужно напрягаться. В третьем цикле вы забыли про это и автовекторизатор смог справиться.
Кстати, во всяких вычислительных задачах, особенно на Фортране, часто встречаются вычисления, в которых часть массивов доступается поэлементно, а часть — нет. Но векторизация очень выгодна. Поэтому плохо, что непоследовательный доступ препятствует работе автовекторизатора gcc.
У меня сложилось несколько другое представление о степени воздействия NUMA на производительность приложения. При работе с вычислительными задачами мы сталкивались с двухразовым изменением производительности. Даже простое однопоточное приложение запущенное на вычислительных системах с NUMA показывает очень нестабильное поведение из-за того, что может перейти на вычислительное ядро другого сокета. Изменение производительности на 10-15 процентов довольно распространенная ситуация. И действительно, приходится использовать установку affinity чтобы получать более-менее стабильные цифры.
Ошибся. #pragma unroll (N) учитывается автовекторизатором. Т.е. можно эксперементировать и выбирать уровень развертки оптимальный для обрабатываемого векторизованного цикла. Но N — будет число итераций уже векторизованного цикла.
В нашем компиляторе есть оптимизация обратная развертке — свертка (reroll), но она почему-то здесь себя не проявила. Я посмотрел совсем простой пример — не работает.
Было бы интересно посмотреть, что сообщает компилятор о причинах, почему он не сделал векторизацию. (-Qvec_report3). Если цикл предварительно не свернуть, то наш автовекторизатор создает неэффективный код и заполняет векторные регистры поэлементно. Поэтому, на мой взгляд, #pragma simd — это ложная альтернатива для получения удовольствия от векторизации. Нужно выбирать — выгода от векторизации + развертка по умолчанию (ее делает сам автовекторизатор) или удовольствие от ручной развертки + неэффективной векторизации. Есть еще #pragma unroll (N), но у меня сложилось мнение, что для векторизованных циклов эта возможность не работает.
И много встречается таких примеров ручной развертки?
Это приятно, что вы правильно готовитесь к году Змеи!
Мне довольно трудно прокомментировать ваши результаты, поскольку все же здесь есть масса деталей, которые могут на них влиять. Например, насколько я знаю, gcc уже сейчас использует ansi_alias по умолчанию. (Интел тоже вроде собирается это сделать). Как работает с этими правилами ваш экспериментальный векторизатор? Будет ли он векторизовать, например, 1 и 2 цикл, если вы ему явно укажете, что вы не выполняете правила ansi alias? Если да, то его можно обмануть, например так, a[x]=&gn.
С -Qansi_alias Интеловский компилятор тоже часть циклов успешно разруливает и векторизует.
Ну и Интеловскому компилятору есть еще куда расти. 6 и 7 цикл он мог бы распознать сделав некие предварительные манипуляции. Кстати говоря, на 6 цикл я уже создал дефект и он был реализован. Правда в продуктовых версиях этой правки еще нет.
Хочется, пользуясь случаем, поздравить всех с наступающим Новым Годом.
Я не занимаюсь оптимизацией Java, но у нас есть подразделение, которое этим занимается. Из общих соображений и каких-то обсуждений с ребятами из этой команды я вижу следующую разницу — оптимизирующий компилятор может потратить массу времени, делая различные виды анализа и оптимизаций. Анализ и оптимизации компилятора, в основном, статические, т.е. попытка угадать структуру входных данных плюс подстраховаться проверками времени выполнения. Есть использование динамической профилировки — но это отдельная песня. Java машина же пытается динамически оптимизировать код, который уже выполняется и может собирать и использовать какую-то информацию об этом выполнении, но наверное сильно ограничена во времени, которое может на это затратить. На мой взгляд, разница в подходах к оптимизации существенная.
В Интеле оптимизации работают на внутреннем представлении и наш оптимизирующий компилятор обслуживает Fortran, C, C++ фронтенды. Т.е. задача фронтендов конвертировать программу в это представление, после чего компилятор будет работать и его оптимизировать. Поэтому, чтобы обслужить любой язык нужно просто написать трансляцию в представление, которое понимает опт. компилятор.
Понятно, что есть функциональность специфическая для конкретного языка. Вот, например, процедура разрешения неоднозначности при работе с аргументами указателями будет работать по разному в C/C++ и Фортране из-за разницы в стандартах. В C/C++ в функцию могут приходить указатели на одну и ту-же память, а в Фортране это запрещено. Поэтому какие-то доработки в компиляторе для учета особенностей языка необходимо сделать.
В Java тоже делают оптимизации, но наверное, там серьезная специфика ведь в случае виртуальной машины все приходится делать «на лету», хотя принципы оптимизаций общие.
Вы правы. Векторы заполняются и выгружаются в память с использованием команд типа movss,movups,movlhps,unpcklps,psrldq.
Я так понимаю, что в AVX2 появились scatter-gather инструкции, но я пока не представляю, будет ли их использование в данном случае эффективнее скалярного кода.
Я, к сожалению, не эксперт в C++, поэтому могу эстетические тонкости не понимать. Компилятор, в основном, написан на C. А работа с оптимизациями сводится уже с работой с внутренним представлением. Поэтому прошу извинить, если несуразным примером затронул ваше чувство прекрасного :)
Подстановка — одна из главных межпроцедурных оптимизаций (Inter-Procedural Optimization). Все скалярные и цикловые оптимизации страдают от наличия вызовов в коде. Векторизация циклов с вызовами не выполняется (кроме случаев векторных функций), Для того, чтобы протянуть в вызываемую функцию константный аргумент нужно выполнять клонирование функций, что не всегда является возможным. Можно провести массу примеров, когда подстановка улучшает производительность. Поэтому не понял вашу первую мысль.
От PGO достаточно много толку. Некоторые оптимизации выполняются только с PGO, например, трансформации данных. Благодаря примерному представлению о размерах массивов эффективней выполняются цикловые оптимизации. Мой эксперимент показывает, что с PGO эффективней выполняются подстановки. Т.е. PGO мало используется потому, что не все программисты представляют какие PGO решает задачи + не все заинтересованы в получении высокой производительности. Смысл вашего посыла о порядке условий от меня ускользнул. Какой порядок условий вы имеете в виду и почему от него перестала зависеть скорость выполнения программы?
Компиляторы и gcc и icc занимаются тем, что выносят в специальные области «холодный» код. Аналогом является вынос холодного кода в функции и запрет их подстановки. Мне кажется вы не поняли, о чем идет речь, поскольку непонятно, что вы имеете в виду под «убиранием фрейма вызова функции» в этом контексте.
Наверное, компилятор мог бы сам векторизовать такие случаи и использовать последовательный доступ к массиву А, но делать маскированные вычисления, т.е. через элемент. И это было бы красивее и выгоднее, разве только в реальных вычислениях такой доступ редко случается и тратить на такой изыск время разработчики не захотят.
test.c(2): (col. 3) remark: LOOP WAS VECTORIZED
test.c(9): (col. 3) remark: LOOP WAS VECTORIZED
test.c(17): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient
Автовекторизатору не очень нравится конечный вариант. Взятие остатка от деления дорогущая операция, которую векторизация вряд ли будет в состоянии окупить.
Кстати, во всяких вычислительных задачах, особенно на Фортране, часто встречаются вычисления, в которых часть массивов доступается поэлементно, а часть — нет. Но векторизация очень выгодна. Поэтому плохо, что непоследовательный доступ препятствует работе автовекторизатора gcc.
Было бы интересно посмотреть, что сообщает компилятор о причинах, почему он не сделал векторизацию. (-Qvec_report3). Если цикл предварительно не свернуть, то наш автовекторизатор создает неэффективный код и заполняет векторные регистры поэлементно. Поэтому, на мой взгляд, #pragma simd — это ложная альтернатива для получения удовольствия от векторизации. Нужно выбирать — выгода от векторизации + развертка по умолчанию (ее делает сам автовекторизатор) или удовольствие от ручной развертки + неэффективной векторизации. Есть еще #pragma unroll (N), но у меня сложилось мнение, что для векторизованных циклов эта возможность не работает.
И много встречается таких примеров ручной развертки?
Мне довольно трудно прокомментировать ваши результаты, поскольку все же здесь есть масса деталей, которые могут на них влиять. Например, насколько я знаю, gcc уже сейчас использует ansi_alias по умолчанию. (Интел тоже вроде собирается это сделать). Как работает с этими правилами ваш экспериментальный векторизатор? Будет ли он векторизовать, например, 1 и 2 цикл, если вы ему явно укажете, что вы не выполняете правила ansi alias? Если да, то его можно обмануть, например так, a[x]=&gn.
С -Qansi_alias Интеловский компилятор тоже часть циклов успешно разруливает и векторизует.
Ну и Интеловскому компилятору есть еще куда расти. 6 и 7 цикл он мог бы распознать сделав некие предварительные манипуляции. Кстати говоря, на 6 цикл я уже создал дефект и он был реализован. Правда в продуктовых версиях этой правки еще нет.
Хочется, пользуясь случаем, поздравить всех с наступающим Новым Годом.
Понятно, что есть функциональность специфическая для конкретного языка. Вот, например, процедура разрешения неоднозначности при работе с аргументами указателями будет работать по разному в C/C++ и Фортране из-за разницы в стандартах. В C/C++ в функцию могут приходить указатели на одну и ту-же память, а в Фортране это запрещено. Поэтому какие-то доработки в компиляторе для учета особенностей языка необходимо сделать.
В Java тоже делают оптимизации, но наверное, там серьезная специфика ведь в случае виртуальной машины все приходится делать «на лету», хотя принципы оптимизаций общие.
Я так понимаю, что в AVX2 появились scatter-gather инструкции, но я пока не представляю, будет ли их использование в данном случае эффективнее скалярного кода.