ArrayBlockingQueue V.S. LinkedBlockingQueue

最近看《分布式JAVA应用 基础与实践》 里面有一段话

林昊 写道

ArrayBlockingQueue为一个固定大小数组、ReentrantLock以及Condition实现的可阻塞的先进先出的Queue。

除ArrayBlockingQueue之外，BlockingQueue的实现还有LinkedBlockingQueue，LinkedBlockingQueue实现的不同为采用对象的next构成链表的方式存储对象。由于读只操作对头，而写只操作队尾，这里巧妙地采用了两把锁，对于put和offer采用一把锁，对于take和poll则采用另外一把锁，避免了读写时互相竞争锁的情况，因此LinkedBlockingQueue在高并发读写操作都多的情况下，性能会较ArrayBlockingQueue好很多，在遍历以及删除元素则要两把锁都锁住。

 
乍一看，ArrayBlockingQueue怎么都不如LinkedBlockingQueue性能强大，那ArrayBlockingQueue存在的意义是什么呢？带着这个疑问，自己亲身写了个程序，4个生产者总共生产4* 102,4000*10个产品，4个消费者去消费，队列的最大大小是102,4000，队列分别采用ArrayBQ和LinkedBQ，对比2者消耗时间。（读者可以直接运行该程序得出对比结果)。

 

 

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.ArrayBlockingQueue;

public class ArrayBlockingQueueVsLinkedBlockingQueue {
	//队列最大容量
	public static final int Q_SIZE = 1024000;
	//生产者/消费者线程数
	public static final int THREAD_NUM = 4;
	
	//产品
	class Product{
		String name;
		Product(String name){
			this.name = name;
		}
	}
	public void test(final BlockingQueue<Product> q) throws InterruptedException{
		//生产者线程
		class Producer implements Runnable{
			@Override
			public void run() {
				for(int i=0;i<Q_SIZE*10;i++){
					try {
						q.put(new Product("Lee"));
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
				}
			}
			
		};
		//消费者线程
		class Consumer implements Runnable{
			@Override
			public void run(){
				for(int i=0;i<Q_SIZE*10;i++){
					try {
						q.take();
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				}
			}
		};
		//创建生产者
		Thread[] arrProducerThread = new Thread[THREAD_NUM];
		for(int i=0;i<THREAD_NUM;i++){
			arrProducerThread[i] = new Thread(new Producer());
		}
		//创建消费者
		Thread[] arrConsumerThread = new Thread[THREAD_NUM];
		for(int i=0;i<THREAD_NUM;i++){
			arrConsumerThread[i] = new Thread(new Consumer());
		}
		//go!
		long t1 = System.currentTimeMillis();
		for(int i=0;i<THREAD_NUM;i++){
			arrProducerThread[i].start();
			arrConsumerThread[i].start();
		}
		for(int i=0;i<THREAD_NUM;i++){
			arrProducerThread[i].join();
			arrConsumerThread[i].join();
		}
		long t2 = System.currentTimeMillis();
		System.out.println(q.getClass().getSimpleName() + " cost : " + (t2-t1));
	}
	public static void main(String[] args) throws InterruptedException{
		final BlockingQueue<Product> q1 = new LinkedBlockingQueue<Product>(Q_SIZE);
	    final BlockingQueue<Product> q2 = new ArrayBlockingQueue<Product>(Q_SIZE);
		new ArrayBlockingQueueVsLinkedBlockingQueue().test(q1);
		new ArrayBlockingQueueVsLinkedBlockingQueue().test(q2);
	}
}

 

 

结果令人我意外，ArrayBQ耗时只有LinkedBQ的一半！而且运行的时候ArrayBQ没占满CPU，LinkedBQ却一直占满！


(我的机器 JDK1.6 win7_64 -Xms1024M -Xmx1024M)

(群友的机器)
我这就不懂了，锁竞争更小的LinkedBQ输给了ArrayBQ。。。难道是线程不够多？
于是我把参数改成以下

//队列最大容量
public static final int Q_SIZE = 10240;
//生产者/消费者线程数
public static final int THREAD_NUM = 1280;

 
结果还是ArrayBQ更快。。。

各位技术的朋友，这究竟解释？如果您知道为什么，请务必留言告知鄙人！

 

我现在唯一的想到的是，LinkedQueue需要建立Node，而且增删时引用的操作比ArrayBQ复杂。ArrayBQ的内部的数组在增删时并不会产生复制的操作，而是当作一个环，增删只会改变putIndex和takeIndex，操作非常简单。

 

 

评论

14 楼 sadamu900912 2019-02-13  

long t1 = System.currentTimeMillis();这一句不是应该在所有线程启动之后吗？这么测，不是把线程启动的时候算进去了，有什么意义？

13 楼 ygmyth 2017-03-20  

jag522 写道

ArrayBlockingQueue和LinkedBlockingQueue的区别：

1. 队列中的锁的实现不同
       ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；
       LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock
   
2. 在生产或消费时操作不同

• 在使用ArrayBlockingQueue和LinkedBlockingQueue分别对1000000个简单字符做入队操作时，

所以文章中的疑问跟你的答案什么关系呢

12 楼 jag522 2014-09-15  

ArrayBlockingQueue和LinkedBlockingQueue的区别：

1. 队列中的锁的实现不同
       ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；
       LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock
   
2. 在生产或消费时操作不同
     ArrayBlockingQueue基于数组，在生产和消费的时候，是直接将枚举对象插入或移除的，不会产生或销毁任何额外的对象实例；
     LinkedBlockingQueue基于链表，在生产和消费的时候，需要把枚举对象转换为Node<E>进行插入或移除，会生成一个额外的Node对象，这在长时间内需要高效并发地处理大批量数据的系统中，其对于GC的影响还是存在一定的区别。

3. 队列大小初始化方式不同
     ArrayBlockingQueue是有界的，必须指定队列的大小；
     LinkedBlockingQueue是无界的，可以不指定队列的大小，但是默认是Integer.MAX_VALUE。当然也可以指定队列大小，从而成为有界的。
   
注意:
• 在使用LinkedBlockingQueue时，若用默认大小且当生产速度大于消费速度时候，有可能会内存溢出
• 在使用ArrayBlockingQueue和LinkedBlockingQueue分别对1000000个简单字符做入队操作时，
       LinkedBlockingQueue的消耗是ArrayBlockingQueue消耗的10倍左右，
       即LinkedBlockingQueue消耗在1500毫秒左右，而ArrayBlockingQueue只需150毫秒左右。
• 按照实现原理来分析，ArrayBlockingQueue完全可以采用分离锁，从而实现生产者和消费者操作的完全并行运行。Doug Lea之所以没这样去做，也许是因为ArrayBlockingQueue的数据写入和获取操作已经足够轻巧，以至于引入独立的锁机制，除了给代码带来额外的复杂性外，其在性能上完全占不到任何便宜。

11 楼 xwqiang 2014-04-17  

mark 一下

10 楼 lazy_ 2013-06-25  

teasp 写道

public class ArrayBlockingQueueVsLinkedBlockingQueue {
	//队列最大容量
	public static final int Q_SIZE = 1024000;
	//生产者/消费者线程数
	public static final int THREAD_NUM_P = 4;
	public static final int THREAD_NUM_C = 2;
	....

环境：winXP；
java version "1.6.0_10-rc2"
Java(TM) SE Runtime Environment (build 1.6.0_10-rc2-b32)
Java HotSpot(TM) Client VM (build 11.0-b15, mixed mode, sharing)

感谢您贴上测试代码。我在自己的64位机器和公司的64位机器上测试您的代码，都是LinkedBQ比ArrayBQ慢一般。晚些我找部32位机器再测一下。

9 楼 teasp 2013-06-24  

public class ArrayBlockingQueueVsLinkedBlockingQueue {
	//队列最大容量
	public static final int Q_SIZE = 1024000;
	//生产者/消费者线程数
	public static final int THREAD_NUM_P = 4;
	public static final int THREAD_NUM_C = 2;
	
	//产品
	class Product{
		String name;
		Product(String name){
			this.name = name;
		}
	}
	public void test(final BlockingQueue<Product> q) throws InterruptedException{
		//生产者线程
		class Producer implements Runnable{
			@Override
			public void run() {
				for(int i=0;i<Q_SIZE*10;i++){
					try {
						q.put(new Product("Lee"));
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
				}
			}
			
		};
		//消费者线程
		class Consumer implements Runnable{
			@Override
			public void run(){
				for(int i=0;i<Q_SIZE*20;i++){
					try {
						q.take();
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				}
			}
		};
		//创建生产者
		Thread[] arrProducerThread = new Thread[THREAD_NUM_P];
		for(int i=0;i<THREAD_NUM_P;i++){
			arrProducerThread[i] = new Thread(new Producer());
		}
		//创建消费者
		Thread[] arrConsumerThread = new Thread[THREAD_NUM_C];
		for(int i=0;i<THREAD_NUM_C;i++){
			arrConsumerThread[i] = new Thread(new Consumer());
		}
		//go!
		long t1 = System.currentTimeMillis();
		for(int i=0;i<THREAD_NUM_P;i++){
			arrProducerThread[i].start();
		}
		for(int i=0;i<THREAD_NUM_C;i++){
			arrConsumerThread[i].start();
		}
		
		for(int i=0;i<THREAD_NUM_P;i++){
			arrProducerThread[i].join();
		}
		for(int i=0;i<THREAD_NUM_C;i++){
			arrConsumerThread[i].join();
		}
		long t2 = System.currentTimeMillis();
		System.out.println(q.getClass().getSimpleName() + " cost : " + (t2-t1));
	}
	public static void main(String[] args) throws InterruptedException{
		final BlockingQueue<Product> q1 = new LinkedBlockingQueue<Product>(Q_SIZE);
	    final BlockingQueue<Product> q2 = new ArrayBlockingQueue<Product>(Q_SIZE);
		new ArrayBlockingQueueVsLinkedBlockingQueue().test(q1);
		new ArrayBlockingQueueVsLinkedBlockingQueue().test(q2);
	}

环境：winXP；
java version "1.6.0_10-rc2"
Java(TM) SE Runtime Environment (build 1.6.0_10-rc2-b32)
Java HotSpot(TM) Client VM (build 11.0-b15, mixed mode, sharing)

8 楼 teasp 2013-06-23  

lazy_ 写道

teasp 写道

我把消费者线程数改成2之后得到如下结果：
LinkedBlockingQueue cost : 29312
ArrayBlockingQueue cost : 41078

所以楼主你的测试其实模拟的一种很极端的情况，这种情况用阻塞队列可能不合适。

我把THREAD_NUM改成2，并且把测试LinkedBQ和ArrayBQ的顺序调换，还是LinkedBQ比ArrayBQ满一半。有可能是64和32位JDK的原因？

不是把THREAD_NUM改成2，我是把生产者和消费者的线程数取了不同值，生产者是4，消费者是2，单个消费者线程处理的数量*2。你按这种测一下试试。

7 楼 lazy_ 2013-06-23  

xhd730 写道

LinkedBlockingQueue cost : 19015
ArrayBlockingQueue cost : 42625

额，你是怎么测出这个数据的。。。THREAD_NUM，Q_SIZE是多少？是不是32位的JDK？

6 楼 lazy_ 2013-06-23  

teasp 写道

我把消费者线程数改成2之后得到如下结果：
LinkedBlockingQueue cost : 29312
ArrayBlockingQueue cost : 41078

所以楼主你的测试其实模拟的一种很极端的情况，这种情况用阻塞队列可能不合适。

我把THREAD_NUM改成2，并且把测试LinkedBQ和ArrayBQ的顺序调换，还是LinkedBQ比ArrayBQ满一半。有可能是64和32位JDK的原因？

5 楼 anglestudio 2013-06-23  

后面运行的占便宜,现在虚拟机优化的很厉害,你可以分成两个类来试一下,或者加个-Xint
或者-Xcomp

4 楼 xhd730 2013-06-23  

LinkedBlockingQueue cost : 19015
ArrayBlockingQueue cost : 42625

3 楼 teasp 2013-06-23  

还有一点博主你要注意，你要把对两者测试的先后顺序调整之后再进行对比。虚拟机有很多优化的，一般而言，后面执行的代码会快一些，这会影响你的测试结果。微基准测试是一项难度很高的活。

2 楼 teasp 2013-06-23  

我把消费者线程数改成2之后得到如下结果：
LinkedBlockingQueue cost : 29312
ArrayBlockingQueue cost : 41078

所以楼主你的测试其实模拟的一种很极端的情况，这种情况用阻塞队列可能不合适。

1 楼 teasp 2013-06-23  

你这里的情况应该是读比写快造成的，队列里面基本上是空的，你想办法让队列里始终保持一定数据看看，或者把读的线程减一点试试。