Tutorial 1: An Introduction - markcox80/specialization-store GitHub Wiki

This tutorial uses the specialization-store system to implement a function, named naxpy, which performs the operation

y = ax + y

where y and x are objects which "contain" numbers and a is a number.

We seek to specialize this operator to specific argument types in order to improve run-time performance.

The requirements on the naxpy operator are:

  1. The operator destructively modifies the input argument y.
  2. The operator returns no values.
  3. The containers x and y contain the same number of numbers.

The macro defstore is used to add a new store function to the global environment. The syntax of defstore is

defstore store-name store-lambda-list &body store-options

The naxpy store function can be introduced by evaluating the following code

(defstore naxpy (a x y))

The behavior of a store function is determined by the store function object, the type of arguments given to the function and the set of specializations added to the store function.

A specialization encapsulates a function, a domain for which the function is defined and the result type of the function.

Specializations are added to a store function using the defspecialization macro. The syntax for this operator is

defspecialization store-name specialized-lambda-list result-type &body body

The following code uses defspecialization to add a specialization that is defined for all numbers and sequences.

(defspecialization naxpy ((a number) (x sequence) (y sequence)) (values)
  (unless (zerop a)
    (map-into y (lambda (x-i y-i)
                  (+ (* a x-i) y-i))
              x y))
  (values))

Note that we omit error checking for the sake of presentation.

The above implementation performs a function call per element in the sequence. We can eliminate this overhead if we know the representation of the containers x and y.

The following specialization is specific to containers of type list.

(defspecialization naxpy ((a number) (x list) (y list)) (values)
  (unless (zerop a)
    (loop
      for sub-y on y
      for x-i in x
      for y-i = (car sub-y)
      do
         (incf (car sub-y) (* a x-i))
  (values))

The specialization below is for containers of type array.

(defspecialization naxpy ((a number) (x array) (y array)) (values)
  (unless (zerop a)
    (dotimes (i (array-total-size x))
      (incf (row-major-aref y i) (* a (row-major-aref x i)))))
  (values))

An important detail in the above specializations is the use of (unless (zerop a) ...). One could have introduced the following specialization.

(defspecialization naxpy ((a (satisfies zerop)) (x t) (y t)) (values)
  (declare (ignore a x y))
  (values))

Unfortunately, it is undefined which specialization a store function applies in situations where the above (satisfies zerop) specialization and one of the list or array specializations are also applicable. Consider the application of naxpy in the following example.

(defun example ()
  (let* ((x (list 1 2 3))
         (y (list 4 5 6)))
    (naxpy 0 x y)))

The process of selecting the most applicable specialization for arguments given to a store functions of fixed arity is:

  1. Remove specializations that are not applicable.
  2. Remove specialization x with domain X if there exists another specialization whose domain is a subset of X.
  3. Apply one of the remaining specializations to the arguments.

Applying this procedure to the example above we find two specializations remaining before entering step 3.

  • (defspecialization naxpy ((a (satisfies zerop)) (x t) (y t)) ...)
  • (defspecialization naxpy ((a number) (x list) (y list)) ...)

According to step 3, it is undefined which of the two specializations is invoked.

This highlights an important premise of the specialization-store system, specifically, all specializations have the same effect.

The premise is broader then required but it provides easy guidance for the kind of problems the specialization store system is useful for i.e. operators where knowledge of object representation can improve run-time performance.