Ситуация:
Я оптимизирую реализацию алгоритма сжатия 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
Логически, это идентично версии для разработки, но в ней используется цикл 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;
}
Окончательное редактирование:
Я отметил лучший ответ, насколько он был принят, так как срок почти истек. Поскольку до принятия решения о размещении кода у меня ушло так много времени, я буду продолжать высказывать замечания и отвечать на комментарии там, где это возможно. Извинения, если код грязный: этот код представлен в разработке, а не отшлифован для фиксации.