С большим удовольствием ознакомился со статьями: Возможности оптимизации в языках 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
