Как я могу кодировать Java, чтобы разрешить использование SSE и устранение проверки границ (или другие дополнительные оптимизации)?
Ситуация:
Я оптимизирую реализацию алгоритма сжатия LZF на чистой Java, которая включает в себя множество байтов [] и базовых математических методов для хеширования и сравнения. Производительность действительно имеет значение, потому что цель сжатия - снизить требования к вводу / выводу. Я не публикую код, потому что он еще не очищен и может быть сильно изменен.
Вопросы:
- Как я могу написать свой код, чтобы позволить его JIT-компилировать в форму, используя более быстрые операции SSE?
- Как я могу структурировать это так, чтобы компилятор мог легко устранить проверки границ массива?
- Существуют ли какие-либо широкие ссылки на относительную скорость определенных математических операций (сколько приращений / уменьшений требуется, чтобы равняться обычному сложению / вычитанию, насколько быстро происходит сдвиг или выбор доступа к массиву)?
- Как я могу работать над оптимизацией ветвления - лучше ли иметь множество условных операторов с короткими телами или несколько длинных или коротких с вложенными условиями?
- В текущей версии 1.6 JVM, сколько элементов должно быть скопировано, прежде чем System.arraycopy превзойдет цикл копирования?
Что я уже сделал:
Прежде чем меня атаковали за преждевременную оптимизацию: базовый алгоритм уже превосходен, но реализация Java меньше, чем 2/3 скорости эквивалентного C. Я уже заменил циклы копирования на System.arraycopy, работал над оптимизацией циклов и исключил необходимые операции.
Я интенсивно использую битовое перемешивание и упаковываю байты в целые для повышения производительности, а также сдвига и маскирования.
По юридическим причинам я не могу смотреть на реализации в подобных библиотеках, и существующие библиотеки имеют слишком ограничительные условия лицензии для использования.
Требования к ХОРОШЕМУ (принятому) ответу:
- Неприемлемые ответы: "это быстрее" без объяснения того, сколько И почему, ИЛИ не было протестировано с JIT-компилятором.
- Пограничные ответы: до Hotspot 1.4 ничего не тестировалось
- Основные ответы: предоставит общее правило и объяснение того, почему он быстрее на уровне компилятора и примерно насколько быстрее
- Хорошие ответы: включите пару примеров кода для демонстрации
- Отличные ответы: есть тесты с JRE 1.5 и 1.6
- ОТЛИЧНЫЙ ответ: кто-то, кто работал над компилятором HotSpot, и может полностью объяснить или ссылаться на условия для оптимизации, и насколько она обычно быстрее. Может включать код Java и пример кода сборки, сгенерированного HotSpot.
Кроме того: если у кого-то есть ссылки с подробным описанием оптимизации Hotspot и производительности ветвления, это приветствуется. Я знаю достаточно о байт-коде, чтобы сайт, анализирующий производительность на уровне байт-кода, а не на уровне исходного кода, был бы полезен.
(Изменить) Частичный ответ: Проверка границ:
Это взято из предоставленной ссылки на внутреннюю вики HotSpot по адресу: https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination
HotSpot устраняет проверки границ во всех циклах со следующими условиями:
- Массив является инвариантом цикла (не перераспределяется внутри цикла)
- Индексная переменная имеет постоянный шаг (увеличивается / уменьшается на постоянную величину, только в одном месте, если это возможно)
- Массив индексируется линейной функцией переменной.
Пример: int val = array[index*2 + 5]
ИЛИ ЖЕ: int val = array[index+9]
НЕ: int val = array[Math.min(var,index)+7]
Ранняя версия кода:
Это примерная версия. Не крадите его, потому что это неизданная версия кода для проекта базы данных H2. Окончательная версия будет с открытым исходным кодом. Это оптимизация кода здесь: H2 CompressLZF code
По логике это совпадает с версией разработки, но в ней используется цикл for(...) для пошагового ввода и цикл if/else для различной логики между литеральным и обратным ссылками. Это уменьшает доступ к массиву и проверки между режимами.
public int compressNewer(final byte[] in, final int inLen, final byte[] out, int outPos){
int inPos = 0;
// initialize the hash table
if (cachedHashTable == null) {
cachedHashTable = new int[HASH_SIZE];
} else {
System.arraycopy(EMPTY, 0, cachedHashTable, 0, HASH_SIZE);
}
int[] hashTab = cachedHashTable;
// number of literals in current run
int literals = 0;
int future = first(in, inPos);
final int endPos = inLen-4;
// Loop through data until all of it has been compressed
while (inPos < endPos) {
future = (future << 8) | in[inPos+2] & 255;
// hash = next(hash,in,inPos);
int off = hash(future);
// ref = possible index of matching group in data
int ref = hashTab[off];
hashTab[off] = inPos;
off = inPos - ref - 1; //dropped for speed
// has match if bytes at ref match bytes in future, etc
// note: using ref++ rather than ref+1, ref+2, etc is about 15% faster
boolean hasMatch = (ref > 0 && off <= MAX_OFF && (in[ref++] == (byte) (future >> 16) && in[ref++] == (byte)(future >> 8) && in[ref] == (byte)future));
ref -=2; // ...EVEN when I have to recover it
// write out literals, if max literals reached, OR has a match
if ((hasMatch && literals != 0) || (literals == MAX_LITERAL)) {
out[outPos++] = (byte) (literals - 1);
System.arraycopy(in, inPos - literals, out, outPos, literals);
outPos += literals;
literals = 0;
}
//literal copying split because this improved performance by 5%
if (hasMatch) { // grow match as much as possible
int maxLen = inLen - inPos - 2;
maxLen = maxLen > MAX_REF ? MAX_REF : maxLen;
int len = 3;
// grow match length as possible...
while (len < maxLen && in[ref + len] == in[inPos + len]) {
len++;
}
len -= 2;
// short matches write length to first byte, longer write to 2nd too
if (len < 7) {
out[outPos++] = (byte) ((off >> 8) + (len << 5));
} else {
out[outPos++] = (byte) ((off >> 8) + (7 << 5));
out[outPos++] = (byte) (len - 7);
}
out[outPos++] = (byte) off;
inPos += len;
//OPTIMIZATION: don't store hashtable entry for last byte of match and next byte
// rebuild neighborhood for hashing, but don't store location for this 3-byte group
// improves compress performance by ~10% or more, sacrificing ~2% compression...
future = ((in[inPos+1] & 255) << 16) | ((in[inPos + 2] & 255) << 8) | (in[inPos + 3] & 255);
inPos += 2;
} else { //grow literals
literals++;
inPos++;
}
}
// write out remaining literals
literals += inLen-inPos;
inPos = inLen-literals;
if(literals >= MAX_LITERAL){
out[outPos++] = (byte)(MAX_LITERAL-1);
System.arraycopy(in, inPos, out, outPos, MAX_LITERAL);
outPos += MAX_LITERAL;
inPos += MAX_LITERAL;
literals -= MAX_LITERAL;
}
if (literals != 0) {
out[outPos++] = (byte) (literals - 1);
System.arraycopy(in, inPos, out, outPos, literals);
outPos += literals;
}
return outPos;
}
Окончательное редактирование:
Я отметил лучший ответ, насколько это было принято, так как срок почти истек. Поскольку до принятия решения о размещении кода у меня ушло так много времени, я буду продолжать давать комментарии и отвечать на комментарии там, где это возможно. Извиняюсь, если код запутан: этот код представлен в разработке, а не отшлифован для фиксации.
4 ответа
Не полный ответ, у меня просто нет времени на подробные тесты, которые нужны вашему вопросу, но, надеюсь, полезные.
Знай своего врага
Вы нацелены на комбинацию JVM (по сути JIT) и базовой подсистемы CPU/Memory. Таким образом, "это быстрее на JVM X", вероятно, не будет действительным во всех случаях, когда вы переходите к более агрессивной оптимизации.
Если ваш целевой рынок / приложение будет в основном работать на определенной архитектуре, вам следует подумать о том, чтобы инвестировать средства в специфичные для него инструменты. * Если ваша производительность на x86 является критическим фактором, то VTune от Intel отлично подходит для углубленного анализа того типа анализа JIT, который вы описываете. * Различия между 64-битными и 32-битными JIT могут быть значительными, особенно на платформах x86, где могут меняться соглашения о вызовах и возможности регистрации очень разные.
Получить правильные инструменты
Вы, вероятно, захотите получить профилировщик выборки. Затраты на инструментарий (и связанный с этим удар по таким вещам, как встраивание, загрязнение кэша и инфляция размера кода) для ваших конкретных потребностей были бы слишком велики. Анализатор Intel VTune действительно можно использовать для Java, хотя интеграция не такая тесная, как у других.
Если вы используете Sun JVM и рады только зная, что делает последняя / самая лучшая версия, то варианты, доступные для исследования выходных данных JIT, значительны, если вы немного разбираетесь в сборке. В этой статье подробно описан интересный анализ с использованием этой функциональности.
Учитесь у других реализаций
История изменений истории изменений указывает на то, что предыдущая встроенная сборка была на самом деле контрпродуктивной и что предоставление компилятору полного контроля над выходом (с изменениями в коде, а не с директивами в сборке) дало лучшие результаты.
Некоторая специфика
Поскольку LZF в эффективной неуправляемой реализации на современном настольном компьютере CPUS в значительной степени ограничен пропускной способностью памяти (следовательно, он конкурирует со скоростью неоптимизированной memcpy), вам потребуется код, чтобы он полностью оставался в кеше 1-го уровня.
Таким образом, любые статические поля, которые вы не можете преобразовать в константы, должны быть помещены в один и тот же класс, поскольку эти значения часто помещаются в одну и ту же область памяти, посвященную виртуальным таблицам и метаданным, связанным с классами.
Следует избегать размещения объектов, которые не могут быть отслежены с помощью Escape Analysis (только в версии 1.6 и далее).
Код c активно использует развертывание цикла. Однако производительность этого на более старых (1.4 эпоха) виртуальных машинах сильно зависит от режима, в котором находится JVM. По-видимому, последние версии Sun JVM более агрессивны при встраивании и развертывании, особенно в режиме сервера.
Инструкции предварительной выборки, сгенерированные JIT, могут иметь значение для кода, подобного этому, который близок к памяти.
"Это идет прямо к нам"
Ваша цель движется и будет продолжать. Опять предыдущий опыт Марка Лемана:
размер HLOG по умолчанию теперь 15 (кэши процессора увеличились)
Даже незначительные обновления jvm могут повлечь за собой значительные изменения в компиляторе.
6544668 Не проверяйте операции с массивами, которые нельзя выровнять во время выполнения. 6536652 Реализация некоторых оптимизаций суперслов (SIMD). 6531696 не использует непосредственное 16-разрядное хранилище значений в памяти на процессорах Intel. 6468290 Деление и выделение вне eden для каждого процессора.
Капитан Очевидность
Мера, мера, мера. ЕСЛИ вы можете заставить свою библиотеку включать (в отдельном dll) простой и легкий для выполнения тест, который регистрирует соответствующую информацию (версия vm, процессор, ОС, параметры командной строки и т. Д.) И упрощает отправку обратно вам, вы получите увеличьте ваше покрытие, лучше всего вы покроете тех людей, которые его используют.
Что касается исключения проверки границ, я полагаю, что новый JDK уже будет включать улучшенный алгоритм, который устраняет его, когда это возможно. Это две основные статьи на эту тему:
- В. Михеев, С. Федосеев, В. Сухарев, Н. Липский. 2002Эффективное улучшение контроля версий в Java. Ссылка Эта статья написана ребятами из Excelsior, которые внедрили эту технику в свою Jet JVM.
- Вюртингер, Томас, Кристиан Виммер и Ханспетер Мёссенбёк. 2007. Устранение проверки границ массива для клиентского компилятора HotSpot. PPPJ. Ссылка Слегка основываясь на приведенном выше документе, это реализация, которая, я думаю, будет включена в следующий JDK. Достигнутые ускорения также представлены.
Также есть эта запись в блоге, которая поверхностно обсуждает одну из статей, а также представляет некоторые результаты сравнительного анализа не только для массивов, но и для арифметики в новом JDK. Комментарии к записи в блоге также очень интересны, так как авторы вышеупомянутых работ представляют некоторые очень интересные комментарии и обсуждают аргументы. Кроме того, есть некоторые ссылки на другие подобные сообщения в блоге на эту тему.
Надеюсь, поможет.
Маловероятно, что вам нужно сильно помогать JIT-компилятору в оптимизации простого алгоритма обработки чисел, такого как LZW. ShuggyCoUk упомянул об этом, но я думаю, что это заслуживает дополнительного внимания:
Кэш-дружественность вашего кода будет большим фактором.
Вы должны уменьшить размер своего рабочего режима и максимально улучшить доступ к данным. Вы упоминаете "упаковку байтов в целые числа для производительности". Это похоже на использование int для хранения байтовых значений, чтобы выровнять их по словам. Не делай этого! Увеличенный размер набора данных перевесит любой выигрыш (однажды я преобразовал некоторый код обработки числа ECC из int[] в byte[] и получил ускорение в 2 раза).
Если есть вероятность, что вы этого не знаете: если вам нужно обрабатывать некоторые данные как байты и целые, вам не нужно сдвигать и |-мазывать их - используйте ByteBuffer.asIntBuffer() и связанные методы.
В текущей версии 1.6 JVM, сколько элементов должно быть скопировано, прежде чем System.arraycopy превзойдет цикл копирования?
Лучше сделайте тест самостоятельно. Когда я делал это в то время, когда в Java 1,3 раза, это было где-то около 2000 элементов.
Пока много ответов, но есть несколько дополнительных вещей:
- Мера, мера, мера. Столько, сколько большинство Java-разработчиков предостерегают от микробанчмаркинга, обязательно сравнивайте производительность между изменениями. Оптимизации, которые не приводят к измеримым улучшениям, как правило, не стоит оставлять (конечно, иногда это комбинация вещей, и это становится сложнее)
- Тесные циклы имеют значение для Java так же, как и для C (и то же самое с распределением переменных - хотя вы не управляете им напрямую, HotSpot в конечном итоге должен будет это сделать). Мне удается практически удвоить скорость декодирования UTF-8, переставив тугой цикл для обработки однобайтового регистра (7-битный ASCII) в качестве жесткого (эр) внутреннего цикла, оставив другие случаи вне.
- Не стоит недооценивать затраты на выделение и / или очистку больших массивов - если вы хотите, чтобы кодирование / декодирование lzf было более быстрым для небольших / средних кусков (не только мегабайтного размера), имейте в виду, что ВСЕ выделения байтов []/int[] несколько дорогостоящие; не из-за GC, а потому что JVM ДОЛЖЕН очистить пространство.
Реализация H2 также была немного оптимизирована (например: она больше не очищает хеш-массив, это часто имеет смысл); и я на самом деле помог изменить его для использования в другом проекте Java. Мой вклад в основном сводился к тому, чтобы изменить его, чтобы он был более оптимальным для не потокового случая, но это не касалось узких циклов кодирования / декодирования.