[concurrency-interest] private field

Jean Morissette jean.morissette666@videotron.ca
Thu, 14 Oct 2004 11:44:53 -0400


Thank for your reply.

Doug Lea wrote:
>>I want to use very fast queue for the SEDA framework.  One 
>>performance-critical method is to move all elements of the queue in a 
>>array. 
> 
>
> Do you really nead an array? If you instead use ArrayList, it ought to
> be acceptable to do:
> 
>   ArrayList c = new ArrayList(q.size());
>   q.drainTo(c);
> 
> I suspect the performance difference between this and a custom
> solution would be negligible.  The ArrayList will only occasionally
> need to resize. To further reduce the likelihood at the expense of
> some space overhead, you could create it with say 2*q.size() capacity.

I like your suggestion of using an ArrayList to drain my 
LinkedBlockingQueue.  I will change my specification to expose 
Collection instead of raw array.  Also, with some refactoring, I can 
reuse the ArrayList (like David Holmes have suggested), so performance 
will be improved.



But, is-it possible to improve performance one step farther?  I am 
worried about memory allocation and garbage collection; maybe we can 
improve performance by reusing LinkedBlockingQueue.Node?

Here is what I mean:

PooledLinkedBlockingQueue extends AbstractQueue implements BlockingQueue {

   private Node[] pool = new Node[POOL_SIZE];

   private addToPool(Node n) {
     ...
   }

   // Get a queue that return their Nodes in the pool
   // instead of droping it.
   public Queue getQueue() {
     return new QueueImpl(this);
   }

   // A simple non-blocking and non-thread-safe Queue like LinkedList
   // that use the same Node than it's outer class.
   private class QueueImpl implements Queue {
     PooledLinkedBlockingQueue outerQueue;
     public QueueImpl(PooledLinkedBlockingQueue outerQueue) {
       this.outerQueue = outerQueue;
     }

     public Object poll() {
       removedNode = ...
       outerQueue.addToPool(removedNode);
       ...
     }
   }

   // drainTo is really fast when c is QueueImpl
   public int drainTo(Collection<? super E> c) {
     ...
     if (c.getClass().equals(QueueImpl.class)) {
       Node first;
       fullyLock();
       try {
         int size = count.get();
         first = head.next;
         head.next = null;
         if (count.getAndSet(0) == capacity)
           notFull.signalAll();
       } finally {
         fullyUnlock();
       }

       // Transfer the elements outside of locks.
       // The time here is O(1) instead of O(n).
       ((QueueImpl) c).last = first;
       return size;

     } else { ... }
   }
}

Now drainTo method requires O(1) instead of O(n) time.  Also, I can use 
QueueImpl instead of ArrayList and reuse Node (and don't use memory for 
array), so memory allocation and garbage collection will appear less 
frequently, improving performance.

But, I am wondering about node pool synchronization.  I'm not sure if I 
need synchronization and if yes, what are the impact on the performance? 
  Advice?

Thank
-Jean