0

I had begun scouring my code for optimization opportunities (execution speed, data parallelism, workload parallelism) yesterday when I noticed that there are very few opportunities for speeding up integer divisions. Integer division is heavily used in a hot spot area. Not only is it slow relative to the bit shifts, it’s possibly a showstopper for vectorization (data parallelism). If I want to use SSE/AVX as the design currently stands, the easiest way is to sacrifice some range so that all the intermediate calculations fit in 53-bits—the precision of a double since there are no instructions for integer division. The lack of integer division support is also apparent with “division-free” being a frequent selling point such as for specialized algorithms in the compression/encoding space.

How common or relevant is it in decision-making processes to pursue (or consider) division-free algorithms and data structures that will end up in hot spot areas of applications? It’s still pretty early in the design process for me so there’s opportunity to consider future needs like parallelization and CPU-architecture-dependent performance characteristics.

  • 1
    Any solution is as "common or relevant" to a problem as it fits to the problem. And optimization must always match the specific problem. Sorry, but I think without knowing exactly the problem you want to solve and the specific algorithm you want to implement for this goal, it makes not much sense to guess around if "division-free algorithms and data structures" might be of help. – Doc Brown Apr 29 at 19:22
  • 1
    Why not tell us what exactly your problem is, instead of asking for blind guesses? – gnasher729 Apr 29 at 20:02
  • 1
    If you have a small number of constant divisors, you can pre-compute the inverse such that multiplying by the inverse will give you the quotient, modulo the word size. This is a technique often used on old mini- and micro-computers for converting from binary to decimal. – BobDalgleish Apr 29 at 20:37
  • The subject matter may be more suitable for Computational Science Stack Exchange site. (Note: it is different from the Computer Science site.) Refer to their on-topic guideline for details. – rwong Apr 30 at 1:21
5

Division always has been and always will be one of the slower operations for CPUs, no matter if integer or floating point. This has to do with the very nature of that operation. You can also see that by the fact that all clever compilers will optimize f / 4.0 to f * 0.25 and i / 4 to i >> 2 (f = floating point value; i = integer value), as there is no guarantee that this will be faster for sure but can you show me just one CPU where this will be slower? I don't know of any, so you can only win by this optimization. There used to be times where multiplication also was among the slower operations (still much faster than division, though) but today it is almost as or even equally fast as addition. And bit shifting has always been among the fastest operation a CPU would offer.

On the other hand, division is not that horrible. On an Intel Core-i Skylake generation a 32 bit unsigned integer division takes 26 clock cycles. This may sound like a lot but keep in mind that no instruction can be less than a single clock cycle, so in the same time you could at most have performed 26 other operations. Thus a 32 bit division is as expensive as 26 additions, shifts or logical operations, which isn't that bad. Throwing two divisions into an already very complex calculation will not make a huge difference for the overall performance in most cases, especially as modern CPUs don't have to perform operations strictly serialized, they may overlap. That means an operation may start, while the last operation is still in progress and the next operation may start before the current one has completed. When you perform one thousand integer divisions in a row, they will overlap with a latency of 6 clock cycles only. So it will take 26 cycles before the first result arrives but after that you will get the next result every 6 clock cycles, as every 6 clock cycles the next division can start.

64 bit is a different thing, though, as it takes 35 to 88 clock cycles and even with overlapping it will take 21 to 83 clock cycles (again for Skylake). On the other hand, a 4 core Skylake running at 2.8 GHz has 2,800,000,000 clock cycles available per second per core, so even with the worst case of 83 clock cycles it can perform almost 34 Mio divisions a second per core. So don't assume a few divisions are an issue until you know that for sure. Also the overlapping limit is only the limit between divisions, other operations like additions or multiplications don't block divisions at all and aren't blocked by divisions either. So while your division is still in progress, other operations will often be performed in parallel, which is possible as long as they don't depend on the division result. To make optimal use of that ability (running instructions in parallel), these CPUs even emulate virtual cores (hyper-threading), where one physical core performs instructions for two virtual ones as often these can be performed in parallel as otherwise large parts of the CPU potential would go unused.

In practice, the speed of divisions or the lack of SIMD support for certain kind of integer divisions is often irrelevant. Neither one will usually be the bottleneck of your performance. If it is, you may want to look for a way to avoid the divisions but I wouldn't try to avoid them to begin with, that is just premature optimization. Be sure to write your code flexible (e.g. with swap-able modules) and if it turns out that a module with division is the cause of a performance issue, swap it with one that avoids division, yet no need to touch the rest of the system with clean module separation. Even operating system kernels work that way today (split code into modules and swap them if there is an issue or a better one) and those are already at the very low level end of development. Also 3D game engines work that way and they need to perform an awful lot of divisions to paint a single frame to screen, yet with floating point numbers, that's why CPUs and GPUs have SIMD instructions for floating point division. Integer division is usually not such a common operation that an extra SIMD instruction would pay off.

The key point of optimization is to profile your code and find out exactly what the bottleneck is. If data is processed through several steps in a pipeline and one of these steps performs a lot of divisions yet isn't the slowest processing step, even eliminating all the divisions will have no impact on the overall performance as you always need to optimize the slowest step first. And if the slowest one uses division, it's not said that these are responsible for the slowness. You need to know exactly how much time is spend at which code lines during runtime to make a reasonable decision on what to optimize.

Oh, and if anyone cares for the clock cycles of various x86 instructions on different CPUs, here is a very detailed list, listing almost all x86 CPUs from Intel, AMD, and Via that can still be seen relevant as of today.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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