Tuesday, February 24, 2015

A lock-free Java object pool

It's a little bit surprising for me that I could not find an article or library of a totally lock-free Java object pool by googling. The closet one is Lock Less Java Object Pool. Here comes my version of a totally lock-free Java object pool.

The code is shared as  a public project at Github. Fell free to share or fork it.

The idea is simple. All returned objects (which need to be cached) are stored in a stack, which is held in an AtomicReferenceArray instance and an AtomicInteger-typed variable stores the top position of the stack. allocation or freeing of an object contains two steps:
  1. Firstly, a change of the top variable needs to be reserved,
  2. Then we try get/put the element in the reserved position,
  3. Since some other thread may also reserve the same place because the stack could expand and shrink, we may have to start over if this happens, i.e. Step 2 failed.
Step 1 utilizes the method of compareAndSet of AtomicInteger in a loop and step 2 uses getAndSet/compareAndSet of AtomicReferenceArray. Both are in a lock-free style.

This framework is also known as an optimisitic locking. It is useful for cases when contentions are relatively rare events.

Here are some code fragments:

    public E alloc() {
        while (true) {
            // Try reserve a cached object in objects
            int n;
            do {
                n = top.get();
                if (n == 0) {
                    // No cached oobjects, allocate a new one
                    return factory.alloc();
                }
            } while (!top.compareAndSet(n, n - 1));
            // Try fetch the cached object
            E e = objects.getAndSet(n, null);
            if (e != null) {
                return e;
            }
            // It is possible that the reserved object was extracted before
            // the current thread tried to get it. Let's start over again.
        }
    }
    
    public void free(E e) {
        while (true) {
            // Try reserve a place in this.objects for e.
            int n;
            do {
                n = top.get();
                if (n == objects.length()) {
                    // the pool is full, e is not cached.
                    factory.free(e);
                }
            } while (!top.compareAndSet(n, n + 1));
            // Try put e at the reserved place.
            if (objects.compareAndSet(n + 1, null, e)) {
                return;
            }
            // It is possible that the reserved place was occupied before
            // the current thread tried to put e in it. Let's start over again.
        }
    }

Any comments are welcome!