Let's say that you are writing a program where there are a very large number of scenarios. All of which are arithmetic in nature (a+b/c - . . .yada yada). So, you write an algorithm to deal with all of the scenarios. However, in real practice, only (100) of those scenarios are actually implemented 90% of the time. Would there be a speed savings to forgo the algorithm for those (100) scenarios and simply store those particular results in the binary, while implementing the algorithm for the others?
Benchmark, benchmark, benchmark ......
(Criterion is a fairly good library for that. Hyperfine if you're doing command line benchmarking).
3 Likes
I should have preambled my question with the fact that I am a newbie, so please respond as though I'm your favorite first-grader.
It depends...
If you have a 100 calculations like "a+b/c" where a, b and c are constants the compiler will calculate the results at compile time and plug them in where needed. No need to store the values, it's effectively done for you.
On the other hand if a, b and c are variables of 64 bit integer type then you all ready have bazillions of possible results depending on their values at run time. No hope of storing all of those.
As noted above, your best bet is to implement your code both ways and measure the execution time.
Note that if you do store bazillions of results in some kind of look up table then actually doing the look up could tale longer than recalculating the things. This is due to the way cache memory works on modern processors. Depends how many things you have and how complex each calculation is.
4 Likes
Okay, so I'll expand on my answer...
The sort of difference you're trying to ask advice about is very difficult to predict on an empirical basis. It depends on way too many factors, including actual sizes of the algorithms, version of the compiler, the exact processor model you're using. So, the only real test here is to implement it both ways and benchmark. If you need more specific help about benchmarking, you can ask about that.
Also, I am obliged (by the gods of computer engineering) to remind you that "premature optimization is the root of all evil". What this means is that only start optimizing when you have a roughly complete implementation. It's difficult to predict ahead of time what is the bottleneck (some experts can do that, though) and so your best bet would be profile your implementation, optimize, benchmark, repeat - until you're satisfied with the performance.
8 Likes
There is also another option:
Implement your algorithm behind a caching layer. I thinker I have seen some crates for this some time ago, my keyword for a search on crates.io / lib.rs would be memoization.
This technique is most often used in functional programming languages since they are more "mathematical" in some sense (functions usually cannot have side effects and, for example not depend on network or filesystem data), which allows the compiler to automatically include memoization for functions.
3 Likes
Only micro-optimize for speed if you have a reason to do it. Most of the time there is no real reason. If you're saving yourself 10 seconds of CPU time total, there is no reason to spend time trying to improve it. So usually you want to optimize for code simplicity. In which case you don't want to complicate the code by adding caching.
When you optimize for speed, first thing you want to do is to have a benchmark, or multiple benchmarks. I.e. a measurement of the speed. There are two reasons:
- You want to know what it is you're trying to optimize. Once you have a number, you have a specific thing you want to decrease.
- You want to have a way to measure whether or not a change you've just made is an improvement. Often what may intuitively seem like an improvement only makes things worse.
In your scenario, whether caching will help depends on the task. If the calculation is literally "a + b/c", then caching will likely only slow it down. Arithmetic operations are rarely a bottleneck.
1 Like
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.