This post originated from an RSS feed registered with Java Buzz by Lalit Pant. Original Post: Efficient Concurrency Feed Title: All Things Runnable / Java Feed URL: http://feeds.feedburner.com/lalitpant/java Feed Description: Java related posts on Lalit Pant's Blog Latest Java Buzz Posts Latest Java Buzz Posts by Lalit Pant Latest Posts From All Things Runnable / Java

• Using locks: but this is very inefficient under high read-write load, especially because multiple readers interfere with each other.
• Using read-write locks: this works better, because readers can run concurrently while no writes are taking place.
• Using non-blocking algorithms based on the Compare-and-Swap (CAS) primitive: this works very well at low to moderate load levels, but makes the application code more complicated.
• Using striping: where different sections of a large structure are protected with different locks (java.util.concurrent.ConcurrentHashMap uses this technique)
• Using copy-on-write structures: where a new copy of a structure is made on every write. Reads do not interfere with each other. This works well if the number of reads are much, much higher than the number of writes.
• Using immutable, functional structures: this is arguably the best way to manage concurrency. Reads do not interfere with each other. Writes need to acquire a lock for a very short time while replacing the root of the structure.

• The List class is abstract.
• List has two subclasses: Cons and Nil.
• Nil stands for an empty list.
• A Cons has two cells. One holds a value; the other points to the rest of the List. So a Cons essentially implements a singly-linked list.
  
• The last entry in a list is a Nil. At this point in the list, the rest of the list is empty.
• Users of the List class never see Cons and Nil. They create a List using a factory method, and then use List operations to work on the list.
• The core List operations are:
  

public List<T> prepend(T elem)
public T head();
public List<T> tail();
public boolean isEmpty();
public List<T> remove(T elem);

• The only way to add something to a list is to prepend() to it. This returns a new list with the additional element. Threads that already hold a reference to the list continue to see the list as it was before the prepend.
• head() and tail() give me a clean way to iterate through the list.
• isEmpty() allows me to check for the end of the list.
• As a concession to the need for modification, List supplies a remove(T elem) method. This returns a new list that does not contain the supplied element. The implementation of this method uses an optimized form of copy-on-write.