Ищем на 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.