Designing high-performance State Machine in Java

Question

I am in the process of starting to write a Java library to implement high-performance Finite State Machines. I know there are a lot of libraries out there, but I want to write my own from scratch, as almost all the libraries out there construct automatons optimized for handling only one at a time.

I would like to know what the people in the SO community who have dabbled in state machine design feels are the most important / best design principles when it comes to implementing high-performance libraries like these.

Considerations

1. The automatons generated are typically not massive. (~ 100-500 states).
2. The implementation should be able to scale though.
3. The implementation should enable fast transformations (minimization, determinization etc.).
4. Looking to implement DFA, NFA, GNFA, PDA and possibly Tree Automata. Hopefully under a single interface if possible.
5. Should have a good balance between memory use and performance.

Current questions regarding design for me at the moment are:

1. Should classes for State, Symbol and Transition be defined? Or should a "hidden" internal structure be used. Personally I feel that using classes as such would waste a lot of memory since the same information can be stored in a much more condensed form. But, does this enable faster transformations? Does it hold any other pros / cons?

2. What would be the best way to store the data internally? Using data structures like HashMap and HashSet enables amortized constant time lookups, but there is an element of overhead involved. Is this the best way? Storing the transition information as a primitive (or not) array seems to waste quite a bit of memory. Especially when the library needs to handle a lot of automatons at a time. What are the pros / cons of the different data structures?

I appreciate any input. Thanks!

Answer 1

I have some questions:

• Which part do you need to be fast, the inputting of the FSA, the building of the FSA, or the execution of the FSA?

• Where does the input of the FSA come from? Does a human put in states and arcs, or some automatic process? Does the real input come from a regular expression that's converted to a FSA?

• How often can the FSA change? Once a second? Once a year?

You know what you need. Aside from academic Turing machines, I've never seen a significant state machine that didn't start from a textual representation, either as a regular expression or a structured program.

In every case I've dealt with, the preferred implementation was to convert the regular expression directly into a simple structured program and compile it. Nothing will execute any faster than that.

Answer 2

Well how fast do you want it to be? The code at brics.dk/automaton does declare its own State and Transition classes altough, obviously, these could be rewritten using primitives (heck, the entire Transition class's state apparently would easily fit on a long).

Thing is, if you move, for example, the Transition class to simply a primitive, then you're not forced to use anymore the slow HashMap<Transition,...> default Java collections: you can use libraries like Trove's TLongObjectHashMap (or TLongInt... or TLongLong, whatever) which owns the default HashMap big times (the Trove libraries basically provides maps and sets that are super efficient, both fast and small, when you work with primitives: you don't generate countless garbage nor constant needless wrapping around primitives, so less GC etc. If you're into performance, then you do want to check Trove... And their 3.0 upcoming release is 20% faster than Trove 2.0).

But is it really useful? Apparently that library is already plenty of fast. There's no doubt it can be made faster by not wastefully creating objects and by using collections that do actually perform well but it's not clear that it would be desirable.

Besides that, I'm pretty sure that the library above is not thread safe. The State constructor creates a unique ID by doing this:

static int next_id;
.
.
.
id = next_id++;

and that constructor is called from... 90 different places!

Textbook example of a way to not create a unique ID in a multi-threaded scenario (heck, even making next_id volatile wouldn't be sufficient, you want, say, an AtomicInteger here). I don't know the library well enough but this ID thinggy looks very fishy to me.