Friday, 21 June 2013

Amdahl's law and the root of all evil

Introduction


In the blog post "Why shared mutable state is the root of all evil." I was trying to explaining why it is important to use proper synchronization while accessing shared-mutable state in your concurrent programs to make sure they behave like expected. What I didn't get around to was talking about reasons why this synchronisation is so bad for performance and therefore the root of all evil for performance optimization.

Speedup


One performance measure is the speed-up of a programme. The speed-up basically compares the time a programme takes when executed one a single core to the time it takes to execute on multiple cores.



To calculate the speed-up (S2) on a dual core system simply measure the time to execute on a single core (T1) and divide to the execution time of on a dual core (T2).

For example if you are running a single-threaded program it doesn't matter how many cores your host system will have. The execution time will stay roughly constant and additional available cores will remain unused and idle. The speed-up therefore will be always one.

If you are running a perfectly parallelizable program on a dual core system the execution time will be exactly half the time than for a single processor system. In this case the program has a speed-up of 2. In cases where the program speed-up grows linear with the number of cores you add to the system we call it a "linear speed-up". That kind of speed-ups are the ideal.

In practise these kind of speed-ups are really rare and this is due to Amdahl's law.


Amdahl's law

What Amdahl's law basically says is that the maximal possible speed-up of a is determined by the part of the program which cannot run in parallel. For example this means if 50% of your algorithm are structured in a way they can't run by multiple threads then the maximal speed-up you will ever be able to achieve is 2. Say this algorithm would take 1 minute to execute on a single threaded system. If you optimize the heck out of your host system and let the algorithm run on with 100 threads you would be able to reduce the timing for the parallel (50%) part of the algorithm by factor 100. You still would be stuck with the single-threaded (50%) part of the algorithm which doesn't benefit from the additional threads. In the end the best you can ever achieve is a runtime of 30 seconds.

Below is a nice graph from wikipedia showing this law for different percentages of parallel proportions of the algorithm.


You can see that the different coloured graphs all flatten out after a while. Adding more threads to the equation doesn't result in any benefits any more. Even for an algorithm with 95% parallel proportion the maximal speed-up you can ever achieve is 20.

In practise having the algorithm run with a large number of threads is actually likely to reduce the speed-up again. This is due to the cost of multi-threading in the operating system like context switching.



What does this mean for my programs?

Like I tried to explain in my blog post "Free lunch for programers" the time of easy performance gains is over and only parallel programs will benefit from future advances in computer hardware. But because of Amdahl's law even parallel programs are very limited in its potential performance gains due to its non-parallel sections.

So in a way we have two conflicting forces: Safety and Performance. You need to use synchronization to make your concurrent programs correct and safe but by introducing synchronization you are installing so called critical sections which are essentially single-threaded and therefore harming performance.

By minimizing shared mutable state you can reduce the amount of synchronization used in your programs and therefore enable them to a higher performance.

Conclusion

Shared mutable state really is the root of all evil. Eliminate it wherever possible and your live as a developer will be a lot easier.


44 comments:

  1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Java developer learn from Java Training in Chennai. or learn thru Java Online Training India . Nowadays Java has tons of job opportunities on various vertical industry.

    ReplyDelete
    Replies
    1. Great Article Cyber Security Projects projects for cse Networking Security Projects JavaScript Training in Chennai JavaScript Training in Chennai The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

      Delete
  2. Gun Shot Strike Mod Apk is a new action capturing game. Is a globe loaded with dealing with as well as glory? Every element of the video game will make you really feel shocked. Now that you are an expert battle task force shooter, your goal is to damage all opponents. Hold your weapon and locate the terrorists around you through the radar.

    They do not know your presence, yet when you start Gun Shot Strike Mod Apk the adversary will find your presence, so be extremely careful. Attention to the enemy’s strike, to shield their very own safety. mission accomplished. Depending on the degree of Gun Shot Strike Mod Apk Unlimited Money and AI, you will encounter a number of obstacles. The world’s best multiplayer Basketball Stars Mod Apk No Root facilitate on reduced, from the makers of different raving accomplishment online redirections excitements! Sniper Killer Shooter Mod Apk is the really amazing game with the high graphics and setting with this you can play the game easily and without any hesitation so this game includes many features and the moded version has also

    Now you have a new mission! A terrorist team has occupied the S city, pirating innocent guests as hostages. As an excellent mercenary and also your goal is to eliminate all the terrorists and rescue the hostages. Here you require a cool head abnormality evaluation and quickly, aggressive, precise shooting methods, permit your head to cool down, to enjoy this tough video game now!

    ReplyDelete
  3. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Awaiting for your next update. Thanks
    DedicatedHosting4u.com

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Good blog information
    Sanjary Kids is one of the best play school and preschool in Hyderabad,India. Give your child the best preschool experience by choosing the best playschool of Hyderabad in Abids. we provide programs like Play group,Nursery,Junior KG,Senior KG,and provides Teacher Training Program.
    pre and primary teacher training course in hyderabad

    ReplyDelete
  6. Thanks for posting useful information.You have provided an nice article, Thank you very much for this one. And i hope this will be useful for many people.. and i am waiting for your next post keep on updating these kinds of knowledgeable things...Really it was an awesome article...very interesting to read..please sharing like this information.

    Thanks
    Cpa offers

    ReplyDelete
  7. Your post is very good. I got to learn a lot from your post. Thank you for sharing your article for us. it is amazing post
    what is seo
    types of seo


    ReplyDelete
  8. This is a fantastic idea! I like it a lot because it's super easy for the audience to see the value of opting in. wonderful and amazing post very use full your post thanks for sharing your article
    Android Application development
    Web application

    ReplyDelete
  9. Good blog posting information of the topic

    Sanjary Academy is the best Piping Design institute in Hyderabad, Telangana. It is the best Piping design Course in India and we have offer professional Engineering Courses like Piping design Course, QA/QC Course, document controller course, Pressure Vessel Design Course, Welding Inspector Course, Quality Management Course and Safety Officer Course.
    Piping Design Course
    Piping Design Course in Hyderabad ­
    Piping Design Course in India­

    ReplyDelete
  10. Thank you so much sharing this beautiful post.
    It is very helpful for us.
    tezlyrics.com

    ReplyDelete
  11. Excellent explanation of the blog posts I liked it

    Sanjary Academy provide pressure vessel design, quality management system course piping design course, qa/qc course and document controller course.
    Welding Inspector Course
    Safety officer course
    Quality Management Course
    Quality Management Course in India

    ReplyDelete
  12. Thanks for the informative article. This is one of the best resources I have found in quite some time. Nicely written and great info. I really cannot thank you enough for sharing.
    Data Science Online Training | Data Science Online Certification |Learn Data Science Course

    ReplyDelete
  13. Nice Post
    Yaaron Studios is one of the rapidly growing editing studios in Hyderabad. We are the best Video Editing services in Hyderabad. We provides best graphic works like logo reveals, corporate presentation Etc. And also we gives the best Outdoor/Indoor shoots and Ad Making services.
    Best video editing services in Hyderabad,ameerpet
    Best Graphic Designing services in Hyderabad,ameerpet­
    Best Ad Making services in Hyderabad,ameerpet­

    ReplyDelete
  14. good information
    "Sanjary Academy provides excellent training for Piping design course. Best Piping Design Training Institute in Hyderabad,
    Telangana. We have offer professional Engineering Course like Piping Design Course,QA / QC Course,document Controller
    course,pressure Vessel Design Course, Welding Inspector Course, Quality Management Course, #Safety officer course."
    Piping Design Course in India­
    Piping Design Course in Hyderabad
    Piping Design Course in Hyderabad
    QA / QC Course
    QA / QC Course in india
    QA / QC Course in Hyderabad
    Document Controller course
    Pressure Vessel Design Course
    Welding Inspector Course
    Quality Management Course
    Quality Management Course in india
    Safety officer course

    ReplyDelete

  15. 1croreprojects offersmobile computing projects chennai We list heaps of IEEE Final Year Studies (CSE, ECE, IT, EEE) projects.

    ReplyDelete
  16. 1croreprojects offersieee 2019 power system, electronics projects We list heaps of IEEE Final Year Studies (CSE, ECE, IT, EEE) projects.

    ReplyDelete
  17. Thanks for provide great informatic and looking beautiful blog, really nice required information & the things i never imagined and i would request, wright more blog and blog post like that for us. Thanks you once agian

    court marriage in delhi ncr
    court marriage in delhi
    court marriage in noida
    court marriage in ghaziabad
    court marriage in gurgaon
    court marriage in faridabad
    court marriage in greater noida
    name change online
    court marriage in chandigarh
    court marriage in bangalore

    ReplyDelete
  18. We as a team of real-time industrial experience with a lot of knowledge in developing applications in python programming (7+ years) will ensure that we will deliver our best in python training in vijayawada. , and we believe that no one matches us in this context.

    ReplyDelete
  19. Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care
    http://chennaitraining.in/creo-training-in-chennai/
    http://chennaitraining.in/building-estimation-and-costing-training-in-chennai/
    http://chennaitraining.in/machine-learning-training-in-chennai/
    http://chennaitraining.in/data-science-training-in-chennai/
    http://chennaitraining.in/rpa-training-in-chennai/
    http://chennaitraining.in/blueprism-training-in-chennai/

    ReplyDelete
  20. It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...
    http://chennaitraining.in/etl-testing-training-in-chennai/
    http://chennaitraining.in/java-training-in-chennai/
    http://chennaitraining.in/python-training-in-chennai/
    http://chennaitraining.in/r-programming-training-in-chennai/
    http://chennaitraining.in/salesforce-developer-training-in-chennai/
    http://chennaitraining.in/sap-hana-training-in-chennai/

    ReplyDelete
  21. Nice information. I’ve bookmarked your site, and I’m adding your RSS feeds to my Google account to get updates instantly.

    App development
    software developer

    ReplyDelete
  22. Nice information. I’ve bookmarked your site, fue turkey

    ReplyDelete
  23. They are very useful article. I like your post. Thanks for sharing your information. Fashion Designer Boutique in Mumbai

    ReplyDelete
  24. This site helps to clear your all query.
    This is really worth reading. nice informative article.
    vbspu bsc 3rd year result
    ddugu bsc 3rd year result

    ReplyDelete