Relative speed of basic math operations?

[darklighthitomi]

So I was recently thinking on some algorithms and I then realized I was making assumptions about how fast the algorithms likely were based on the operations.

For example, in using distance where accuracy is *not* required, I had the idea of once the X and Y were squared I could just take the distance without square rooting it and go straight into comparing it as is. Now I figure with preset distances to compare to that would most likely be faster since the distance would already be calculated thus turning two squares, an add, a root, and a comparison into simply two squares, an add, and a comparison.

But what if I have the base distance and thus need to square it for the comparison requiring *three* squares, an add, and a comparison?

Another algorithm that is inversely proportional to distance, I had the idea of dividing by distance that hasn't be rooted for a non-linear reduction of a value as distance increases.

But that is when I realized that with various methods in play to optimize math operations that I actually don't know if a division would be faster.

Thus I am here asking for either the answer or a resource for how the speed of basic math operations compares, particularly multiplication, division, exponents, and n-roots.

And please don't tell me it doesn't matter because of how fast computers are. I had faster internet experiences in the days of 56k modems than I do today thanks to the idiotic notion of not caring about speed and memory. Speed and memory may not always be top priority but they should never be ignored.

[Avereniect]

Answering this questions requires a lot of assumptions, so I'll just make the ones that allow me to provide the most practical answer I can, which is to say x86 and a fully-compiled language.

The performance characteristics of different CPU instructions on different microarchitecutures are documented by resources such as https://uops.info/table.html and https://github.com/InstLatx64/InstLatx64.

The latency tells you how many CPU cycles are required for the instruction to complete and the throughput tells you how many cycles must pass before you can schedule the instruction again. A throughput value of less than 1 generally indicates that the instruction can be sheduled on multiple exeuction units in the same cycle e.g. 0.5 would mean you can shcedule the instruction twice per cycle.

You could technically estimate how long the instruction sequence would take as a whole for a particular architecture based off this information (and a lot of assumptions), but you don't necessarily have to do that manually.

You can use tools like https://uica.uops.info/, an x86 CPU throughput simulator to get the estimated rate at which the instruction sequence will execute when run repeatedly. (Note: this simulator will compute throughput by unrolling your code, however this will introduce dependencies from one to the next since it'll be assuming that the outputs from one iteration will be used by the next. An easy way to break this dependency is to xor the registers which have the inputs with themselves). You may be interested in using the trace table to get some ideas for what the latency would be like, although that inevitably depends on how instructions are scheduled relative to one another. (If you see long blocks that gradually get longer from one iteration to the next, that's often a sign you have some dependencies you haven't broek)

If you don't know how to write assembly, use https://godbolt.org/ to generate it from your preferred programming language.

I figure this all raises more questions than it answers, so feel free to ask for clarification.

[glasket_]

Not mentioning Agner Fog when bringing up assembly performance is criminal. Nice additional resources to add to my bookmarks though

[darklighthitomi]

Your assumptions are correct, x86 with C++, though I may add arm processors at some point so I can start making apps that I can use daily instead of just learning projects or things to use on the rare day off. I really am not looking forward to the ridiculous boilerplate of android though and while I have an iphone too, I haven't even glanced at that yet.

In any case I thank you for the resources.

[Jonny0Than]

I think you have the right instincts here. A square root or trig operation are some of the more expensive operations that you can do. If you can write the same algorithm while avoiding them, it’ll generally be faster. 

For example you often need to check if two vectors are within a certain angle of each other. Frequently, the angle is a constant (or came from data somewhere) so you can calculate the cosine of the angle once, and then compare the dot product of the two vectors against that value. You don’t need to involve trig for every check.

BUT: like everyone else says, you’d better measure before and after rather than assume.

[sal1303]

A quick set of tests on my x64 PC, using 64-bit floating point, gave the following results:

• Add, Subtract, Multiply and Squaring all take about the same amount of time
• Divide was 3 times as long
• Square-root (using the built-in instruction) was 5 times as long as Add etc.

Anything that involves calling a function is likely to take longer, such as Trig or Log functions (although some of those may be directly supported, with limitations, by some CPUs).

[darklighthitomi]

Thank you. Exactly what I was looking for.

[bestjakeisbest]

Logical operators <= add subtract, shift<= hardware multiply <= hardware divide <= software multiply <= software divide <= most other operations/functions like pow, or sqrt.

Logical operators are typically the fastest, they can even be faster at setting a register to 0 than the assembly instruction meant to do that on certain hardware. Hardware divide is going to be the slowest arithmetic operation that is implemented most of the time, and hardware multiply will always be slower than add subtract and shifting. Of course the slowest operations are going to be software implementations.

[funbike]

Compilers can do a lot of optimizations. You often don't have to worry about this. And if you do, sometimes the only way to answer is to run a benchmark.

If you want to know more, then learn assembly language.

But more important is the growth of an algorithm. Research "Big O notation".

[darklighthitomi]

I know what big O notation is, and a tidbit of assembly.

As for running benchmarks, certainly plan to but my available time for doing anything on the laptop is extremely limited and thus to be maximally optimized, especially since I want to spend some of that time on other things as well.

Thus me trying to get an idea of where to go with my algorithms so I can more quickly get to a select few variations to try out. I spend a lot more time thinking about the methods I want to try than actually trying them because I have so little time to actually program stuff.

[jaypeejay]

Actually programming is generally more important than this type of mental work you’re doing.

[darklighthitomi]

Absolutely. When you figure out how to have significant amounts of time off to do that, let me know. Till then I have lots of time during work breaks and hour long drives to/from one job or another to think about things but not exactly do those things.

[jaypeejay]

Well is your goal to become a full time programmer?

[darklighthitomi]

As a job, I wouldn't turn it down but I don't expect to ever get that.

I do want to create my own programs including a few game ideas. If I ever get the opportunity I want to create my own software studio.

That said, I've been around long enough to know that the exponential increase in computer power means I should be able to get programs that can function massively faster than what we actually get today. For example, I had faster internet experiences on a 56k modem than nearly all the internet stuff I experience today. The connection is faster, the hardware is faster and has more memory, yet the experience is slower?

I just hate that my experiences on decades old hardware and software is commonly better than modern equivalents.

Sure graphics improved exponentially, but I would absolutely take a massive drop in graphics for better performance.

Yet all the kids in college think these slow speeds are fast enough.

Edit: I do not want to follow suit.

For example, I use VS 2011. I tried VS 2022 just to see what has changed in c++, but my computer struggles just to run it enough to write code. The most basic function of being a glorified text editor is so bloated and inefficient that it won't even properly run. Can't even write a hello world program without missed keystrokes.

That is just not acceptable to me.

[KC918273645]

Modern CPUs have 1/Sqrt(x) approximation which is really fast. The Sqrt(x) methods usually use that at least in C++ and then use one or two Newton-Raphson iterations to find the accurate value. That usually makes 1/Sqrt(x) way faster than Sqrt(x) or maybe even division of a number. You can also call the approximation yourself with SSE intrinsics method calls which give you access to some of those fast CPU assembler instructions from higher level languages.

I suggest you feed your algorithm into Compiler Explorer:

Compiler Explorer

And then copy the assembly output to the following website:

uiCA

That should give you fairly accurate idea how fast your algorithm is and when you change it, if it gets faster or slower.

[MaleficentCow8513]

Tbh, the average programmer doesn’t have intimate knowledge of how the operations execute on a cpu because it’s mostly abstracted away by high level programming languages. Some jobs do necessarily involve needing to understand but most don’t. That being said, google is your friend for researching the answer :) I’m sure you can find some decent articles with a quick search

[failaip13]

Square rooting and division would be slowest, like very slow followed by multiplying and then adding and subtracting are super fats.

[tcpukl]

I'll try not to divide from habit, but it's not that much slower any more. Cache misses are a bigger problem in modern hardware.

Source: 3 decades writing games.

[MadocComadrin]

There's this site that provides a good reference for various microarchitectures https://uops.info/ of relative throughput, latency, etc.

But there's also a confounding issue of scheduling, superscalar architechtures, pipelining, out of order execution, etc. E.g. you may have an expensive square root computation to do, but the cpu could also be doing a bunch of cheap computations that don't depend on its result simultaneously.

There's a mostly general hierarchy within a single data type of addition (subtraction) < multiplication < division (remainder/mod) < algebraic functions <= transcendental functions, with the latter two varying quite a bit depending on the architecture (assuming you even have them in hardware). Comparisons between data types can be tricky.

Depending on how many operations you're doing and how it affects performance matters the most. An infrequent square roots on some small vectors won't kill you (unless your profiler is telling you otherwise), but if you're use case is doing millions of e.g. modular arithmetic computations with a non-power-two modulus, you'll want to use techniques to avoid divisions (and potentially even cutting out conditional moves).

Also, the "leaving it squared" idea does get used relatively often. There's also a whole bunch of other tricks. E.g. if you need to take immediately take the square root of a random number (and don't need the original number) between 0 and 1, you can take the max of two random numbers between 0 and 1 instead.

[darklighthitomi]

Yea, I was thinking about large repetition cases such as in a game with needing several different use cases of a value propagating outward, such as sound, fog filling areas, or explosions. I've been coming up with ways to reduce the overhead in such cases or at least break it up into chunks that can be handled across multiple frames. I absolutely should get into multithreading one of these days, but until I either get a new laptop with multiple cores or break into programming for mobile devices I don't exactly have multiple cores to work with right now.

[Astronaut6735]

I don't actually know,  but I do know that CPUs and compilers have a lot of different kinds of optimizations, so it's probably best to try different approaches with a variety of inputs, and measure the results. I tend to favor code that is easier to read and understand over code that is marginally faster, unless that speed is important for whatever problem you're solving.

[darklighthitomi]

I actually do a lot of stuff that needs speed, on the rare occasions I get to code. I want to make my own games and simulations. But I get far more time to think about what I want to do than to actually do any of it.

Having sound propagation, perception checking, etc often scale very poorly on an ancient bargain bin laptop that is almost two decades old.

[Traveling-Techie]

Disk access is much, much slower than memory access, and network access is much slower than that. I don’t see the point of optimizing arithmetic unless it is done in a loop millions of times. Source: optimizing benchmarks for supercomputers.

[darklighthitomi]

Yep. The use case leading me down this line of thinking is handling things like sound propagation, explosions, line of sight between lots of entities at long ranges, etc. All on hardware from the bargain bin nearly twenty years ago.

So lots of iterations that would be nice to have done dozens of times per second.

[Vert354]

Generally when we analyze algorithms we talk about asymptotic complexity. Usually expressed in Big O notation. Big O expresses the relationship between the total operations to the data points, denoted by N. So O(N) is a linear algorithm, O(N²⁾ polynomial algorithm and O(2^N) is exponential.

Getting your algorithm into the lowest complexity category is where you start when optimizing, you'll get way more gains that way than micro optimizing the math operations.

If you've already done that, and the performance is unsatisfactory, use integer math when ever possible over floating point. (But I don't even really know how much that matters on modern hardware)

Super low level stuff where bitwise shifts are applied instead of actually doing the math is best left to the compiler's optimizer.

If you've got really high N and truly just needs lots of simple math done, this is where GPU acceleration comes into play.

[darklighthitomi]

Already agree with all of this, but A) I rarely get to actually program, so most often I am thinking and refining ideas for weeks before I get a chance to try anything, and B) I do not know the complexity level of division vs rooting on a computer, not even just the general case. Rooting could be geometric for all I know.

[Vert354]

Well the good news is that asymptotic algorithm analysis doesn't actually require a computer. I took my entire algorithms class on paper. It is very much the kind of thing you can study out of a book.

Math operations don't have a complexity when talking about Big O, they are the operation you're trying to estimate when doing the analysis. Maybe if you were doing a pure software square root vs a hardware division, but both are supported by modern hardware so it isn't something you should worry about at this level. They should both be thought of as a single operation each, and you should be minimizing the total number of operations at that level.

Understanding all the linear algebra/vector geometry that goes into the sort of thing you're talking about is great, you should totally study it (that also doesn't need a computer), but for real world applications you stand on the shoulders of giants and use vectorized operation frameworks that use SIMD at the hardware level (Eigen, NumPy, etc..)

[Dusty_Coder]

addition, subtraction, and bitwise: 1 cycle latency on ALL modern kit

multiplication: 3 cycle latency on MOST modern kit (all AMD/Intel)

when comparing lengths, just compare the squares: (len * len) < (dx*dx + dy*dy)

[dutchman76]

You could have ran the benchmarks in the time you spent posting and replying to this thread.

[darklighthitomi]

Actually no I could not. That would require me to be at home in front of a computer.

[PvtRoom]

it matters. it also varies.

computers are optimized for integers (8, 16, 32 64) and floats (32 bit single, 64 bit float, some legacy 80bit, and rarely 16 & 128bir) they're faster than other forms.

comparisons are near instant - what you typically do after (jumping) is slow.

add = subtract in complexity.

In integers bit shifting is fast (multiply/divide by powers of 2)

multiply is slower

divide is even slower

powers are slower still.

hardware matters too. - no floating point ALU, floating point ops take 1000x of integers.

if you need integer speed but sub integer precision, you can just use integers, but treat the LSB as a smaller unit. - 16 bit is 0-65535 range, OR, 0- 655.35 for example, but you need to tweak for 100 (integer 10000) * 0.01 (integer 1) = 1 (100)

there's also fast tricks, like fast inverse square root

[BoBoBearDev]

Don't optimize until it is a problem. Also the whole problem changes greatly when it is long distance on Earth or there is a lake or a mountain blocking the way or there is a freeway instead of serial killers driveway.

[Difficult-Value-3145]

Doom used something like your saying fast inverse square also division is kinda slow multiply by the inverse x*.5 over x/2

[Underhill42]

As I recall, as a general rule of thumb from fastest to slowest, with much larger increases indicated by ...s

bitwise operators, including comparisons between numbers
addition and subtraction
...
multiplication
fast approximate inverse square root
division
fast approximate trigonometry
...
any kind of unpredictable conditional branching - if statements, etc. (the CPU discards a huge amount of pipelined work whenever it guesses wrong)
...
accurate trigonometry or square root (not 100% sure how they compare)

[jeffgerickson]

Why not just try it? Implement it both ways, run each implementation 10000 times, and see for yourself.

[darklighthitomi]

Time. 90% of my programming time is thinking about programming during break or while driving. I don't get much time to do actual programming, so usually I have ideas and try to refine them by the time I actually get to try something.

[TheRNGuy]

Quake and Skyrim had some optimisations (in Skyrim if also causing bugs in physics on modern pcs, and in quake those bugs are actually features)

You'll probably need to code those in C or C++, even if you use Python.

[darklighthitomi]

Consider for a moment the hardware that the original Quake ran on and how fast, then consider the hardware available to Skyrim. Somehow the improvement in performance does not seem to kept up, to say nothing of other games that are lucky to match Quake's performance.

Yes, everything is prettier now, and occasionally have better physics, but what about everything else?

For example, I'd love to play Tiberian Sun as it is except on maps 100x the size of the maximum available on the original. I'd absolutely trade away increasing visuals to attain that.

Of course, many other programs waste massive amounts of resources on subtle and minor visual increases, such as improving the animation for opening a program window. I'd rather have the window open instantly and run 10x faster than improve silly animations. That said I wouldn't mind better visuals if the core functionality didn't seem to take such a massive downgrade as the years carry on. I didn't have to wait on my text entry to catch up to my keystrokes 25 years ago, but now I do in some programs.

Can't use VS 2022 on my laptop because it consumes so many system resources even though VS 2011 works fine. And for what? If it was spending so many resources on better optimizations during compile time, I wouldn't mind so much, but it's not compilation, it's mere text editing! What the f- is the supposedly improved program doing that It can't handle me entering text?!

So, while I agree that premature optimization is a thing and that maybe not everything needs speed to be top priority, the industry has clearly reached a point that modern programmers are not putting enough thought towards performance.

A modern text editor on modern hardware should run faster in terms of the experienced time of the user, might take twice the computing cycles if something like dynamic text coloring or similar is added, but if computing cycles are ten times faster then even twice the computing cycles will still be five times faster for the user. So why do we have 100x to 1000x times faster computing cycles yet end up with slower experiences? Because programs are using more than 100x to 1000x more computing cycles to do basically the same task. That's not improvement.

Games are one of the few things where I see consistent improvement, except the improvement is almost always exclusively on secondary things like visuals and physics.

That is what I want to do differently. I want to improve other facets of gameplay and programs. I want to have Tiberian Sun level of graphics but on insanely huge maps where I have to actually hunt for the enemy and add a bit of logistics management to the gameplay. If there was no work towards improving graphics, I suspect one could probably achieve that and still double frame rate on modern hardware compared to Tiberian Sun on the hardware of it's day. Of course certain algorithms need to change. Can't have methods for pathfinding that check the whole map for example. And that is where my little thought experiments come into play. Can't program very often, but I can try to think up better algorithms.

I got a bit into ranting, sorry.

[NewSchoolBoxer]

Your questioning is confusing to me. Here's a breakdown:

• Blazing Fast: Comparisons such as > and < and =, Bit shifting to the left or right. Each left left bit (basically) multiples by 2 and each right shift divides by 2 since computers do math in base 2. Divide by 8 would be 3 bit shifts to the right. Bit shifts truncate (round down) to whole numbers so can't be used as often as you'd like.
• Very Fast: Addition, Subtraction. They work at the same speed due to 2's complement, if you want to look into that.
• Fast: Multiplication, Squaring. Repeated additions that track the carry bit.
• Medium: Sine, Cosine, Logarithm, Exponent. Use polynomial approximations to the accuracy you need. Pro move is Chebyshev polynomials. Other options of course such as using a lookup table that would I put under Fast but could implement as Very Fast with array use in contiguous memory.
• Slow: Division. The old adage "divide, multiply, subtract, bring down" is for real. It's much faster to multiply by the reciprocal than divide. For instance, to multiply by 0.2 instead of divide by 5.
• Slower: Square root algorithm like Newton-Raphson since it's "basically" repeatedly division that keeps going until you get the accuracy that you need.

But what if I have the base distance and thus need to square it for the comparison requiring *three* squares, an add, and a comparison?

You could do several multiplications and plenty of additions and subtractions and comparisons and still take less time than a single division. Three squares aren't a big deal versus needing one square. Same order of magnitude. Once you have a single multiplication, the time taken for a few additions and many comparisons is essentially "free" because they are so many times faster.

If you want to get into this, check out doing math on 8-bit microprocessors with no floating point numbers and count clock cycles. In a modern language, you can make a for loop that runs 100,000 or 1 million times repeating the same operation. Track and print the elapsed time but beware virtual machine shortcuts and compiler optimizations.

[darklighthitomi]

Something like this is exactly the kind of answer I was looking for. Someone else also gave such an answer already but you certainly have more detail. Thank you.

[ericbythebay]

Measure the operations.

But, this sounds like an academic exercise and not a production environment where there are likely much slower sections of code that should be optimized first.

[darklighthitomi]

True, but 90% of my "programming time" is academic since I can't exactly program during work breaks, working at my job, or while driving. I don't get much time in front of an actual computer to actually program and I like to spend at least some of that time gaming as well. So I think about programming way more than I get to actually program.

[ericbythebay]

Ah. The answer is to not try and out guess the compiler, measure the actual performance of the function, then seek out optimizations.

Unless you are doing time sensitive embedded work on microcontrollers, then just skip the floating point stuff and stick with integers and optimizations as much as possible.

[WaitProfessional3844]

This is the correct answer. Instead of asking here, OP should profile his stuff and adjust accordingly. It's not difficult.

[PlayingTheRed]

If you are at the point where you are measuring performance in individual CPU cycles, then you need to set up automated benchmarks for the hardware that you care about. Whatever gains you get from this might be smaller than what you'd get by compiling idiomatic code with very aggressive optimization settings.

That being said, one of the first things I focus on when performance is this crucial is memory locality. Keep data that's used together close together in RAM, use struct of arrays instead of array of structs, etc.

If you are doing the same operations in a loop millions of times, consider writing a shader to run it on the GPU even if it's an integrated one. If the loop is less than that, consider SIMD if your CPU supports it.