Where can I learn about optimal math in C on a micro-controller like, say, ARMv7?_问答_开发者

I'm trying to optimize some functions and I realized that I know next to nothing about how long certain things take.

I can ask all the questions here, but I'd rather just find a good article on the subject if anyone knows one.

I'm using IAR to write a program in C for an ATMEL SAM7S processor. I have a sort function that takes 500uS or so, and I wanted to see if I could speed it up. I could also just post it here but I was hoping to learn for myself.

Like, is it any faster to subtract two 16 bit integers than it is to subtract two 开发者_如何学C32 bit integers? And how long does an operation like that take? Just one cycle or more? How long does multiplication take compared to subtraction?

Anyone know a place to look? I tried googling for some stuff but I couldn't come up with any useful search terms.

If anyone has an ideas on my specific function, I can post details. I'm basically trying to match two analog values to the closest index in a table of calibrated values. Right now I iterate through the whole table and use least squares to determine the closest match. Its pretty straightforward and I'm not sure there is a faster way without applying some extra logic to my table. But if I at least knew how long certain things took, I could probably optimize it myself.

is it any faster to subtract two 16 bit integers than it is to subtract two 32 bit integers?

Not on an ARM architecture which has native 32-bit registers, no.

Anyone know a place to look?

The canonical place for instruction cycle timings would be the Tech Ref Manual for the particular architecture your chip implements, eg. ARM7TDMI; timings for simple alu ops here and yes, it is one cycle. This is not friendly doc to be reading if you're not already well familiar with the instruction set, though...

Right now I iterate through the whole table

You'll be much better off looking at algorithmic optimisations here (eg indexing the table, sorting by one co-ordinate to narrow it down, etc) than worrying about instruction-level micro-optimisations.

A good first stage could be to study the assembly language of the architecture you are coding for.

After you should be able to read the binary file generated by your compiler and finally compare what the computer will really have to do with two different implementation.

You can use the timers in your SAM7S. Read a timer on start, and read it after N number of searches and subtract to get the difference. Try different algorithms and see what you see.

As far as 16 bit math vs 32 bit math, yes there can be a huge difference, but you have to look at your architecture. A subtract operation between two registers will take the same one clock be it 16 bit or 32 bit. But coming from C code eventually the variables may land in memory and you have to know if you have a 16 bit or 32 bit data bus (yes ARM7s can have a 16 bit bus, look at the GameBoy Advance, thumb code runs significantly faster than ARM code on that processor). Takes twice as many cycles to read or write 32 bit numbers on a 16 but bus. You likely do NOT have a 16 bit bus though. Using 16 bit variables on a 32 bit processor causes the processor to have to add extra instructions to strip or extend the upper bits so that the math is correct for a 16 bit variable. Those extra instructions can cause performance hits, a simple subtract which might have been say 3 or 4 instructions worst case might now be 5 or 6 and that is noticeable if it is in a tight loop. Generally you want to use variables that match the processors register size, on a 32 bit ARM use 32 bit variables as much as possible even if you are only counting to 10.

Hopefully I am understanding the problem you are trying to solve here, if not let me know and I will edit/remove this response:

Depending on how many bits in your measurement the typical solution for what you are doing is to use a look up table. So that I can show an example lets say you are taking a 4 bit measurement that you want to calibrate. Call it 0 to 15. Calibration of the sensor generated a list of data points, lets say:

raw cal
0x03  16
0x08  31
0x14  49

I assume what you are doing runtime is something like this, if the sensor reads a 0x5 you would look through the list looking for entries your sensor reading matches or is between two of the cal points.

searching you will find it to be between 0x03 and 0x08 to get the calibrated result from the raw 0x05 measurement

cal=  (((0x05-0x03)/(0x08-0x03))*(31-16)+16 = 22

You have a divide in there which is a HUGE performance killer on most processors, ARM7 in particular as it doesnt have a divide. Not sure about the multiply but you want to avoid those like the plague as well. And if you think about how many instructions all of that takes.

Instead what you do is take the algorithm you are using run-time, and in an ad-hoc program generate all the possible outputs from all the possible inputs:

Now turn that into a table in your run-time code:

unsigned char cal_table[16]={7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52};

and then runtime

cal = cal_table[raw&15];

The code to implement this looks something like:

ldr r3, =cal_table
and r0, r0, #15
ldrb    r0, [r3, r0]

takes like 5 clocks to execute.

Just the math to find cal from raw after you have searched through the table:

cal=  (((raw-xlo)/(xhi-xlo))*(yhi-ylo)+ylo);

looks something like this:

docal:
    stmfd   sp!, {r3, r4, r5, lr}
    ldr r3, .L2
    ldr r5, .L2+4
    ldr lr, .L2+8
    ldr ip, [r5, #0]
    ldr r0, [r3, #0]
    ldr r1, [lr, #0]
    ldr r2, .L2+12
    rsb r0, ip, r0
    rsb r1, ip, r1
    ldr r5, [r2, #0]
    bl  __aeabi_uidiv
    ldr r4, .L2+16
    ldr r3, .L2+20
    ldr r4, [r4, #0]
    rsb r5, r4, r5
    mla r4, r0, r5, r4
    str r4, [r3, #0]
    ldmfd   sp!, {r3, r4, r5, pc}

And the divide function is as bad if not worse. The look up table should make your code run dozens of times faster.

The problem with look up tables is you trade memory for performance so you have to have a table big enough to cover all the possible inputs. A 12 bit sensor would give you as many as 4096 entries in the look up table for example. If say you knew the measurement would never be below 0x100 you could make the table 0x1000 - 0x100 or 3840 entries deep and subtract 0x100 from the raw value before looking it up, trading an couple of instructions at run time to save a few hundred bytes of memory.

If the table would be too big you could try some other tricks like make a look up table of the upper bits, and the output of that might be a pre-computed offset into the cal table to start your search. So if you had a 12 bit ADC, but didnt have room for a 4096 entry look up table you could make a 16 entry look up table, take the upper 4 bits of the ADC output and use it to look in the table. The table would contain the entry in the cal table to start searching. Say your cal table had these entries:

....
entry 27 raw = 0x598 cal = 1005
entry 28 raw = 0x634 cal = 1600
entry 29 raw = 0x6AB cal = 1800
entry 30 raw = 0x777 cal = 2000

your 16 deep look up table would then have these entries

...
[6] = 27;
[7] = 29;
...

And how you would use it is

start = lut[raw>>8];
for(i=start;i<cal_tab_len;i++)
{
...
}

instead of

for(i=0;i<cal_tabl_len;i++)
{
}

It could potentially greatly shorten the time it takes to find the entry in the table for you to perform the math needed.

For the particular problem of taking a raw value and turning that into a calibrated value at runtime, there are many many similar shortcuts. I dont know of one book that would cover them all. Which path to take has a lot to do with your processor, memory system and availability, and the size and nature of your data. You generally want to avoid divides in particular and multiples sometimes if your processor does not support them (using very few clock cycles). Most processors do not. (Yes, the one or two processors most programmers target, do have a single cycle multiply and divide). Even for processors that have a single cycle multiply and divide they often have to be wrapped with a C library to decide if it is safe to perform the operation with the hardware instruction or if it has to be synthesized with a library. I mentioned above that for most variables you want to match the native register size of the processor. If you have fixed point multiplies or divides you will often want to use half the register size of the processor. A 32 bit processor, unless you take the time to examine the instructions in detail, you probably want to limit your multiples to 16 bit inputs with a 32 bit output and divides to 32 bit inputs with a 16 bit output and hope the optimizer helps you out.

Again, If I have assumed incorrectly what the problem you were trying to solve is please comment and I will edit/modify this response.