0
$\begingroup$

I've been Googling "FIR filters" and "FFT convolution" etc. and I ran across something interesting.

Array Index vs. Pointers: http://www.bores.com/courses/intro/program/7_array.htm http://www.dspguru.com/dsp/tricks/fir-filtering-in-c

So, here's my question: Why is almost every "Fast!!" Fourier Transform function on the web using Array Indexing? (I just thought I would throw it out there.)

Improve this question
$\endgroup$
  • 1
    $\begingroup$ This may seem like a programming question, but it is actually an excellent practical implementation question. I would like to see some responses. $\endgroup$ – user2718 Mar 1 '13 at 23:08
  • $\begingroup$ Because indexing maps well to both the algorithm's most common descriptions, and to the instruction set of most popular CPU architectures (base+offset load/stores). $\endgroup$ – hotpaw2 Mar 2 '13 at 2:55
  • $\begingroup$ It depends on the processor, the compiler, and what you're trying to do (eg: see agner.org/optimize/optimizing_cpp.pdf , section 7.6, bottom of p. 35). For efficiency questions, timing your code is the ultimate test. And code readability, reliability, portability, etc. can also be important factors. $\endgroup$ – Kevin McGee Mar 2 '13 at 7:09
  • 3
    $\begingroup$ I vote to close this question, as it seems ill-formed for this site. The OP seems to have confusion between how arrays and pointers are treated in C/C++, which isn't really a signal processing issue. $\endgroup$ – Jason R Mar 2 '13 at 20:18
  • 1
    $\begingroup$ I think the question can be posed within the context of this forum. Mr. G- You've hit on the subject of bit-reversal with the FFT algorithm. Depending on the implementation of the FFT algorithm, you may get bit-reversed outputs or you may have to bit reverse your inputs. Some DSPs even offer bit-reversed addressing as a performance feature. I think it's certainly an important aspect of the algorithm. $\endgroup$ – Bryan Mar 6 '13 at 15:44
1
$\begingroup$

First link is broken, the second link is about unrolling loops, so it's not entirely clear (to me) what exactly you mean by "array indexing". Anyway most of this heavily depends on the instruction set of the processor. For example and FIR filter would have to do something like this (in the innner loop)

  • read filter coefficient
  • read delayed input sample (state variable)
  • multiply the two
  • add to accumulator
  • decrement coefficient pointer (or decrement coefficient read index)
  • increment state pointer (or increment state read index)
  • warp state pointer if needed (these tend to be circular buffers)
  • decrement loop counter, test for 0
  • jump to beginning of loop or past the loop depending on previous test

So that's a lot of stuff to do. Especially the "wrapping" part can be quite expensive as it includes a test for wrap around and a conditional which can break the pipeline on many processors.

Anyway on some processors, like a risc, or i86 this can easily take 10-20 cycles, on a dedicated DSP like an Analog devices Sharc or a TI TMS320 these take about half a cycle (can do two in a single CPU clock), so there is a huge dependency on instruction set efficiency. The tricks the second long talks about can help with avoiding the unwarpping part and also reduces the overhead for looping since you only do it once every 4 coefficients.

Improve this answer
$\endgroup$
  • $\begingroup$ The first link works for me, you really need to read it. Is anyone else having a problem with that link? $\endgroup$ – user3981 Mar 2 '13 at 15:00
  • $\begingroup$ Try Google cache $\endgroup$ – user3981 Mar 2 '13 at 15:08
  • 1
    $\begingroup$ The link works for me. The discussion claims array indexing compiles down to less efficient code than pointer references. Seems like this would be entirely dependent on the compiler/development tools/hardware. $\endgroup$ – user2718 Mar 2 '13 at 21:44
  • $\begingroup$ Ah, link works now. This is mostly non-sense (IMHO), any half way decent optimizing compiler will compile this into the same assembly code. $\endgroup$ – Hilmar Mar 6 '13 at 15:44
0
$\begingroup$

Since this was a semi-rhetorical question, the answer is - example code that you find on the web is often written for readability. Meaning, you should always look for ways to optimize it. Especially if said code is used in the field of DSP.

(feel free to close this question now)

Improve this answer
$\endgroup$