From fc053e7df033d7fb70f389579105326e2f13c9a0 Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Sat, 8 Feb 2014 21:02:08 +0000 Subject: [PATCH] some benchmarketing. --- els-specializers.org | 56 +++++++++++++++++++++++++++++++++++++++----- 1 file changed, 50 insertions(+), 6 deletions(-) diff --git a/els-specializers.org b/els-specializers.org index b4e3e79..d7e129d 100644 --- a/els-specializers.org +++ b/els-specializers.org @@ -143,11 +143,26 @@ #| XXX insert motivating example from Newton/Rhodes here |# #+end_src ** signum - NB this example can definitely be done using filtered dispatch. + Our second example of the implementation and use of generalized + specializers is a reimplementation of one of the examples in + \cite{Costanza.etal:2008}: specifically, the factorial function. + Here, we will perform dispatch based on the =signum= of the + argument, and again, at most one method with a =signum= specializer + will be appliable to any given argument, which makes the structure + of the specializer implementation very similar to the =cons= + specializers in the previous section. - Point out obvious similarity between this and car-of-cons. Note - the subtlety, though, in generalizer-of-using-class / signum wrt - rational vs floating point arguments + We have chosen to compare signum values using \texttt{=}, which + means that a method with specializer =(signum 1)= will be + applicable to positive floating-point arguments (see the first + method on =specializer-accepts-generalizer-p= and the method on + =specializer=accepts-p= below). This leads to one subtle + difference in behaviour compared to that of the =cons= + specializers: in the case of =signum= specializers, the /next/ + method after any =signum= specializer can be different, depending + on the class of the argument. This aspect of the dispatch is + handled by the second method on =specializer-accepts-generalizer-p= + below. #+begin_src lisp (defclass signum-specializer (specializer) ((%signum :reader %signum :initarg :signum))) @@ -176,13 +191,42 @@ (and (realp o) (= (%signum s) (signum o)))) #| again elide more boring methods |# +#+end_src + +Given these definitions, and some more straightforward ones elided for +reasons of space, we can implement the factorial function as follows: +#+begin_src lisp (defgeneric fact (n) (:generic-function-class signum-generic-function)) (defmethod fact ((n (signum 0))) 1) (defmethod fact ((n (signum 1))) (* n (fact (1- n)))) -(defmethod fact ((n (signum -1))) - (error "factorial of negative number: ~D" n)) +#+end_src + +We do not need to include a method on (signum -1), as the standard +=no-applicable-method= protocol will automatically apply to negative +real or non-real arguments. + +Benchmarketing: we chose to benchmark 20! because that is the largest +factorial whose answer fits in SBCL's 63-bit fixnums, so as to attempt +to measure the maximum effect of dispatch (unobscured by allocation / +gc issues) + +| fact (signum-gf) | %fact (fun) | %%fact (gf / 1meth) | fact (signum-gf / 1arg hash-special-case) | +|------------------+-------------+---------------------+-------------------------------------------| +| 0.284 | 0.004 | 0.016 | 0.032 | +| 0.076 | 0.008 | 0.012 | 0.024 | +| 0.072 | 0.004 | 0.012 | 0.116 | +| 0.264 | 0.004 | 0.008 | 0.120 | +| 0.292 | 0.008 | 0.012 | 0.120 | +| 0.264 | 0.004 | 0.016 | 0.084 | +| 0.276 | 0.008 | 0.012 | 0.092 | +| 0.264 | 0.008 | 0.012 | 0.036 | +| 0.276 | 0.008 | 0.004 | 0.104 | +| 0.272 | 0.004 | 0.012 | 0.020 | + +#+begin_src lisp +(progn (gc :full t) (time (dotimes (i 10000) (%fact 20)))) #+end_src ** HTTP Accept header implement RFC2616 content negotiation -- 2.30.2