[concurrency-interest] PooledLinkedBlockingQueue

Jean Morissette jean.morissette666@videotron.ca
Tue, 02 Nov 2004 23:07:18 -0500


Doug Lea wrote:
> While there
> are lock-free solutions to the node-recycling problem, they are very
> complicated and tend to add more overhead than does GC. For some
> recent research papers on the subject see work by Maged Michael
> (http://www.research.ibm.com/people/m/michael/pubs.htm) and by Mark
> Moir and colleagues (http://research.sun.com/scalable/moir.html).

I have read "Hazard Pointers: Safe Memory Reclamation for Lock-Free 
Objects".  If I understand well, each thread have a pool of nodes. 
Is-it exact?

With this in mind, I have implemented a simple version of 
LinkedBlockingQueue that use a method named 'alloc' to create/reuse a 
node and a method 'free' to return a node to the pool.  The pool is 
based on ThreadLocal.  See below.

Until now, the performance of this implementation don't seem to 
outperform conventionnal node allocation/deallocation.  Even, the 
performance is worse.  A lot of time is taken by the method 
'ThreadLocal.get()'.  Do you have some suggestions to improve this 
implementation?

Maybe that it could be more efficient to use a shared lock-based pool 
node in the LinkedBlockingQueue class because this class already block, 
so no overhead would be introduced?  Maybe, we could use the locks 
already defined in this class (takeLock and putLock) to synchronize our 
pool?  Any advice?

Thanks
Jean


  static class ThreadSafePool {
     private static ThreadLocal pool = new ThreadLocal() {
       protected Object initialValue() {
         return new Pool();
       }
     };

     public static Pool get() {
       return (Pool) pool.get();
     }
   }

   static class Pool {
     Node head;
     Node tail;
     int count;
   }

   private Node<E> alloc(E x) {
     Node<E> node;
     Pool pool = ThreadSafePool.get();
     if (pool.head != null) {
       node = pool.head;
       pool.head = pool.head.next;
       node.next = null;
       pool.count--;
       if (node == pool.tail)
         pool.tail = null;
     }
     else {
       node = new Node<E>(null);
     }
     node.item = x;
     return node;
   }

   private void free(Node<E> node) {
     node.next = null;
     node.item = null;
     Pool pool = ThreadSafePool.get();
     if (pool.count >= 1000) return;
     if (pool.tail == null) { // isEmpty
       pool.tail = node;
       pool.head = node;
     }
     else {
       pool.tail.next = node;
       pool.tail = node;
     }
     pool.count++;
   }