We've just published a new article by Dibyendu Roy, Rethinking Multi-Threaded Design Principles, Part 2. In this article, Dibyendu presents and overview of the laws and principles that relate to application speed-up due to multithreading, then he talks about locks and non-blocking operations and their impact.
If you've worked with multithreaded development, your probably familiar with Amdahl's law, which defines the theoretical speed-up of an application when part of its code is parallelized. In Dibyendu's article, he presents the speed-up using this equivalent representation:
Speed Enhancement = 1 / (Fs + ((1 - Fs) / N))
Here, Fs is the fraction of the program that is running sequentially, and N is the number of cores or processors. Here's Dibyendu's explanation:
if N is 1, we get no speedup, but as N increases (tends to infinity, (1 - Fs)/N becomes 0), the speed is totally dependent on the 1/Fs part - which leads to the conclusion that, to improve execution speed of an application, we need to figure out ways or patterns to make more code execute in parallel.
This really is a very interesting equation, and it illustrates why sometimes beginning developers are stunned to find out that a performance improvement they spent days or weeks working on ultimately has little impact on the application's actual performance.
The question is: how do you "compute" Fs, the fraction of the program that is running sequentially? Do you divide the number of lines of code that run sequentiall by the total number of lines of code in the program? Of course not. Fs is really a measure of time. Fs is the amount of time that the unparallelized code occupies, divided by the amount of time the entire application takes to run when there is only one processor.
Hence, if the unparallelized code takes 10 seconds to run, and the parallelized code takes 5 seconds to run when there is a only one processor, Fs = 10/15 = 2/3; and the maximum speed-up of the application is only 1.5 (if you had infinite cores).
Practically, of course, the situation is very different. Multithreading an application actually adds more processing to the application -- all the management of the threads, potential dividing of the application's data into snippets which then have to be re-assembled after the parallel code has been executed, etc. This is why, believe it or not, a multithreaded application can actually run slower than its purely sequential, single-threaded starting point. This is increasingly possible the greater Fs is.
But wait! It gets worse. As Dibyendu notes, even when you have significant segments of code parallelized, there will almost always be points where
different parts of the code must contend for some resource that requires a lock. Whenever any thread tries to access a lock that's already being held by someone, it gets suspended first and awakened later when lock is available, thus spending some time doing nothing.
That's not good. Also, it requires a lot of care to properly implement locks. Dibyendu also talks about the non-blocking operation technique Compare-And-Swap (CAS). This is helpful in cases where there's something else a thread can work on if it finds that a locked resource is presently unavailable. But, what if there's nothing else for the thread to do?
Yes, writing multithreaded applications has been known to induce actual physical headaches for developers. Along with bruised hands, as they pound their desks while watching their apps hang forever due to a deadlock, or find that with each execution the app produces a different answer (due to threads overwriting each other's data)...
So, you might ask, if multithreading applications is so complicated, why even bother trying to do it?
Well, maybe to keep your job? If your product runs only on a single processor in 2015, and your competitor's product has a low Fs and can use all 16 cores on cheap $600 (US) machines that populate many corporate office desks and homes in 2015, how long do you think it will be before people switch from your doggedly slow app to your competitor's blazingly fast one?
• The inevitable (but profoundly silly) "Java is dead" (talios)
• The pragmatic (!) "it'll leave room for us youngsters" (in French)
• Somewhat cynic "Oracle is helping LOTS of companies with ex-Sun's :-)" (oemilio)...
1. Java EE 5/6 Patterns in Hamburg (26.04-30.04.2010) - some (3-5) places left. 2. 60 minutes with Java EE 6, 04.05 at JAX conference - this should be fun. I will hack a Java EE 6 application in 60 minutes on stage. Still no idea which one - but suggestions are highly appreciated. I will use Java EE 6 - and so less slides, than last year for explanation (Java EE 6 is even simpler, than Java EE 5) :-).
*After the session*, we will discuss Java EE 6 / EJB / JMS etc. features, problems and workarounds during the "open space" part at the JAX conference. Watch the table "Weightless Beans" in the Ballroom...
Debugging nondeterministic defects in multithreaded applications has to be one of the most painful and frustrating activities known to software developers. So, like a lot of people, I've been caught up in the excitement about concurrent programming with functional languages like Erlang and Scala. Both Scala and Erlang employ the actor model, rather than threads, for concurrent programming. Innovations around the actor model aren't limited to just languages; the actor model is also accessible on Java-based actor frameworks like Kilim...
In my last blog entry I described the generic user procedures as used in CAFE. These procedures can be used for registration and various parts of presence. In this installment I will go a bit deeper into the presence related user procedures, showing how to publish presence information on behalf of a user and subscribe to presence information...
I'm excited to show you all one of the things I've been working on since I joined Palm. Today we launched a new microsite called Palm Hot Apps. This is a leader board for our Hot Apps promotion, where the top selling & downloaded apps compete to earn bonuses between $1,000 and $100,000 dollars. Since this is a competition we wanted to have a constantly updated site that shows who's winning right now and who might be winning in the future. If you are a JavaScript developer, or interested in mobile app development in general, or just a Palm enthusiast, you'll definitely want to check out the site...
There were a few ripples around the Java community given that James Gosling the founding father of Java has left Oracle/Sun. I'm not that surprised, I'm sure many others are not either. Google must have made inquiries on more than one occasion and Sun had a number of painful years even when I was there, plenty of layoffs that made each release more difficult and that was 5 years ago. What does this mean to the day to day Java platform...
In the Forums, in the Metro and JAXB forum frans_van_buul asks about Case normalization of HTTP header names: Hi, We're using JAX-WS RI 2.1.7 for web service clients. We've noted that JAX-WS normalizes the case of HTTP header names to an initial upper case character followed by all lower case character. Formally, the case doesn't matter...
In the LWUIT forum, bakih posted a question about screen size ,please advise: i have a question. as i understand lwuit support in all screen size, is that current? if so how can i implement this issue, for example , if i put button in the center of the screen by using padding ,mergin in the resource manager is that the...
In the GlassFish WebTier forum, gabox01 has questions regarding Pojo extends HashMap: Hi, I would like my POJO entities to have dynamic properties. This way i could easily decorate my object graph with JSF specific information. For example: public class Category extends HashMap{ ...
Eduardo Pelegri-Llopart announces: "The replays from our presentation on the GlassFish Roadmap are now available in different formats, including SlideCast (Slides with synchronized audio)..."
Registered users can submit event listings for the java.net Events Page using our events submission form. All submissions go through an editorial review before being posted to the site.
Archives and Subscriptions: This blog is delivered weekdays as the Java Today RSS feed. Also, once this page is no longer featured as the front page of java.net it will be archived along with other past issues in the java.net Archive.
Previous Topic
