Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In every programming language there are sets of opcodes that are recommended over others. I've tried to list them here, in order of speed.

  1. Bitwise
  2. Integer Addition / Subtraction
  3. Integer Multiplication / Division
  4. Comparison
  5. Control flow
  6. Float Addition / Subtraction
  7. Float Multiplication / Division

Where you need high-performance code, C++ can be hand optimized in assembly, to use SIMD instructions or more efficient control flow, data types, etc. So I'm trying to understand if the data type (int32 / float32 / float64) or the operation used (*, +, &) affects performance at the CPU level.

  1. Is a single multiply slower on the CPU than an addition?
  2. In MCU theory you learn that speed of opcodes is determined by the number of CPU cycles it takes to execute. So does it mean that multiply takes 4 cycles and add takes 2?
  3. Exactly what are the speed characteristics of the basic math and control flow opcodes?
  4. If two opcodes take the same number of cycles to execute, then both can be used interchangeably without any performance gain / loss?
  5. Any other technical details you can share regarding x86 CPU performance is appreciated
share|improve this question

closed as off-topic by Josh Petrie Feb 3 at 1:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions that aren't specific to game development are off-topic here, but can be asked on Stack Overflow. A good rule of thumb is to ask yourself "would a professional game developer give me a better/different/more specific answer to this question than other programmers?"" – Josh Petrie
If this question can be reworded to fit the rules in the help center, please edit the question.

15  
This sounds a lot like premature optimization, and remember that the compiler doesn't output what you type in, and you really don't want to write assembly unless you really really have too. – Roy T. Apr 11 '12 at 10:02
3  
Float multiplication and division are totally different things, you should not put them in the same category. For n-bit numbers, multiplication is a O(n) process, and division is a O(nlogn) process. This makes division about 5 times slower than multiplication on modern CPUs. – sam hocevar Apr 11 '12 at 11:35
1  
The only real answer is "profile it". – Tetrad Apr 11 '12 at 17:00
1  
Expanding on Roy's answer, hand optimizing assembly is almost always going to be a net loss unless you're really really exceptional. Modern CPUs are very complex beasts and good optimizing compilers pull off code transformations that are entirely non-obvious and not trivial to code by hand. Even for SSE/SIMD, always always use intrinsics in C/C++, and let the compiler optimize their usage for you. Using raw assembly disables compiler optimizations and you lose out big. – Sean Middleditch Apr 11 '12 at 22:19
    
You don't need to hand-optimize to assembly to use SIMD. SIMD is very useful to optimize for depending on the situation, but there is a mostly-standard convention (it works on GCC and MSVC at least) for using SSE2. As far as your list is concerned, on a modern supserscalar multi-pipelined processor, data dependency and register pressure cause more issues than raw integer and sometimes floating point performance; the same is true of data locality. By the way, integer division is the same as multiplication on a modern x86 – OrgnlDave Apr 12 '12 at 4:19
up vote 9 down vote accepted

Agner Fog's optimization guides are excellent. He has guides, tables of instruction timings, and docs on the microarchitecture of all recent x86 CPU designs (going back as far as Intel Pentium). See also some other resources linked from http://stackoverflow.com/tags/x86/info

Just for fun, I'll answer some of the questions (numbers from recent Intel CPUs). Choice of ops is not the major factor in optimizing code (unless you can avoid division.)

Is a single multiply slower on the CPU than an addition?

Yes (unless it's by a power of 2). (3-4x the latency, with only one per clock throughput on Intel.) Don't go far out of your way to avoid it, though, since it's as fast as 2 or 3 adds.

Exactly what are the speed characteristics of the basic math and control flow opcodes?

See Agner Fog's instruction tables and microarchitecture guide if you want to know exactly :P. Be careful with conditional jumps. Unconditional jumps (like function calls) have some small overhead, but not much.

If two opcodes take the same number of cycles to execute, then both can be used interchangeably without any performance gain / loss?

Nope, they might compete for the same execution port as something else, or they might not. It depends on what other dependency chains the CPU can be working on in parallel. (In practice, there's not usually any useful decision to be made. It occasionally comes up that you could use a vector shift or a vector shuffle, which run on different ports on Intel CPUs. But shift-by-bytes of the whole register (PSLLDQ etc.) runs in the shuffle unit.)

Any other technical details you can share regarding x86 CPU performance is appreciated

Agner Fog's microarch docs describe the pipelines of Intel and AMD CPUs in enough detail to work out exactly how many cycles a loop should take per iteration, and whether the bottleneck is uop throughput, a dependency chain, or contention for one execution port. See some of my answers on StackOverflow, like this one or this one.

Also, http://www.realworldtech.com/haswell-cpu/ (and similar for earlier designs) is fun reading if you like CPU design.

Here's your list, sorted for a Haswell CPU, based on my best guestimates. This isn't really a useful way of thinking about things for anything but tuning an asm loop, though. Cache / branch-prediction effects usually dominate, so write your code to have good patterns. Numbers are very hand-wavey, and try to account for high latency, even if throughput is not an issue, or for generating more uops which clog up the pipe for other things to happen in parallel. Esp. the cache / branch numbers are very made-up. Latency matters for loop-carried dependencies, throughput matters when each iteration is independent.

  • 1 Bitwise / Integer Addition / Subtraction /
    shift and rotate (compile-time const count) /
    vector versions of all of these (1 to 4 per cycle throughput, 1 cycle latency)
  • 1 vector min, max, compare-equal, compare-greater (to create a mask)
  • 1.25 vector shuffles. Haswell and newer only have one shuffle port, and it seems to me it's common to need a lot of shuffling if you need any, so I'm weighting it slightly higher to encourage thinking about using fewer shuffles. They're not free, esp. if you need a pshufb control mask from memory.
  • 1.5 some 256b vector shuffle (extra latency on insns that can move data between 128b lanes of an AVX vector)
  • 1.5 load / store (L1 cache hit)
  • 2 inserting/extracting general-purpose registers into vector elements (_mm_insert_epi8, etc.)
  • 2 Integer Multiplication (3c latency/one per 1c tput on Intel, 4c lat on AMD and only one per 2c tput)
  • 2.5 shift / rotate by variable count (2c latency, one per 2c throughput on Intel, faster on AMD)
  • 2.5 Comparison without branching (y = x ? a : b, or y = x >= 0) (test / setcc or cmov)
  • 3 fp add/sub (and vector versions of the same) (1 or 2 per cycle throughtput, 3 to 5 cycle latency)
  • 3 int-> float conversion
  • 4 vector int/fp mul
  • 4 perfectly predicted Control flow (predicted branch, call, return)
  • 5 vector horizontal ops (e.g. PHADD adding values within a vector)
  • 12? load/store (L3 cache hit)
  • 13? Control Flow (poorly-predicted branch, maybe 75% predictable)
  • 15 (vector)FP Division (10-13c latency, one per 7c throughput)
  • 17 int division (yes really, it's slower than FP division, and can't vectorize). (note that compilers divide by a constant using mul/shift/add with a magic constant, and div/mod by powers of 2 is very cheap.)
  • 17 (vector)FP sqrt
  • 50? FP trig / exp / log
  • 50-80? always-mispredicted branch, costing 15-20 cycles
  • 200-400? load/store (cache miss)
  • 3000??? read page from file (OS disk cache hit) (making up numbers here)
  • 20000??? disk read page (OS disk-cache miss, fast SSD) (totally made-up number)

I totally made this up based on guesswork. If something looks wrong, it's either because I was thinking of a different use-case, or an editing error.

The relative cost of things on AMD CPUs will be similar, except they have faster integer shifters when the shift-count is variable. AMD CPUs are of course slower on most code, for a variety of reasons.

Keep in mind that it's really impossible to boil things down to a one-dimensional cost. Other than cache-misses and branch mispredicts, the bottleneck in a block of code can be latency, total uop throughput (frontend), or throughput of a specific port (execution port).

A "slow" operation like FP division can be very cheap if the surrounding code keeps the CPU busy with other work. (vector FP div or sqrt are 1 uop each, they just have bad latency and throughput. They only block the divide unit, not the whole execution port that it's on. Integer div is several uops.) So if you only have one FP divide for every ~20 mul and add, and there's other work for the CPU to do (e.g. an independent loop iteration), then the "cost" of the FP div could be about the same as an FP mul. This is probably the best example of something that's low throughput when it's all you're doing, but mixes very well with other code (when latency isn't a factor), because of low total uops.

Note that integer division is not nearly as friendly to surrounding code: On Haswell, it's 9 uops, with one per 8-11c throughput, and 22-29c latency. (64bit division is much slower, even on Skylake.) So the latency and throughput numbers are somewhat similar to FP div, but FP div is only one uop.

For examples of analysing a short sequence of insns for throughput, latency, and total uops, see some of my SO answers:

IDK if other people write SO answers including this kind of analysis. I have a much easier time finding my own, because I know I go into this detail often, and I can remember what I've written.

share|improve this answer
    
Great answer.... – Geotarget Jul 26 '15 at 7:24
    
The "predicted branch" at 4 makes sense -- what should the "predicted branch" at 20-25 really be? (I had thought that mis-predicted branches (listed around 13) were much more expensive than that, but that's exactly why I'm on this page, to learn something closer to the truth -- thanks for the great table!) – Matt Feb 2 at 19:49
    
@Matt: I think it was an editing error and was supposed to be "mispredicted branch". Thanks for pointing that out. Note that 13 is for an imperfectly-predicted branch, not an always-mispredicted branch, so I clarified that. I re-did the handwaving and made some edits. :P – Peter Cordes Feb 3 at 0:49

It depends on the CPU in question, but for a modern CPU the list is something like this:

  1. Bitwise, addition, subtraction, comparison, multiplication
  2. Division
  3. Control flow (see answer 3)

Depending on CPU there may be a considerable toll for working with 64 bit data types.

Your questions:

  1. Not at all or not appreciably on a modern CPU. Depend on CPU.
  2. That information is something like 20 to 30 years outdated (School sucks, you have now got proof), modern CPUs handle a variable number of instructions per clock, how many depend on what the scheduler come up with.
  3. Division is a bit slower than the rest, control flow is very fast if the branch prediction is correct, and very slow if it is wrong (something like 20 cycles, depend on CPU). The result is that a lot of code is limited mainly by control flow. Don't do with an if what you can reasonably do with arithmetic.
  4. There is no fixed number for how many cycles any instruction take, but sometimes two different instructions may perform equally, put them in another context and maybe they don't, run them on a different CPU and you are likely to see a 3rd result.
  5. On top of control flow the other big time waster is cache misses, whenever you try to read data that is not in cache the CPU will have to wait for it to be fetched from memory. In general you should try to handle data pieces next to one another simultaneously rather than picking data out from all over the place.

And finally, if you are making a game, don't worry too much about all this, better concentrate on making a good game than chopping CPU cycles.

share|improve this answer
    
I'd also like to point out that the FPU is pretty damn quick: especially on Intel - so fixed-point is only really needed if you want deterministic results. – Jonathan Dickinson Apr 12 '12 at 11:03
1  
I'd just put more emphasis on the last part - make a good game. It helps to have the code clear - which is why 3. only applies when you actually measure a performance problem. It's always easy to change those ifs into something better if the need arises. On the other hand, 5. is trickier - I definitely agree that that's a case where you really want to think first, since it usually means changing the architecture. – Luaan Apr 30 '14 at 7:43

I made a test about integer operation witch looped a million times on x64_64 , reach brief conclusion like below,

add ---116 microseconds

sub----116 microseconds

mul----1036 microseconds

div----13037 microseconds

the data above have already reduced the overhead induced by loop,

share|improve this answer

The intel processor manuals are a free download from their website. They are fairly large but technically can answer your question. The optimization manual in particular is what you are after, but the instruction manual also has the timings and latencies for most of the major CPU lines for simd instructions since they vary from chip to chip.

In general I would consider full branches as well as pointer-chasing (link list traverals, calling virtual functions) the top to perf killers, but the x86/x64 cpus are very good at both, compared to other architectures. If you ever port to another platform you will see how much of a problem they can be, if you are writing high performance code.

share|improve this answer
    
+1, dependent loads (pointer chasing) is a big deal. A cache miss will block future loads from even getting started. Having many loads from main memory in flight at once gives much better bandwidth than having one op require the previous to fully complete. – Peter Cordes Feb 4 at 5:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.