We are looking for java, runtime optimization

I was very pleased to have read the articles: Optimization possibilities in C and C ++ languages and Development and execution speeds that are not achievable in C. In them optimization in compilation is in details sorted. The main condition for this optimization is the availability of the values ​​of most variables at the compilation stage. In the real world, unfortunately, this is not always the case.

Let's try to do something similar, but already in the process of program execution. For this we use java, the execution system of which optimizes the code at the execution stage. Plus, it allows you to create code on the fly.


And so, the condition of the problem is similar - a linear search over an array of structures with filters. I would like to get comparable execution time and memory consumption compared to C / C ++.
')
To represent our records, we use an array of longs and a wrapper class that allows us to conveniently work with them: CashAccountRow .

The rest of the mechanics are concentrated in the CashAccountStore class.
In the designer we fill our table. CashAccountFinder provides a primitive DSL and generates a list of predicates. Since, for comparison, the implementation is shown without code generation on the fly, the predicate contains the fieldGetter element.
The compileList function converts a Map into an array and sorts it according to selectivity.

Search without code generation:

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; } 

For code generation on the fly, use Javassist . The find2 function generates the name of the generated class for the search:

 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()); } 

Checks whether a class has already been created for this set and predicate order:

 if(classMapper.containsKey(cname.toString())) { matcherBase = classMapper.get(cname.toString()); } 

If not, it creates a new class:

 //     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); 

Search:

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

In the main run the search 2 times. The first launch is needed to “warm up”, so that jit and inlining will work.

  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 VM Server (build 23.21-b01, mixed mode)

The result of the launch on the 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

The result of the program from the first article on the same machine:

 Generated rows: 10,000,000
 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

The result of the program from the second article on the same machine:

 Generated rows: 10,000,000
 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

Almost on a par with the statically optimized C ++ version. The code is available on GitHub.com .