Non-Blocking stack和Block stack的插入时间对比

本文通过对实现了两个Stack，一个是基于非阻塞(Non-Blocking)算法，另一个是基于阻塞算法(Blocking)的，然后对这两个队列进行多线程环境下的大量Insert操作，通过比较二者的消耗时间，进而比较基于Volatile和CAS轮询操作的非阻塞算法和基于锁的阻塞算法在时间上的性能差异究竟有多大。

 

基于非阻塞算法的Stack

 

public class ConcurrentStack<E> {

	AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
	
	public void push(E item)
	{
		Node<E> newHead = new Node<E>(item);
		Node<E> oldHead;
		
		do
		{
			oldHead = top.get();
			newHead.next = oldHead;
		}while(!top.compareAndSet(oldHead, newHead));
	}
	
	public E pop()
	{
		Node<E> newHead;
		Node<E> oldHead;
		
		do
		{
			oldHead = top.get();
			if(oldHead == null)
			{
				return null;
			}
			
			newHead = oldHead.next;
		}while(!top.compareAndSet(oldHead, newHead));
		
		return oldHead.item;
	}
	
	private static class Node<E>
	{
		public final E item;
		public Node<E> next;
		
		public Node(E item)
		{
			this.item = item;
		}
	}
}

 

  阻塞算法的Stack

 

public class BlockingStack<E> {
	
	Node<E> top = new Node<E>(null);
	
	public synchronized void push(E item)
	{
		Node<E> newHead = new Node<E>(item);
		Node<E> oldHead;
		
		oldHead = top;
		newHead.next = oldHead;
		top = newHead;
	}
	
	public synchronized E pop()
	{
		Node<E> newHead;
		Node<E> oldHead;
		
		if(top == null)
		{
			return null;
		}
		oldHead = top;
		newHead = top.next;
		top = newHead;
		
		return oldHead.item;
	}
	
	private static class Node<E>
	{
		public final E item;
		public Node<E> next;
		
		public Node(E item)
		{
			this.item = item;
		}
		
	}
}

 

  测试代码

 

public class TestNonAndBlockingStack {
	
	private int insertNums;
	
	public TestNonAndBlockingStack(int insertNums)
	{
		this.insertNums = insertNums;
	}

	class NonBlockStackThread extends Thread
	{
		private ConcurrentStack<String> stack;
		private CountDownLatch startGate;
		private CountDownLatch endGate;
		
		public NonBlockStackThread(ConcurrentStack<String> stack,
								   CountDownLatch startGate,
								   CountDownLatch endGate)
		{
			this.stack = stack;
			this.startGate = startGate;
			this.endGate = endGate;
		}
		
		public void run()
		{
			try {
				startGate.await();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			for(int i = 0; i < insertNums; i++)
			{
				stack.push("olylakers");
			}
			endGate.countDown();
		}
	}
	
	class BlockStackThread extends Thread
	{
		private BlockingStack<String> stack;
		private CountDownLatch startGate;
		private CountDownLatch endGate;
		
		public BlockStackThread(BlockingStack<String> stack,
								CountDownLatch startGate,
								CountDownLatch endGate)
		{
			this.stack = stack;
			this.startGate = startGate;
			this.endGate = endGate;
		}
		
		public void run()
		{
			try {
				startGate.await();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			for(int i = 0; i < insertNums; i++)
			{
				stack.push("oly");
			}
			
			endGate.countDown();
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int threadNums = 100;
		int insertNums = 50000;
		TestNonAndBlockingStack test = new TestNonAndBlockingStack(insertNums);
		
		CountDownLatch startGateN = new CountDownLatch(1);
		CountDownLatch endGateN = new CountDownLatch(threadNums);
		ConcurrentStack<String> concurrentStack = new ConcurrentStack<String>();
		
		CountDownLatch startGateB = new CountDownLatch(1);
     	CountDownLatch endGateB = new CountDownLatch(threadNums);
     	BlockingStack<String> blockingStack = new BlockingStack<String>();
     	
     	for(int i = 0; i < threadNums; i++)
     	{
     		test.new NonBlockStackThread(concurrentStack, startGateN, endGateN).start();
     	}
     	
     	long startTime = System.currentTimeMillis();
     	startGateN.countDown();
     	try {
			endGateN.await();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println("The concurrent stack push cost: "+ (System.currentTimeMillis() - startTime));
     	
     	for(int i = 0; i < threadNums; i++)
     	{
     		test.new BlockStackThread(blockingStack, startGateB, endGateB).start();
     	}
     	
     	startTime = System.currentTimeMillis();
     	startGateB.countDown();
     	try {
			endGateB.await();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println("The blocking stack push cost: "+ (System.currentTimeMillis() - startTime));				
	}
}

 

  当 threadNums = 100， insertNums = 50000时，跑两次的测试结果为：

The concurrent stack push cost: 2125 The blocking stack push cost: 3657

 

 

        The concurrent stack push cost: 1953

        The blocking stack push cost: 3078

 

 

 

  当 threadNums = 500， insertNums = 10000时，跑两次的测试结果为：

        The concurrent stack push cost: 2141 The blocking stack push cost: 3219

 

 

The concurrent stack push cost: 2171

The blocking stack push cost: 3344

 

测试机器为:Core2(TM)2 Quad CPU Q9500 @2.83GHz, 4核。内存：3.25G。