Презумпция виновности программиста или почему компилятор иногда «тупит»

[EndUser]

«Первородный грех программы перед программистом в том, что она делает то, что он запрограммировал, а не то, что он имел в виду»
©утерян.

[halyavin]

А разве есть SSE инструкции, которые могут выполнить a[ind[i]] += b[i]?

[vikky13]

Для int -нет, есть для char (pshufb или _mm_shuffle_epi8 в виде интринсика) для а и ind с последующим сложением с b.
Хотя, можно изврат… исхитриться и для int с использованием pshufd, если сдвигами создать из ind[i] константу. Но не факт, что это будет достаточно быстро.

[halyavin]

Если n больше 8, то эти инструкции помочь не могут.

[vikky13]

Для восьми битных данных n>16, не восьми. А дальше — тоже помочь могут, но не по отдельности, а только вместе с головой :) Я недавно писала довольно эффективную выборку из таблицы 32 элементов, но это совсем не предел.

[andrei_an]

Конечно есть. Просто это будет неэффективно в смысле производительности, поэтому если в приведенном тесте поставить #pragma ivdep, то компилятор сообщит, что векторизация возможна, но неэфективна и придется добавить #pragma vector always, чтобы заставить компилятор делать векторизацию несмотря на его сомнения. Автовекторизатору придется потратить массу усилий на формирование векторов.

[halyavin]

Это и значит, что в SSE нет таких (scatter-gather) инструкций ;).

[andrei_an]

Вы правы. Векторы заполняются и выгружаются в память с использованием команд типа movss,movups,movlhps,unpcklps,psrldq.
Я так понимаю, что в AVX2 появились scatter-gather инструкции, но я пока не представляю, будет ли их использование в данном случае эффективнее скалярного кода.

[beeruser]

Ну и чтобы не обидеть поклонников C++ небольшой синтетический тест на C++.

Objects = (int*) malloc(nobjects*sizeof(int));

почему не new int[nobjects]?

[andrei_an]

Я, к сожалению, не эксперт в C++, поэтому могу эстетические тонкости не понимать. Компилятор, в основном, написан на C. А работа с оптимизациями сводится уже с работой с внутренним представлением. Поэтому прошу извинить, если несуразным примером затронул ваше чувство прекрасного :)

[beeruser]

malloc как минимум не вызывает конструкторы обьектов.

[firedragon]

Извините за дурацкий вопрос. А оптимизаторы под языки высокого уровня существуют? Грубо говоря асм это родной язык, С близок к нему. C#, Java сильно завязаны на виртуальную машину, но какие то рекомендации есть? Или чисто эмперически

[andrei_an]

В Интеле оптимизации работают на внутреннем представлении и наш оптимизирующий компилятор обслуживает Fortran, C, C++ фронтенды. Т.е. задача фронтендов конвертировать программу в это представление, после чего компилятор будет работать и его оптимизировать. Поэтому, чтобы обслужить любой язык нужно просто написать трансляцию в представление, которое понимает опт. компилятор.
Понятно, что есть функциональность специфическая для конкретного языка. Вот, например, процедура разрешения неоднозначности при работе с аргументами указателями будет работать по разному в C/C++ и Фортране из-за разницы в стандартах. В C/C++ в функцию могут приходить указатели на одну и ту-же память, а в Фортране это запрещено. Поэтому какие-то доработки в компиляторе для учета особенностей языка необходимо сделать.
В Java тоже делают оптимизации, но наверное, там серьезная специфика ведь в случае виртуальной машины все приходится делать «на лету», хотя принципы оптимизаций общие.

[cypok]

Замечу, что AOT компиляция Java возможна и при этом нет никакой особенной специфики виртуальной машины.

[andrei_an]

Я не занимаюсь оптимизацией Java, но у нас есть подразделение, которое этим занимается. Из общих соображений и каких-то обсуждений с ребятами из этой команды я вижу следующую разницу — оптимизирующий компилятор может потратить массу времени, делая различные виды анализа и оптимизаций. Анализ и оптимизации компилятора, в основном, статические, т.е. попытка угадать структуру входных данных плюс подстраховаться проверками времени выполнения. Есть использование динамической профилировки — но это отдельная песня. Java машина же пытается динамически оптимизировать код, который уже выполняется и может собирать и использовать какую-то информацию об этом выполнении, но наверное сильно ограничена во времени, которое может на это затратить. На мой взгляд, разница в подходах к оптимизации существенная.

[gribozavr]

Я ваши циклы разнёс по отдельным функциям и скормил LLVM. Вот что с вашими циклами сделал экспериментальный векторизатор (ну и остальные оптимизации):
1. заменён на memset
2. векторизован + хвост memset
3. выброшен за ненадобностью, так как b[10] он не инициализирует :)
4. не векторизирован
5. не векторизирован
6. векторизован
7. не векторизирован
8. векторизован
9. векторизован

[andrei_an]

Это приятно, что вы правильно готовитесь к году Змеи!
Мне довольно трудно прокомментировать ваши результаты, поскольку все же здесь есть масса деталей, которые могут на них влиять. Например, насколько я знаю, gcc уже сейчас использует ansi_alias по умолчанию. (Интел тоже вроде собирается это сделать). Как работает с этими правилами ваш экспериментальный векторизатор? Будет ли он векторизовать, например, 1 и 2 цикл, если вы ему явно укажете, что вы не выполняете правила ansi alias? Если да, то его можно обмануть, например так, a[x]=&gn.
С -Qansi_alias Интеловский компилятор тоже часть циклов успешно разруливает и векторизует.
Ну и Интеловскому компилятору есть еще куда расти. 6 и 7 цикл он мог бы распознать сделав некие предварительные манипуляции. Кстати говоря, на 6 цикл я уже создал дефект и он был реализован. Правда в продуктовых версиях этой правки еще нет.
Хочется, пользуясь случаем, поздравить всех с наступающим Новым Годом.

[gribozavr]

-fstrict-aliasing включен в Clang по умолчанию. Если его выключить -fno-strict-aliasing, то метаданные TBAA (type-based alias analysis) не будут сгенерированы и TBAA не сможет доказать что float *a и int gi не алиасят друг друга, соответственно векторизации не будет.