List vs multiple values 2

[privet-kitty]

Summary

An implementation using a list can be as fast as the current implementation using multiple values if appropriate declarations (type and dynamic-extent) are put. If so, it is worth considering that future versions (0.3 or 0.4?) handle a list instead of multiple values.

I put the code of this experiment in a new branch: experiment.lisp

Body

Take the converter lchab-to-lrgb (LCH_ab to linear RGB) as an example, which is composed of the three converters, lchab-to-lab, lab-to-xyz, and xyz-to-lrgb. Below is the benchmark of the current implementation using multiple values.

(in-package :dufy-core)

;; Current implementation (automatically generated)
(declaim (inline lchab-to-lrgb)
         (ftype (function * (values double-float double-float double-float &optional))
                lchab-to-lrgb))
(defun lchab-to-lrgb (lstar cstarab hab &key (rgbspace +srgb+)
                      &aux (illuminant (rgbspace-illuminant rgbspace)))
  (declare (optimize (speed 3) (safety 1))
           (type real lstar cstarab hab))
  (multiple-value-call #'xyz-to-lrgb
    (multiple-value-call #'lab-to-xyz
      (lchab-to-lab lstar cstarab hab)
      :illuminant
      illuminant)
    :rgbspace
    rgbspace))

;; benchmark
(defun bench-mv-version (num &optional (sample 10))
  (let ((state (sb-ext:seed-random-state 1)))
    (format t "~&~F sec."
            (time-median sample ;; Repeats SAMPLE times and returns the median time.
              (print (loop repeat num
                           sum (multiple-value-call
                                   #'(lambda (x y z)
                                       (declare (double-float x y z))
                                       (+ x y z))
                                   (lchab-to-lrgb (random 100d0 state)
                                                  (- (random 128d0 state) 256d0)
                                                  (- (random 128d0 state) 256d0)))))))))

(bench-mv-version 5000000)
;; 0.969 sec.

And then the benchmark code for a list version will be as follows:

(defun bench-list-version (num &optional (sample 10))
  (let ((state (sb-ext:seed-random-state 1)))
    (format t "~&~F sec."
            (time-median sample
              (print (loop repeat num
                           sum (destructuring-bind (x y z)
                                   (list-lchab-to-lrgb (random 100d0 state)
                                                       (- (random 128d0 state) 256d0)
                                                       (- (random 128d0 state) 256d0))
                                 (declare (double-float x y z))
                                 (+ x y z))))))))

The problem is how we append the converters list-lchab-to-lab, list-lab-to-xyz, and list-xyz-to-lrgb into list-lchab-to-lrgb. The simplest way will be apply and rcurry:

(declaim (inline list-lchab-to-lrgb)
         (ftype (function * (values (%list double-float double-float double-float) &optional))
                list-lchab-to-lrgb))
(defun list-lchab-to-lrgb (lstar cstarab hab &key (rgbspace +srgb+)
                           &aux (illuminant (rgbspace-illuminant rgbspace)))
  (declare (optimize (speed 3) (safety 1))
           (type real lstar cstarab hab))
  (apply (alexandria:rcurry #'list-xyz-to-lrgb :rgbspace rgbspace)
         (apply (alexandria:rcurry #'list-lab-to-xyz :illuminant illuminant)
                (list-lchab-to-lab lstar cstarab hab))))

(bench-list-version 5000000)
;; 2.4135 sec.

(The type (%list double-float double-float double-float) here is equivalent to (cons double-float (cons double-float (cons double-float))).)

Unfortunately alexandria:rcurry doesn't seem to be efficient here. (Maybe extra type declarations make it a bit faster.) The second simplest and much faster way is to use destructuring-bind (or a compiler-macro like rcurry expanded to destructuring-bind):

(defun list-lchab-to-lrgb (lstar cstarab hab &key (rgbspace +srgb+)
                           &aux (illuminant (rgbspace-illuminant rgbspace)))
  (declare (optimize (speed 3) (safety 1))
           (type real lstar cstarab hab))
  (destructuring-bind (lstar astar bstar)
      (list-lchab-to-lab lstar cstarab hab)
    (declare (type double-float lstar astar bstar))
    (destructuring-bind (x y z)
        (list-lab-to-xyz lstar astar bstar :illuminant illuminant)
      (declare (type double-float x y z))
      (list-xyz-to-lrgb x y z :rgbspace rgbspace))))

(bench-list-version 5000000)
;; 1.219 sec.

It is, however, still slower than the reference.

By the way, the destructuring-bind of SBCL is expanded as follows:

(destructuring-bind (x y z)
        (list-lab-to-xyz lstar astar bstar :illuminant illuminant)
      (declare (type double-float x y z))
      (list-xyz-to-lrgb x y z :rgbspace rgbspace))

;; macroexpand =>

(let* ((#:g646
        (sb-c::check-ds-list
         (list-lab-to-xyz lstar astar bstar :illuminant illuminant) 3 3
         '(x y z)))
       (x (pop #:g646))
       (y (pop #:g646))
       (z (pop #:g646)))
  (declare (type double-float x y z))
  (list-xyz-to-lrgb x y z :rgbspace rgbspace))

In this case it will be effective to declare dynamic-extent and the type of the returned list. A desirable macro-expansion will be as follows:

(let* ((#:g650 (list-lab-to-xyz lstar astar bstar :illuminant illuminant))
       (x (car #:g650)))
  (declare (dynamic-extent #:g650)
           (type (%list double-float double-float double-float) #:g650)
           (type double-float x))
  (let* ((#:g651 (cdr #:g650))
         (y (car #:g651)))
    (declare (type (%list double-float double-float) #:g651)
             (type double-float y))
    (let* ((#:g652 (cdr #:g651))
           (z (car #:g652)))
      (declare (type (%list double-float) #:g652)
               (type double-float z))
      (list-xyz-to-lrgb x y z :rgbspace rgbspace))))
	  
;; The following expansion is simpler and works on SBCL though it appears to be illegal.
(let* ((#:g653 (list-lab-to-xyz lstar astar bstar :illuminant illuminant))
       (x (pop #:g653))
       (y (pop #:g653))
       (z (pop #:g653)))
  (declare (dynamic-extent #:g653)
           (type (%list double-float double-float double-float) #:g653)
           (type double-float x)
           (type double-float y)
           (type double-float z))
  (list-xyz-to-lrgb x y z :rgbspace rgbspace))

Such a macro (named typed-destructuring-bind) makes it faster than the previous one:

(defun list-lchab-to-lrgb
    (lstar cstarab hab &key (rgbspace +srgb+) &aux (illuminant (rgbspace-illuminant rgbspace)))
  (declare (optimize (speed 3) (safety 1))
           (type real lstar cstarab hab))
  (typed-destructuring-bind ((lstar double-float) (astar double-float) (bstar double-float))
      (list-lchab-to-lab lstar cstarab hab)
    (typed-destructuring-bind ((x double-float) (y double-float) (z double-float))
        (list-lab-to-xyz lstar astar bstar :illuminant illuminant)
      (list-xyz-to-lrgb x y z :rgbspace rgbspace))))
	  
(bench-list-version 5000000)
;; 0.968 sec.

Now we have (probably) achieved the same performance as the multiple-value version.

This issue has the same topic as #3.

[wasserwerk]

Great news! I would very appreciate the comeback of lists.

[privet-kitty]

I have dropped the most obvious version that manually expands an ideal rcurry:

(defun list-lchab-to-lrgb
    (lstar cstarab hab &key (rgbspace +srgb+) &aux (illuminant (rgbspace-illuminant rgbspace)))
  (declare (optimize (speed 3) (safety 1))
           (type real lstar cstarab hab))
  (apply #'(lambda (x y z)
             (declare (type double-float x y z))
             (list-xyz-to-lrgb x y z :rgbspace rgbspace))
         (apply #'(lambda (lstar astar bstar)
                    (declare (type double-float lstar astar bstar))
                    (list-lab-to-xyz lstar astar bstar :illuminant illuminant))
                (list-lchab-to-lab lstar cstarab hab))))

(dufy-core::bench-list-version 5000000)
;; 1.235 sec.