Performance of hardcoded finite automata
Software - Practice and Experience
School of Computing, University of South Africa, Pretoria 0003, South Africa; Fastar Research Group, Department of Computer Science, University of Pretoria, Pretoria 0002, South Africa; School of Computing, University of South Africa, UNISA, P.O. Box 392, Pretoria 0003, South Africa
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.
Algorithms; Cache memory; Codes (symbols); Computer architecture; Information technology; Regression analysis; Statistical methods; Hardcoding; Multivariate equations; Processing mechanisms; Table-driven algorithms; Finite automata