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