public static ByteBuffer allocate(int length) {
	ByteBuffer byteBuffer = ByteBuffer.allocate(length);
	byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
	return byteBuffer;
}

public static ByteBuffer duplicate(ByteBuffer buffer) {
	ByteBuffer duplicateBuffer = (ByteBuffer)buffer.duplicate();
	duplicateBuffer.order(buffer.order());       // duplicate() does not preserve ordering!
	return duplicateBuffer;
}

class User {

    String name

    String emailAddress

    Date dateOfBirth

    int weight

    String toString() {
        name
    }

}

def frank  = new User(name:"Frank Thompson", dateOfBirth: new Date(75, 0, 11), weight:150)
def bob    = new User(name:"Bob Turner", dateOfBirth: new Date(67, 4, 9), weight:115)
def james  = new User(name:"James Van Klein", dateOfBirth: new Date(58, 11, 13), weight:175)
def brad   = new User(name:"Brad Franklin", dateOfBirth: new Date(105, 7, 23), weight:25)

def userList = [frank, bob, james, brad]

public class UserNameComparator implements Comparator<User> {

    public int compare(User a, User b) {
        def aValue = a.getName();
        def bValue = b.getName();

        if (!aValue && !bValue)
            return 0;
        else if (!aValue)
            return -1;
        else if (!bValue)
            return 1;
        else
            return aValue.compareTo(bValue);
    }

}

def sortClosure = { attribute a, b ->
    def aValue = a.@"${attribute}"
    def bValue = b.@"${attribute}"

    if (!aValue && !bValue)
        return 0
    else if (!aValue)
        return -1
    else if (!bValue)
        return 1
    else
        return aValue.compareTo(bValue)
}

println "Sorted by name: ${userList.sort(sortClosure.curry('name'))}"
println "Sorted by email address: ${userList.sort(sortClosure.curry('emailAddress'))}"
println "Sorted by dob: ${userList.sort(sortClosure.curry('dateOfBirth'))}"
println "Sorted by weight: ${userList.sort(sortClosure.curry('weight'))}"

July 5, 2007

Introducing the Java Concurrency APIs

Posted in Design, Java at 4:13 PM by Kirk True

I recently had the privilege of helping one of my clients conduct technical interviews for a Senior Java Developer position. I enjoy interviewing candidates in part because it gives me a chance to learn something. While conducting the interviews I did learn a few things, so I’m happy However, one unfortunate thing I learned is that not many developers are familiar with the Java Concurrency APIs. Only one developer out of about 20 that we interviewed had used it, and only two or three had even read up on it. Now, I certainly don’t expect that everyone know every API out there. But in the case of this particular position, we needed someone who knew how to write multi-threaded applications correctly. There are many reasons to get up to speed with the APIs, especially if your applications operate in a multi-threaded environment as my client’s does.

So – I want to share some data that may motivate you to take a further look into the Concurrent APIs if you haven’t done so already. But first let’s take a 30,000 foot view of the APIs. (If you’re really impatient, skip down to the graphs, then come back here to find out what they mean.)

Overview of the Concurrency APIs

The java.util.concurrent package was introduced via JSR-166 and is present as a standard part of the Java libraries as of Java 5. However, for those unfortunate souls still on JDK versions 1.3 and 1.4 there are at least two mainstream back-port implementations of the concurrent package:

• Doug Lea’s
• Emory University’s

This refutes the notion that the Concurrency APIs are only for those whose product requires Java 5 or above.

The Concurrency APIs offer many different interfaces and classes to help with your multi-threaded application. So we’ll focus on one specific subset of the Concurrency APIs found in the java.util.concurrent.lock package: the Lock interface. An object of type Lock is an object representation of a lock in the JVM, similar to the synchronization primitive offered by the synchronized keyword. Rather than use a specific keyword, the Lock object represents the lock using class(es) and methods on which the lock is enabled, disabled, and so forth. The core Lock API contains a handful of methods, but the two most important are:

public interface Lock {

    public void lock();

    public void unlock();

}

These are the main methods used to perform — you guessed it! — locking and unlocking. OK, admittedly, the Lock interface doesn’t look convincing enough to run out and switch all your tried-and-true-and-tested code over to the Lock API. But let’s look at another interface in the java.util.concurrent.locks package: ReadWriteLock. Here is the interface in its entirety:

public interface ReadWriteLock {

    public Lock readLock();

    public Lock writeLock();

}

Wow – pretty short! But as you’ve probably guessed, the ReadWriteLock API is a step toward implementing the read-write locking pattern in your code. Let’s note the JavaDoc for the interface for what this pattern can achieve:

A ReadWriteLock maintains a pair of associated locks, one for read-only operations and one for writing. The read lock may be held simultaneously by multiple reader threads, so long as there are no writers. The write lock is exclusive.

So if the usage pattern of a particular piece of synchronized data is read-mostly, it’s possible to have more than one reader thread in the critical section. But when a write does occur, all other readers (and writers) will block until the current writer is finished. But unless a write is being performed, the code can achieve a higher degree of parallelism.

Usage of the Concurrency APIs

To see how straightforward it is to use the Lock as a replacement for the synchronized keyword, let’s use an example. My canonical example is, of course, a cache:

public interface Cache<K, V> {

    public void put(K key, V value);

    public V get(K key);

}

Let’s look at the pre-Concurrency API implementation that uses “classic” synchronization:

public class ClassicallySynchronizedCache<K, V> implements Cache<K, V> {

    private Map<K, V> cache = new HashMap<K, V>();

    public void put(K key, V value) {
        synchronized (cache) {
            cache.put(key, value);
        }
    }

    public V get(K key) {
        synchronized (cache) {
            return cache.get(key);
        }
    }

}

Pretty straightforward. Our cache allows for insertions and retrievals and uses synchronization to ensure that we don’t have any concurrency issues internal to our java.util.HashMap. Now let’s see how the code can be revised using the Lock API:

public class LockCache<K, V> implements Cache<K, V> {

    private Map<K, V> cache = new HashMap<K, V>();

    private Lock lock = new ReentrantLock();

    public void put(K key, V value) {
        try {
            lock.lock();
            cache.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    public V get(K key) {
        try {
            lock.lock();
            return cache.get(key);
        } finally {
            lock.unlock();
        }
    }

}

As was mentioned, there are no longer blocks of code demarcated by the synchronized keyword. Instead, we have replaced that with a Lock object upon which we lock and unlock around our critical section.

Now let’s implement our Cache using the ReadWriteLock interface:

public class ReadWriteLockCache<K, V> implements Cache<K, V> {

    private Map<K, V> cache = new HashMap<K, V>();

    private ReadWriteLock lock = new ReentrantReadWriteLock();

    public void put(K key, V value) {
        try {
            lock.writeLock().lock();
            cache.put(key, value);
        } finally {
            lock.writeLock().unlock();
        }
    }

    public V get(K key) {
        try {
            lock.readLock().lock();
            return cache.get(key);
        } finally {
            lock.readLock().unlock();
        }
    }

}

The natural progression of the code is to separate the locks used to manage the reads/gets and writes/puts. These are both managed by the ReadWriteLock implementation to ensure that the locks coordinate and function as defined.

Results

But – as they say – the proof is in the pudding. Does all of this actually have any benefit for parallelization? Let’s take a comparative look of these three implementations running under different scenarios.

These scenarios usage different usage patterns to show how the different locking schemes affect parallelization. These results are generated using a benchmark tool I wrote to test out different locking schemes. The benchmark tests each of the three above styles of locking in a parameterized fashion so as to approximate a specific usage pattern. The test machine is a Core 2 Duo E6700 with 2 GB of RAM running Linux Fedora with Java 1.6.0_01. All listed times are expressed in milliseconds.

Scenario 1: Read-mostly, Fast Reads, Infrequent Writes

The first locking scenario is characterized by:

• Reading threads outnumber writing threads 4:1
• Read threads each perform 10,000,000 reads from the cache
• Read lock duration short (reading shared data takes near-zero time)
• Write lock duration medium (writing shared data occurs every second and takes 10 milliseconds)

Here we see that simply switching to a Lock-based locking scheme improves performance by 5x over the old-style synchronized approach even though the degree of parallelization is the same (only one reader or writer in the critical section concurrently). Interestingly, we note that while the ReadWriteLock does offer better parallelization (via more than one reader in the critical section at a time), the overhead of the internal locking algorithms is enough to degrade performance to where speed wins out over parallelization.

Scenario 2: Read-mostly, Slow Reads, Infrequent Writes

The second locking scenario is characterized by:

• Reading threads outnumber writing threads 4:1
• Read threads each perform 100 reads from the cache
• Read lock duration long (reading shared data takes one millisecond)
• Write lock duration medium (writing shared data occurs every second and takes 10 milliseconds)

Here we see that simply switching to a Lock-based locking scheme does not improve performance over the old-style synchronized approach. However, just look at how much more parallelization we achieve by taking advantage of the ReadWriteLock mechanism — performance increases by nearly 40x! We achieve better parallelization by allowing more than one reader in the critical section at a time. Since the reads are comparatively slow, the overhead of the internal locking algorithms does not adversely affect performance. On the other hand, the other two implementations begin blocking most severely.

Scenario 3: Read-mostly, Fast Reads, Frequent Writes

The third locking scenario is characterized by:

• Reading threads outnumber writing threads 4:1
• Read threads each perform 100,000,000 reads from the cache
• Read lock duration short (reading shared data takes near-zero time)
• Write lock duration medium (writing shared data occurs every 10 milliseconds and takes 10 milliseconds)

Again, simply switching to a Lock-based locking scheme improves performance by over 4x over the old-style synchronized approach with the same degree of parallelization. Interestingly, we again notice the overhead of the ReadWriteLock internal locking algorithm’s affect on performance, though still over 2x that of the synchronized approach.

Scenario 4: Equal Read and Write Threads, Fast Reads, Infrequent Writes

The last locking scenario is characterized by:

• Reading threads and writing threads 1:1
• Read threads each perform 10,000,000 reads from the cache
• Read lock duration short (reading shared data takes near-zero time)
• Write lock duration medium (writing shared data occurs every second and takes 10 milliseconds)

Yet again, simply switching to a Lock-based locking scheme improves performance by over 4x over the old-style synchronized approach with the same degree of parallelization. Interestingly, we again notice the overhead of the ReadWriteLock internal locking algorithm’s affect on performance, though the increased parallelization yields a nearly 3x performance improvement over that of the synchronized approach.

Conclusion

So what can we conclude from this? That we should immediately switch to using the Lock and/or ReadWriteLock APIs? No.

The point is:

No one locking mechanism will consistently perform better than another. Review your usage patterns, the locking mechanism they use, and test performance. Use the right tool for the job.

As usual, there are several factors involved with a given usage pattern:

• Number of concurrent reader threads attempting to access the shared data structure
• Time needed to read a value from the shared data structure
• Number of concurrent writer threads attempting to modify the shared data structure
• Time needed to write a value to the shared data structure
• Time between write accesses

Of course, this list isn’t exhaustive, but it gives us an idea what factors come into play.

Remember too that the boxes that run our applications are being imbued with the ability to do more in parallel via multiple CPUs and N-core CPUs. A noticed trend is for CPU designers to rely more on the number of cores rather than raw performance of each core itself. That is, the number of cores may increase faster than the speed of each core. It behooves developers to ensure they’re using the appropriate amount of parallelization.

So – take a look at the Concurrency APIs if you haven’t already. There are many more gems in it that make it worth your while.

Permalink Comments off

May 1, 2007

The Dangers of Escapism

Posted in Design, Java at 8:31 PM by Kirk True

I’m the kind of guy that has a ‘word of the day’ calendar and will use odd words during a conversation in an attempt to use the word sometime during the day. I especially enjoy when I learn a new word (or a new meaning of a word) that succinctly describes a concept or thought that I’ve been grasping to articulate. One such word that I recently came across describes a software design problem: “escapism.” Now I haven’t found a rigorous text book definition of the word, but I’ll do my best to define it:

Escapism: In software design, the inadvertent release of an object reference outside its current scope.

The usage of the qualifier “inadvertent” here is important because the programmer would probably find such behavior to be undesirable, though not always obvious.

One common source of escaped objects is the release of internal object references to external code. Programmers will work long and hard to encapsulate any internal objects a class uses in an effort to provide confidence in the object’s state, usage, etc. Anything that undermines that confidence should be addressed.

So, let’s look at a detailed example at where this form of escaping objects can cause problems.

Imagine a programmer creates a class—UserCache—to cache User objects. Part of the purpose of the class is that it will notify listeners when a User is added to or removed from the cache. To provide more flexibility, the programmer chooses to utilize the Decorator pattern to enhance an existing data structure with his cache logic rather than creating it from scratch.

Let’s see what the class looks like:

    public class UserCache extends AbstractSet<User> {

        private Set<User> rawSet;

        public UserCache(Set<User> rawSet) {
            this.rawSet = rawSet;
        }

        @Override
        public Iterator<User> iterator() {
            return rawSet.iterator();
        }

        @Override
        public boolean add(User user) {
            boolean wasAdded = rawSet.add(user);
            notifyListeners(user);
            return wasAdded;
        }

        @Override
        public boolean remove(Object o) {
            boolean wasRemoved = rawSet.remove(o);
            notifyListeners((User)o);
            return wasRemoved;
        }

    }

This is pretty standard use of the Decorator pattern. The programmer has decorated a standard java.util.Set named rawSet with some listener notification logic.

In general, whenever a class decorates another object it’s important (usually imperative) that the decoratee not be used for other purposes. For instance, adding or removing objects to the decoratee directly would be problematic:

    Set<User> internalSet = new HashSet<User>(64);
    Set<User> users       = new UserCache(internalSet);
    . . .
    internalSet.add(someUser);
    internalSet.add(anotherUser);

It is clearly inappropriate to use internalSet in this manner after it has been decorated as we would not call our listeners about these additions. As the creator of the UserCache class, we might not have any idea what sort of code depends on the listener notifications to work correctly. The result of missed notifications could result in any number of really bad problems. So it’s important we make the UserCache class bulletproof in terms of delivering event notifications.

Worried by this possibility the programmer rewrites the UserCache to use an internal java.util.Set rather than decorating a user-provided Set:

    public class UserCache extends AbstractSet<User> {

        private Set<User> rawSet;

        public UserCache() {
            rawSet = new HashSet<User>();
        }

        . . .

    }

So while it isn’t as flexible, at least now there’s no way that a user can get access to the internal java.util.Set and add or remove objects directly, right? As we look over the class we don’t see anywhere that rawSet is returned or passed as a parameter or anything. It would appear that the programmer has solved the problem. While there isn’t anywhere that we return rawSet directly, is there a way that we could be returning another object that will allow access to rawSet?

Take a closer look at the iterator method:

    @Override
    public Iterator<User> iterator() {
        return rawSet.iterator();
    }

Notice that it returns a java.util.Iterator based on rawSet. ‘But,’ you might say, ‘I want to be able to iterate over all the users.’ That’s fine. But recall that the java.util.Iterator interface includes a method named remove that removes the object last returned from next. What happens when we call remove is that the object is removed from rawSet directly – not from UserCache. In this case, UserCache would not receive any notification of the removal and thus it has no possible way to notify the listeners. While we would agree that most callers of iterator do simply want to iterate over the users, there’s no way to guarantee that some caller, some time, may try to remove a user directly via that interface.

In this example we would say that rawSet has escaped via the iterator method. This is a slight variation of escapism because strictly speaking we aren’t returning a reference to rawSet to external code, but we are returning a view of rawSet through which we can modify it. Unfortunately this is a fairly simple example. Take a look at the java.util.List and java.util.Map interfaces and see how many places a view of the internal object is returned. And note too the java.util.ListIterator that extends Iterator and includes an add and a set method

At this point it should be emphasized that it isn’t just java.util.Collection-related classes that need to be worried about escapism. The following code snippet shows how an object reference can escape through the constructor:

    public class FileRepository implements FileEventListener {

        private File directory;

        public FileRepository(File directory) {
            FileEventListenerManager.register(this);
            this.directory = directory;
        }

        public void fileAccessed(FileEvent fileEvent) {
            File updatedFile = fileEvent.getFile();

            if (directory.equals(updatedFile.getParentFile()))
                touch(updatedFile);
        }

        . . .

    }

In this second example, we have a class—FileRepository—that listens for accesses to files and touches them if they’re within a certain directory. Notice that constructor lets the this reference escape through the call to FileEventListenerManager.register(). While this may seem innocuous (and arguably intentional), note that the internal directory object has not been initialized. In a multithreaded environment it is perfectly possible that immediately after the listener registration occurs that a file is accessed, thus calling the FileRepository‘s fileAccessed method. If this occurs, a java.lang.NullPointerException will be thrown when the equals method is invoked on a then-null object.

As you can begin to imagine, there are many scenarios in which escapism can cause problems. So, how do we solve the problem of escapism?

In our UserCache example, we have to implement iterator as it’s part of the java.util.Set interface. A first shot might be to provide an implementation of java.util.Iterator that calls back to rawSet on calls to Iterator.remove. While this may seem like a workable solution on the surface, when Iterator.remove is called and then rawSet.remove is called, the caller will receive a java.util.ConcurrentModificationException because he’s both iterating and modifying rawSet “concurrently.”

Another possibility would be to return a java.util.Iterator from a read-only view of rawSet via:

    @Override
    public Iterator<User> iterator() {
        return Collections.unmodifiableSet(rawSet).iterator();
    }

The caller can still call Iterator.remove, but he will receive an java.lang.UnsupportedOperationException. While it’s arguable that teasing the caller with a method that will only fail in this way is bad design, at least it’s consistently so with other parts of the JDK.

In the example of the FileRepository it may seem like the easist thing to do is switch the code in the constructor to read:

    public class FileRepository implements FileEventListener {

        private File directory;

        public FileRepository(File directory) {
            this.directory = directory;
            FileEventListenerManager.register(this);
        }

        public void fileAccessed(FileEvent fileEvent) {
            File updatedFile = fileEvent.getFile();

            if (directory.equals(updatedFile.getParentFile()))
                touch(updatedFile);
        }

        . . .

    }

Initializing the directory object first will make a big difference. However, in other cases it might not be so cut and dry, especially in concurrent applications. The book Java Concurrency in Practice succinctly and bluntly advises:

Do not allow the this reference to escape during construction.

Some suggestions for this case are to create a static factory method such that the object can be fully constructed (and thus ensuring that its object reference is valid) before being handed off to any external code:

    public class FileRepository implements FileEventListener {

        private File directory;

        private FileRepository(File directory) {
            this.directory = directory;
        }

        public void fileAccessed(FileEvent fileEvent) {
            File updatedFile = fileEvent.getFile();

            if (directory.equals(updatedFile.getParentFile()))
                touch(updatedFile);
        }

        public static FileRepository create(File directory) {
            FileRepository fr = new FileRepository(directory);
            FileEventListenerManager.register(fr);
            return fr;
        }

        . . .

    }

Finding possible escape paths for objects takes serious attention to detail, knowing a little about the internals of the objects in use, and, of course, testing. But finding the problem is only half the battle, patching the escape paths is equally challenging. Unfortunately there is no across-the-board way to fix the problems, it takes hunkering down and thinking through the seeming myriad of possibilities.

Happy hunting!

Permalink Comments off