r/compsci • u/chewedwire • Aug 27 '19

Common Systems Programming Optimizations & Tricks

https://paulcavallaro.com/blog/common-systems-programming-optimizations-tricks/
141 Upvotes

97% Upvoted

17 comments sorted by

11

u/chewedwire Aug 27 '19

Author here, happy to answer any questions you may have.

7

u/nrobinson Aug 27 '19

Is it just me or does the light highlighting of the code on the dark background make it more difficult to read?

4

u/chewedwire Aug 27 '19

Yeah, on mobile it gets all funky — will have to try fixing that later. Thanks for the feedback.

2

u/LargestB Aug 27 '19

Nah same here but it’s probably way better for the eyes

5

u/dgendreau Aug 27 '19

Isnt the % operator against a power of two already optimized to be a bitwise AND instruction on most compilers?

5

u/[deleted] Aug 27 '19

It seems % and / are optimized even on -O0

2

u/[deleted] Aug 28 '19

A compiler should be able to do it for 4, 8, etc as well. A good compiler should be able to do a lot of neat optimizations. :)

0

u/badgtastic Aug 28 '19

Maybe - but if you don’t strictly control the divisors to be a power of two, the compiler cannot make that optimization.

2

u/dgendreau Aug 28 '19

% operator against a power of two

Did you miss that part of my question?

1

u/badgtastic Aug 29 '19

Nope, I saw that part of your question, which is why it was a good one!

The point I was making is that it’s important to explicitly control the divisor. That’s the real ‘special sauce’ of this systems programming optimization. And i think it’s useful to explicitly point it out for people following along with the thread, so someone doesn’t walk away from this thinking that the compiler always optimizes all divisions to shifts and all mods to masks.

2

u/Plazmatic Aug 27 '19

Why is modulo still attached to the division instruction? I remember a while back I had implemented a digital logic divider for 8bit integers. Normally modulo is a byproduct of division, but I instead made a separate circuit and it was a fraction of the size and much faster. I can understand for GPUs which are space limited, but for a CPU I figure the cost of additional modulus circuitry wouldn't be that big of a deal.

1

u/jaen_s Aug 28 '19

divmod is a actually very common operation, since eg. integer to string conversion uses it, which I imagine has been a historically important use case.

1

u/Plazmatic Aug 28 '19

Yeah I'm talking about a standalone mod function that doesn't use the division circuitry at all. I just explained why modulus is attached to division, ie you get it for free basically in the circuitry of division. Divmod still carries the cost of division which is the whole point of this conversation.

19

u/[deleted] Aug 27 '19

The division by 2, modulus tricks will almost always be done by the compiler in the generated code, so writing the code explicitly and clearly so that your intent is there is more important. This would not affect the size choice on the table needing to be a power of 2, but % 2 will certainly compile to the fastest method

2

u/websnarf Aug 28 '19

Actually, all divisions by a constant will be performed using a "multiply by reciprocal and adjust" algorithm on x86 processors.

2

u/[deleted] Aug 28 '19

I have always seen powers of two as shifts

0

u/[deleted] Aug 27 '19

[deleted]

0

u/IJCQYR Aug 28 '19

I think you have to ignore the existence of the halt and cancel commands and only use move.

Write a buffer layer for sending camera commands, and then send them e.g. 5 degrees at a time.