[concurrency-interest] PooledLinkedBlockingQueue

kav@itu.dk kav@itu.dk
Thu, 4 Nov 2004 10:05:07 +0100 (CET)


On top of my head what about using something like the following (untested,
could require some optimization, and potentially i've just completely
missed something)

The idea is to loosely cache a maximum of MAX_ITEMS nodes. Under normal
conditions we cache all nodes, however, once in a while we loose a node
and need to create a new one.

First you extend the Node class that you have previously defined with an
inUse atomicBoolean that indicates whether or not the node is in use.

For the NodeCacher the cacheNode() is used for caching nodes (surprise).
Under concurrent access it will sometimes insert two nodes at the same
slot in the array. However, this is okay because we do not mind loosing a
node or two once in a while. GC should take of removing these nodes. One
thing is sure though, they will never attempt to put a node into a slot
with an index bigger then MAX_ITEMS (so no ArrayOutOfBoundException).

getNode() is used for retrieving the cached nodes or optionally create a
new one. If a previous Node has been cached the getNode(Node) method will
most likely find it. If there is concurrent access one of two things might
happen either the threads will acquire the same Node in which case we use
the node's inUse atomic boolean to decide which thread gets the node. The
thread(s) that "lost" can then create a new Node instead (or optionally
use some retry-based mechanism). The other scenario is that we get a null
from accessing the array in which case we also create a new node.

public class Node {
    final AtomicBoolean inUse = new AtomicBoolean();
    ..........your other pointers
}

public class NodeCacher {

    private volatile int index = 0;
    private final static int MAX_ITEMS = 1000;
    private final Node[] array = new Node[MAX_ITEMS];

    public void cacheNode(Node node) {
        node.inUse.set(false);
        int i = index;
        if (i < MAX_ITEMS) {
            array[i] = node;
            index = i + 1;
        }
    }

    public Node getNode() {
        int i = index - 1;
        if (i > -1) {
            Node n = array[i];
            if (n != null && n.inUse.compareAndSet(false, true)) {
                array[i] = null;
                index = i;
                return n;
            }
        }
        return new Node();
    }
}

- Kasper