A few tips for better thread synchronization in Java from Java Concurrency in Practice:

1. Narrow lock scope

Lock only the portion of code that really needs to be locked. This can dramatically reduce the time threads wait to acquire the lock. Consider the following method:

public synchronized boolean addItem(Item item) {
    if (validate(item)) {
         return itemsArray.add(item);
    }
    return false;
}

The method level lock prevents two threads from concurrently running validate(item), which need not be synchronized. To get the full benefit of multi-threading we change the method like this:

public boolean addItem(Item item) {
    if (validate(item)) {
     synchronized(this) {
             return itemsArray.add(item);
         }
    }
return false;
}

2. Reduce lock granularity

If there are two objects whose concurrent modification are sure not to create havoc, synchronize them with dedicated locks. For instance, here the thread that adds an Item will have to wait until the thread that adds an Order is finished :

public boolean addItem(Item item) {
    if (validate(item)) {
     synchronized(this) {
             return itemsArray.add(item);
         }
    }
return false;
}

public boolean addOrder(Order order) {
    if (validate(order)) {
     synchronized(this) {
             return ordersArray.add(order);
         }
    }
return false;
}

The performance can be improved by increasing the granularity of the locks:

private Object itemLock = new Object();
private Object orderLock = new Object();

public boolean addItem(Item item) {
    if (validate(item)) {
     synchronized(itemLock) {
             return itemsArray.add(item);
         }
    }
return false;
}

public boolean addOrder(Order order) {
    if (validate(order)) {
     synchronized(orderLock) {
             return ordersArray.add(order);
         }
    }
return false;
}

3. Strip locks, if possible

A single collection can be partition locked, like we see in the implementation of this Map:

public class HighlyResponsiveMap {
     private static final int N_LOCKS = 16;
     private final Object locks[] = new Object[N_LOCKS];
 private final Node buckets[];

 public HighlyResponsiveMap(int numBuckets) {
     buckets = new Node[numBuckets];
     for (int i = 0; i < N_LOCKS; ++i) {
         locks[i] = new Object();
         }
     }

 public Object get(Object key) {
      int hash = key.hashCode();
      synchronized(locks[hash % N_LOCKS]) {
          // Find node from the bucket and return its value.
          }
          return null;
 }
}

4. Avoid object pools

In days of yore, when allocating memory for a new Object was really slow, people used to depend on object pools. These days creating a new object in Java often outperforms C’s malloc. Synchronizing an object pool can be expensive than creating a new Object when needed. If you are using Java 5 or later, avoid object pools.

Ever imagined of using C as a scripting language? Install TCC. Write a simple C program:

// add.c
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv)
{
   /* No error checking. */
   int a = atoi(argv[1]);
   int b = atoi(argv[2]);
   printf("%d\n", (a + b));
   return 0;
}

Add this line to the top of the file:

#!tcc -run

Mark the file as executable:

$ chmod +x add.c

Run it:

$ ./add.c 10 20
30

The TCC executable is only 100Kb in size, but it can compile the Linux kernel! An ideal use for TCC is as an embedded compiler to dynamically generate executables.

It is a bad idea to have functions return null. This is especially true for C/C++ libraries. Think of a hypothetical CharBuffer API:

#include <iostream>
#include <cstring>

class CharBuffer
{
public:
CharBuffer (const char* s) : buffer_ (NULL)
{
    size_t len = 0;
    if (s != NULL && (len = strlen (s)) > 0)
    {
        buffer_ = new char [len + 1];
        strcpy (buffer_, s);
    }
 }
 ~CharBuffer () { delete[] buffer_; }
 const char* GetBuffer ()
 {
    return buffer_;
 }
 private:
 char* buffer_;
};

This is a valid usage of the library, but it will result in the abnormal exit of the program:

int main ()
 {
    CharBuffer b ("");
    std::cout << b.GetBuffer () << '\n';
    return 0;
 }

There are two ways to cleanup the implementation of CharBuffer::GetBuffer():

1. Throw an exception if buffer_ is NULL.
2. Return a ‘default’ buffer object.

I prefer the second option as C++ do not have checked exceptions. Continuing with the above sample, we add a new static variable to the CharBuffer class:

static const char* DEFAULT_BUFFER;

and intilialize it like this:

const char* CharBuffer::DEFAULT_BUFFER = "";

The GetBuffer() function should return DEFAULT_BUFFER if buffer_ is NULL:

const char* GetBuffer ()
{
   if (buffer_ == NULL)
      return DEFAULT_BUFFER;
   return buffer_;
}

This gives the user to take appropriate action if the retuned value is the ‘default’ object. Even if he ignore to check it, the program will not behave badly. If the value to be defined is a complex type, and you need to return and non-const pointer, you can clone the DEFAULT_OBJECT and return the new copy.

This is a simple idiom, but can have important consequence on software quality as most of the errors caused by null pointers manifest at production sites. BTW, I was just wondering, do we really need NULL at all?

“Value semantics” is used to refer to classes whose objects when copied gives two independent copies, with the same value. C++ has value semantics for both built-in and user-defined types. This is in accordance with one of C++’s core design principles – “support user-defined and built-in types equally well”. For example:

int a = 10;
int b = a; // Now we have two ints with the same value.
++b; // Changes the value of `b' to 11, but `a' still remains 10.

// A user-defined type that represents a 64-bit integer.
class Int64
{
     // Supports value semantics by overloading the
     //  copy constructor and the = operator. 
     Int64(const Int64& val);
     Int64& operator=(const Int64& val);
};

Int64 a = 10;
Int64 b = a; // Two objects of Int64 with the same value.
++b; // Only b changes, a remains the same.

Java has value semantics for primitive types like int and char. But user-defined types have “reference semantics”:

class Int64 {
    // ...
}

Int64 a = new Int64(10);
Int64 b = a; // a and b points to the same object.
b.increment(); // a and b is changed.

This is often a source of confusion to newcomers.

The designers of Java omitted typedefs on the ground that it introduces “too much context”. This is true to some extent. I mostly depend on typedefs for declaring generic containers. This saves a lot of keystrokes and screen space, especially when declaring functions that consume or return such containers:

typedef map<string, int> NameAgeMap;

static void InitSample(NameAgeMap& sample)
{
   sample["joe"] = 20;
   sample["mark"] = 22;
}

// ....

NameAgeMap sample;
InitSample(sample);
NameAgeMap::const_iterator iter = sample.begin();
while (iter != sample.end())
{
   std::cout << iter->first << ':' << iter->second << '\n';
   ++iter;
}

If the new type is properly named, we need not look at the typedef to infer what it really is. An IDE might even show the real type when the mouse is hovered over the variable. Contrast this with Java. I have to type the lengthy container declaration where ever I need it:

public void InitSample(HashMap<String, Integer> sample) { 
    sample.put("joe", 20);
    sample.put("mark", 22);
}

// ...

HashMap<String, Integer>sample = new HashMap<String, Integer>();
InitSample(sample);
Set<String>keys = sample.keySet();
for (String name : keys) {
     System.out.println(name + ':' + sample.get(name));
}

I suppose that the argument against typedef was made before Java had generics. As the view on enum was later compromised, Java may eventually introduce typedef.

You can create a new class in Squeak, without using the class browser. The following session in the Workspace shows how:

Object subclass: #Person 
       instanceVariableNames: 'name age'
       classVariableNames: '' 
       poolDictionaries: '' 
       category: 'vijay'.

Person compile: 'name ^name' classified: #accessing.
Person compile: 'age ^age' classified: #accesing.
Person compile: 'age: a age := a' classified: #accessing.
Person compile: 'name: n name := n' classified: #accessing.

p := Person new.
p name: 'Vijay'; age: 32.
p name => "Vijay".
p age => 32

Click here to download:

bigit.erl (2 KB)

An Erlang implementation of the Bignum representation as described in EOPL. Usage instructions are in the header comments.

Installed Programmer's Font in Emacs, out of curiosity. See the screenshots showing some Scheme and Java code. Doesn't this make Lisp really look like the programming language of aliens?

(download)

Click here to download:

alien-s-font-pmynHumacqvddqHibpzB.zip (145 KB)

What is wrong with the following code?

public class Counter {
    public synchronized int getNext() {
        return ++value;
    }
    private int value;
}

It is correctly synchronized, but can cause a liveness problem if some code obtains a lock on an instance of Counter:

public class Test {
    public static void main(String args[]) throws Exception {
        Counter c = new Counter();
        CounterThread ct = new CounterThread(c);
        // This will cause c.next() to wait for the lock on c to be
        // released, which will never happen. 
        // The program will hang here.
        synchronized (c) {
            ct.start();
            ct.join();
        }
    }
    public static class CounterThread extends Thread {
        public CounterThread(Counter counter) {
            this.counter = counter;
        }
        public void run() {
            System.out.println(counter.next());
        }
        private Counter counter;
    }
}

The solution is to use a private lock object rather than using Counter’s intrinsic lock. Make sure that this lock is not published:

public class Counter {
    public int next() {
        synchronized (lock) {
            return ++value;
        }
    }
    private int value;
    private Object lock = new Object();
}

Java concurrency is surprisingly difficult to get right. Some operations that look atomic can be especially deceptive. For instance, look at the following simple class. It has only one method which does an operation that looks atomic:

public class UniqueNumber {
    // Returns a unique integer value.
    public int get() {
        return ++val;
    }
    private int val;
}

The ++ operator applied to an integer might look like an atomic operation but it can lead to incorrect results if an object of UniqueNumber is shared by multiple threads. Why? Because ++ is not really atomic as we see from the following byte code dump:

> javap -c UniqueNumber
........
........
public int get();
Code:
0: aload_0
1: dup
2: getfield #2; //Field val:I
5: iconst_1
6: iadd
7: dup_x1
8: putfield #2; //Field val:I
11: ireturn

++ gets expanded to VM operations that loads the variable, adds 1 to it and saves the new value back. Now imagine two threads simultaneously calling get() on a UniqueNumber object. (The opcodes executed is shown as comma separated numbers with reference to the above byte code listing and the current stack is shown in square brackets):

Thread1 => 0,1,2 [0]
Thread2 => 0,1,2 [0], 5 [0 1], 6 [1]
Thread1 => 5 [0 1], 6 [1]
.... and so on ....

In the end both threads end up fetching the value 1, which is not what the UniqueNumber class was expected to produce!

Even fetching values directly from “primitive” types can be non-atomic operations at the VM level. The is true for 64-bit types like long and double as a Java implementation (especially on a 32 bit arch) can choose to implement those types using two 32 bit values. Then reading and writing a long/double will get expanded to two VM opcodes. If primitive types like boolean, int, long and double are shared between threads (even if only one thread does all the writing) declare them as volatile.