Posts

Showing posts from October, 2011

Java and the Intrinsic Lock

I was working on converting a Java application to a multi-threaded application today and wanted to use the simplest means possible. This involves the following steps: Make the class implement Runnable or descend from the Thread class Put the previously sequential code into threads Use the "synchronized" keyword on methods that should be critical sections Join the threads before working on the results Now, there are variations on this theme. Because each object in Java has an intrinsic lock, you can use any old Object as a mutex by calling synchronized(object){} around the critical section you want to protect. so this: private synchronized foo(){ // critical section stuff } is the same as this: private foo(){ synchronized(this){ // critical section stuff } } And when trying to synchronize multiple threads, both are wrong!! The problem is that each object has an intrinsic lock, not each class. This is easiest to see in the second case. Because each t

Threaded Search

I spent a little bit of time threadifying the classic mergesort. This sort works by using recursively dividing the array to be sorted down to some depth, and then eventually merging the sorted members of the array. This sort also has the desirable characteristic that it sorts in-place. There is no additional memory location required. This is a *good thing* when you have hundreds of thousands of elements in your array. In this particular implementation, an insertion sort is used when the recursive division has less than 100 elements. Multi-threading *could* occur at the first n levels of bifurcation, at the bottom level only, or at some intermediary number of levels. Limiting the number of threads and making them a small multiple of the number of CPU cores causes the threading overhead and context switching to be limited as well. The optimal multiplier appears to be quite low, only about 2 threads per CPU core. For these reasons, I choose to thread only at one depth level. Let's lo