title: Designing high-performance State Machine in Java
body: <p>I am in the process of starting to write a Java library to implement high-performance Finite State Machines. <em>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.</em></p>
  
  <p>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.</p>
  
  <p><strong>Considerations</strong></p>
  
  <ol>
  <li>The automatons generated are typically not massive. (~ 100-500 states).</li>
  <li>The implementation should be able to <strong>scale</strong> though.</li>
  <li>The implementation should enable <strong>fast transformations</strong> (minimization, determinization etc.).</li>
  <li>Looking to implement DFA, NFA, GNFA, PDA and possibly Tree Automata. Hopefully under a single interface if possible.</li>
  <li>Should have a good balance between memory use and performance.</li>
  </ol>
  
  <p><em>Current questions regarding design for me at the moment are:</em></p>
  
  <ol>
  <li><p>Should classes for <code>State</code>, <code>Symbol</code> and <code>Transition</code> 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?</p></li>
  <li><p>What would be the best way to store the data internally? Using data structures like <code>HashMap</code> and <code>HashSet</code> 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?</p></li>
  </ol>
  
  <p>I appreciate any input. Thanks!</p>