CSS-Selectors: quicker compiler with lambda trees

CSS-Selectors and TALCL are both, at heart, translators from some language (css-selectors and xml respectively) into compiled common lisp functions. We translate these expressions by translating the source language into a tree of common-lisp, inserting that common-lisp into a lambda form, then calling compile on that lambda. Because this is a central part of the utility they provide, slow compilation speed can be somewhat annoying. This led to me implementing compiler macros and other caching schemes so that compiling could be handled at compile time (when possible/constantp), where the slow compilation would be less problematic.

A while back I read an article by Xach about compiling queries without calling either “eval” or “compile” by utilizing lambda building functions. He wrote that this technique yielded much quicker compilation and no real loss of performance. To investigate, I wrote a second compiler for CSS-Selectors utilizing this compilation technique. I then wrote tests to compare this new compiler with the old.

Below are the results comparing the two compilers. My experiment confirmed Xachs findings from 2007. The lambda tree version of the compiler is MUCH quicker (~1000x in SBCL) with comparable execution speed. This hasn’t sped up the (cl-yacc produced) parser, so I think that much of the caching and compiler macro code is still valid and still saving user time, just less crucially so now. The only downside I saw was that debugging was a touch harder because there was no human readable version of the fully translated expression (which I could get from the old translator).

15:37:03 BEGIN Running Test TEST-COMPILER1-SPEED | form translation and compile
Evaluation took:
7.266 seconds of real time
7.140000 seconds of total run time (5.840000 user, 1.300000 system)
[ Run times consist of 1.780 seconds GC time, and 5.360 seconds non-GC time. ]
98.27% CPU
606 forms interpreted
6,262 lambdas converted
18,119,140,305 processor cycles
683,883,136 bytes consed

15:37:11 BEGIN Running Test TEST-COMPILER2-SPEED | lambda trees
Evaluation took:
0.008 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
0.00% CPU
19,072,358 processor cycles
1,572,384 bytes consed

Evaluation took:
0.907 seconds of real time
0.890000 seconds of total run time (0.880000 user, 0.010000 system)
[ Run times consist of 0.080 seconds GC time, and 0.810 seconds non-GC time. ]
98.13% CPU
2,261,249,550 processor cycles
39,185,920 bytes consed

Evaluation took:
0.881 seconds of real time
0.850000 seconds of total run time (0.840000 user, 0.010000 system)
[ Run times consist of 0.040 seconds GC time, and 0.810 seconds non-GC time. ]
96.48% CPU
2,196,945,765 processor cycles
39,155,152 bytes consed

Source Code:

One thought on “CSS-Selectors: quicker compiler with lambda trees

  1. I’m glad you found the article useful. Just wanted to emphasize that part of the issue is that SBCL’s compiler is really slow, but it also does a lot of work. For a language that has complicated semantics that can be heavily optimized in some situations, it’s worth it. The simple closure-tree technique would also get slow if it did the same amount of work.

    Regarding debugging, I’ve wondered about that, and I think I would introduce a stage in the closure generation that would e.g. allow naming the closure and tracing its arguments and return values based on some debug flag.

Leave a Reply

Your email address will not be published. Required fields are marked *