The Problem
The other day, I was working on an old project of mine on GitHub. This project had a lot of tasks to do, but the whole program was designed to run one task at a time, one after the other. It was slow, and I wasn't happy with how I had programmed it in the past (maybe because I was new to programming back then). So, I decided to break the program into smaller tasks, hoping to make it faster and improve its performance.
The Before and After Measurement
Before making any changes, I measured how long it took for the program to finish its job. After I finished optimizing it, I measured the time again, and I was surprised to find that the execution time remained the same both before and after the changes. Why did this happen?
Amdahl's Law: The Key Insight
As I looked into why this happened, I came across something called "Amdahl's Law."
from wikipedia :
In computer architecture, Amdahl's law (or Amdahl's argument) is a formula which gives the theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved.
Now, let's simplify this:
Amdahl's Law tells us that the overall speedup we can achieve by parallelizing a program is limited by the portion of the program that cannot be parallelized
So let's take a simple example:
imagine you have a race with different parts, like running and swimming. Amdahl's Law is like saying, "Your overall race time can never be faster than your slowest part of the race." In other words, even if you're really fast at running, if you're slow at swimming, your race won't be faster overall
The Parallelism Pitfall
in my case, the program was initially entirely sequential, meaning it had no inherent parallelism. When I divided it into smaller tasks, I introduced parallelism, which should theoretically lead to faster execution. However, here's the catch: Amdahl's Law reminds us that if a significant portion of the program still remains sequential and cannot be parallelized, the speedup will be limited.
Confronting Sequential Bottlenecks
in my scenario, I have found that a part of my program couldn't be broken down into smaller parallel tasks due to dependencies on other tasks. This non-parallelizable portion acted as bottleneck, preventing the program from running significantly faster, no matter how well-optimized the parallelizable parts were.
So, Amdahl's Law helped me understand that simply breaking down the program into smaller tasks and parallelizing it wouldn't yield the desired performance improvements. To make the program faster, I needed to identify and address the sequential bottlenecks that were holding it back. In essence, Amdahl's Law taught me that true performance gains require a comprehensive understanding of a program's limitations, not just a superficial attempt at parallelism.
Conclusion
In conclusion, let's sum up the important lessons i've learned about parallel programming in simpler terms:
Before you try to make your software faster with parallelism, Check if the program can be divided into smaller independent tasks and these individual tasks can be executed concurrently and independently. If you can do this, then this type of program can take advantage of parallel computing.
If your program can't be split into independent tasks, then parallelism won't help much. Some programs just can't be made parallel.
Identify the Performance Bottlenecks, these bottlenecks often hide in sequential portions of your program, which, if left unaddressed, can limit your optimization efforts.
You need to have deep understanding of your program's limitations.
Remember that parallelism isn't always the answer. If your program is small and simple, it might be better to keep it sequential. Parallel programming can be a lot more complicated, with threads and processes to manage, and tricky problems to solve.
That's all for now! 😊 I hope you've gained some valuable insights from this article. If you have any questions or if you've encountered similar challenges, please feel free to share them in the comments. I'm eager to read and respond to your comments, and I'm open to any suggestions you may have to improve this article. Happy coding!.
Top comments (2)
Thanks for the article. One thing I'd like to add is that beyond measuring/profiling starting performance, it's useful to set a starting hypothesis for what improvement changes are expected to bring, both a theoretical upper bound (assume the change will make some portion run in 0s), and an estimated realistic timesave (going from O^2 to O, perhaps) in terms of seconds and percent relative to starting performance under a representative load.
Doing this exercise before making changes will train this "deep understanding" of systems and oftentimes stop you from doing low-impact work.
I really appreciate you reading my article and I'm grateful for your valuable comment. I wanted to let you know that I did some research on what you suggested and it makes a lot of sense, I understood that before making changes to something, it's helpful to think about what we expect those changes to achieve. This includes two things: first, the best-case scenario where the changes make things super fast, and second, a more realistic estimate of how much time they might save compared to how things are right now. Your suggestion could be the basis for a whole new article!
Thank you again and I'd love to hear more of your thoughts in the future.