No amount of parallelization will make your program faster than the slowest non-parallelizable path. You can be as clever as you want and it won’t matter squat unless you fix the bottleneck.
This extends to all types of optimization and even teamwork. Just make the slowest part faster. Really.
Simple problems, e.g. solving a system of equations, will usually include some non-negligible sequential part, which, according to Amdahl’s Law will limit the amount of speed-up provided by hardware parallelism.
On the other hand, complex problems, e.g. designing an integrated circuit, can usually be decomposed in a very great number of simpler subproblems that have weaker dependencies between them, than between the parts of a subproblem, so that by distributing the execution of the simple subproblems over parallel hardware that executes sequentially each subproblem you can obtain much greater acceleration factors than when attempting to parallelize the execution of each simple subproblem.
With clever decomposition of a complex problem and with good execution planning for its subtasks, it is much easier to approach the performance of an embarrassingly parallel problem, than when trying to find parallel versions of simple algorithms, whose performance is frequently limited to low values by Amdahl’s Law.
Amdahl’s Law frequently prevents you from reducing the execution time of some task from 1 minute to 1 second, but it normally does not prevent you from reducing the execution time of some task from 1 year to 1 week, because a task so complex to have required weeks, months or years before parallelization normally contains a great enough number of weakly-coupled subproblems.
Or at least, I find it trivially scalable to parallel case. Often it helped for me in modeling how interconnect would be a possibly limiting element for a task even for embarassingly parallel tasks.
Rather, than the slowest non-parallelized path. Ultimately you may reach maximum speed on that path but the assumptions that we are close to it often turn out to be poorly considered, or considered before 8 other engineers added bug fixes and features to that code.
From a performance standpoint you need to challenge all of those assumptions. Re-ask all of those questions. Why is this part single threaded? Does the whole thing need to be single threaded? What about in the middle here? Can we rearrange this work? Maybe by adding an intermediate state?
> It sounds obvious when spelled out but it blew my mind.
A cliche is a phrase that's so obvious everyone innately knows or understands it; yet, it is so obvious no one internalizes it, forcing the phrase to be used ad nauseam
Like Amdahl's Law, I think many of these take a surprising amount of work to prove despite the result sounding so obvious. The big question is if it was obvious a priori or only post hoc. We often confuse the two, getting us into trouble. I don't think the genius of the statement hits unless you really dig down into proving it and trying to make your measurements in a nontrivially complex parallel program. I think that's true about a lot of things we take for granted
In it's original context it means the opposite of how people use it today.
When optimizing, always consider the cost of doing the optimization vs. it's impact.
In a project where you are looking a 45/30/25 type split. The 45 may actually be well optimized, so the real gains may be in the 30 or 25.
The key is to understand the impact you CAN have, and what the business value of that impact is. :)
The other rule I've learned is: There is always a slowest path.
Like I tell everyone in system design interviews: AWS will rent you a machine with 32TB of RAM. Are you still sure about all this extra complexity?
How long does it take your team once to make that resource consumption go away permanently? An hour? Even a month? You'd still be ahead.
I’ve heard that some companies spend hundreds of millions per year on cloud hosting and it’s still worth it. I can’t even imagine that level of scale.
PS: The context in which I bring this up is a design exercise that would deal with maybe 5gb of data per month. People really over-complicate it :)
Sometimes leaving the spaghetti alone IS correct. Sometimes it isn't.
But most awful spaghetti happens because what it was asked to do was awful, IMHO.
I'd expect even rather junior programmers to recognize that the more time you spend working on a project the more new and unexpected things you find. New features, better ways to implement things, whatever. And ultimately, we all look back at code we wrote a year ago and are going to say "what idiot wrote this garbage?" I mean, if you don't, it is probably a sign that you aren't improving. It's impossible to write perfect code, and even if it was, what would be "perfect" is a moving target. So either way, you should be writing better code today when compared to yesterday.
> without the expensive big rewrite.
If I need three weeks to optimize a code that will run for 2 hours per month, it's not worth it.
But if code happens to be used 10 times a week and takes about a day or two to run, it's a no brainer: spending a month optimizing for 10% speed increase is worth it !
Exercise for the reader, given an unlimited budget to hire 1800's clerks how many FFS could you achieve running doom. (obviously the number is too low to make the game playable)
you're still releasing resources - so you might not become faster overall but you can compute more in the same time later if necessity arises (althougth that might be somewhat premature but can be good for library code - so it becomes more applicable in different environments)
and there are some rare but tricky scenarios like:
hardware is mobile phone: app seem to be bottlenecked on arithmetics according to the profiler, so it feels obvious to start optimization there
in reality what happens - hardware has limit on power, so it can't give full power to CPU, GPU and memory all at the same time
since app uses too much memory - it has to redirect power there, also memory emits heat, so CPU becomes throttled
By optimizing memory, everything runs colder -> CPU gets more power, can run sustained higher frequencies - app becomes faster
Perhaps restated: If the optimization cannot be felt (ie, impact on the product experience), it is not an optimization worth pursuing.
Oh, that might still be good for battery life (or power consumption in general).
It's a single line phrase, I wouldn't interpret it too literally. Usually you got to be pretty liberal when interpreting those easy to remember lines. It's a lot harder to remember the literally multiple books we could fill when bringing up exceptions.
1. Decide if optimization is even necessary.
2. Then optimize the slowest path