6 ms·

Amdahl’s Law is the single best thing I learned in 4 years of university. It sounds obvious when spelled out but it blew my mind. No amount of parallelization

by Swizec 1y ago

Amdahl’s Law is the single best thing I learned in 4 years of university. It sounds obvious when spelled out but it blew my mind. 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. https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law

godelski 1y ago
> It sounds obvious when spelled out but it blew my mind. I think there's a weird thing that happens with stuff like this. Cliches are a good example, and I'll propose an alternative definition to them. 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 At least, it works for a subset of cliches. Like "road to hell," "read between the lines," Goodheart's Law, and I think even Amdahl's Law fits (though certainly not others. e.g. some are bastardized, like Premature Optimization or "blood is thicker than water"). Essentially they are "easier said than done," so require system 2 thinking to resolve but we act like system 1 will catch them. 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
- chinchilla2020 1y ago
  another commonly misinterpreted one is the `shouting fire in a crowded theatre` quote. In it's original context it means the opposite of how people use it today.
  - comex 1y ago
    Well, sort of. The specific point Justice Oliver Wendell Holmes was making is pretty much the same as how it’s used today: some speech is so obviously harmful that it can’t be protected by freedom of speech. The problem is that Holmes was using it as an example of what even “the most stringent protection of free speech” would leave unprotected, and he went on to interpret the First Amendment rather less stringently, ruling that it didn’t protect anti-draft flyers.
hinkley 1y ago
> faster than the slowest non-parallelizable path 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?
ilc 1y ago
Interestingly, you didn't learn the full lesson: 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.
- Swizec 1y ago
  > The key is to understand the impact you CAN have, and what the business value of that impact is. :) 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?
  - naniwaduni 1y ago
    ... to the tune of about 10 cents a second, yeah. If you can hire a dev team to optimize one of those out, you plausibly come out ahead (well, vs face value).
    - what 1y ago
      How do you come out ahead hiring an entire team to save $6/hour?
      - naniwaduni 1y ago
        That's $6/minute, $360/hour. Granted, if you're using it at a scale approaching FTE costs, you probably want at least some reserved capacity and you're likely not paying face value, but then the comparison was never going to be rigorous anyway.
        what 1y ago
        Oh, I’m an idiot. Sorry, ignore me.
chinchilla2020 1y ago
There is more to it than that. 1. Decide if optimization is even necessary. 2. Then optimize the slowest path
nurettin 1y ago
There is also the "death by a thousand cuts" kind of slowness that accrues over time and it doesn't really matter where you start peeling the onion and the part you started is rarely the best.
adrian_b 1y ago
While Amdahl’s Law is very important, its practical effects are very frequently overestimated, at least as frequently as Knuth is misquoted. 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.
- p_l 1y ago
  I find Amdahl's Law very useful for parallelizable work as well. 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.
wiz21c 1y ago
Before optimizing, I always balance the time I'll need to code the optimization and the time I (or the users of my code) will effectively gain once the optimization is there (that is, real-life time, not CPU time). If I need three weeks to optimize a code that will run for 2 hours per month, it's not worth it.
- bruce343434 1y ago
  But by not optimizing, you don't grow your profiling/optimizing skills and you miss out on a reduction in how long optimizing takes you for future work. Therefore many more codes will not meet the threshold and your skills may not grow for a long time.
  - wiz21c 1y ago
    You couldn't know, but my job is 50% about optimizing computational workloads. But many times, when questionning my users, it happens that they want an optimisation for some code that will run 2 or 3 times. So eventhough they'll have to wait a week for the computation to run, it'll take me just as much time to make the optimisation run :-) 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 !
- bluGill 1y ago
  The one question that needs to be asked is would the users run it more often if it didn't take so long? There is nothing a computer can do that a room full of clerks in 1800 couldn't do, but the runtime would be so slow (or the cost in clerks so high) that nobody dared ask those questions. 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)
sethammons 1y ago
A former boss: an optimization made at a non-bottleneck is not an optimization.
- mholub 1y ago
  it's more nuanced: 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
  - sethammons 1y ago
    And if the app becoming faster doesn't mean anything because the app is waiting for user input the whole time, it was a lot of work for naught. Perhaps restated: If the optimization cannot be felt (ie, impact on the product experience), it is not an optimization worth pursuing.
    - eru 1y ago
      > And if the app becoming faster doesn't mean anything because the app is waiting for user input the whole time, it was a lot of work for naught. Oh, that might still be good for battery life (or power consumption in general).
    - progmetaldev 1y ago
      This one is more dangerous, as there may be backend resources in use that could be optimized, which could drop costs drastically. This may not change anything for your users, but is definitely worth exploring when it comes to getting the most out of your investment.

by Swizec 1y ago

godelski 1y ago

> It sounds obvious when spelled out but it blew my mind. I think there's a weird thing that happens with stuff like this. Cliches are a good example, and I'll propose an alternative definition to them. 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 At least, it works for a subset of cliches. Like "road to hell," "read between the lines," Goodheart's Law, and I think even Amdahl's Law fits (though certainly not others. e.g. some are bastardized, like Premature Optimization or "blood is thicker than water"). Essentially they are "easier said than done," so require system 2 thinking to resolve but we act like system 1 will catch them. 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

chinchilla2020 1y ago
another commonly misinterpreted one is the `shouting fire in a crowded theatre` quote. In it's original context it means the opposite of how people use it today.
- comex 1y ago
  Well, sort of. The specific point Justice Oliver Wendell Holmes was making is pretty much the same as how it’s used today: some speech is so obviously harmful that it can’t be protected by freedom of speech. The problem is that Holmes was using it as an example of what even “the most stringent protection of free speech” would leave unprotected, and he went on to interpret the First Amendment rather less stringently, ruling that it didn’t protect anti-draft flyers.

hinkley 1y ago

> faster than the slowest non-parallelizable path 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?

ilc 1y ago

Interestingly, you didn't learn the full lesson: 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.

Swizec 1y ago
> The key is to understand the impact you CAN have, and what the business value of that impact is. :) 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?
- naniwaduni 1y ago
  ... to the tune of about 10 cents a second, yeah. If you can hire a dev team to optimize one of those out, you plausibly come out ahead (well, vs face value).
  - what 1y ago
    How do you come out ahead hiring an entire team to save $6/hour?
    - naniwaduni 1y ago
      That's $6/minute, $360/hour. Granted, if you're using it at a scale approaching FTE costs, you probably want at least some reserved capacity and you're likely not paying face value, but then the comparison was never going to be rigorous anyway.
      - what 1y ago
        Oh, I’m an idiot. Sorry, ignore me.

chinchilla2020 1y ago

There is more to it than that. 1. Decide if optimization is even necessary. 2. Then optimize the slowest path

nurettin 1y ago

There is also the "death by a thousand cuts" kind of slowness that accrues over time and it doesn't really matter where you start peeling the onion and the part you started is rarely the best.

adrian_b 1y ago

While Amdahl’s Law is very important, its practical effects are very frequently overestimated, at least as frequently as Knuth is misquoted. 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.

p_l 1y ago
I find Amdahl's Law very useful for parallelizable work as well. 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.

wiz21c 1y ago

Before optimizing, I always balance the time I'll need to code the optimization and the time I (or the users of my code) will effectively gain once the optimization is there (that is, real-life time, not CPU time). If I need three weeks to optimize a code that will run for 2 hours per month, it's not worth it.

bruce343434 1y ago
But by not optimizing, you don't grow your profiling/optimizing skills and you miss out on a reduction in how long optimizing takes you for future work. Therefore many more codes will not meet the threshold and your skills may not grow for a long time.
- wiz21c 1y ago
  You couldn't know, but my job is 50% about optimizing computational workloads. But many times, when questionning my users, it happens that they want an optimisation for some code that will run 2 or 3 times. So eventhough they'll have to wait a week for the computation to run, it'll take me just as much time to make the optimisation run :-) 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 !
bluGill 1y ago
The one question that needs to be asked is would the users run it more often if it didn't take so long? There is nothing a computer can do that a room full of clerks in 1800 couldn't do, but the runtime would be so slow (or the cost in clerks so high) that nobody dared ask those questions. 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)

sethammons 1y ago

A former boss: an optimization made at a non-bottleneck is not an optimization.

mholub 1y ago
it's more nuanced: 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
- sethammons 1y ago
  And if the app becoming faster doesn't mean anything because the app is waiting for user input the whole time, it was a lot of work for naught. Perhaps restated: If the optimization cannot be felt (ie, impact on the product experience), it is not an optimization worth pursuing.
  - eru 1y ago
    > And if the app becoming faster doesn't mean anything because the app is waiting for user input the whole time, it was a lot of work for naught. Oh, that might still be good for battery life (or power consumption in general).
  - progmetaldev 1y ago
    This one is more dangerous, as there may be backend resources in use that could be optimized, which could drop costs drastically. This may not change anything for your users, but is definitely worth exploring when it comes to getting the most out of your investment.