Conceptual model for pointer arithmetic in FIR filter implementation?

"Chris Bore" schrieb
> [...] I've also learnt that optimization costs a lot - and
> is often done to parts of a program that don't matter (many
> programmers in practice spend weeks optimizaing a piece of
> code that in the first place only took up 1% of the total
> time).
>
> I am now struggling to fully understand these questions of
> 'code to the hardware' versus 'code to the application' and
> trying to see what real practical guidance one can offer.
>
You might want to read
http://catb.org/~esr/writings/taoup/html/ch01s06.html#rule_of_optimi
zation

...
Rule of Optimization: Prototype before polishing. Get it
working before you optimize it.
The most basic argument for prototyping first is Kernighan &
Plauger's; "90% of the functionality delivered now is better

than

100% of it delivered never". Prototyping first may help keep

you from investing far too much time for marginal gains.

...



Back to your original question, I think that beginners should

learn the array approach, because this is the "natural" formulation

of the problem set. As a footnote, the C pecularity of the pointer

approach can be shown so that C-beginners know that other approaches

are possible.



Regards

Martin

chris_bore@yahoo.co.uk (Chris Bore) writes:

> As to the question whether real DSP on non-traditional architectures
> is done in C, then yes very much so - most of Philips and Sony work on
> audio and video for digital and analog TV is done in C, even in C++ -
> this at least for the Nexperia processors. They use VLIW for this. The
> compilers become enormously expensive (hundreds of man-years of
> effort) and the code base becomes highly valuble (hunderds of millions
> of dollars) - so the software tools start to cost almost as much as
> the system-on-chip itself. 

And all this to avoid a little assembly language programming? Methinks
we have our heads up our rears. Put that effort into the base implementation
and you're light years ahead in terms of speed, code size, performance, 
and man-years. Even time-to-market won't suffer when compared to such 
gargantuan efforts for the tools. 
-- 
%  Randy Yates                  % "Bird, on the wing,
%% Fuquay-Varina, NC            %   goes floating by
%%% 919-577-9882                %   but there's a teardrop in his eye..."
%%%% <yates@ieee.org>           % 'One Summer Dream', *Face The Music*, ELO
http://home.earthlink.net/~yatescr

"Martin Blume" <mblume@socha.net> writes:

> "Chris Bore" schrieb
>> [...] I've also learnt that optimization costs a lot - and
>> is often done to parts of a program that don't matter (many
>> programmers in practice spend weeks optimizaing a piece of
>> code that in the first place only took up 1% of the total
>> time).
>>
>> I am now struggling to fully understand these questions of
>> 'code to the hardware' versus 'code to the application' and
>> trying to see what real practical guidance one can offer.
>>
> You might want to read
> http://catb.org/~esr/writings/taoup/html/ch01s06.html#rule_of_optimi
> zation
>
> ...
> Rule of Optimization: Prototype before polishing. Get it
> working before you optimize it.
> The most basic argument for prototyping first is Kernighan &
> Plauger's; "90% of the functionality delivered now is better
>
> than
>
> 100% of it delivered never". Prototyping first may help keep
>
> you from investing far too much time for marginal gains.

I'll take the low road and buck Kernighan. It's a matter of faith
and competency. The "delivered never" is bullshit.

The problem with these sorts of development cycles is that management
can't "see" the progress. But if they had the faith that the people
leading the technical development will do what they say they'd do
(and those people put forth realistic estimates in the beginning),
then the end-result can be magnitudes better in performance, cost,
speed, etc.
-- 
%  Randy Yates                  % "And all that I can do
%% Fuquay-Varina, NC            %  is say I'm sorry, 
%%% 919-577-9882                %  that's the way it goes..."
%%%% <yates@ieee.org>           % Getting To The Point', *Balance of Power*, ELO
http://home.earthlink.net/~yatescr

"Randy Yates" schrieb
> >> [...] I've also learnt that optimization costs a lot - and
> >> is often done to parts of a program that don't matter
> > ...
> > Rule of Optimization: Prototype before polishing. Get it
> > working before you optimize it.
> > ...
> > The most basic argument for prototyping first is Kernighan &
> > Plauger's; "90% of the functionality delivered now is better
> > than 100% of it delivered never".
>
> I'll take the low road and buck Kernighan. It's a matter of faith
> and competency. The "delivered never" is bullshit.
>
Depends on the project. There are projects that were never
delivered.

In the field of DSP apps, performance and hence optimizing is
obviously more important than elsewhere. But also here, an algorithm
has first to work correctly (if necessary at a lower sample rate)
before it can be optimized.

> The problem with these sorts of development cycles is that
> management can't "see" the progress.
The problem is not only between developers and management, but also
between management and end clients.
Bad specifications, misunderstandings between all parties all
conspire to crash projects.
Prototyping helps to uncover misunderstandings before the cost of
repairing them gets too big or even impossible.

> But if they had the faith that the people
> leading the technical development will do what they say they'd do
> (and those people put forth realistic estimates in the beginning),
> then the end-result can be magnitudes better in performance, cost,
> speed, etc.
Ack.

Every rule is to be taken with a grain of salt: it has to be applied
to the circumstances at hand. But thinking about such rules makes
you
take conscious decisions based on arguments as opposed to just
skidding along.

Regards
Martin

Martin Blume wrote:
  ...

> Back to your original question, I think that beginners should
> learn the array approach, because this is the "natural" formulation
> of the problem set. 

  ...

What is natural to one is forced to another. It depends on how one sees
the problem. Why is a set of coefficients most naturally seen as an
array? I see it as a list, occasionally best dealt with as an array.

"There's not much difference between an elephant and a rope."

"There's not much difference between an elephant and a tree trunk."

"To get a good solution, develop an understanding of the whole problem,
then divide it into tractable parts that connect in a sensible way."

"To get a good solution, start from the end and work backward."

"If you don't see the problem the way I do, your view is defective."

A good teacher is more than an adept in the field he teaches. He has to
see what he teaches from many points of view in order to adapt the
material to the student's mind set.

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

Yes, of course, I was being careless (and slipping back into old
assumptions about how code is written..). The autoincrement code you
write is of course closer to the DSP hardware. Actually, what
interested me in this piece of code was the way the programmer had in
fact exactly duplicated what the compiler would do anyway, and then in
the discussion I sort of forgot the real code and went back to
remembering the way I would have done it some time ago.

It seemed to me one flaw here was, the programmer thinking he knew
better than the compiler - which may or may not be true but cannot
just be assumed.

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


Tim Wescott <tim@wescottnospamdesign.com> wrote in message news:<10n14rbgte9h44@corp.supernews.com>...
> Chris Bore wrote:
> 
> > Jerry Avins <jya@ieee.org> wrote in message news:<2t5lg5F1rgltnU1@uni-berlin.de>...
> > 
> >>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
>  > Thanks, Jerry.
>  >
>  > I do not think your thinking has gone astray. But is it thinking from
>  > just one side of the problem? The pointer notation is in fact close to
>  > the hardware model of what happens (provided the architecture is
>  > indeed what the programmer thinks it is). Which is helpful for a
>  > programmer thinking 'how do I implement this?'. But it is not close to
>  > the way the math would be written. So if you are coming up from the
>  > hardware implementation the pointers make sense, whereas if you are
>  > coming down from the math they may not be so immediately obvious.
>  >
>  > A second point is perhaps, that the C code here is written with
>  > assumptions about the underlying architecture (the programmer who
>  > wrote this explained to me that 'all DSP processors work like this..').
>  > For example a particular processor may not offer an autoincrement
>  > register - VLIWs typically don't. So the assumption may be too narrow:
>  > 'all DSP programs are written for DSP processors and all DSP
>  > processors have this simple architecture so this code will result in
>  > efficient use of the machine....'.
>  >
> Actually the code in your original post is _not_ written the way an 
> autoincrement machine might do it.  What most DSP chips worthy of the 
> name do is something like:
> 
> for (n = endCount; --n;)
>    accumulator += (*x++) * (*y++);
> 
> -- and that's ignoring the any circular buffers that you may have set up!
> 
> Up until a few years ago the above code snippet would have been slightly 
> faster than what you have in your original post (and yes, I know the 
> functionality is a bit different).  I honestly don't know if compilers 
> less than 5 years old can go from your post's arrangement to mine -- I 
> do know that TI's compiler for the '2812 is distressingly unable to 
> optimize it's way to a MAC instruction, so that must be written in assembly.

"Jerry Avins" schrieb
>
> > Back to your original question, I think that beginners should
> > learn the array approach, because this is the "natural"
> > formulation of the problem set.
>   ...
>
> What is natural to one is forced to another.
> It depends on how one sees the problem.
> Why is a set of coefficients most naturally seen as an array?
> I see it as a list, occasionally best dealt with as an array.
>
You are right. But in this case I think that the array approach
is the best and indeed the "natural" approach for beginners.
For a guy having assembler experience, the pointer approach may
of course be more natural.

> ...
> "To get a good solution, develop an understanding
> of the whole problem, then divide it into tractable
> parts that connect in a sensible way."
>
Yes.

>
> "To get a good solution, start from the end and work backward."
>
That's the best way ... :-)

>
> "If you don't see the problem the way I do, your view is
defective."
>
Not necessarily. Your (my) view may be incomplete (either the
understanding of the problem, or the descriptive power of the view).

>
> A good teacher is more than an adept in the field he teaches.
> He has to see what he teaches from many points of view in order to
> adapt the material to the student's mind set.
>
I think that is what defines a good understanding of a problem:
that one can look at it from different angles and understand and
describe the phenomena. Indeed a problem should be looked at from
as many possible angles as possible in order to get a deeper
understanding.
In that sense my understanding of C is not yet complete: although
 I can read  and understand the pointer notation, I wouldn't write
code in that way. So that explains why (in my view) the array
notation
is the "natural" one.


Regards
Martin

Chris Bore wrote:
> Yes, of course, I was being careless (and slipping back into old
> assumptions about how code is written..). The autoincrement code you
> write is of course closer to the DSP hardware. Actually, what
> interested me in this piece of code was the way the programmer had in
> fact exactly duplicated what the compiler would do anyway, and then in
> the discussion I sort of forgot the real code and went back to
> remembering the way I would have done it some time ago.
> 
> It seemed to me one flaw here was, the programmer thinking he knew
> better than the compiler - which may or may not be true but cannot
> just be assumed.
> 
The only reason that I can think of to write that original code snippet 
was to make _very_ clear that one was dealing with pointers rather than 
arrays -- since they are almost identical in C it's a bit odd to do what 
he did.  A compiler would have to be pretty lame to not generate 
identical code in both cases -- but I've seen some pretty lame 
compilers, so who knows.

Any time I am writing something and it's critical the assembly gets 
generated just the right way I will compile to assembly and check.  This 
is an essential part of embedded systems programming, and since much DSP 
happens in embedded systems, I do it.

-- 

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

Martin Blume wrote:

> "Jerry Avins" schrieb
> 
>>>Back to your original question, I think that beginners should
>>>learn the array approach, because this is the "natural"
>>>formulation of the problem set.
>>
>>  ...
>>
>>What is natural to one is forced to another.
>>It depends on how one sees the problem.
>>Why is a set of coefficients most naturally seen as an array?
>>I see it as a list, occasionally best dealt with as an array.
>>
> 
> You are right. But in this case I think that the array approach
> is the best and indeed the "natural" approach for beginners.
> For a guy having assembler experience, the pointer approach may
> of course be more natural.

Why are the coefficients of an FIR best seen as an array, while the
names of my grandchildren in their order of birth, a list? I think
there's a bit of preconception there, and also an influence of the
language one expects to express it in.

>>...
>>"To get a good solution, develop an understanding
>>of the whole problem, then divide it into tractable
>>parts that connect in a sensible way."
>>
> 
> Yes.

I meant all the sentences in quotes to be seen as sometime truths (and
therefore dangerous generalizations) or evident nonsense.

>>"To get a good solution, start from the end and work backward."
>>
> 
> That's the best way ... :-)
> 
> 
>>"If you don't see the problem the way I do, your view is
>> defective."
> 
> Not necessarily. Your (my) view may be incomplete (either the
> understanding of the problem, or the descriptive power of the view).

The point is that a problem can be described in many ways. and that what
is a best approach depends in part on the recipient of the description.

>>A good teacher is more than an adept in the field he teaches.
>>He has to see what he teaches from many points of view in order to
>>adapt the material to the student's mind set.
>>
> 
> I think that is what defines a good understanding of a problem:
> that one can look at it from different angles and understand and
> describe the phenomena. Indeed a problem should be looked at from
> as many possible angles as possible in order to get a deeper
> understanding.
> In that sense my understanding of C is not yet complete: although
>  I can read  and understand the pointer notation, I wouldn't write
> code in that way. So that explains why (in my view) the array
> notation
> is the "natural" one.

It's been my experience that math is one of the more poorly taught
subjects because once one understands, it becomes nearly impossible for
most people to comprehend how anyone could not understand. Those who
teach it best are those who recently struggled with it, and the
exceedingly rare individuals who can truly comprehend another's
difficulty while themselves being at ease. When teaching anything, I try
to achieve that gift and occasionally succeed.

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

"Martin Blume" <mblume@socha.net> writes:

> "Jerry Avins" schrieb
>>
>> > Back to your original question, I think that beginners should
>> > learn the array approach, because this is the "natural"
>> > formulation of the problem set.
>>   ...
>>
>> What is natural to one is forced to another.
>> It depends on how one sees the problem.
>> Why is a set of coefficients most naturally seen as an array?
>> I see it as a list, occasionally best dealt with as an array.
>>
> You are right. But in this case I think that the array approach
> is the best and indeed the "natural" approach for beginners.
> For a guy having assembler experience, the pointer approach may
> of course be more natural.
>
>> ...
>> "To get a good solution, develop an understanding
>> of the whole problem, then divide it into tractable
>> parts that connect in a sensible way."
>>
> Yes.
>
>>
>> "To get a good solution, start from the end and work backward."
>>
> That's the best way ... :-)
>
>>
>> "If you don't see the problem the way I do, your view is
> defective."
>>
> Not necessarily. Your (my) view may be incomplete (either the
> understanding of the problem, or the descriptive power of the view).
>
>>
>> A good teacher is more than an adept in the field he teaches.
>> He has to see what he teaches from many points of view in order to
>> adapt the material to the student's mind set.
>>
> I think that is what defines a good understanding of a problem:
> that one can look at it from different angles and understand and
> describe the phenomena. Indeed a problem should be looked at from
> as many possible angles as possible in order to get a deeper
> understanding.
> In that sense my understanding of C is not yet complete: although
>  I can read  and understand the pointer notation, I wouldn't write
> code in that way. So that explains why (in my view) the array
> notation
> is the "natural" one.

Trick question:

int count[20];
int i;

for (i = 0; i < 20; i++)
{
printf("count is %d\n", i[count]);
}

Will this compile and run?
-- 
%  Randy Yates                  % "She's sweet on Wagner-I think she'd die for Beethoven.
%% Fuquay-Varina, NC            %  She love the way Puccini lays down a tune, and
%%% 919-577-9882                %  Verdi's always creepin' from her room." 
%%%% <yates@ieee.org>           % "Rockaria", *A New World Record*, ELO   
http://home.earthlink.net/~yatescr