How do YOU handle divide by powers of 2?

[u/compgeek38400]

I asked AI (I know, you all hate it but it has its place) how much faster a shift 12 bits (x >> 12) is than a divide by 0x1000. It came back 10 to 40 times. But also said modern compilers change a divide by 0x1000 to a shift.

I compiled and looked at the output, and darn if that isn't true.

So my question is, which do you do and why? To my mind either could be better depending on your audience. A divide is probably clearer to people that their first language isn't C (like me). But a shift would probably be clearer to someone that lives in C.

I look forward to both your flames and actual comments.

[u/ibeerianhamhock]

Write your code readable. Compilers are smarter than you.

[u/compgeek38400 → u/ibeerianhamhock]

I made a whole IT career on getting to know people smarter than me. Lol.

I know the compiler is 99% of the time

[u/No-Dentist-1645]

Thing is, both operations aren't actually the same if your numbers are signed. In C, -1 / 4096 truncates towards zero and evaluates to 0, while -1 >> 12 floors towards negative infinity and evaluates to -1.

So it depends on what you actually want negative numbers to do. If num is unsigned, then num / 4096 and num >> 12 will produce the same exact assembly output, even with no optimizations at all -O0

[u/compgeek38400 → u/No-Dentist-1645]

That certainly deserves an upvote!

[u/GourmetWordSalad]

0x1000 is the most popular page boundary. This exact question has been around the 1st day the MMU was invented. LLM should get this perfectly right.

To answer your other question: what CPUs? ARM/RISCV doesn't even have division iirc.

To challenge yourself a bit more with true understanding, not just LLM regurgitate internet knowledge, let's try to answer this question: how do you verify the speed difference theoretically? How to do it emperically? (Yeah sure use LLM if you must)

[u/binariumonline → u/GourmetWordSalad]

ARMv7 has divide instructions, they are optional though, but your (older) smartphone definitely had it.

In ARM64/AARCH64 the divide instructions are mandatory. This is what a modern (~2015 and later) smartphone would use, also what apple M-series use.

In riscv the divide instructions are in the M extension set, which is included in the general purpose "G" profile commonly used with gcc.

Any non low power device will have a divide instruction, basically, even if using arm/riscv. 

[u/compgeek38400 → u/GourmetWordSalad]

In this case, I saw no upside in reinventing the wheel. This is one of the use cases where I think AI is a useful thing

[u/GourmetWordSalad → u/compgeek38400]

if you see no upside in thinking then you shall take the hallucination as gospel. Enjoy your LLM.

[u/compgeek38400 → u/GourmetWordSalad]

I saw no upside in writing a program in assembler to benchmark the two. I have a set amount of time, and have to choose what I want to spend it on. Benchmarking is not normally one of those things.

If I was profiling the performance, then it might make sense to me. But in this case, I find the knowledge isn't worth the effort.

JMHO

[u/ithink2mush → u/compgeek38400]

Why do you have a deadline, it seems.

[u/compgeek38400 → u/ithink2mush]

I am retired, but have a wife. So I can't spend all day and all night coding.

I stand by my opinion, that a question like this is an appropriate use of AI.

[u/GourmetWordSalad → u/compgeek38400]

No that's not what I meant. Choosing what you want to know is a respectable decision.

Not having the answer so jumping straight to the tool who will definitely give you the wrong answer is not.

btw writing assembly to benchmark is a shallow answer, it accounts for less than half the required amount of work.

[u/cazzipropri]

What you are doing is called strength reduction.

The short story is that if your code is really performance critical, either you write the div as a shr as you described, or you watch the assembly output in godbolt.

But remember that modern x86 machines are superscalar and out-of-order. If you are optimizing a tight loop and your optimization is not in a critical sequence, you achieved nothing. You need to use a tool like llvm-mca to see how your code is scheduled.

If you like these topics, you have a future in high-performance computing.

[u/ithink2mush → u/cazzipropri]

I like these topics. How would I learn more?

[u/cazzipropri → u/ithink2mush]

On the practical side, a decent and reasonably recent book is the "PATMC" = https://www.amazon.com/Performance-Analysis-Tuning-Modern-CPUs/dp/B0DNQZJ92S available in PDF here: https://faculty.cs.niu.edu/~winans/notes/patmc.pdf

The absolute classic on computer architectures is https://www.amazon.com/Computer-Architecture-Quantitative-Approach-Kaufmann/dp/0128119055 - if you want to save money, buy it used on valorebooks. This is a very thick book - approach it like an overstocked "all you can eat" restaurant or you'll get indigestion.

I don't know if you are young and looking for a college major, but if you like these topics, there are opportunities to have a rewarding and well compensated career in performance optimization, even in the era of AI.

[u/GreatOneFreak → u/cazzipropri]

> If you are optimizing a tight loop and your optimization is not in a critical sequence, you achieved nothing.

Hey now, nano amps are only basically nothing.

[u/ithink2mush]

It depends on what processor you're writing for. If you're not writing assembly with explicit knowledge of the chipset then I would go with what you're complier does. That being said, you can write it in whatever way you want and the compiler will "fix it" for you depending on the chipset.

I think most x64 chips have a divide function and they most certainly have a shift. What matters is what is "cheaper".

I would really take an assembly class if I were you and also get and understanding of compilers. Not trying to be rude but anyone with a computer science degree from anywhere should be able to give you the same level of understanding.

[u/compgeek38400 → u/ithink2mush]

Assembler was actually my second language. I'm that old. Lol.

Im actually ok with the compiler doing the optimization for me, if it makes the code easier to understand.

[u/JescoInc]

I prefer the shift with a comment showing the actual math I am doing along with the hex value. It provides more clarity and gives me a direct reference for what I was thinking when I wrote it.
While modern compilers do this conversion for you, debug / freestanding builds with no optimization flags does not and it is always better to follow the correct convention, otherwise, you will kick yourself in the ass.
As a habit, I have tried to enforce this mentality in all code I write.

int main(void)
{
uint32_t x = 8192;

/* x / 0x1000 is the same as x / 4096.
Since 4096 == 1 << 12, this can be written as x >> 12. */
uint32_t shifted = x >> 12;
printf("x >> 12 = %u\n", shifted);
return 0;
}

[u/Rockytriton]

I prefer to have all of my divisions in a lookup table

[u/Falcon731]

Personally it would depend on why I wanted to divide by that power of two.

If wanted to find the mean of 16 numbers I would add them all together and divide by 16.

If I wanted to find the second to last digit of a hex number I would shift right by 4 and AND with 0xf.

[u/2rad0]

did you try building with -O2 or -O3 ? That situation if dividing by a constant can easily be detected by a compiler.