Как можно ускорить этот код Java?

Question

Я пытаюсь оценить, насколько быстро Java может выполнить простую задачу: прочитать огромный файл в память, а затем выполнить некоторые бессмысленные вычисления для данных. Все виды оптимизаций учитываются. Будь то переписывание кода по-другому или использование другой JVM, обман JIT ..

Входной файл представляет собой список длиной 32 миллиона из 32-битных целочисленных пар, разделенных запятой. Как это:

44439,5023
33140,22257
...

Этот файл занимает 5,5 ГБ на моей машине. Программа не может использовать более 8 ГБ ОЗУ и может использовать только однопоточный .

package speedracer;

import java.io.FileInputStream;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;

public class Main
{
    public static void main(String[] args)
    {
        int[] list = new int[1000000000];

        long start1 = System.nanoTime();
        parse(list);
        long end1 = System.nanoTime();

        System.out.println("Parsing took: " + (end1 - start1) / 1000000000.0);

        int rs = 0;
        long start2 = System.nanoTime();

        for (int k = 0; k < list.length; k++) {
            rs = calc(list[k++], list[k++], list[k++], list[k]);
        }

        long end2 = System.nanoTime();

        System.out.println(rs);
        System.out.println("Calculations took: " + (end2 - start2) / 1000000000.0);
    }

    public static int calc(final int a1, final int a2, final int b1, final int b2)
    {
        int c1 = (a1 + a2) ^ a2;
        int c2 = (b1 - b2) << 4;

        for (int z = 0; z < 100; z++) {
            c1 ^= z + c2;
        }

        return c1;
    }

    public static void parse(int[] list)
    {
        FileChannel fc = null;
        int i = 0;

        MappedByteBuffer byteBuffer;

        try {
            fc = new FileInputStream("in.txt").getChannel();

            long size = fc.size();
            long allocated = 0;
            long allocate = 0;

            while (size > allocated) {

               if ((size - allocated) > Integer.MAX_VALUE) {
                   allocate = Integer.MAX_VALUE;
               } else {
                   allocate = size - allocated;
               }

               byteBuffer = fc.map(FileChannel.MapMode.READ_ONLY, allocated, allocate);
               byteBuffer.clear();

               allocated += allocate;

               int number = 0;

               while (byteBuffer.hasRemaining()) {
                   char val = (char) byteBuffer.get();
                   if (val == '\n' || val == ',') {
                        list[i] = number;

                        number = 0;
                        i++;
                   } else {
                       number = number * 10 + (val - '0');
                   }
                }
            }

            fc.close();

        } catch (Exception e) {
            System.err.println("Parsing error: " + e);
        }
    }
}

Я перепробовал все, что мог придумать. Пробовал разные читатели, пробовал openjdk6, sunjdk6, sunjdk7. Пробовал разных читателей. Пришлось сделать некрасивый разбор, так как MappedByteBuffer не может отобразить более 2 ГБ памяти одновременно. Я бегу:

   Linux AS292 2.6.38-11-generic #48-Ubuntu SMP 
   Fri Jul 29 19:02:55 UTC 2011 
   x86_64 GNU/Linux. Ubuntu 11.04. 
   CPU: is Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz.

В настоящее время мои результаты для анализа: 26.50s, вычисления: 11.27s. Я конкурирую с аналогичным тестом C ++, который выполняет ввод-вывод примерно в то же время, но вычисления занимают всего 4,5 с. Моя главная цель - сократить время расчета любым возможным способом. Есть идеи?

Обновление: Похоже, что основное улучшение скорости может быть вызвано тем, что называется Авто-векторизация . Мне удалось найти некоторые намеки на то, что текущий JIT от Sun делает только «некоторую векторизацию», однако я не могу это подтвердить. Было бы замечательно найти какую-нибудь JVM или JIT, которая бы имела лучшую поддержку оптимизации векторизации.

Answer 1

Прежде всего, -O3 включает:

-finline-functions
-ftree-vectorize

среди прочих ...

Так что, похоже, на самом деле это может быть векторизация.

РЕДАКТИРОВАТЬ: Это было подтверждено. (см. комментарии) Версия C ++ действительно векторизована компилятором. С отключенной векторизацией, версия C ++ работает немного медленнее, чем версия Java

Предполагая, что JIT не векторизует цикл, для версии Java может быть трудно / невозможно соответствовать скорости версии C ++.

---

Теперь, если бы я был умным компилятором C / C ++, вот как я бы организовал этот цикл (на x64):

int c1 = (a1 + a2) ^ a2;
int c2 = (b1 - b2) << 4;

int tmp0 = c1;
int tmp1 = 0;
int tmp2 = 0;
int tmp3 = 0;

int z0 = 0;
int z1 = 1;
int z2 = 2;
int z3 = 3;

do{
    tmp0 ^= z0 + c2;
    tmp1 ^= z1 + c2;
    tmp2 ^= z2 + c2;
    tmp3 ^= z3 + c2;
    z0 += 4;
    z1 += 4;
    z2 += 4;
    z3 += 4;
}while (z0 < 100);

tmp0 ^= tmp1;
tmp2 ^= tmp3;

tmp0 ^= tmp2;

return tmp0;

Обратите внимание, что этот цикл полностью векторизован.

Еще лучше, я бы полностью развернул этот цикл. Это то, что будет делать компилятор C / C ++. Но теперь вопрос, будет ли это делать JIT?

Answer 2

Интересный вопрос.:-) Это, вероятно, больше комментарий, так как я не буду отвечать на ваш вопрос, но он слишком длинный для поля комментария.

Микробанкинг в Java сложен, потому что JIT может сходить с ума с оптимизацией,Но этот конкретный код обманывает JIT таким образом, что он каким-то образом не может выполнять свою обычную оптимизацию.

Обычно этот код выполняется за O (1) время, потому что ваш основной цикл ни на что не влияет:

    for (int k = 0; k < list.length; k++) {
        rs = calc(list[k++], list[k++], list[k++], list[k]);
    }

Обратите внимание, что конечный результат rs на самом деле не зависит от выполнения всех итераций цикла;только последний.Вы можете вычислить окончательное значение «k» для цикла без необходимости фактически запускать цикл.Обычно JIT замечает это и превращает ваш цикл в одно присваивание, он может обнаружить, что вызываемая функция (calc) не имеет побочных эффектов (чего не происходит).

Но, так или иначе,этот оператор в функции calc () портит JIT:

        c1 ^= z + c2;

Каким-то образом это добавляет слишком много сложности для JIT, чтобы решить, что весь этот код в конце ничего не меняет и что оригиналцикл может быть оптимизирован.

Если вы измените этот конкретный оператор на что-то еще более бессмысленное, например:

        c1 = z + c2;

Тогда JIT подхватит и оптимизирует ваши циклы.Попробуйте это.: -)

Я пытался локально с гораздо меньшим набором данных, и с версией «^ =» вычисления занимали ~ 1,6 с, тогда как с версией «=» они занимали 0,007 секунды (или, другими словами,это оптимизировало цикл).

Как я уже сказал, на самом деле это не ответ, но я подумал, что это может быть интересно.

Answer 3

Используйте Hotspot JVM в режиме сервера и убедитесь, что подогревает ее .Также дайте достаточно времени для того, чтобы алгоритмы сборки мусора установились в стабильном темпе, если сборка является основной частью вашего теста.Я не вижу ничего такого, что заставляет меня думать, что это будет ...

Answer 4

Я пытаюсь оценить, насколько быстро Java может выполнить простую задачу: прочитать огромный файл в память, а затем выполнить некоторые бессмысленные вычисления для данных.

Если задача состоит в том, чтобы выполнить бессмысленный расчет, то наилучшей оптимизацией будет , чтобы не выполнить расчет .

Если то, что вы действительно пытаетесь сделать здесь, это выяснить, существует ли общая методика ускорения вычислений, тогда я думаю, что вы лаете не на то дерево. Там нет такой техники. То, что вы узнаете по оптимизации бессмысленных вычислений, вряд ли применимо к другим (надеюсь значимым ) вычислениям.

Если вычисление не бессмысленно , и цель состоит в том, чтобы заставить всю программу работать быстрее, вы, вероятно, уже достигли точки, когда оптимизация - пустая трата времени.

• Текущий (Java) - 26,50 с + 11,27 с = ~ 38 секунд
• Цель (C ++) - ~ 26,5 с + 4,50 = ~ 31 с
• ускорение в процентах - менее 20%.

Ускорение менее чем на 20% для расчета ~ 40 секунд, вероятно, не стоит усилий. Дешевле заставить пользователя крутить пальцы в течение этих дополнительных 7 секунд.

---

Это также говорит вам кое-что интересное. Что в этом сценарии не имеет значения большой разницы в относительном выражении, используете ли вы C ++ или Java. В общей производительности программы преобладает фаза, в которой C ++ и Java сравнимы.

Answer 5

MappedByteBuffer вносит только около 20% в производительность ввода-вывода, и это огромные затраты памяти - если это вызывает переключение лечения, это хуже, чем болезнь.

Я бы использовал BufferedReader вокруг FileReaderи, может быть, Сканер, чтобы получить целые числа, или, по крайней мере, Integer.parseInt (), который с гораздо большей вероятностью был нагрет HotSpot, чем ваш собственный код преобразования radix.

Answer 6

Каков счет, если вы переместите несколько строк своей функции calc внутри итерации списка?
Я знаю, что она не очень чистая, но вы выиграете над стеком вызовов.

[...]
    for (int k = 0; k < list.length; k++) {
        int a1 = list[k++];
        int a2 = list[k++];
        int b1 = list[k++];
        int b2 = list[k];

        int c1 = (a1 + a2) ^ a2;
        int c2 = (b1 - b2) << 4;

        for (int z = 0; z < 100; z++) {
            c1 ^= z + c2;
        }

        rs = c1;
    }

Answer 7

Вы пробовали "встраивать" parse () и calc (), т.е. помещали весь код в main ()?