Automating widetag dispatch

I would like to optimize some (apply #'map-into ..) calls where the
sequence(s) passed are not created by me. That is, optimize the
non-open-coded MAP-INTO.

I gathered the pieces of the widetag dispatching code for
VECTOR-SUBSEQ* and wrote a general macro for creating dispatch tables.
Using the first parameter as the specialized array,
DEFINE-ARRAY-DISPATCH defines each specializing function with a
corresponding type declaration inside. VECTOR-SUBSEQ* may now be
written as:

(define-array-dispatch vector-subseq-dispatch (array start end)
  (declare (optimize speed (safety 0)))
  (declare (type index start end))
  (subseq array start end))

(defun vector-subseq* (sequence start end)
  (declare (type vector sequence))
  (declare (type index start)
           (type (or null index) end)
           (optimize speed))
  (with-array-data ((data sequence)
                    (start start)
                    (end end)
                    :check-fill-pointer t
                    :force-inline t)
    (vector-subseq-dispatch data start end)))

To slightly complicate matters, the current MAP-INTO is kludgy. With
that kludginess fixed[1], a basic MAP-INTO benchmark drops from 385ms
to 227ms. When we add widetag dispatching[2][3] on top of that fix, it
goes from 227ms to 110ms.

However it's not clear whether it is appropriate to do this
optimization inside SBCL since a time/space trade-off is involved. Is
an 86K core size increase (uncompressed) worth it? This is only for
MAP-INTO.

Of course, if a user wants performance then he should be using
declarations with the open-coded MAP-INTO. But there are still cases
where declarations can't easily be made, my own situation being one of
them.

It would be nice to have something like

(defmacro with-declared-array-type (array &body body)
  (check-type array symbol)
  `(typecase ,array
     , <at> (loop
          :for saetp
	  :across sb-vm:*specialized-array-element-type-properties*
          :collect `((simple-array ,(sb-vm:saetp-specifier saetp))
                     , <at> body))
     (otherwise
      , <at> body)))

available in userland. This would make it easier to do such
optimizations without depending upon internals. Ideally it would have
constant lookup, although the linear search with TYPEP is quick enough
for most purposes.

(Out of curiosity I implemented WITH-DECLARED-ARRAY-TYPE using a
stack-allocated vector of FLET functions, but this was slower than
TYPECASE even for the worst-case TYPEP search. A fast
WITH-DECLARED-ARRAY-TYPE seems possible in principle, though it would
presumably require new special operator(s) and/or magic.)

Getting back to SBCL innards, considering that SUBSEQ and FILL already
use widetag dispatch there may be another place which would benefit
from it. If so then [2] will help. If not then it may be needless
abstraction.

[1] 0001-fix-MAP-INTO-performance.patch -- same as bug #1001043

[2] 0002-automate-widetag-dispatching.patch

[3] 0003-widetag-dispatch-for-MAP-INTO.patch -- needs [1]

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/

_______________________________________________
Sbcl-devel mailing list
Sbcl-devel <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel