The Artima Developer Community
Sponsored Link

Java Community News
Nonblocking Algorithms: Performance and Complexity

2 replies on 1 page. Most recent reply: Apr 30, 2006 12:50 AM by Peter Booth

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 2 replies on 1 page
Bill Venners

Posts: 2244
Nickname: bv
Registered: Jan, 2002

Nonblocking Algorithms: Performance and Complexity Posted: Apr 27, 2006 2:08 PM
Reply to this message Reply
Summary
In a recent developerWorks article, Brian Goetz illustrates using the Java 5.0 concurrency package to implement non-blocking algorithms. He compares the complexity of blocking and non-blocking algorithms, and the performance implications.
Advertisement

In the article, Introduction to nonblocking algorithms, author Brian Goetz explains that compared to blocking algorithms, non-blocking algorithms take a more optimistic approach:

[Non-blocking algorithms] proceed with the assumption that there will be no interference. If interference is detected, they back off and retry.

As a result, they tend to outperform blocking algorithms when the number of threads vying for the resource is relatively low:

Under light to moderate contention, nonblocking algorithms tend to outperform blocking ones because most of the time the CAS [compare-and-swap operation] succeeds on the first try, and the penalty for contention when it does occur does not involve thread suspension and context switching, just a few more iterations of the loop....Under high contention—when many threads are pounding on a single memory location—lock-based algorithms start to offer better throughput than nonblocking ones because when a thread blocks, it stops pounding and patiently waits its turn, avoiding further contention.

Although a non-blocking algorithm may tend to perform better than its blocking counterpart in common situations, non-blocking algorithms may also tend to be more complex:

Nonblocking algorithms tend to be far more complicated than lock-based ones.

When do you feel it is appropriate to reach for a non-blocking algorithm? If you think the non-blocking approach is more complex than an equivalent blocking approach, would you consider using the non-blocking approach a performance optimization, one that you should reach for only if you discover you have a real performance problem with a blocking alternative?


Slava Imeshev

Posts: 114
Nickname: imeshev
Registered: Sep, 2004

Re: Nonblocking Algorithms: Performance and Complexity Posted: Apr 28, 2006 4:20 PM
Reply to this message Reply
> <p>
> When do you feel it is appropriate to reach for a
> non-blocking algorithm? If you think the non-blocking
> approach is more complex than an equivalent blocking
> approach, would you consider using the non-blocking
> approach a performance optimization, one that you should
> reach for only if you discover you have a real performance
> problem with a blocking alternative?
> </p>

To make long story short here is the book that was written by the author of the java.concurrent and that answers these questions. This is a must-read book:

http://www.amazon.com/gp/product/0201310090/

Though it talks about Java, the concurrency primitives and the approaches to developing concurrent software in this book are applicable to any language.

Regards,

Slava Imeshev

Peter Booth

Posts: 62
Nickname: alohashirt
Registered: Aug, 2004

Re: Nonblocking Algorithms: Performance and Complexity Posted: Apr 30, 2006 12:50 AM
Reply to this message Reply
> > <p>
> > When do you feel it is appropriate to reach for a
> > non-blocking algorithm? If you think the non-blocking
> > approach is more complex than an equivalent blocking
> > approach, would you consider using the non-blocking
> > approach a performance optimization, one that you
> should
> > reach for only if you discover you have a real
> performance
> > problem with a blocking alternative?
> > </p>
>
> To make long story short here is the book that was written
> by the author of the java.concurrent and that answers
> these questions. This is a must-read book:
>
> http://www.amazon.com/gp/product/0201310090/
>
> Though it talks about Java, the concurrency primitives and
> the approaches to developing concurrent software in this
> book are applicable to any language.
>
> Regards,
>
> Slava Imeshev

I think the question about non-blocking algorithms is a good question. I think what's important to first consider is which algorithm fits. For example, using an atomic to increment an int counter is clearly better answer than synchronizing reads and writes of the counter. There will be some obvious use cases for say ConcurrentHashMap. For some constructs, such as reader/writer locks, choosing the optimal approach requires an understanding of the likely input data and probably some testing. The bottom line is that concurrent programming is hard and its a mistake to assume that because something sounds "reasonable" a concurrent application will behave the way a reasonable programmer might expect.

You make a great point about Doug Lea's book, but it's also worth acknowledging that Lea is a genius and his book is hard for a non-genius to grok. I own both editions, have read it at least four times, but I'm delighted that Brian Goetz has a book on concurrency coming out and look forward to reading it. Unfortunately many of the books on (Java) concurrency are flawed, confusing, and sometimes plain wrong

Flat View: This topic has 2 replies on 1 page
Topic: Nonblocking Algorithms: Performance and Complexity Previous Topic   Next Topic Topic: How Do You Test JavaScript?


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us