What are you favorite low level code optimization

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 7 years ago.

I know that you should only optimize things when it is deemed necessary. But, if it is deemed necessary, what are your favorite low level (as opposed to algorithmic level) optimization tricks.

For example: loop unrolling.

Answer 1

precalculating values.

For instance, instead of sin(a) or cos(a), if your application doesn't necessarily need angles to be very precise, maybe you represent angles in 1/256 of a circle, and create arrays of floats sine[] and cosine[] precalculating the sin and cos of those angles.

And, if you need a vector at some angle of a given length frequently, you might precalculate all those sines and cosines already multiplied by that length.

Or, to put it more generally, trade memory for speed.

Or, even more generally, "All programming is an exercise in caching" -- Terje Mathisen

Some things are less obvious. For instance traversing a two dimensional array, you might do something like

    for (x=0;x<maxx;x++)
       for (y=0;y<maxy;y++)
          do_something(a[x,y]);

You might find the processor cache likes it better if you do:

   for (y=0;y<maxy;y++)
       for (x=0;x<maxx;x++)
           do_something(a[x,y]);

or vice versa.

Answer 2

Why, bit twiddling hacks, of course!

Answer 3

I wouldn't necessarily call it a low level optimization, but I have saved orders of magnitude more cycles through judicious application of caching than I have through all my applications of low level tricks combined. Many of these methods are applications specific.

• Having an LRU cache of database queries (or any other IPC based request).
• Remembering the last failed database query and returning a failure if re-requested within a certain time frame.
• Remembering your location in a large data structure to ensure that if the next request is for the same node, the search is free.
• Caching calculation results to prevent duplicate work. In addition to more complex scenarios, this is often found in if or for statements.

CPUs and compilers are constantly changing. Whatever low level code trick that made sense 3 CPU chips ago with a different compiler may actually be slower on the current architecture and there may be a good chance that this trick may confuse whoever is maintaining this code in the future.

Answer 4

Eliminating branches (if/elses) by using boolean math:

if(x == 0)
    x = 5;

// becomes:

x += (x == 0) * 5;
// if '5' was a base 2 number, let's say 4:
x += (x == 0) << 2;

// divide by 2 if flag is set
sum >>= (blendMode == BLEND);

This REALLY speeds things out especially when those ifs are in a loop or somewhere that is being called a lot.

Answer 5

In addition to Joshua's comment about code generation (a big win), and other good suggestions, ...

I'm not sure if you would call it "low-level", but (and this is downvote-bait) 1) stay away from using any more levels of abstraction than absolutely necessary, and 2) stay away from event-driven notification-style programming, if possible.

1. If a computer executing a program is like a car running a race, a method call is like a detour. That's not necessarily bad except there's a strong temptation to nest those things, because once you're written a method call, you tend to forget what that call could cost you.

2. If your're relying on events and notifications, it's because you have multiple data structures that need to be kept in agreement. This is costly, and should only be done if you can't avoid it.

In my experience, the biggest performance killers are too much data structure and too much abstraction.

Answer 6

The one from Assembler:

xor ax, ax

instead of:

mov ax, 0

Classical optimization for program size and performance.