Fast Compilation with Lisp

While reading about finite automata and regular languages, I realized something: compilation is faster than interpretation, but programming languages are a specific case of interpretation and compilation.

Put another way, compilers and interpreters are two ways of handling an abstract syntax tree. The interpreter is data structure driven: it follows the abstract syntax tree performing actions as it goes. The compiler is also data structure driven: it takes an abstract syntax tree and converts it to an executable. The key insight is that an abstract syntax tree is a special case. Any data structure driven program is either an interpreter or a compiler.

As an example, consider the scanner in compilers. The job of the scanner is to split the source code text stream into tokens for the parser. There are two ways to implement the scanner: one is to hand code the fastest scanner you can; the other is to identify the regular expressions describing the language, compile the regular expressions into a table, and then use the table to drive the scanner. It is common knowledge that hand written scanners are faster than table driven scanners. [Programming languages] However, this seems to be a false dichotomy. There's a third option.

In a compiler, the scanner acts as a kind of compiler itself. It takes a stream of text and creates tokens. Then, the parser acts as a kind of compiler, it takes the stream of tokens and returns an abstract syntax tree. I use compiler to mean a transformation on static data: a transformation that can be done on input known ahead of time. It's hard to imagine a scanner or parser that works differently.

interpreter1.png

Figure 1: An interpreter takes program input and source code at the same time. A compiler translates program input into an optimized executable and then maps input to output.

A scanner, a tool that transforms a regular language into a table is a kind of compiler itself. It takes a stream of text and creates tokens. But how is the table handled? In a table driven scanner, the table is interpreted. A program walks the table to handle a stream of source code. The obvious question is "If the table is constant, why not compile the table?"

interpreter2.png

Figure 2: Walking a static data structure is like interpreting a programming language, slow and easy.

This has been done. Consider Doug Hoyte's description of Edi Weitz's Common Lisp regular expression library:

[…] CL-PPCRE is fast. Really fast. When compiled with a good native code compiler, benchmarks suggest that for most regular expressions CL-PPCRE is roughly twice as fast as Perl, often much faster. And Perl has one of the fastest non-lisp regular expression engines around: a highly optimised engine written in C. How is this possible? Surely Perl's low-level implementation should have a performance edge over anything written in a high-level language like lisp.

Let Over Lambda, Chapter 4, Doug Hoyte

My guess is that Edi is compiling regular expressions into a table and compiling the resulting table. While this seems difficult, compiling code in Lisp is very easy. All you have to do is walk the data structure and build up a large lambda. Paul Graham's On Lisp includes a chapter where Paul Graham compiles a decision tree.

By representing the nodes as closures, we are able to transform our twenty-questions network entirely into code. As it is, the code will have to look up the node functions by name at runtime. However, if we know that the network is not going to be redefined on the fly, we can add a further enhancement: we can have node functions call their destinations directly, without having to go through a hash-table.

The end of the chapter sums up the basic idea.

"To represent with closures" is another way of saying "to compile,"

To make our system faster, we'll hand generate jumps using Common Lisp's support for goto.

Example

To make my point, I created a small library working with finite state machines. There are two ways to use a state machine with my library: the finite state machine can be interpreted with the scan method and the finite state machine can be compiled directly into a two tier jump table. To show the distinction between the two methods I'll need an example state machine, example input, and then a measurement of each case.

My finite state machine is an example taken from Sisper.

sisper1.png

Figure 3: This finite state machine tracks a bounded position state. The u can be interpreted as "Up". The d can be interpreted as "Down".

Below, I define a FSM equivalent to the state diagram. I start by defining the state-transition function with a hash table and then I create an object containing the start state, alphabet, list of states, end states, and transition table.

(defparameter *transition-table-example-2* (make-hash-table :test #'equalp))
(let ((table *transition-table-example-2*))
  (setf (gethash #(base #\u) table) 'u)
  (setf (gethash #(base #\d) table) 'd)
  (setf (gethash #(u #\u) table) 'uu)
  (setf (gethash #(u #\d) table) 'base)
  (setf (gethash #(d #\u) table) 'base)
  (setf (gethash #(d #\d) table) 'dd)
  (setf (gethash #(uu #\u) table) 'uuu)
  (setf (gethash #(uu #\d) table) 'u)
  (setf (gethash #(uuu #\u) table) 'uuu)
  (setf (gethash #(uuu #\d) table) 'uu)
  (setf (gethash #(dd #\u) table) 'd)
  (setf (gethash #(dd #\d) table) 'ddd)
  (setf (gethash #(ddd #\u) table) 'dd)
  (setf (gethash #(ddd #\d) table) 'ddd))

(defparameter *automata-example-2*
  (make-instance 'finite-automata
		 :start-state 'base
		 :alphabet (list #\u #\d)
		 :states (list 'base 'u 'd 'uu 'dd 'uuu 'ddd)
		 :end-states (list 'base)
		 :transition-table *transition-table-example-2*))

Next, I need some input. Random input should be fine, so I'll generate a random sequence of 1000 valid characters.

(defparameter *inputs-example-1*
  (flet ((random-input ()
	   (aref #(#\u #\d) (random 2))))
    (coerce (loop for i below 1000
	       collect (random-input))
	    'string)))

The input is shown below.

"uuududdduddduududududddduuudududduudddduuududududuuduuuuuduudduuuuuuddduddduduuuudduudududduudduuduudduduududduuduuuuduuudddddddudduuuuduuuduuuudududdduduudddddddduuuddduduuuudduddduuuduuuudduuduudddddududududduuuduuuududdddduuuuuuduududuuuduuuuuduuddduududuududuududduddududduuuuuududududuuuduuududduudddddddduududduuuudddduuuuduuuddddududduudduduuudddddudddddddduuuuduudddddududduudduuuududuuduuuduudduuuuddddudduddduddudduduuududddduddduudduuduuuuddduuuudduduudduuduududduuuduuudddduddduuuuuudduddududddduuududddudddudddudduuduuduuddduddudddduuudduudduduuduuddduudduduududduuddudduduudddddduududuuuuuddduudddduddudddddddduduuduuduududdduddduddduudduduuuuuduuuduuuddududuuuddddddddduuddudduududdddududuudddduuudduudduuduuududuudduduuuuudududuuududdudduduuudduuuudududduddduuuuududuuudddddduuuuuuddduududduudduuuuuduuuuduududuudududuudduuuuduuuddududuuuudduuuududdddduuduuddudduuddduududdududuuduuddduuuudduuudddduddddduuuuuudduudddudduuudududuuduudddddduudduduuddudududdududuuddddduduuuudduuududuuu"

I can benchmark the code using the trival-benchmark package.

(ql:quickload 'trivial-benchmark)
(benchmark:with-timing (10)
  'test)

This results in the following output:

-                SAMPLES  TOTAL  MINIMUM  MAXIMUM  MEDIAN  AVERAGE  DEVIATION  
REAL-TIME        10       0      0        0        0       0        0.0        
RUN-TIME         10       0      0        0        0       0        0.0        
USER-RUN-TIME    10       0      0        0        0       0        0.0        
SYSTEM-RUN-TIME  10       0      0        0        0       0        0.0        
PAGE-FAULTS      10       0      0        0        0       0        0.0        
GC-RUN-TIME      10       0      0        0        0       0        0.0        
BYTES-CONSED     10       0      0        0        0       0        0.0        
EVAL-CALLS       10       0      0        0        0       0        0.0        
NIL

With an example state machine, test input, and a benchmark tool, we can now compare interpretation to compilation.

Table Driven Interpreter

The table driven interpreter uses the scan method to walk the table until the input is exhausted.

(benchmark:with-timing (100000)
  (with-input-from-string (input *inputs-example-1*)
    (scan *automata-example-2* input)))

The timing results are below:

-                SAMPLES  TOTAL       MINIMUM  MAXIMUM  MEDIAN  AVERAGE    DEVIATION  
REAL-TIME        100000   12.187      0        0.016    0       0.000122   0.000351   
RUN-TIME         100000   12.208      0        0.012    0       0.000122   0.000692   
USER-RUN-TIME    100000   12.036      0        0.012    0       0.00012    0.000688   
SYSTEM-RUN-TIME  100000   0.184       0        0.004    0       0.000002   0.000086   
PAGE-FAULTS      100000   0           0        0        0       0          0.0        
GC-RUN-TIME      100000   0.276       0        0.012    0       0.000003   0.00013    
BYTES-CONSED     100000   3214350368  0        1142480  32768   32143.504  5735.312   
EVAL-CALLS       100000   0           0        0        0       0          0.0        

Compiled Table

The compiler transforms the automata table to machine code. The transformation is done outside of the benchmark timing, because it can be done at compile time; the compiled automata is reused each time. Unlike the table driven interpeter, the method scan is not used. The compile creates a lambda that can be called with funcall.

(let ((scanner (eval (compile-automata *automata-example-2*))))
  (benchmark:with-timing (100000)
    (with-input-from-string (input *inputs-example-1*)
      (funcall scanner input))))

The dissasembly of the scanner function can be seen below.

(let ((scanner (eval (compile-automata *automata-example-2*))))
  (disassemble scanner))

The timing results are below:

-                SAMPLES  TOTAL     MINIMUM  MAXIMUM  MEDIAN  AVERAGE    DEVIATION  
REAL-TIME        100000   1.606     0        0.012    0       0.000016   0.000131   
RUN-TIME         100000   1.596     0        0.012    0       0.000016   0.000254   
USER-RUN-TIME    100000   1.424     0        0.012    0       0.000014   0.00024    
SYSTEM-RUN-TIME  100000   0.196     0        0.004    0       0.000002   0.000089   
PAGE-FAULTS      100000   19        0        3        0       0.00019    0.016431   
GC-RUN-TIME      100000   0.012     0        0.012    0       0.0        0.000038   
BYTES-CONSED     100000   12953552  0        130960   0       129.53552  2090.5718  
EVAL-CALLS       100000   0         0        0        0       0          0.0        
NIL

Conclusion

The compiled version is ~10 times faster, but the compiler implementation is less than 20 lines of code.

(defun compile-automata (automata)
  (let ((escape (gensym "ESCAPE-"))
	(eof-value (gensym "EOF-VALUE-")))
    `(lambda (input)
       (declare (optimize (safety 0) (speed 3)))
       (block ,escape
	 (tagbody
	    ,@(loop for state in (states automata)
		 append (list state
			      `(ecase (read-char input nil ',eof-value)
				 ,@(loop for input in (alphabet automata)
				      collect `(,input (go ,(gethash (vector state input) (transition-table automata)))))
				 (',eof-value (return-from ,escape ',state))))))))))

The compiler is a dense. An example will help explain what happens. The output of compiling the example state machine is shown below.

(LAMBDA (REGULAR-LANGUAGE-COMPILER::INPUT)
  (DECLARE (OPTIMIZE (SAFETY 0) (SPEED 3)))
  (BLOCK #:ESCAPE-726
    (TAGBODY
     BASE
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO U))
	(#\d (GO D))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'BASE)))
     U
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO U))
	(#\d (GO BASE))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'U)))
     D
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO BASE))
	(#\d (GO DD))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'D)))
     UU
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO UUU))
	(#\d (GO U))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'UU)))
     DD
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO D))
	(#\d (GO DDD))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'DD)))
     UUU
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO UUU))
	(#\d (GO UU))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'UUU)))
     DDD
      (ECASE (READ-CHAR REGULAR-LANGUAGE-COMPILER::INPUT NIL '#:EOF-VALUE-727)
	(#\u (GO DD))
	(#\d (GO DDD))
	((QUOTE #:EOF-VALUE-727) (RETURN-FROM #:ESCAPE-726 'DDD))))))

This goto laden code is a two tier jump table.

An example of the same state machine hand written is below.

(with-input-from-string (input *inputs-example*)
  (symbol-macrolet ((value (read-char input nil 'eof-value)))
    (block escape
      (tagbody
       base (ecase value
	      (#\u (go u))
	      (#\d (go d))
	      (eof-value (return-from escape 'base)))
       u (ecase value
	   (#\u (go uu))
	   (#\d (go base))
	   (eof-value (return-from escape 'u)))
       d (ecase value
	   (#\u (go base))
	   (#\d (go dd))
	   (eof-value (return-from escape 'd)))
       uu (ecase value
	    (#\u (go uuu))
	    (#\d (go d))
	    (eof-value (return-from escape 'uu)))
       dd (ecase value
	    (#\u (go d))
	    (#\d (go ddd))
	    (eof-value (return-from escape 'dd)))
       uuu (ecase value
	     (#\u (go uuu))
	     (#\d (go uu))
	     (eof-value (return-from escape 'uuu)))
       ddd (ecase value
	     (#\u (go dd))
	     (#\d (go ddd))
	     (eof-value (return-from escape 'ddd)))))))

To write the compiler, I first hand wrote this state machine. Then, I wrote the compiler.

The benchmark results are impressive, but the interpreter is very slow. It uses a hash table rather than a 2D array. An interpreter that translates states and inputs to array indices might perform better. On the other hand, a better interpreter might be more complicated than my simple compiler.