Ситуация:
Я оптимизирую реализацию pure-java алгоритма сжатия LZF, который включает в себя много байтов [] доступа и базовую интегральную математику для хэширования и сравнения. Производительность действительно имеет значение, поскольку цель сжатия заключается в сокращении требований ввода-вывода. Я не отправляю код, потому что он еще не очищен и может быть сильно реструктурирован.
Вопросы:
- Как я могу написать свой код, чтобы он мог скомпилировать JIT в форму, используя более быстрые операции SSE?
- Как я могу его структурировать, чтобы компилятор мог легко устранить проверки границ массива?
- Существуют ли какие-либо широкие ссылки относительно относительной скорости конкретных математических операций (сколько приращений/декрементов требуется для равномерного добавления/вычитания, насколько быстро сдвиг или доступ к массиву)?
- Как я могу работать над оптимизацией ветвления - лучше ли иметь множество условных операторов с короткими телами или несколькими длинными или короткими с вложенными условиями?
- С текущим 1,6 JVM, сколько элементов нужно скопировать, прежде чем System.arraycopy будет бить цикл копирования?
Что я уже сделал:
Прежде, чем я начну атаковать, для преждевременной оптимизации: базовый алгоритм уже отлично, но реализация Java составляет менее 2/3 скорости эквивалента C. Я уже заменил циклы копирования с помощью System.arraycopy, работал над оптимизацией циклов и устранили ненужные операции.
Я сильно использую бит-бит и упаковку байтов в ints для производительности, а также для переключения и маскировки.
По юридическим причинам я не могу смотреть на реализации в похожих библиотеках, а существующие библиотеки имеют слишком ограничительные условия использования.
Требования к ХОРОШЕМУ (принятому) ответу:
- Неприемлемые ответы: "это быстрее" без объяснения того, насколько И почему, ИЛИ не был протестирован с помощью компилятора JIT.
- Пограничные ответы: не были протестированы ни с чем, кроме Hotspot 1.4
- Основные ответы: предоставит общее правило и объяснение того, почему оно быстрее на уровне компилятора и примерно как быстрее
- Хорошие ответы: включают пару образцов кода для демонстрации
- Отличные ответы: имеют ориентиры с JRE 1.5 и 1.6
- СОВЕРШЕННЫЙ ответ: Является кем-то, кто работал с компилятором HotSpot, и может полностью объяснять или ссылаться на условия для оптимизации, которые будут использоваться, и насколько это быстрее. Может содержать код Java и код сборки образца, сгенерированный HotSpot.
Также: если у кого есть ссылки, в которых подробно описываются кишки оптимизации Hotspot и производительности ветвления, это приветствуется. Я достаточно разбираюсь в байт-коде, что полезен сайт, анализирующий производительность на уровне байт-кода, а не на уровне исходного кода.
(Редактировать) Частичный ответ: Обозначения выравнивания:
Это взято из предоставленной ссылки на внутреннюю вики HotSpot по адресу: https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination
HotSpot устранит проверки границ во всех циклах со следующими условиями:
- Array является инвариантом цикла (не перераспределяется внутри цикла)
- Индексная переменная имеет постоянный шаг (увеличивается/уменьшается на постоянную величину, только в одном месте, если это возможно)
- Массив индексируется линейной функцией переменной.
Пример: 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 для различной логики между режимами literal и backreference. Это уменьшает доступ к массиву и проверяет между режимами.
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;
}
Окончательное редактирование:
Я отметил наилучший ответ, насколько это принято, поскольку крайний срок близок. Поскольку я так долго занимался тем, что решил отправить код, я буду продолжать высказываться и отвечать на комментарии там, где это возможно. Извиняется, если код грязный: этот представленный код в разработке, а не отполирован для фиксации.
