How do compilers optimize divisions

Forum: Microcontrollers and Digital Electronics Faster division





Hello I am programming an ATmega with the help of the AVR studio. I would be interested in which calculation step is faster on the µC and why. 20/5; or 20 >> 4; Can the µC work faster with the shift commands? And how exactly would he do the division? Greeting.



Baum2 wrote:> I would be interested in which calculation step is faster on the µC, why don't you just simulate it? 20/5; 20 >> 4; It doesn't come out the same anyway, what do you want to compare? > Can the µC work faster with the shift commands? mostly yes, more details are in the data sheet



Peter II wrote:> Baum2 wrote:> I would be interested in which calculation step on the µC is faster >> why don't you just simulate it? >> 20/5;> 20 >> 4; >> The same thing doesn't come out anyway Out, what do you want to compare? I am concerned with the calculation steps that he needs.



Look in the processor manual to see how many cycles a div needs and how many cycles a shift needs. Shift is presumably more quickly.


Baum2 wrote:> Hello >> I am programming an ATmega with the help of the AVR studio.> I would be interested in which calculation step on the µC is faster> and why. >> 20/5; >> or >> 20 >> 4;> > Can the µC work faster with the shift commands? And how exactly> would he do the division?> Salute. What matters is what the compiler does with your code. It is very likely that he will implement it in such a way that there is no benefit in writing a shift command in the code instead of a division.



Baum2 wrote: >> The same thing doesn't come out anyway, what do you want to compare that?> I'm concerned with the calculation steps that he needs. the calculation steps depend on the values ​​in the formula. Division by 1 is e.g. very fast.

by Jörg W. (dl8dtl) (Moderator)


Peter II wrote:> A division by 1 is e.g. very fast. ... followed by division by whole powers of two. Constant divisions are of course unsuitable for the comparison anyway, because they are optimized out by the compiler. Divisions by constant powers of two are typically also replaced by the compiler without a library call by suitable shift operations.



Baum2 wrote:> I am concerned with the calculation steps that he needs. Write yourself a mini-program that carries out the same calculation one way and the other. Compile it and look at the * .lss file generated by the compiler. There you can understand what the processor should do at assembler level. However, you should switch off the optimization because the compiler may choose the same method for both calculation paths.

by Jörg W. (dl8dtl) (Moderator)


Assem-Blär wrote:> However, you should turn off the optimization. Bad advice. Then completely unpractical stuff comes out. "How fast can this car go there?" "No idea, try it out, but leave the handbrake on."

: Edited by the moderator


I would just like to know whether it makes more sense in terms of optimization to only divide by powers of two.



Dirk_Geber wrote:> I would just like to know whether it makes more sense in terms of optimization> to only divide by powers of two, it definitely doesn’t hurt. In order for it to be faster, the divisor must be constant at compile time.


Dirk_Geber wrote:> I would just like to know whether it makes more sense in terms of optimization> to only divide by powers of two. First of all, you usually want to have correct results. So you just do the calculations that are necessary to get the desired result. I haven't heard of any real application in which you had to completely refrain from correctly dividing for performance reasons.

by Arduino Fanboy D. (ufuf)


> wahsaga wrote on a comparable time: "Forum posting with a performance question Evaluation rule of thumb: Whoever asks questions about the performance of such gimmicks, the programming is probably not even remotely high-performance. Otherwise, if he really and rightly worked on an application in which this little bit is decisive is, he shouldn't have to ask that question anymore. "

by Jörg W. (dl8dtl) (Moderator)


Peter II wrote:> So that it is faster, the divisor must be constant at compile time>. No. Even at runtime, division by 2 ^ N is still faster than other divisions. The algorithm is then finished faster. (At compile time, only the compiler can optimize it.) It’s the same for computers and people. Translated into the decimal system: if you have to divide 37568 by 100, you will be finished with the result much faster than if you have to divide it by 101.



Mark B. wrote:> First of all, you usually want to have correct results. Yes, absolutely correct results and then calculated instantaneously, that is of course the ideal. The only stupid thing is: it can't be done. A certain running time will always be required and often certain deviations from the absolutely correct result will also have to occur. The trick in numerics is to find a suitable compromise between correctness and running time. Unfortunately, it depends on the application which compromise is suitable. Anyone who has not understood this has not yet understood much about programming.

by Volker B. (Company: L-E-A) (vobs)


Alex wrote:> Look in the processor manual to see how many cycles a div needs> and how many cycles a shift needs. Which AVRs even have a division order? Grüßle, Volker.

by Arduino Fanboy D. (ufuf)


Volker B. wrote:> Which AVRs actually have a division order? Even a BarrelShifter is sorely missed.



c-hater wrote:> Yes, absolutely correct results and then calculated instantaneously,> that is of course the ideal. Without a running time, only the path-optimized division by 1 works, but why should one divide at all if it is known beforehand. Everything else has something from Radio Yerevan ...



Pushing is faster BUT only to the corresponding base of the number system. In terms of binary it means you can only divide by 2 on the 10 basis it is just / 10. So the task of you is to map the vision in such a way that you can not only divide by the base of the corresponding number system but also other divisors are possible. You need all the other stuff ...



So if I had to calculate: Then I'll do it like this: ;-) Otherwise I see it like Arduino F. wrote: >> wahsaga wrote to a comparable time:> "> Forum posting with performance question Rule of thumb:> Anyone who asks questions about the performance of such frills who> probably doesn't even begin to program with high performance.> Otherwise, if he really and rightly worked on an application where this little bit is crucial, he shouldn't have to ask this question> at all.> "



Draco wrote:> So if you had to calculate: >> uint8_t value = 20/5; the preprocessor should do that and use 4 I guess.



Mark B. wrote:> What matters is what the compiler does with your code. Very> likely he will implement it in such a way that there is no benefit in writing a shift command in the> code instead of a division. Tell that to the Keil C51 compiler.


Bernd K. wrote:> Mark B. wrote: >> What the compiler does with your code is decisive. Very >> he will probably implement it in such a way that there is no benefit in >> adding a shift command to the code instead of a division. >> Tell the Keil C51 compiler that. Okay, so: one more reasonable The compiler will implement it in such a way that there is no benefit in adding a shift command instead of a division. ;-)

by Jörg W. (dl8dtl) (Moderator)


Joachim B. wrote:> The preprocessor should do that and use 4 I suspect> times.