Re: LW compiler optimizations
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]>
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
I once had a specialized SONY co-processor that could do 4- and 16-ply Butterfly operations. (ca. 1990) I see that even Apple could use these extended Butterfly ops. They only give access to a conventional 2-ply butterfly. > On Jan 13, 2025, at 07:59, David McClain <[email protected]> wrote: > > There ought to be a way to extend an underlying Lisp implementation, like we have in almost every Forth system. But this also requires detailed knowledge of the layout of data in memory, how to access the contents of bindings, etc. > > I’m thinking that something like a vector MAC is so simple, and yet so fundamental to so many DSP algorithms, that it would be worthwhile having it as an extension to the Lisp system. And probably not just for DSP calculations - I think it would also apply over bignum arithmetic to finite-field calculations used in every corner of cryptography. Hence a huge economic value. > > … and then, while you are at it, add a Fourier Butterfly operation as a fundamental operation. That not only helps DSP, but also bignum multiply, NTT (Number Theoretic Transforms) over finite fields, and again cryptography. > > > > >> On Jan 13, 2025, at 07:47, David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote: >> >> And yet, if I follow that advice in the simple DOTIMES loop, I get even worse timings than before. >> >> So the boxing advice only seems to apply to the innards of a closure being mapped across the arrays. Otherwise, avoid this advice. >> >> >> >>> On Jan 13, 2025, at 07:41, David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote: >>> >>> So I see that the inner closure is calling Compiler Double-float Box on the computation. The allocations must be reflecting that across 5633 calls, which translates to 48 bytes per call. >>> >>> So to see if I can get rid of boxing, I set up the SUM as a one-element array, specialized to double-float elements. And sure enough, that more than doubled the speed and cut the allocations down to a little over half the original number. >>> >>> Oddly, when I reran my bench test, at the start, this time the mapping routine took twice as long as in my earlier bench tests. (very puzzling behavior) >>> >>> So now with the 1 element array SUM, I’m back to 124 μs/invocation on 5633 elements. >>> >>> But the fact remains, if you want to avoid boxing, use a specialized array destination for the computed result. >>> >>>> On Jan 13, 2025, at 07:13, David McClain <[email protected]> wrote: >>>> >>>> I divided down the allocations to per-invocation costs. >>>> >>>> The worst offender in this regard is the implementation that MAP’s a closure across the pairs of elements in the dot-product. It takes a whopping 270 kB per buffer dot-product. >>>> >>>> And yet it is so simple. The closure should only be formed just once per invocation. >>>> >>>> (defun fir-dotpr-map (fir vec &key (start2 0)) >>>> ;; 128 μs/invocation for 5633 element vectors >>>> ;; 270,502 bytes/invocation >>>> #F >>>> (declare ((vector double-float *) fir vec) >>>> (fixnum start2)) >>>> (let ((sum 0d0) >>>> (v (make-array (length fir) >>>> :element-type 'double-float >>>> :displaced-to vec >>>> :displaced-index-offset start2))) >>>> (declare (double-float sum) >>>> ((vector double-float *) v) >>>> (dynamic-extent v)) >>>> (map nil (lambda (a b) >>>> (declare (double-float a b)) >>>> (incf sum (* a b))) >>>> fir v) >>>> sum)) >>>> >>> >> >