Programming without jumps

Question

I try to find articles, books or anything about programming without jumps (x86 arch). I know that generally it is impossible but I try to avoid jumps but gcc even with inline func uses jumps many times. Coding only in Assembly is some sort of solution, but writing equivalent of 1000 lines in C is like hell party to my eyes..

Answer 1

I think you may mean branching. In C there are bit twiddling tricks to use to speed up certain operations

See bit hacks:

http://www-graphics.stanford.edu/~seander/bithacks.html

Answer 2

Not knowing what your code looks like, it's hard to give any advice. But I will give it a try.

Before you start optimizing, run a profiling tool to locate the problem areas. After optimizing, run the profiling tool again to see if you actually made it faster.

It's hard to actually remove branches, but you can minimize them by doing loop unrolling.

Someone mentioned conditional move instructions, there's plenty of conditional instructions on the ARM architecture, but if they're not executed they will translate to a NOP and take one cycle each. Not sure how they work on x86. It might actually get slower then using a simple branch depending on how long the pipeline is.

There's a lot of other optimizing tricks you could try before removing branches.

Answer 3

Optimize only performance critical code, and only once you really know it is performance critical. Do not try to optimize jumps only because you read they case a performance hit. Everything causes a performance hit, and the fastest possible code is the code which does nothing. There are other things much worse than jumps.

If you will show a particular example of a jump in the generated code, chance is there will be some way to avoid it, but it is more likely the code you will show will still contain more serious issues.

One particular way how to avoid branches is to use "conditional move" instructions. They can be used e.g. to compute max or min. If you allow the compiler to use SSE architecture, it assumes the CPU also supports CMOV/FCOMI/FCOMIP/FUCOMI/FUCOMIP instructions and will use them (beware: sometimes it may be tricky to make the compiler to do what you want, see e.g. this gamedev.net discussion).

Answer 4

Unless your jumps are really random, branch prediction should eliminate most of overhead involved.

I would dedicate more effort to optimizing memory access patterns in order to improve locality and reduce cache misses. These days, memory latency is the major bottleneck to performance.

Another good direction is improving parallelism (using both vectorized SIMD instructions and, if possible, more than one core).

Answer 5

It is not impossible to code without jumps but it seems pointless to try.

In the end if you need to do something more than once then your choices are:

• Loop unrolling (i.e. repeating the code instead of looping).
• Somehow get the instruction pointer to visit the same code more than once.

The first approach requiers knowing the number of iterations in advance and doesn't scale and the second involves some sort of jump.