Decision Table Optimization

The Benchmarking have been implemented and tested, before publishing I'd like to make a few DT optimizations.Here is some ideas for Decision Table Optimization approach(from OpenL Tablets javadoc):

The basic algorithm for decision table evaluation is simple:

1. For each rule (column) evaluate conditions from the top to the bottom.
2. If any condition is false, evaluate all the actions in the rule.
3. If the action is non-empty return action, return the value of the action
4. If all columns were evaluated return null

The rules for the basic algorithm must hold true for all the optimizations that we are going to implement here, and for all the future implementations.

The assumption that has the most impact on the optimization technique in this algorithm is the read-onlyness of the input data with regard to the decision table execution. In other words, DT actions should not affect the results of condition evaluations. If your decision table does not conform to this assumption, you should not use optimizations. It is also recommended that you take another look at your design and ask yourself: was it really necessary to produce such a twisted logic?

To make optimizations more explicit and simultaneously slightly reduce the number of the keystrokes, the condition expressions that are intended for optimization have one notable distinction: their type is not boolean!!!!

Before you start scratching your head let me explain quickly. For example we have condition

driver.type == type

This condition intended for optimization will look like this:

driver.type

The OpenL Tablets DT Optimizer will automatically recognize this as the equality condition if the condition parameter is String or as contains() if it is an array or some other collection of Strings

We will describe the approach more formally later, but now let's discuss the advantages of this approach.

• there is less to type and therefore less to read, less places to make typos etc.
• there is less to compile and parse, the less work for the compiler or optimizer to determine programmer's intentions == better performance and less errors
• optimization algorithm is easy to turn on or off for any condition, it is easy to predict what kind of optimization will be used for what kind of data, there would not be any "black box magic". Eventually we are going to publish all the optimization algorithms and provide if possible some formula-based estimates for expected performance. In theory this would provide the basis for static compile-time performance analysis.

The table below will describe the optimizations that we are implementing now and some future ones:

Expr Type	N Params	Param Type	Condition	Optimization
String	1	String	x == value	Index with constant(HashMap) performance
String	1	String[]	list.contains(x)	Index with constant(HashMap) performance
int	1	int	x == value	Index with constant(HashMap) performance
int	1	int[]	list.contains(x)	Index with constant(HashMap) performance
int	2	int	min < x && x < max	Index with ln(n) performance

The more detailed analysis of the performance to be continued ...

Ratatouille and Math SAT

Last night we watched Ratatouille with my son, I enjoyed the movie, but could not help checking computer animation effects all the time. For the record, I never have done anything in this area professionally so my excitement was purely aesthetical. Still, from the professional programmer's point of view one can appreciate the amount of effort and intellectual breakthrough that went into the making of this movie.

Now, let's consider this, remember the fact that 10 years ago Deep Blue beat Kasparov in the series of 6 games, and contrast it with the level of the "intellect" that Vista demonstrates after swallowing billions dollars in investments, that mostly correspond to dozens of millions of man-hours in programmers work. Or let's go even lower and ask our computer to take a simple SAT test in Math. What would be the results? You can try and ask.

I also want to underscore that "stupid" Vista PC and "smart and cool" Mac will fare equally in this case, or fail equally, Mac just would handle the failure with more grace (judging from the famous commercial series).

If I am wrong and you are aware of any software program that is capable of taking SAT Math test (for example, in form of text file) and produce at least 700 (I want 800 - it is a computer for God's sake) result - drop me a line. Or give your perspective on when and how this is going to happen and whether you think that this is important? IMO, many problems of modern software development stem from the fact that everybody wants to beat Kasparov, but nobody wants to take SATs, and one is practically impossible without another.

From a bit another perspective, let's imagine that Pixar open-sourced all of it's IPed and patented algorithms - how would this affect the mainstream programming? Is there a way to apply knowledge without huge overhead of studying it first? Is there a way to make it as simple, as writing

import know.how.AdvancedMathSkills;

?

to be continued ...

300

Today we achieved a landmark 300 downloads on OpenL Tablets sourceforge site. 300 unknown heroes against zillions of other downloads. My OpenL Thoughts are today with you.

I hope, today is a good day to start a blog. The beginning of the 7th month of the 7th year. If my interpretation of the numbers is correct.

Let's try to keep this blog interesting, this will require some effort on your part too, dear reader.