Performance of hardcoded finite automata

Abstract

We study the performance of a hardcoded algorithm for recognizing strings of a finite automaton's language and compare it with the use of the more conventional table-driven algorithm. In both cases, performance depends on the finite automaton's dimensions such as alphabet size and the number of states. However, the respective processing mechanisms that influence the performance, in particular cache memory usage, depend on the details of the processor's underlying architecture. In the hardcoded case, the automaton's dimensions determine the size of the code which is, in turn, the primary determinant of the way in which cache memory is used. In the table-driven case, cache memory usage is primarily determined by the way in which portions of the transition table are stored in it. Using statistical regression analysis, we provide multivariate equations to model the observed time efficiency of both methods. The equations obtained are cross-compared and conclusions are drawn. Copyright © 2006 John Wiley & Sons, Ltd.