AVR-Chat

--- In AVR-Chat@yahoogroups.com, Martin Jay McKee 
<MartinJayMcKee@d...> wrote:
> I'd like to find a way to minimize the difference between the
> run times of the subroutine for states 1 and state N.

Instead of using a sequential set of comparisons (sometimes called a 
skip chain), use a dispatch table instead.  The table would contain 
code space addresses, you index it with the state value (after 
checking validity), load the address from the table into r31:30, and 
them do an ijmp or icall.  (Your target processor may or may not 
support these instructions.)

As a side note, in the code that you showed the clz instruction is 
superfluous.  The compare instruction will either set or clear the Z 
flag depending on the values.

Don

Hi Martin,

> My problem is that all the states are basically equally likely.  I'd like to find a way to minimize the difference between the run times of the subroutine for states 1 and state N.   The states are sequential (or at least close enough that it's not worrying about) and memory use isn't an option.  Also I'm more interested in balance between the execution rate then brute speed, though, as always, faster is better.  Does anyone have any ideas on how to solve this little problem?  Any ideas are much appreciated, thank you in advance.

The normal technique would be to use a lookup table with the state as
an index. The looked up value would be the address to jump to (i.e.
address of the state).

--
Dave Hylands
Vancouver, BC, Canada
http://www.DaveHylands.com/

Hi Martin,

> Interesting idea, I think in this case the table lookup would be the
> preferable way to go (no real memory constraints and constant time, but I
> think I'll keep a binary tree comparison in mind for possible future use.
> Always more than one way to skin a cat…  Thanks again.

Yeah - if the states values are "dense" (i.e. values like 0, 1, 2, 3,
4, ...) then the lookup table will be faster and take up less memory.
If you're implementing something where the states are "sparse" (i.e.
values like 1, 17, 23, 24, 51) then using the binary search method
would be better.

From your other email:
> It's been a while since I did a complete read through the data sheet, I
> just looked through the instruction set reference and missed IJUMP.
> I guess I need to take a vacation…  Thanks again.

My usual method of implementing something like lookup tables in
assembler when I'm unfamiliar with the assembler (I can barely claim
to know any AVR assembler) is to code it in C (which I know) and look
at the compiler generated output.

--
Dave Hylands
Vancouver, BC, Canada
http://www.DaveHylands.com/

I've found that I really like programming in assembler (strange for someone
that doesn't like details...?) but most of the programming I do on the PC is
C++ and I'm quite comfortable with that.  I've installed WinAVR but I have
yet to find anything that I feel I need a high level language for yet so I
haven't done a thing with it yet... sooner or later.

I feel a bit stupid, I knew what I was looking for... I just never found it.
Oh well, it's been one of those weeks I guess.

Martin Jay McKee

On Oct 26, 2005, at 7:18 PM, Dave Hylands wrote:
>
>> Interesting idea, I think in this case the table lookup would be the
>> preferable way to go (no real memory constraints and constant  
>> time, but I
>> think I'll keep a binary tree comparison in mind for possible  
>> future use.
>> Always more than one way to skin a cat…  Thanks again.
>
> Yeah - if the states values are "dense" (i.e. values like 0, 1, 2, 3,
> 4, ...) then the lookup table will be faster and take up less memory.
> If you're implementing something where the states are "sparse" (i.e.
> values like 1, 17, 23, 24, 51) then using the binary search method
> would be better.

Is there any good reason the states have to be sparse? If there is  
nothing between 1 and 17 then just mark 17 as 2...

Had one spent much time with a Microchip PIC16F87x one would be  
fluent in calculated jump tables as that is the only way to read an  
array of data from code space. No kidding, "ABCDE" translates into  
"RET A", "RET B", ... "RET E" and to get the Nth entry one JSRs to  
code immediately prior which adds the index to the program counter  
causing a skip to the return containing the desired data.

On the 16F876 I created several "tasks" which never busy-waited. Each  
task used a state index to return to wherever it was previously,  
typically waiting on input. If no input then simply return. Next time  
around it will return back to the same input test based on the state  
index. If input then process it and bump the state index that the  
next time we do the next thing until the last which zeros the index  
on completion so the whole process starts over. Used the same indexed  
jump structure as required for constant string processing.

Worked great for parsing incoming data frames. Actions based on the  
content of a frame could be controlled by branching to a different  
section of the state list.

--
David Kelly N4HHE, dkelly@HiWAAY.net
========================================================================
Whom computers would destroy, they must first drive mad.

David Kelly wrote:
> On Oct 26, 2005, at 7:18 PM, Dave Hylands wrote:
> 
>>>Interesting idea, I think in this case the table lookup would be the
>>>preferable way to go (no real memory constraints and constant  
>>>time, but I
>>>think I'll keep a binary tree comparison in mind for possible  
>>>future use.
>>>Always more than one way to skin a cat…  Thanks again.
>>
>>Yeah - if the states values are "dense" (i.e. values like 0, 1, 2, 3,
>>4, ...) then the lookup table will be faster and take up less memory.
>>If you're implementing something where the states are "sparse" (i.e.
>>values like 1, 17, 23, 24, 51) then using the binary search method
>>would be better.
> 
> 
> Is there any good reason the states have to be sparse? If there is  
> nothing between 1 and 17 then just mark 17 as 2...
> 
> Had one spent much time with a Microchip PIC16F87x one would be  
> fluent in calculated jump tables as that is the only way to read an  
> array of data from code space. No kidding, "ABCDE" translates into  
> "RET A", "RET B", ... "RET E" and to get the Nth entry one JSRs to  
> code immediately prior which adds the index to the program counter  
> causing a skip to the return containing the desired data.

Oh, the memories!

I have a fried PIC16C55 in my desk. It was used in a project where much 
of the first 256 words of program space consisted of text strings, data 
constants, and subroutines used by the remainder of the 512 words total 
program space. The processor had a 9 bit wide stack, 1 deep, but JSR 
could only use an 8 bit wide address, so it could only JSR into the 
first 256 words.

The chip used UV erasable EPROM, so there is a window on it that shows 
the four hunks of Si in all their glory. It is fun pulling it out of my 
desk to show people what a complete computer looks like.

John

I'm the same way.  I write mostly in assembler, for a couple reasons 
anyway: 1 - it makes me "think" like the microcontroller, and 2 - it seems 
the little bits of C code I've written have redundundundant lines in them 
that make the code longer than if I write it in assembler.

I used to know all sorts of tricks with Fortran II that allowed me to 
write programs that were much shorter than if you didn't know them.

I'm not knocking the higher-level languages, it's just that I haven't 
really needed them myself.

Zack

On Wed, 26 Oct 2005, Martin Jay McKee wrote:

> I've found that I really like programming in assembler (strange for
> someone
> that doesn't like details...?) but most of the programming I do on the PC
> is
> C++ and I'm quite comfortable with that.  I've installed WinAVR but I
> have
> yet to find anything that I feel I need a high level language for yet so
> I
> haven't done a thing with it yet... sooner or later.
> 
> I feel a bit stupid, I knew what I was looking for... I just never found
> it.
> Oh well, it's been one of those weeks I guess.
> 
> Martin Jay McKee
>

Hi Zack,

> I'm not knocking the higher-level languages, it's just that I haven't
> really needed them myself.

I work on a whole bunch of processors (AVR, ARM, PC) so being able to
share source code really helps.

Different strokes for different folks :)

--
Dave Hylands
Vancouver, BC, Canada
http://www.DaveHylands.com/

Yes - whatever works!

Some years ago I rewrote some code I'd originally written for the Z-80 for 
an 8051.  The 8051 actually seemed more versatile, even though the Z-80 
had a larger instruction set.

I recently rewrote some code originally for a PIC into AVR assembler.  The 
AVR code came out about two-thirds the size of the PIC code.  

I got an ad sheet in the mail the other day from Dallas Semiconductor.  
It had data about a new microcontroller.  It indicated they are the 
fastest microcontrollers on the market now, apparently far surpassing 
AVR's in speed.  They do have some neat features, including on-chip DAC's 
as well as ADC's. But I' not ready to give up on AVR's yet. So it goes.

Zack

On Wed, 26 Oct 2005, Dave Hylands wrote:

> Hi Zack,
> 
> > I'm not knocking the higher-level languages, it's just that I haven't
> > really needed them myself.
> 
> I work on a whole bunch of processors (AVR, ARM, PC) so being able to
> share source code really helps.
> 
> Different strokes for different folks :)
> 
> --
> Dave Hylands

On 27 Oct 2005 at 7:14, Zack Widup wrote:

> I recently rewrote some code originally for a PIC into AVR
> assembler. The AVR code came out about two-thirds the size of the
> PIC code.  


	I did that a couple times and the AVR code came out 
almost 50% the size of the PIC code. Not to mention speed...

	Mark Jordan

On Wed, 2005-10-26 at 22:46 -0500, Zack Widup wrote:
> I'm the same way.  I write mostly in assembler, for a couple reasons 
> anyway: 1 - it makes me "think" like the microcontroller, and 2 - it
> seems the little bits of C code I've written have redundundundant
> lines in them that make the code longer than if I write it in
> assembler.

   Yes.  Assuming any degree of competence in assemblker at all, code
written in assembler will be smaller and faster than code generated by a
compiler.  This is because the compiler, in order to provide the very
generalized programming environemnt necessary in high level languages,
must use very generalized structures and flows.  Further, because the
compiler has no way of "knowing" what your intentions as programmer are,
it must manage resources on the target in fixed ways, which are often
not efficient for the sopecific purpose your progarm is designed for.
Vis all the ridiculous register swapping that compiled code often
contains.

> I'm not knocking the higher-level languages, it's just that I haven't 
> really needed them myself.

  Well, while I agree with you, I feel compelled to point out that the
primary reasons most people who use high level languages to do embedded
programming are 1) lack of knowledge and expoerience in assembly
language programming, and 2)  in commercial development enviroinments,
the time savings to develop working code can be significant, and time
saved equates to development costs saved.

   Reason #2 is not going to ever go away, because it is almost always
bean counters who make the important decisions in a business.  Reason #1
probably won't ever go away either, because so many people are unwilling
to learn new programming languages or methodologies.

   Personally, I plan to do most of my embedded programming in assem,bly
language, because I find it challenegin and fun to, as you pointy out,
"think like the processor," as well as because it affords me direct
control over the hardware.  You just can't get any closer to the machine
than assembly language (some might argue that programming in "machine
language" (e.g., binary op codes directly entered into memory using a
switch register) is closer, but I disagree.   With the exeception that
most decent assemblers support macro processing and mnemonic labeling,
assembly language translates directly into machine code, and is just as
close to the hardware as the machine code is.

Tom

Thomas Keller wrote:
> On Wed, 2005-10-26 at 22:46 -0500, Zack Widup wrote:
> 
>>I'm the same way.  I write mostly in assembler, for a couple reasons 
>>anyway: 1 - it makes me "think" like the microcontroller, and 2 - it
>>seems the little bits of C code I've written have redundundundant
>>lines in them that make the code longer than if I write it in
>>assembler.
> 
> 
>    Yes.  Assuming any degree of competence in assemblker at all, code
> written in assembler will be smaller and faster than code generated by a
> compiler.  This is because the compiler, in order to provide the very
> generalized programming environemnt necessary in high level languages,
> must use very generalized structures and flows.  Further, because the
> compiler has no way of "knowing" what your intentions as programmer are,
> it must manage resources on the target in fixed ways, which are often
> not efficient for the sopecific purpose your progarm is designed for.
> Vis all the ridiculous register swapping that compiled code often
> contains.
> 
> 
>>I'm not knocking the higher-level languages, it's just that I haven't 
>>really needed them myself.
> 
> 
>   Well, while I agree with you, I feel compelled to point out that the
> primary reasons most people who use high level languages to do embedded
> programming are 1) lack of knowledge and expoerience in assembly
> language programming, and 2)  in commercial development enviroinments,
> the time savings to develop working code can be significant, and time
> saved equates to development costs saved.
> 
>    Reason #2 is not going to ever go away, because it is almost always
> bean counters who make the important decisions in a business.  Reason #1
> probably won't ever go away either, because so many people are unwilling
> to learn new programming languages or methodologies.
> 
>    Personally, I plan to do most of my embedded programming in assem,bly
> language, because I find it challenegin and fun to, as you pointy out,
> "think like the processor," as well as because it affords me direct
> control over the hardware.  You just can't get any closer to the machine
> than assembly language (some might argue that programming in "machine
> language" (e.g., binary op codes directly entered into memory using a
> switch register) is closer, but I disagree.   With the exeception that
> most decent assemblers support macro processing and mnemonic labeling,
> assembly language translates directly into machine code, and is just as
> close to the hardware as the machine code is.
> 
> Tom

Good points there.  I personally like to model my programme 
in a high-level language on the PC mainly to get a feel for 
what it is that I am trying to do.  Then I refine that 
programme until I am satisfied with its performance.  When 
it works correctly on the PC, I then hand-translate it to 
assembler code.

Of course, there are limitations to that approach (like 
working with the on-chip peripherals which don't model 
easily), but it gives me a code base which I can then add 
stuff to.

The high-level is also useful in documentation where I am 
trying to explain just what it is that the programme does.

Things get even better if I have a compiler that excretes 
assembly code for whatever CPU I'm working with; then I can 
go in and hand-optimise the compiler's output.

erikc

On Thu, Oct 27, 2005 at 09:59:16AM -0500, Thomas Keller wrote:

>    Yes.  Assuming any degree of competence in assemblker at all, code
> written in assembler will be smaller and faster than code generated by
> a compiler.

Thats a common oft-repeated generalization. As with any generalization
its easy to repeat but not precisely accurate.

Andy Hertzfeld (bottom of http://www.pbs.org/cringely/nerdtv/shows/)
said, "I was -- in my heyday anyway - a very fast programmer. I got
things done quickly. The way that works is to have it all in your head
so you never have to look anything up." This is partly how a high level
language helps, that it helps simplify the problem so that one can keep
it all in one's head. That if one knows what is happening elsewhere one
doesn't recreate similar code. What I'm saying is in the real world
often the output of a C compiler is smaller than what a programmer might
do in assembly.

>> I'm not knocking the higher-level languages, it's just that I haven't
>> really needed them myself.
>
>   Well, while I agree with you, I feel compelled to point out that the
> primary reasons most people who use high level languages to do  
> embedded
> programming are 1) lack of knowledge and expoerience in assembly
> language programming, and 2)  in commercial development enviroinments,
> the time savings to develop working code can be significant, and time
> saved equates to development costs saved.

Biased view of an assembly programmer. Its not wrong but is biased.

My position is, "whatever it takes." If an application is internally
time critical, so much so that the necessary control is not available in
C then at least that section of it shall be in assembly. On the other
hand modern inexpensive MCUs are extremely fast and low power. I
typically select operating frequency based on the cost of crystals.

Recently selected an ATmega64L for a project. When the project shipped
was using less than half of the I/O pins and only 14k of FLASH. Coded
with avr-gcc. Could fairly easily migrate to another AVR at lower cost
but there isn't much point until we start producing 50,000/year. The 64L
already costs less than half the non-AVR OTP part it replaced. The code
was a clean sheet redesign. With equivalent functionality the C code was
6k and the assembly was 4k. The assembly code was breaking every time
features were added. The C code is a long way from that level of chaos.

Before *I* wrote the new application above in C another who knew the
assembly did a virtually literal translation to C. His code worked but
was a disaster of chaotic disorder. And much larger than my final code.
The point being is the level of chaos is driven largely by the skill of
the programmer. Chaos is the major component of unreliability and high
maintenance costs.

In this application there was no advantage to assembly, only
disadvantages.

When writing C for MCUs I spend a fair amount of time double checking  
the
generated assembly.

-- 
David Kelly N4HHE, dkelly@HiWAAY.net
========================================================================
Whom computers would destroy, they must first drive mad.