Conceptual model for pointer arithmetic in FIR filter implementation?

In preparing a class on DSP, with programming, I want to explain the
following piece of code that implements the inner loop of an FIR:

      *(y+n) = 0;
      for (k = 0; k <= n; k++) {
         *(y+n) += *(h+k)*(*(x+n-k));

An equivalent implementation using arrays would be:

    y[n] = 0;
      for (k = 0; k <= n; k++) {
         y[n] += h[k] * x[n - k];

Now, the array approach is clearly closer to the math (it is very close to
the difference equation).

The pointer approach is because the programmer declares y as a pointer:

    fractional* y = dstSamps;

and dynamically allocates memory using a function that returns a pointer:

So, the programmer chose to keep his code consistent with his declaration
(ie to continue to use pointers).

Apart from the dynamic allocation, the two ways of writing result in
identical code produced by the compiler (as they should..).

So my initial reaction is that the pointer code is implementation-oriented,
while the array code is math-oriented. I can show how the array code arises,
then discuss the implementation details and so explain the programmer's
choices.

But then I tried to think of a conceptual model that would let me directly
explain the pointer code. For example, modelling not from difference
equations but from a diagram showing the lists of coefficients, samples etc.
But here I kept finding I had to come back to implementation details - "it
points to an address in memory" whereas I want to explain in terms of the
math (or more correctly the application).

Question: can anyone suggest a pointer to discussion or explanation of DSP
that directly uses a conceptual model close to pointers?

Second question: is the programmer right to keep his code consistent with
declaration, or is there a higher imperative that means he should have used
a more easily understood conceptual model using arrays?

Thanks,

Chris
==============================
Chris Bore
BORES Signal Processing
chris@bores.com
www.bores.com

"Chris Bore" <chris_bore@yahoo.co.uk> wrote in message
news:468debd2.0410130644.3ce25dcf@posting.google.com...

other stuff snipped

> Second question: is the programmer right to keep his code consistent with
> declaration, or is there a higher imperative that means he should have
used
> a more easily understood conceptual model using arrays?
>

Hello Chris,
Often I will 1st implement something using the array notation just so I get
it functioning. Then once I built up some test vectors, I will write more
efficient (from the point of view of the processor) code and debug using the
test vectors.

You will probably find several schools of thought on this. I also believe
they each have a place. If one needs to run his code as fast as possible,
then all stops are pulled when it comes to writing the code. (However good
comments should reside with the code)  But when teaching new students how to
do stuff, I think you will need to show both approaches. How much time you
spend on each approach will depend on how comfortable they are with
pointers. A very important point with using pointers and or array indexing
is not having to move all of the data. The standard DSP structures are
easily understood in terms of shift registers, but as you know this is just
not an efficient way to do things in software. The array indexing verses
pointers brings up the important issue of data structures and their
accessability. The array form is more general in that it allows random
access although at the cost of an added indirection. The pointer approach is
great for sequencial access.

I think part of your question brings up a big part of practical DSP. I.e.,
I'm referring to the tricks and techniques that are used to efficiently
perform the signal processing. And the basic ideas of data manipulation and
data structures comes into play.

IHTH,
Clay S. Turner

Chris Bore wrote:
> In preparing a class on DSP, with programming, I want to explain the
> following piece of code that implements the inner loop of an FIR:
> 
>[SNIP]
> 
> Second question: is the programmer right to keep his code consistent with
> declaration, or is there a higher imperative that means he should have used
> a more easily understood conceptual model using arrays?
> 

In a class situation the answer would be very audience dependent.

If the class objective is how to write fastest/smallest/bestest/??? code 
you may have one answer.

If understanding what the code ACCOMPLISHES, you may get a different answer.

Personally I understand matrices. Pointers disorient me;}
[ yep write as little C as possible :]!

Chris Bore wrote:

> In preparing a class on DSP, with programming, I want to explain the
> following piece of code that implements the inner loop of an FIR:

>       *(y+n) = 0;
>       for (k = 0; k <= n; k++) {
>          *(y+n) += *(h+k)*(*(x+n-k));

> An equivalent implementation using arrays would be:

>     y[n] = 0;
>       for (k = 0; k <= n; k++) {
>          y[n] += h[k] * x[n - k];

Assuming this is C, the two are exactly equivalent, sort
of by definition.   The first one will work when x and y
are arrays, the second one will work when they are pointers.
One is easier for people to read, the compiler doesn't care.

Even more, note that the [] operator is commutative in C.

y[n] is exactly the same as *(y+n) by definition.

*(y+n) is the same as *(n+y) commutative property of addition

*(n+y) is the same as n[y] by the same definition as above.

Try running the last one as:

  n[y] = 0;
  for (k = 0; k <= n; k++) {
     n[y] += k[h] * (n-k)[x];

Now, there is some belief that using pointers with
autoincrement is faster than indexing, but even that is
questionable.

    y[n]=0;
    yy=y;
    xx=x+n;
    hh=h;
    for(k=0; k<=n, k++) *yy++ += *hh++ * *yy--;

It may have been true on the PDP-11 with early C compilers.
It is much less obvious with modern processors and compilers
that it is faster.  Especially when the compiler has to check
for aliasing (different pointer variables pointing to the
same array) it can be much slower.  (Consider that x and y
could be the same array.)

-- glen

My opinion is similar as Glen's

I don't see a REAL reason to do it with pointer arithmetic, when it can be
much clearer and easier to understand when done with indexing.

Performance? Well, with modern C compilers, the indexing approach can take
very good advantage of processor resources.

JaaC

--
Jaime Andr�s Aranguren Cardona
jaac@nospam.sanjaac.com
SanJaaC Electronics
Soluciones en DSP
www.sanjaac.com

(Remove "nospam" from e-mail address)

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> escribi&#4294967295; en el mensaje
news:ckjpt6$1qr$1@gnus01.u.washington.edu...
>
> It may have been true on the PDP-11 with early C compilers.
> It is much less obvious with modern processors and compilers
> that it is faster.  Especially when the compiler has to check
> for aliasing (different pointer variables pointing to the
> same array) it can be much slower.  (Consider that x and y
> could be the same array.)
>
> -- glen
>

I tend to agree with JaaC and Glen.  To me, the pointer notation obfuscates the
math/DSP concepts.  If you are teaching a class on the C language, then show the
pointer method.  But for understanding DSP, go with the array method.  If you
want to throw in the pointer method at the end as an alternate coding method
that _might_ be more efficient in some cases, then do so.  I wouldn't make a big
deal about it, but it might be nice to mention it because the students may come
across it when looking at other's code in the future.

"Jaime Andr&#4294967295;s Aranguren Cardona" <jaac@nospam.sanjaac.com> wrote in message
news:1097693646.F6sftk9T2porDo2oN5y8qA@teranews...
> My opinion is similar as Glen's
>
> I don't see a REAL reason to do it with pointer arithmetic, when it can be
> much clearer and easier to understand when done with indexing.
>
> Performance? Well, with modern C compilers, the indexing approach can take
> very good advantage of processor resources.
>
> JaaC
>
> --
> Jaime Andr&#4294967295;s Aranguren Cardona
> jaac@nospam.sanjaac.com
> SanJaaC Electronics
> Soluciones en DSP
> www.sanjaac.com
>
> (Remove "nospam" from e-mail address)
>
> "glen herrmannsfeldt" <gah@ugcs.caltech.edu> escribi&#4294967295; en el mensaje
> news:ckjpt6$1qr$1@gnus01.u.washington.edu...
> >
> > It may have been true on the PDP-11 with early C compilers.
> > It is much less obvious with modern processors and compilers
> > that it is faster.  Especially when the compiler has to check
> > for aliasing (different pointer variables pointing to the
> > same array) it can be much slower.  (Consider that x and y
> > could be the same array.)
> >
> > -- glen

chris_bore@yahoo.co.uk (Chris Bore) wrote in message news:<468debd2.0410130644.3ce25dcf@posting.google.com>...
> In preparing a class on DSP, with programming, I want to explain the
> following piece of code that implements the inner loop of an FIR:
> 
>       *(y+n) = 0;
>       for (k = 0; k <= n; k++) {
>          *(y+n) += *(h+k)*(*(x+n-k));
> 
> An equivalent implementation using arrays would be:
> 
>     y[n] = 0;
>       for (k = 0; k <= n; k++) {
>          y[n] += h[k] * x[n - k];
> 
<snipped>

This is a little scary. If x is a long series compared to h[], and y
is to be computed over the length of x (i.e for n large), the index
for h[] is going out of bounds.

Dirk

Jon Harris wrote:

> I tend to agree with JaaC and Glen.  To me, the pointer notation obfuscates the
> math/DSP concepts.  If you are teaching a class on the C language, then show the
> pointer method.  But for understanding DSP, go with the array method.  If you
> want to throw in the pointer method at the end as an alternate coding method
> that _might_ be more efficient in some cases, then do so.  I wouldn't make a big
> deal about it, but it might be nice to mention it because the students may come
> across it when looking at other's code in the future.

I don't want to be seen as arguing against this, but it doesn't really
make sense to me. I'd like to say why not, and be educated.

It seems to me that the natural way to write that code in assembler
(which is my model of "what the machine does") is by loading an address
into an autoincrement register and fetching successive elements as
needed. "x = *pointer++" is practically a paraphrase of that. The array
approach would put the base address on a fixed register and use indexed
addressing with an autoincrement autoincrement register. That's two
registers instead of one, with the possibility that the compiler will
actually calculate an effective address at run time for each reference.
That would not only be slow, but conceptually cumbersome.

Where has my thinking gone astray?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:

(mostly previously snipped discussion about array and pointer
notation in C)

> I don't want to be seen as arguing against this, but it doesn't really
> make sense to me. I'd like to say why not, and be educated.

> It seems to me that the natural way to write that code in assembler
> (which is my model of "what the machine does") is by loading an address
> into an autoincrement register and fetching successive elements as
> needed. "x = *pointer++" is practically a paraphrase of that. 

Well, that assumes that you have an autoincrement register.
There is discussion over which came first, the PDP-11
autoincrement addressing mode or C's ++ operator, but it
does make sense on the PDP-11, especially with only eight
registers including SP and PC.   VAX has autoincrement mode,
and also good indexed modes.  You probably don't use either
of those very often.

 > The array
> approach would put the base address on a fixed register and use indexed
> addressing with an autoincrement autoincrement register. That's two
> registers instead of one, with the possibility that the compiler will
> actually calculate an effective address at run time for each reference.
> That would not only be slow, but conceptually cumbersome.

Well, first of all the OP gave two programs that will both
compile the same way, though one looked pointer like and one
array like.  Many processors now have indexed addressing modes
that scale by the size of the item addressed, and have enough
registers that it doesn't matter so much.  The loop variable
needs to be in a register already, so it really isn't another
register.   Most likely any extra computation can be done
during the time needed to do the memory load/store.

Well, this was on comp.arch not so long ago.  RISC processors
don't tend to have autoincrement mode, and, except for a few
special instructions, x86 doesn't, either.   Then there is the
question of which notation the optimizers recognize.

-- glen

glen herrmannsfeldt wrote:
> 
> 
> Jerry Avins wrote:
> 
> (mostly previously snipped discussion about array and pointer
> notation in C)
> 
>> I don't want to be seen as arguing against this, but it doesn't really
>> make sense to me. I'd like to say why not, and be educated.
> 
> 
>> It seems to me that the natural way to write that code in assembler
>> (which is my model of "what the machine does") is by loading an address
>> into an autoincrement register and fetching successive elements as
>> needed. "x = *pointer++" is practically a paraphrase of that. 
> 
> 
> Well, that assumes that you have an autoincrement register.
> There is discussion over which came first, the PDP-11
> autoincrement addressing mode or C's ++ operator, but it
> does make sense on the PDP-11, especially with only eight
> registers including SP and PC.   VAX has autoincrement mode,
> and also good indexed modes.  You probably don't use either
> of those very often.

On a DSP?  Oh yes you do.  If it doesn't have a MAC instruction that 
lets you multiply two numbers, add the result to an accumulator, load 
their temporary registers, increment their pointers (and possibly wrap 
them in hardware) all in one clock cycle -- then it's a poor excuse for 
a DSP.
> 
>  > The array
> 
>> approach would put the base address on a fixed register and use indexed
>> addressing with an autoincrement autoincrement register. That's two
>> registers instead of one, with the possibility that the compiler will
>> actually calculate an effective address at run time for each reference.
>> That would not only be slow, but conceptually cumbersome.
> 
> 
> Well, first of all the OP gave two programs that will both
> compile the same way, though one looked pointer like and one
> array like.  Many processors now have indexed addressing modes
> that scale by the size of the item addressed, and have enough
> registers that it doesn't matter so much.  The loop variable
> needs to be in a register already, so it really isn't another
> register.   Most likely any extra computation can be done
> during the time needed to do the memory load/store.
> 
> Well, this was on comp.arch not so long ago.  RISC processors
> don't tend to have autoincrement mode, and, except for a few
> special instructions, x86 doesn't, either.   Then there is the
> question of which notation the optimizers recognize.
> 
> -- glen
> 
But digital signal processors do, and this is comp.dsp.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com