Optimizing a function over multiple types for its arguments - pro - mailman3.common-lisp.net

27 Nov 2017


      While I was working on qbase64[1], I stumbled over a peculiar problem:
I wanted it to work as fast as possible when optimized array types
(SIMPLE-ARRAY, SIMLPE-BASE-STRING, etc.) were passed to the
encoding/decoding routines, but I also wanted to support the more
general types.
If I defined my core encoding routine like this:
(defun %encode (bytes string)
  (declare (type (simple-array (unsigned-byte 8)) bytes))
  (declare (type simple-base-string string))
  (declare (optimize speed))
  ...)
SBCL would produce very fast code, but the function would no longer
work for other ARRAY or STRING types:
And if I was to redefine the routine with more general types:
(defun %encode (bytes string)
  (declare (type array bytes))
  (declare (type string string))
  (declare (optimize speed))
  ...)
The code produced would be significantly slower.
My solution to this conundrum was to create a macro that would take
all the different type combinations I wanted to optimize and support
upfront:
(defun/td %encode (bytes string)
    (((bytes (simple-array (unsigned-byte 8))) (string simple-base-string))
     ((bytes (simple-array (unsigned-byte 8))) (string simple-string))
     ((bytes array)                            (string string)))
  (declare (optimize speed))
  ...)
and generate code which would dispatch over the type combinations,
then use LOCALLY to actually declare the types and splice the body in:
(defun %encode (bytes string)
  (cond
    ((and (typep bytes '(simple-array (unsigned-byte 8)))
          (typep string 'simple-base-string))
     (locally
       (declare (type bytes (simple-array (unsigned-byte 8))))
       (declare (type string simple-base-string))
       (declare (optimize speed))
       ...))
    ((and (typep bytes '(simple-array (unsigned-byte 8)))
          (typep string 'simple-string))
     (locally
       (declare (type bytes (simple-array (unsigned-byte 8))))
       (declare (type string simple-string))
       (declare (optimize speed))
       ...))
    ((and (typep bytes 'array)
          (typep string 'string))
     (locally
       (declare (type bytes array))
       (declare (type string string))
       (declare (optimize speed))
       ...))
    (t (error "Unsupported type combination"))))
If the run-time dispatch incurs a slight penalty, it is more than
offset by gains made by using optimized array types, esp. since these
routines have to typically visit every element of the given arrays.
I was wondering if there was a better way to do this. Have I missed a
trick or two?
I was reading about the Lisp Interface Library[2] which supports
parametric polymorphism, but not sure if it would result in optimized
code like the one my macro generates.
Chaitanya
1. https://github.com/chaitanyagupta/qbase64
2. https://common-lisp.net/%7Efrideau/lil-ilc2012/lil-ilc2012.html