Method call optimization - avoiding next-method
Gauche's object system is a direct descendant of stklos, which is
based on TinyCLOS. Each method takes an implicit parameter,
next-method, which is bound to a next-method object and
can be used to invoke the less specific method
in a method chain. It is similar to the
super method in
class-oriented object systems. However, the next-method object
the actual arguments used in the method's invocation.
That is, when it is called without arguments, it should pass the original
arguments to the next method:
gosh> (define-method foo ((a <number>)) `((number ,a))) #<generic foo (2)> gosh> (define-method foo ((a <real>)) (cons `(real ,a) (next-method))) #<generic foo (2)> gosh> (foo 3) ((real 3) (number 3))
(foo <real>) passes
to the next method,
(foo <number>). Note that
the next-method object is a first-class object, so
for example, it can be saved to a global variable:
gosh> (define nm #f) nm gosh> (define-method foo ((a <real>)) (set! nm next-method) nm) #<generic foo (2)> gosh> (foo 3) #<next-method (#<method (foo <number>)>)0 (3)> gosh> nm #<next-method (#<method (foo <number>)>)0 (3)>
And invoked later:
gosh> (nm) ((number 3))
This means that a next-method object must be allocated for every invocation of a method. In many cases, though, next-method isn't used at all in the method body, so it's a waste. Can we do something?
An easy path would be to let programmers indicate whether the method want to use next-method or not, probably using a CL-style method qualifier. But it's kind of silly---whether the method uses next-method or not is already shown in the code; why the programmer need to bother to say it again?
Fortunately, during compilation,
we track how many times each local variable is referenced.
So at some point in the compiler passes, we know whether
next-method is used in the method body or not. We can
extract that information and save in the method object, and
when the method is invoked we check it and avoid next-method
creation if possible.
define-method form is expanded as follows:
(define-method name ((arg spec) ...) <method-body>) | v (add-method! name (make <method> ... :specializers (spec ...) :body (lambda (next-method arg ...) <method-body>)))
The body of the method is just a plain lambda form; it has nothing special about being a method body. So the compiler can't treat method body differently.
Instead, we introduced a general mechanism to save a list of unused argument in each closure; it is a meta-information and saved along source-code information.
<method> initializer looks that information to find out
next-method argument is used. If not, it sets
method-leaf flag of the method object.
The method invocation code looks at the flag and omits creation of next-method object.
Let's see how effective this optimization is. This is the benchmark script.
(use gauche.time) ;; method without next-method (define-method foo (x) #t) ;; method with next-method (for comparison) (define-method bar (x) (when x (next-method))) ($ time-these/report 10000000 `((foo . ,(cut foo #f)) (bar . ,(cut bar #f))))
Benchmark: ran foo, bar, each for 10000000 times. foo: 2.021 real, 3.550 cpu (3.470 user + 0.080 sys)@2816901.41/s n=10000000 bar: 2.099 real, 3.680 cpu (3.570 user + 0.110 sys)@2717391.30/s n=10000000
Benchmark: ran foo, bar, each for 10000000 times. foo: 1.313 real, 1.740 cpu (1.730 user + 0.010 sys)@5747126.44/s n=10000000 bar: 2.051 real, 3.670 cpu (3.570 user + 0.100 sys)@2724795.64/s n=10000000
In wall-clock time, it's about 35% speedup (actually, averaging multiple runs show it's more like 40%). It's also interesting that CPU time is halved---since GC runs in parallel, it indicates this modification generates a lot less garbage, hence less GC time.
Note: Since 0.9.6's built-in methods will be pre-compiled by the 0.9.5 compiler, you won't see the effect of this optimization on built-in methods in the 0.9.6 release. You'll need to rebuild the source with 0.9.6.
There are still lots of room of optimization in our method dispatch mechanism, and we'll explore it more in the comping releases.
Tags: 0.9.6, next-method
Post a comment