From: Fredrik Olofsson
Subject: dsp in lisp - speed?
Date: 
Message-ID: <151219991142277684%fredrik-hemma@ebox.tninet.se>
Newbie question:

I'm trying to use lisp for Digital Signal Processing but it seems too
slow (for me anyway).
How can I, for instance, make this funktion *alot* faster?

(defun convolution (x h)
  (let ((y (make-list (- (+ (length x) (length h)) 1) :initial-element
0)))
    (loop for i from 0 to (- (length y) 1)
          do
          (loop for j from 0 to (- (length h) 1)
                do
                (let ((temp (- i j)))
                  (if (and (>= temp 0)
                           (<= temp (- (length x) 1)))
                    (setf (nth i y) (+ (nth i y) (* (nth j h) (nth temp
x))))))))
    y))

Is this DSP thing a bad idea or am I just a bad programmer? I can
accept a few minutes of computation time for a big soundfile, but not a
few hours!

-- 
/Fredrik Olofsson

From: Warlock
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <3857777E.24D46501@prognoz.ru>
Fredrik Olofsson wrote:

> Newbie question:
>
> I'm trying to use lisp for Digital Signal Processing but it seems too
> slow (for me anyway).
> How can I, for instance, make this funktion *alot* faster?
>
> (defun convolution (x h)
>   (let ((y (make-list (- (+ (length x) (length h)) 1) :initial-element
> 0)))
>     (loop for i from 0 to (- (length y) 1)
>           do
>           (loop for j from 0 to (- (length h) 1)
>                 do
>                 (let ((temp (- i j)))
>                   (if (and (>= temp 0)
>                            (<= temp (- (length x) 1)))
>                     (setf (nth i y) (+ (nth i y) (* (nth j h) (nth temp
> x))))))))
>     y))
>
> Is this DSP thing a bad idea or am I just a bad programmer? I can
> accept a few minutes of computation time for a big soundfile, but not a
> few hours!

I think that the problem is in the data structures.
Use the arrays or sequences instead of lists - it must work faster.

Kind Regards
   Warlock
From: Thomas A. Russ
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <ymiln6v3ldv.fsf@sevak.isi.edu>
Fredrik Olofsson wrote:

> Newbie question:
>
> I'm trying to use lisp for Digital Signal Processing but it seems too
> slow (for me anyway).
> How can I, for instance, make this funktion *alot* faster?
>
> (defun convolution (x h)
>   (let ((y (make-list (- (+ (length x) (length h)) 1) :initial-element
> 0)))
>     (loop for i from 0 to (- (length y) 1)
>           do
>           (loop for j from 0 to (- (length h) 1)
>                 do
>                 (let ((temp (- i j)))
>                   (if (and (>= temp 0)
>                            (<= temp (- (length x) 1)))
>                     (setf (nth i y) (+ (nth i y) (* (nth j h) (nth temp
> x))))))))
>     y))
>
> Is this DSP thing a bad idea or am I just a bad programmer? I can
> accept a few minutes of computation time for a big soundfile, but not a
> few hours!

A number of things can help:

  1.  Use the VECTOR type instead of LIST for "y".  Lists are sequential
      access data structures, so (nth i y) takes time proportional to i.
  2.  Add type declarations.  This is particularly important if you are
      using floating point numbers, although from the initial value it
      looks like integers or fixnums are what you are using.
  3.  A type declaration of INTEGER is unlikely to improve matters, but
      FIXNUM will.  That is because Lisp integers include bignums, which
      are of arbitrary size, so the compiler can't really do much with
      an integer declaration.
  4.  Don't evaluate "(length x)" each time through the inner loop.
      Store the value in a variable and reference that, since it never
      changes.
  5.  (Maybe).  Move the binding of "temp" outside the loops and either
      use SETQ on it, or add it to the Loop clause.  This is marked
      maybe because I'm not sure if the compiler would need to do any
      extra work because of the binding form inside the loop.  I would
      just be paranoid.
  6.  Make sure you COMPILE THE FUNCTION before running it.  When it is
      debugged and running correctly, you can also ask the compiler to 
      optimize for speed by
        (declare (optimize (speed 3) (safety 0) (debug 0)))
  7.  COMPILE THE FUNCTION.
 

(defun convolution (x h)
  (declare (type (vector FIXNUM *) x h)
           (optimize (speed 3) (safety 0) (debug 0)))
  (let* ((length-of-x (length x))
         (length-of-h-minus-1 (- (length h) 1))
         (y (make-array (+ length-of-x length-of-h-minus-1)
             :initial-element 0)))
     (declare (type (vector FIXNUM *) y)
              (type fixnum length-of-x length-of-h-minus-1))
    (loop for i fixnum from 0 to (- (length y) 1)
          do (loop for j fixnum from 0 to length-of-h-minus-1
                   as temp fixnum = (- i j)
                   do (when (< -1 temp length-of-x)
	                 (setf (aref y i)
                            (+ (aref y i) (* (aref h j)
                                             (aref x temp)))))))
     y))

Note:  This assumes that x and h are vectors as well!  If not, then
       it would still probably be faster to coerce them to vectors
       and then use that instead:

    (let ((x-vector (coerce x 'vector)) ...))

-- 
Thomas A. Russ,  USC/Information Sciences Institute          ···@isi.edu    
From: ········@cc.hut.fi
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <m3n1r8hzn6.fsf@mu.tky.hut.fi>
Yet another version:

(defun convolution (x y)
  (declare (type (simple-array double-float (*)) x y)
           (optimize (speed 3) (safety 0) (debug 0)))
  (let* ((m (- (length x) 1))
         (n (- (length y) 1))
         (v (make-array (+ 1 m n) :element-type 'double-float)))
    (declare (type (simple-array double-float (*)) v)
	     (type fixnum m n))
    (loop for i fixnum from 0 below (length v)
      do (loop with sum double-float = 0.0d0
	   for j fixnum from (max 0 (- i m)) to (min i n)
	   do (incf sum (* (aref x (- i j))
			   (aref y j)))
	   finally (setf (aref v i) sum)))
    v))

The main points are:
- the conditional inside the innermost loop has been replaced by smarter
  loop bounds, and
- another micro-optimization which does help on x86 CMUCL is to accumulate
  the element sum in a local variable and only write to the destination
  vector once.
Besides, the original poster did not specify the data type, so I assume
that double-float is more appropriate than fixnum.

CMUCL compiles the innermost loop as follows:

     11E: L3:   MOV   EAX, ECX
     120:       SUB   EAX, EBX
     122:       MOV   [EBP-24], EAX
     125:       MOV   EAX, [EBP-24]
     128:       FSTPD FR0
     12A:       FLDD  [ESI+EAX*2+1]
     12E:       FSTPD FR2
     130:       FLDD  [EDI+EBX*2+1]
     134:       FXCH  FR2
     136:       FMULD FR2
     138:       FADD-STI FR1
     13A:       ADD   EBX, 4
     13D: L4:   CMP   EBX, [EBP-20]
     140:       JLE   L3

Even though I have never studied x86 assembly, I can tell that the moves
at offsets 122 and 125 are completely superfluous, since [EBP-24] is
referred nowhere else.

Hannu Rummukainen
From: Jonathan Coupe
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <8388nc$ekc$1@newsg1.svr.pol.co.uk>
Fredrik Olofsson <·············@ebox.tninet.se> wrote in message
·····································@ebox.tninet.se...
> Newbie question:
>
> I'm trying to use lisp for Digital Signal Processing but it seems too
> slow (for me anyway).
> How can I, for instance, make this funktion *alot* faster?
>
> (defun convolution (x h)
>   (let ((y (make-list (- (+ (length x) (length h)) 1) :initial-element
> 0)))
>     (loop for i from 0 to (- (length y) 1)
>           do
>           (loop for j from 0 to (- (length h) 1)
>                 do
>                 (let ((temp (- i j)))
>                   (if (and (>= temp 0)
>                            (<= temp (- (length x) 1)))
>                     (setf (nth i y) (+ (nth i y) (* (nth j h) (nth temp
> x))))))))
>     y))
>
> Is this DSP thing a bad idea or am I just a bad programmer? I can
> accept a few minutes of computation time for a big soundfile, but not a
> few hours!
>
> --

I'm still new-ish to Lisp, but even so I can see three things that you
should do to speed up this code:

1 Use type declarations
2 Use arrays - preferably simple arrays with element type declaration at
construction  - instead of lists
3 Use (declare (optimize ...))

Any decent Lisp book (at least if written for beyond the very raw beginner
level) should give you more information. I'd recommend either Graham's Ansi
Lisp or Norvig's "Paradigms." Actually, buy both.

How much of a speed up these extremely basic measures will give you is
complier dependent. For the compilers he tested back in 92(?) I think Norvig
quotes speed-ups of a round 40 (yes, forty) for such tactics, which
generally had the code he tested running at about the same speed as C or
Fortran. The work involved should take you about an hour of reading to
understand, then about five minutes of typing to implement.

Lisp offers a vast range of tradeoffs between flexibility, development
speed, and execution speed - this is a good thing. Even better, it makes
easy to switch these trade-offs around during program construction, much
more so than C++ does with its more limited range of behaviour in this
domain. But you have got to take some time to read the books and docs and
understand what the trade-offs are, otherwise the odds are you'll end up
making the wrong ones, which is what has happened to you.

While you're waiting for your books to arrive read up on "declare"
"optimize" "type" "the" and "compile-file" in your compiler docs and the
Ansi spec.

Finally, you don't mention which compiler you're using. They do vary in
execution speed - by a factor of around 8 from the slowest to the fastest,
from the benchmarks I've seen.

Jonathan

> /Fredrik Olofsson
From: Tim Bradshaw
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <ey3puw8jl8p.fsf@cley.com>
* Jonathan Coupe wrote:
> How much of a speed up these extremely basic measures will give you is
> complier dependent. For the compilers he tested back in 92(?) I think Norvig
> quotes speed-ups of a round 40 (yes, forty) for such tactics, which
> generally had the code he tested running at about the same speed as C or
> Fortran. The work involved should take you about an hour of reading to
> understand, then about five minutes of typing to implement.

For the given code, using a constant-time-structure like an array will
result in an improvement in complexity of the algorithm, so the
speedup can't be described by a number. 

(Of course if all your arrays are the same size, then it can).

--tim
From: Eugene Zaikonnikov
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <945267019.336639@lxms.cit.org.by>
Fredrik Olofsson <·············@ebox.tninet.se> wrote in message
·····································@ebox.tninet.se...
> Newbie question:
>
> I'm trying to use lisp for Digital Signal Processing but it seems too
> slow (for me anyway).
> How can I, for instance, make this funktion *alot* faster?
>
> (defun convolution (x h)
>   (let ((y (make-list (- (+ (length x) (length h)) 1) :initial-element
> 0)))
>     (loop for i from 0 to (- (length y) 1)
>           do
>           (loop for j from 0 to (- (length h) 1)
>                 do
>                 (let ((temp (- i j)))
>                   (if (and (>= temp 0)
>                            (<= temp (- (length x) 1)))
>                     (setf (nth i y) (+ (nth i y) (* (nth j h) (nth temp
> x))))))))
>     y))
>
> Is this DSP thing a bad idea or am I just a bad programmer? I can
> accept a few minutes of computation time for a big soundfile, but not a
> few hours!
>

Try this one instead:

(defun convolution (x h)
  (let ((y (make-array (1- (+ (length x) (length h))) :initial-element 0)))
    (declare (optimize (speed 3) (space 0) (safety 0) (debug 0))
             (type (simple-vector *) x h y))
    (loop for i fixnum from 0 below (length y) do
          (loop for j fixnum from 0 below (length h)
                for temp fixnum = (- i j) do
                (when (<= 0 temp (1- (length x)))
                  (incf (svref y i)
                        (* (svref h j) (svref x temp))))))
    y))

CL-USER 22 > (CONVOLUTION #(3 5 7) #(1 2 3 4))
#(3 11 26 41 41 28)

Few notes: this version uses arrays as more appropriate data structure for
your task. There is a good rule about lists: if you use NTH, then you
probably want to use array.
The OPTIMIZE part in the code above advices compiler to make emphasis on
speed when generating code.
Using type declarations like FIXNUM will allow to generate more efficient
numeric code for most of compilers. You may also want to add type
declarations for arithmetic operations, like (the fixnum (-  (the fixnum i)
(the fixnum j)) instead of (- i j), though it's better to define as a macro.
IIRC, http://www.alu.org has a good article on Lisp programming style.

--
  Eugene
  (concatenate 'string "viking" ·@" "cit.org.by")
From: Raymond Toy
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <4n4sdkgrmr.fsf@rtp.ericsson.se>
>>>>> "Eugene" == Eugene Zaikonnikov <······@removeme.cit.org.by> writes:

    Eugene> Fredrik Olofsson <·············@ebox.tninet.se> wrote in message
    Eugene> ·····································@ebox.tninet.se...
    >> Newbie question:
    >> 
    >> I'm trying to use lisp for Digital Signal Processing but it seems too
    >> slow (for me anyway).
[snip]
    >> Is this DSP thing a bad idea or am I just a bad programmer? I can
    >> accept a few minutes of computation time for a big soundfile, but not a
    >> few hours!
    >> 

    Eugene> Try this one instead:

    Eugene> (defun convolution (x h)
    Eugene>   (let ((y (make-array (1- (+ (length x) (length h))) :initial-element 0)))
    Eugene>     (declare (optimize (speed 3) (space 0) (safety 0) (debug 0))
    Eugene>              (type (simple-vector *) x h y))
    Eugene>     (loop for i fixnum from 0 below (length y) do
    Eugene>           (loop for j fixnum from 0 below (length h)
    Eugene>                 for temp fixnum = (- i j) do
    Eugene>                 (when (<= 0 temp (1- (length x)))
    Eugene>                   (incf (svref y i)
    Eugene>                         (* (svref h j) (svref x temp))))))
    Eugene>     y))


You didn't go far enough, as others have mentioned.  Add an
:element-type to the array, like so:

	(let ((y (make-array (1- (+ (length x) (length h)))
	                     :element-type 'double-float
                             :initial-element 0d0)))
           ...
and replace all svref's with aref.

With a good compiler, this should get you performance quite close to C
and Fortran, and the only consing should come from the array y, which
has to cons anyway.

Ray
From: Eugene Zaikonnikov
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <945274242.156066@lxms.cit.org.by>
Raymond Toy <···@rtp.ericsson.se> wrote in message
···················@rtp.ericsson.se...
>
> You didn't go far enough, as others have mentioned.  Add an
> :element-type to the array, like so:
>
> (let ((y (make-array (1- (+ (length x) (length h)))
>                      :element-type 'double-float
>                              :initial-element 0d0)))
>            ...
> and replace all svref's with aref.
>
Actually, I didn't go that far on purpose :) On my personal experience,
simple vector reference is significantly faster than any reference to a
vector with specialized element type.

(defun atest (n)
  (let ((y (make-array n
                       :element-type 'double-float
                       :initial-element 0d0)))
    (declare (optimize (speed 3) (space 0) (safety 0)))
    (loop for i fixnum from 0 below n do
          (setf (aref y i) (the double-float 2.22)))))

(defun svtest (n)
  (let ((y (make-array n
                       :initial-element 0d0)))
    (declare (optimize (speed 3) (space 0) (safety 0)))
    (loop for i fixnum from 0 below n do
          (setf (svref y i) (the double-float 2.22)))))


CL-USER 24 > (time (atest 1000000))

2.7 seconds used.
Standard Allocation 8000304 bytes.
Fixlen Allocation 8 bytes.
NIL

CL-USER 25 > (time (svtest 1000000))

0.3 seconds used.
Standard Allocation 4000256 bytes.
Fixlen Allocation 0 bytes.
NIL

CL-USER 28 > (lisp-implementation-type)
"LispWorks Personal Edition"

CL-USER 29 > (lisp-implementation-version)
"4.1.0 Beta"

--
  Eugene
  (concatenate 'string "viking" ·@" "cit.org.by")
From: Bernhard Pfahringer
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <838ige$5qr4$1@www.univie.ac.at>
In article <················@lxms.cit.org.by>,
Eugene Zaikonnikov <······@removeme.cit.org.by> wrote:
>
>Raymond Toy <···@rtp.ericsson.se> wrote in message
>···················@rtp.ericsson.se...
>>
>> You didn't go far enough, as others have mentioned.  Add an
>> :element-type to the array, like so:
>>
>> (let ((y (make-array (1- (+ (length x) (length h)))
>>                      :element-type 'double-float
>>                              :initial-element 0d0)))
>>            ...
>> and replace all svref's with aref.
>>
>Actually, I didn't go that far on purpose :) On my personal experience,
>simple vector reference is significantly faster than any reference to a
>vector with specialized element type.
>

True

(time (atest 1000000))
; cpu time (non-gc) 330 msec user, 0 msec system
; cpu time (gc)     30 msec user, 0 msec system
; cpu time (total)  360 msec user, 0 msec system
; real time  352 msec
; space allocation:
;  2 cons cells, 0 symbols, 8,000,048 other bytes
NIL

(time (svtest 1000000))
; cpu time (non-gc) 120 msec user, 10 msec system
; cpu time (gc)     20 msec user, 0 msec system
; cpu time (total)  140 msec user, 10 msec system
; real time  148 msec
; space allocation:
;  2 cons cells, 0 symbols, 4,000,048 other bytes
NIL

BUT:

you should also declare the TYPE of the array, then AREF wins!

(defun a+test (n)
  (let ((y (make-array n
                       :element-type 'double-float
                       :initial-element 0d0)))
    (declare (optimize (speed 3) (space 0) (safety 0))
             (type (simple-array double-float (*)) y))
    (loop for i of-type fixnum from 0 below n do
          (setf (aref y i) (the double-float 2.22d0)))))

(time (a+test 1000000))
; cpu time (non-gc) 80 msec user, 0 msec system
; cpu time (gc)     10 msec user, 0 msec system
; cpu time (total)  90 msec user, 0 msec system
; real time  97 msec
; space allocation:
;  2 cons cells, 0 symbols, 8,000,048 other bytes
NIL

Bernhard
-- 
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for  http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence          ········@ai.univie.ac.at 
From: Eugene Zaikonnikov
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <945282725.634952@lxms.cit.org.by>
Bernhard Pfahringer <········@hummel.ai.univie.ac.at> wrote in message
··················@www.univie.ac.at...
[snip]
> BUT:
>
> you should also declare the TYPE of the array, then AREF wins!
>
> (defun a+test (n)
>   (let ((y (make-array n
>                        :element-type 'double-float
>                        :initial-element 0d0)))
>     (declare (optimize (speed 3) (space 0) (safety 0))
>              (type (simple-array double-float (*)) y))
>     (loop for i of-type fixnum from 0 below n do
>           (setf (aref y i) (the double-float 2.22d0)))))
>
> (time (a+test 1000000))
> ; cpu time (non-gc) 80 msec user, 0 msec system
> ; cpu time (gc)     10 msec user, 0 msec system
> ; cpu time (total)  90 msec user, 0 msec system
> ; real time  97 msec
> ; space allocation:
> ;  2 cons cells, 0 symbols, 8,000,048 other bytes
> NIL
>
Let's agree that it is implementation-dependent :)

CL-USER 3 > (time (a+test 1000000))

1.5 seconds used.
Standard Allocation 8000304 bytes.
Fixlen Allocation 8 bytes.
NIL

Certainly it's better than original atest with 2.7 seconds, but still worse
than 0.3 secs of svtest.

--
  Eugene
  (concatenate 'string "viking" ·@" "cit.org.by")
From: Jason Trenouth
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <dLJYOMqhHHROT1E53hmjW06xJ=5k@4ax.com>
On Wed, 15 Dec 1999 20:35:14 +0200, "Eugene Zaikonnikov"
<······@removeme.cit.org.by> wrote:

> >     (declare (optimize (speed 3) (space 0) (safety 0))
> >              (type (simple-array double-float (*)) y))

Remember also:

	(debug 0) (compilation-speed 0) (float 0)

__Jason
From: Tim Bradshaw
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <ey3iu1zj7y0.fsf@cley.com>
* Eugene Zaikonnikov wrote:
> Certainly it's better than original atest with 2.7 seconds, but still worse
> than 0.3 secs of svtest.

I think you are missing the real issue here.  If you are forced to use
simple general vectors to do double-float stuff, then (assuming
double-floats don't have an immediate representation in general
vectors, which is likely to be true in a 32bit Lisp with 64bit
double-floats, but might *not* be true on a 64bit lisp), then you're
basically doomed to horrible performance because of float-consing.

So it needs to be the case that the system has a specialised array type
for double-floats. And if that's true then you won't be able to use
SVREF for it.

--tim
From: Tim Bradshaw
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <ey3ln6vj9m6.fsf@cley.com>
* Eugene Zaikonnikov wrote:
> Raymond Toy <···@rtp.ericsson.se> wrote in message
> ···················@rtp.ericsson.se...
> Actually, I didn't go that far on purpose :) On my personal experience,
> simple vector reference is significantly faster than any reference to a
> vector with specialized element type.

> (defun atest (n)
>   (let ((y (make-array n
>                        :element-type 'double-float
>                        :initial-element 0d0)))
>     (declare (optimize (speed 3) (space 0) (safety 0)))
>     (loop for i fixnum from 0 below n do
>           (setf (aref y i) (the double-float 2.22)))))

Try declaring the array type (yes, I know, the system should be able
to deduce this).

--tim
From: Timo Tossavainen
Subject: Re: dsp in lisp - speed?
Date: 
Message-ID: <385B41B4.D1F5D449@cs.uta.fi>
Fredrik Olofsson wrote:

> Is this DSP thing a bad idea or am I just a bad programmer? I can
> accept a few minutes of computation time for a big soundfile, but not a
> few hours!

As you already have read from the thread it was some of
your programming habits. Lisp is fast enough for DSP. Here
are some times for a small TB303-emulator compiled under
CMUCL-18b on my Celeron 450 generating 10 seconds of
monophonic sound at 44.1kHz.

  Seconds  |  Consed   |  Calls  |  Sec/Call  |  Name:
------------------------------------
     2.180 | 21,114,880 |       1 |    2.18000 | TB-303-RUN
     0.153 |         0 |   3,446 |    0.00004 | WTOSCIL-RUN
     0.113 |         0 |   3,446 |    0.00003 | MOOG-VCF-RUN
     0.093 |         0 |   3,446 |    0.00003 | TB-SEQ-RUN
     0.073 |         0 |   3,446 |    0.00002 | EXPENV-RUN
------------------------------------
     2.612 | 21,114,880 |  13,785 |            | Total

wtoscil is a basic wavetable oscillator, moogvcf is a 4-pole
resonant lpf, expenv is an exponential envelope with attack
and decay and tb-seq is a sequencer module that generates
control signals from note data. TB-303-RUN is not optimized
yet as it is still under development (conses) . As you can see it
can easily do realtime sound generation and the modules are
definitely not optimized enough...

Timo