Subvert the dominant paradigm

Since my last post on performance improvements I have achieved more speedups.

My primary test case is running an OMeta parser against the base.church runtime file. A critical factor in the performance of this type of parser is the memoization of previous parse results. (When the parser backtracks it may apply the same rule for the same input several times, if the results are memoized they can be reused instead of being recomputed).

Previously I had implemented a high-level hashtable in Church for the memo table. Due to the overhead of dynamic dispatch in the hashing and array access, this was quite slow. I replaced it with a low-level hashtable from kazlib. As a rule I have tried to minimize external dependencies for this project, but at this point I would rather reuse this external library than rewrite it in State.

Next I implemented inline caching for dynamic dispatch. By storing the argument types and the code pointer for the previous call in the “code vector” associated with a function, it’s possible to avoid the expensive lookup operation most of the time.

Lastly I also implemented inline caching for slot lookup. Slot lookup basically calculates the offset of the field within an object by counting all the slots in the class hierarchy. We cache this offset based on the argument type and the slot name.

All these changes yield a three-fold performance improvement. The test case now runs in 1 second versus 0.5 seconds for the Lisp implementation. The instruction read count is down from 13 billion before these changes to 2.7 billion.

This is a screenshot of the latest callgrind output. From this call graph for “church-make-closure” we can see that “church-alloc-object” is a candidate for optimization.

I have implemented a new calling convention for State. Functions now take:

<argument count> <closure pointer> <arg1> <arg2> ...

There are two special forms (load-argument-count) and (load-closure-pointer) for accessing these hidden arguments.

Adding an argument count allows implementation of inline caches (see next post) and a “rest parameter” which collects all extra parameters into a list

To implement the rest behaviour in the Church compiler I modified the church grammar to tag a rest parameter as a “:rest-var”

main args
     foo 1 2 3 4 5

foo a *rest
    print a
    print rest

this will print

1
[2 3 4 5]

and then arrange for the code to call out to some runtime code to construct the list:

(define |church-setup-rest-var| (lambda (rest-var-pointer arg-count fixed-param-count)
                                  (let ((rest-temp TAG_NIL)
                                        (remaining-temp (- arg-count fixed-param-count))
                                        (offset-temp 0))
                                    (tagbody
                                     check
;                                      (call-c-extern |printf| "remaining-temp %lu
;" remaining-temp)
                                       (if (= remaining-temp 0)
                                           (begin
                                            (set! (deref rest-var-pointer) (|church-reverse!| rest-temp))
                                            (go end)))
                                       (push (deref (+ rest-var-pointer offset-temp)) rest-temp)
                                       (set! offset-temp (+ offset-temp 4))
                                       (set! remaining-temp (- remaining-temp 1))
                                       (go check)
                                     end))))