Fast paths in concurrent programs

Compiling concurrent programs to run on a sequential processor presents a difficult tradeoff between execution time and size of generated code. On one hand, the process-based approach to compilation generates reasonable sized code but incurs significant execution overhead due to concurrency. On the other hand, the automata-based approach incurs a much smaller execution overhead but can result in code that is several orders of magnitude larger. We propose a way of combining the two approaches so that the performance of the automata-based approach can be achieved without suffering the code size increase due to it. The key insight is that the best of the two approaches can be achieved by using symbolic execution (similar to the automata-based approach) to generate code for the commonly executed paths (referred to as fast paths) and using the process-based approach to generate code for the rest of the program. We demonstrate the effectiveness of this approach by implementing our techniques in the ESP compiler and applying them to a set of filter programs and to VMMC network firmware.