[Openmcl-devel] Type-of and positive/negative integers

[Steven Nunez]

 I'm doing this for performance. Here's the whole function; the coefficients typically have between 5-15 elements.

(declaim (inline evaluate-polynomial))
(defun %evaluate-polynomial (coefficients x)
  "Return the sum of polynomials, weighted by the list of COEFFICIENTS, at X.
X and contents of COEFFICIENTS must be of the same type.
COEFFICIENTS are in descending order from the highest degree down to the constant term."
  (declare (optimize(speed 3)(safety 0))
       #+sbcl (sb-ext:muffle-conditions sb-ext:compiler-note)) ; Function declared inline, but SBCL whines
       ;; See https://groups.google.com/forum/#!msg/comp.lang.lisp/AsKvR0emFtU/ILVjmLTlJ50J
  (assert (and (plusp (length coefficients))
             (every (lambda (elt)
              (typep elt (class-of x)))
                coefficients))
      (coefficients x)
      "Coefficients and X must be of the same type.")
  (etypecase x
    (double-float
     (let((sum (car coefficients)))
       (declare (double-float sum x))
       (loop for i double-float in (cdr coefficients)
      do (setf sum (+ i (* x sum))))
       sum))
    (single-float
     (let((sum (car coefficients)))
       (declare (single-float sum x))
       (loop for i single-float in (cdr coefficients)
      do (setf sum (+ i (* x sum))))
       sum))
    (fixnum
     (let((sum (car coefficients)))
       (declare (fixnum sum x))
       (loop for i fixnum in (cdr coefficients)
      do (setf sum (+ i (* x sum))))
       sum))))

I haven't needed to optimize to any great degree before, but here we're at the bottom levels and this gets called a great many times. I'm just a little surprised there is such a high cost in typep. As I understand your reply, even doing this over a small sequence is going to kill performance (or rather make the declarations pointless given the cost/benefit of the assert). Your suggestion of a specialized arrays would be a good way out, as I already have one that is frequently used:
(deftype simple-double-float-vector (&optional (length '*))
  "Simple vector of double-float elements."
  `(simple-array double-float (,length)))
Thanks.




    On Thursday, October 24, 2019, 7:38:23 PM GMT+8, Stas Boukarev <stassats at gmail.com> wrote:  
 
 On Thu, Oct 24, 2019 at 10:44 AM Steven Nunez <steve_nunez at yahoo.com> wrote:
>
> Okay, having a specialised representation for positive integers makes sense as a further specialisation of INTEGER. I wish this was documented somewhere, a 1 minute google search did not turn up anything.
>
> I still have the problem of ensuring that the parameters to a function, a sequence and a number, are all of the same type so I can dispatch on specialised (typed declared) versions of loop. At the moment I have:
>
>  (assert (and (plusp (length coefficients))
>                (every (lambda (elt)
>                          (typep elt (type-of x)))
>                        coefficients)))
>
> which works fine for single-float and double-float, but fails if any of the coefficients are negative because their type-of is FIXNUM whilst the X or other coefficients may be (INTEGER 0 4611686018427387903)
>
> Any ideas?
Are you doing it for performance? Any performance gains you get from
declaring your variables in a loop will be destroyed by performing
typep at runtime.
The cost of determining type-of, parsing it and applying typep on it
is going to be very high, especially if it's done on every element of
a sequence.
If you do need to perform that operation, you can do
(defun foo (x sequence)
  (macrolet ((make-test (x types)
              `(etypecase ,x
                  ,@(loop for type in types
                          collect `(,type (lambda (x) (typep x ',type)))))))
    (every (make-test x (double-float single-float fixnum))
          sequence)))

Maybe even putting EVERY inside the expansion, to get better inlining.
And handle specialized arrays without going through each element.
  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.clozure.com/pipermail/openmcl-devel/attachments/20191024/bbfabdbe/attachment.htm>