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

в 13:00, , рубрики: 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.

Автор: xlix123

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js