Ищем на java, оптимизация во время исполнения

С большим удовольствием ознакомился со статьями: Возможности оптимизации в языках C и C++ и Скорости разработки и исполнения не достижимые на С. В них детально разобрана оптимизация во время компиляции. Основным условием такой оптимизации является доступность значений большинства переменных на этапе компиляции. В реальном мире, к сожалению, такое встречается не всегда.

Давайте попробуем сделать нечто похожее, но уже в процессе исполнения программы. Для этого используем java, исполняющая система которой оптимизирует код на этапе исполнения. Плюс к этому позволяет создавать код на лету.


И так, условие задачи аналогичное — линейный поиск по массиву структур с фильтрами. Хотелось бы получить сопоставимое время выполнения и потребление памяти по сравнению с С/С++.

Для представления наших записей используем массив long'ов и класс обертку позволяющий с ними удобно работать: CashAccountRow.

Вся остальная механика сосредоточена в классе CashAccountStore.
В конструкторе заполняем нашу таблицу. CashAccountFinder обеспечивает примитвный DSL и формирует список предикатов. Поскольку для сравнения приведена реализация без генерации кода на лету, в предикате содержится элемент fieldGetter.
Функция compileList конвертирует Map в массив и сортирует в соответствии с селективностью.

Поиск без генерации кода:
public final int find(final CashAccountFinder finder) {
        int rValue = 0;
        CashAccountRow c = new CashAccountRow();

        finder.compileList();
        for(int i = 0; i < ROW_COUNT; ++i) {
            if(finder.isMatched(c.setBitStorage(accountRows[i]))) { ++rValue; }
        }

        return rValue;
    }

Для генерации кода на лету используем Javassist. Функция find2 формирует имя генерируемого класса для поиска:
public final int find2(final CashAccountFinder finder) throws Throwable{

        finder.compileList();
        StringBuilder cname = new StringBuilder();
        for(CashAccountFinder.PredicateHolder p: finder.predicateHolderArray) {
            cname.append(p.field.toString());
        }

Проверяет, создавали ли уже класс для этого набора и порядка предикатов:
if(classMapper.containsKey(cname.toString())) {
            matcherBase = classMapper.get(cname.toString());
        }

Если нет, то создает новый класс:
// Пул классов по умолчанию
            ClassPool classPool = ClassPool.getDefault();
// Добавляем classpath из которого загружен базовый класс 
// (нужно в случае нескольких активных classloader'ов, 
// иначе не будет работать под application серверами, контейнерами и exec-maven-plugin )
            classPool.insertClassPath(new ClassClassPath(this.getClass()));
// Загружаем базовый класс
            CtClass base = classPool.get("examples.data.GenMatcherBase");
// Создаем пустой класс
            CtClass gen = classPool.makeClass("examples.data.GenMatcher" + cname, base);
// Формируем функцию проверки записи на соответсвие
            StringBuilder sb = new StringBuilder("public boolean c(examples.data.CashAccountRow r){ return ");
            for(CashAccountFinder.PredicateHolder p: finder.predicateHolderArray) {
                switch (p.field) {
                    case AGE:
                        sb.append("r.getAge() >= " + p.minValue + " && r.getAge() <= " + p.maxValue + " && ");
                        break;
                    case AMOUNT:
                        sb.append("r.getAmount() >= " + p.minValue + " && r.getAmount() <= " + p.maxValue + " && ");
                        break;
                    case CODE:
                        sb.append("r.getCode() >= " + p.minValue + " && r.getCode() <= " + p.maxValue + " && ");
                        break;
                    case GENDER:
                        sb.append("r.getGender() >= " + p.minValue + " && r.getGender() <= " + p.maxValue + " && ");
                        break;
                    case HEIGHT:
                        sb.append("r.getHeight() >= " + p.minValue + " && r.getHeight() <= " + p.maxValue + " && ");
                        break;
                }
            }
            sb.append("true; }");
// И добавляем ее в класс
            gen.addMethod(CtMethod.make(sb.toString(), gen));
// Добавляем класс к списку классов
            matcherBase = (GenMatcherBase) gen.toClass().newInstance();
            classMapper.put(cname.toString(), matcherBase);

Поиск:
        CashAccountRow c = new CashAccountRow();
        int rValue = 0;

        for(int i = 0; i < ROW_COUNT; ++i) {
            if(matcherBase.c(c.setBitStorage(accountRows[i]))) { ++rValue; }
        }

В main запускаем поиск 2 раза. Первый запуск нужен для «разогрева», что бы jit и inlining отработали.
        System.out.println("Warming up...");
        store.find2(finder);
        System.out.println("Running benchmark...");
        long millis = System.currentTimeMillis();
        int i = store.find2(finder);
        long endMillis = System.currentTimeMillis();

JVM:
java version "1.7.0_21"
Java(TM) SE Runtime Environment (build 1.7.0_21-b11)
Java HotSpot(TM) 64-Bit Server VM (build 23.21-b01, mixed mode)

Результат запуска на Core I5-2500k 3.3GHz:
Warming up...
Generated code:
public boolean c(examples.data.CashAccountRow r){ return r.getAmount() >= 0 && r.getAmount() <= 0 && r.getHeight() >= 0 && r.getHeight() <= 0 && r.getGender() >= 0 && r.getGender() <= 0 && true; }
Running benchmark...
Number of records matched:38
Elapsed time:18ms
Used Memory:81MB

Результат работы программы из первой статьи на той же машине:
Generated rows: 10000000
C++-Searching...
C++-optimized search took 0.039000 seconds.
Found rows: 38
C-Searching...
C-search took 0.053000 seconds.
The C++ faster than C: 1.358974 times
Found rows: 38

Результат работы программы из второй статьи на той же машине:
Generated rows: 10000000
C++-Searching...
C++-optimized search took 0.012000 seconds
Found rows: 38
C-Searching...
C-search took 0.051000 seconds.
The C++ faster than C: 4.250000 times
Found rows: 38

Практически вровень со статически оптимизированной версией на C++. Код доступен на GitHub.com.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 21

  • UFO just landed and posted this here
      +5
      Насколько же провокационной моя статья оказалась. Молодцы :)
        +5
        Не провокационная, а на редкость полезная и познавательная :)
          0
          а можно узнать по поводу причины сортировки предикатов?
          гитхаб

          отключение данной сортировки уменьшает время выборки с 33ms до 15ms
            +1
            В этой программе (на примитивном уровне) показывается работа SQL оптимизатора. Предикаты сортируются по селективности — чем меньше мы записей выберем с участием этого предиката, тем раньше мы должны его применить.
            Если в app.java поправить
            //27 строка
            if(random.nextBoolean()) { finder = finder.withAmount(0, 0); } 
            на 
            if(random.nextBoolean()) { finder = finder.withAmount(0, 1000000); }
            и 
            //35 строка
            if(random.nextBoolean()) { finder = finder.withCode(rr, rr + 5); }
            на
            if(random.nextBoolean() || true) { finder = finder.withCode(rr, rr + 5); }
            

            мы ухудшим возможность отсечения ненужных строк по amount. Без сортировки предикатов amount так и останется первым и ухудшит общее время выполнения, а с сортировкой уйдет на вторую позицию.
              0
              с одной стороны я понимаю ЗАЧЕМ это все сделано, но цитируя TheShade:

              – “Real world strikes back!”
              – Исследуем взаимодействие софта с железом на типичных данных
              • Производительность уже нельзя предсказать
              • Производительность можно только измерить

              замерил 20ms с отключенной сортировкой vs 31ms с включенной

              p.s. конечно по хорошему нужно допилить jmh, но пока в качестве костыля увеличил количество прогревов

              for (int i = 0; i < 100; i++) {
              long millis1 = System.currentTimeMillis();
              store.find2(finder);
              long endMillis1 = System.currentTimeMillis();
              System.out.println(«Elapsed time (warm) :» + (endMillis1 — millis1) + «ms»);
              }

              в итоге с отключенной сортировкой действительно первых пару раз еще выполняется быстрее, но потом выходит на стабильное значение в 30-31ms (с 17ms в первой попытке), в то время как с отключенной сортировкой опускается до 19-20ms (33ms в первой попытке).
                0
                Основоной посыл статьи не в абсолютных цифрах :). Сортировка требует времени. В вашем случае это время больше, чем выгода от перестановки предикатов. Почему это так — для ответа на этот вопрос нужно смотреть листинги работы JIT, как это сделать.
                  0
                  не понял, что я именно должен найти в листиге jit?
                  то что сортировка занимает время сравнимое со всем поиском?

                  по поводу кода:
                  0) вносим ваши изменения для матчера
                  1) смотрим какой порядок выбора предложен после сортировки
                  2) enum RecordFields { CODE, AGE, AMOUNT, GENDER, HEIGHT } // порядок который мы получим после анализа предикатов
                  3) отключаем сортировку
                  4) время поиска с оптимальным профилем 9-10ms

                  на этом фоне 30ms c включенной сортировкой как-то смотрится печально, так как теряем почти 20ms на ней
                  даже с неоптимальным профилем выдаем 20ms

                  если посмотреть на первоначальный вариант «профайла», то видно что там порядок полей с сортировкой и так попадает на оптимальный, т.е. тут мы теряем только 15ms на сортировку, что сравнимо с временем выполнения всего кода.

                  так что преждевременные оптимизации далеко не всегда идут во благо

                  p.s. еще есть косяк теста в том, что у нас массив полей неизменяемый и jit начинает уже подстраиваться под него =) поэтому по хорошему нужно еще и его регулярно перегенеривать, конечно если это у нас база данных, а не фиксированный набор полей.

                  p.p.s. как получить асм я представляю и уж если пошла такая пьянка на разминку мозгов:
                  тыц
                  в чем причина, что incrementnFieldCall так проседает относительно incrementnFieldCall2, ведь согласно логики производительность должна быть равна
                  баг уже зарепорчен, но вот поковырять asm вам должно быть прикольно
        +1
        Я ждал этот пост!
          +2
          Этому посту очень не хватает ссылки на недавний доклад Владимира Иванова — Динамическая (JIT) компиляция в JVM.
            –8
            Ну да, джит. Так, знаете ли, можно всю логику закешировать и радоваться, а то, что холодный старт занимает час, так это фигня, да?
              +4
              А перед этим еще и компьютер включить надо — это вообще ужас!
              +2
              Да уж, в изначальной статье поистине «разворошили осиное гнездо». Ждем C# и Haskell.
                0
                Пример на C# мне ThermIt кинул в PullRequest, пока не проверял.
                C#-Searching…
                Затрачена на поиск по Code 0,0359041
                Затрачена на поиск по AmountOfMoney 3E-07
                1 stage 0,0520052 seconds.
                C#-search took 0,0520052 seconds.
                Found rows: 0
                0
                Сразу бросилось в глаза, идея, кстати, тоже должна была подсказать:
                sb.append("r.getGender() >= " + p.minValue + ...

                  0
                  оно выполняется только 1 раз в процессе генерации метода,
                  в последующих вызовах сразу забирает из кеша полученный класс

                  можно конечно написать sb.append для отдельных составляющих, но тогда снижается читабельность
                    0
                    тогда можно было и стрингбилдер не мучать)
                      0
                      Вроде бы при компиляции он всё равно заменит плюсы на append…
                        0
                        да, заменит, но не так как вы себе представляете

                        sb.append("r.getAmount() >= " + p.minValue + " && r.getAmount() <= " + p.maxValue + " && ");
                        


                        после компиляции будет

                        sb.append(
                            new StringBuilder()
                                 .append("r.getAmount() >= ").append(p.minValue)
                                 .append(" && r.getAmount() <= ").append(p.maxValue)
                                 .append(" && ").toString()
                        );
                        


                        в первом посте предложение про полное исключение созданий лишних объектов.
                          0
                          Ну я как раз так себе и представляю. Но интересный вопрос: если компилятор заменяет плюсы на стрингбилдер, может он и так умеет? Вы не проверяли? Я если честно сразу со стрингбилдером пишу, не люблю когда компилятор за меня меняет код, так что как точно это работает не знаю.
                  +1
                  Осталось еще один зубодробительный вариант сделать: Сгенерировать на лету сишный код, собрать его через libclang на лету, а потом подгрузить и зарезолвить получившиеся символы.

                  Only users with full accounts can post comments. Log in, please.