天天看点
返回

OkHttp 源码系列 之 ArrayDeque - 双端队列

源码出处 

public final class Dispatcher {

  /** Ready async calls in the order they'll be run. */
  private final Deque<AsyncCall> readyAsyncCalls = new ArrayDeque<>();

  /** Running asynchronous calls. Includes canceled calls that haven't finished yet. */
  private final Deque<AsyncCall> runningAsyncCalls = new ArrayDeque<>();

  /** Running synchronous calls. Includes canceled calls that haven't finished yet. */
  private final Deque<RealCall> runningSyncCalls = new ArrayDeque<>();
  
  ......
}

疑问

Dispatcher

中的三个任务容器为什么会选择使用双端队列（

ArrayDeque

）？

双端队列

定义

双端队列（

deque

，全名

double-ended queue

）是一种具有队列和栈性质的抽象数据类型。双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。[1]

我们知道普通队列是限制级的一端进，另一端出的FIFO形式，栈是一端进出的LIFO形式，而双端队列就没有这样的限制级，也就是我们可以在队列两端进行插入或者删除操作。[2]

演示 

package com.netease.okhttp.deque;

import android.view.View;

import com.netease.okhttp.BaseActivity;

import java.util.ArrayDeque;
import java.util.Iterator;

/**
 * Created by wupengjian on 2019/2/13.
 * <p>
 * https://blog.csdn.net/u013309870/article/details/71478120
 */
public class DequeActivity extends BaseActivity {

    public void test1(View view) {
        addFirstAddLastPollFirstPollLast();
    }

    /**
     * 入队：addFirst
     * 出队：pollLast
     * 效果：先进先出
     */
    private void addFirstAddLastPollFirstPollLast() {

        StringBuilder sb = new StringBuilder();
        sb.append("addFirstAddLastPollFirstPollLast\n");

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        ArrayDeque<Integer> aDeque = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            if ((i & 1) == 0) {

                //如果i是偶数从队头加入，否则从队尾加入
                aDeque.addFirst(arr[i]);
            } else {

                aDeque.addLast(arr[i]);
            }
        }

        sb.append("ArrayDeque: " + aDeque.toString());
        sb.append("\n");

        while (!aDeque.isEmpty()) {

            int result = aDeque.pollFirst();
            sb.append(result);

            //此处不严谨但是由于arr的元素恰好是偶数个，本例中也不会出现问题。
            result = aDeque.pollLast();
            sb.append(result);
        }

        v(sb.toString());
    }

    public void test2(View view) {
        addFirstPollLast();
    }

    /**
     * 入队：addFirst
     * 出队：pollLast
     * 效果：先进先出
     */
    private void addFirstPollLast() {

        StringBuilder sb = new StringBuilder();
        sb.append("addFirstPollLast\n");

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        ArrayDeque<Integer> aDeque = new ArrayDeque<>();
        //从双端队列的头部加元素
        for (int i = 0; i < arr.length; i++) {

            aDeque.addFirst(arr[i]);
        }

        sb.append("ArrayDeque: " + aDeque.toString());
        sb.append("\n");

        while (!aDeque.isEmpty()) {
            int result = aDeque.pollLast();
            sb.append(result);
        }

        v(sb.toString());
    }

    public void test3(View view) {
        addFirstPollFirst();
    }

    /**
     * 入队：addFirst
     * 出队：pollFirst
     * 效果：先进后出
     */
    private void addFirstPollFirst() {

        StringBuilder sb = new StringBuilder();
        sb.append("addFirstPollFirst\n");

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        ArrayDeque<Integer> aDeque = new ArrayDeque<>();
        //从双端队列的头部加元素
        for (int i = 0; i < arr.length; i++) {

            aDeque.addFirst(arr[i]);
        }

        sb.append("ArrayDeque: " + aDeque.toString());
        sb.append("\n");

        while (!aDeque.isEmpty()) {
            int result = aDeque.pollFirst();
            sb.append(result);
        }

        v(sb.toString());
    }

    public void test4(View view) {
        addFirstIterator();
    }

    /**
     * 入队：addFirst
     * 出队：iterator.next()
     * 效果：先进后出
     */
    private void addFirstIterator() {

        StringBuilder sb = new StringBuilder();
        sb.append("addFirstIterator\n");

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        ArrayDeque<Integer> aDeque = new ArrayDeque<>();
        //从双端队列的头部加元素
        for (int i = 0; i < arr.length; i++) {

            aDeque.addFirst(arr[i]);
        }

        sb.append("ArrayDeque: " + aDeque.toString());
        sb.append("\n");

        for (Iterator<Integer> iterator = aDeque.iterator(); iterator.hasNext(); ) {

            int result = iterator.next();
            sb.append(result);
        }

        v(sb.toString());
    }
}

效果如下：

OkHttp 源码系列 之 ArrayDeque - 双端队列

原理分析

从名字可以看出

ArrayDeque

底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。

ArrayDeque

是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。

OkHttp 源码系列 之 ArrayDeque - 双端队列

上图中我们看到，

head

指向首端第一个有效元素，

tail

指向尾端第一个可以插入元素的空位。因为是循环数组，所以

head

不一定总等于0，

tail

也不一定总是比

head

大。

使用场景

在一般情况，不涉及到并发的情况下，有两个实现类，可根据其自身的特性进行选择，分别是：

  1. LinkedList

     大小可变的链表双端队列，允许元素为

    null

  2. ArrayDeque

     大下可变的数组双端队列，不允许

    null

注意：

LinkedList

和

ArrayDeque

是线程不安全的容器。

在并发场景下，推荐使用

LinkedBlockingDeque

：

  1. LinkedBlockingDeque

     （阻塞的双向队列）

因为

LinkedBlockingDeque

在队列为空的情况下，获取操作将会阻塞，直到有元素添加。[4]

疑问解答

Dispatcher

中的三个任务容器为什么会选择使用双端队列？

这三个队列存放的是进行中的同步/异步的网络请求任务，

Java

中的队列容器有很多，比如

LinkedList

、

SynchronousQueue

等，为什么选择

ArrayDeque

，它有什么优势？

效率高

Java里有一个叫做Stack的类，却没有叫做Queue的类（它是个接口名字）。当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了（次选是LinkedList）。[5]

下面是

java.util.ArrayDeque

类文件上的注释:

/**
 * Resizable-array implementation of the {@link Deque} interface.  Array
 * deques have no capacity restrictions; they grow as necessary to support
 * usage.  They are not thread-safe; in the absence of external
 * synchronization, they do not support concurrent access by multiple threads.
 * Null elements are prohibited.  This class is likely to be faster than
 * {@link Stack} when used as a stack, and faster than {@link LinkedList}
 * when used as a queue.
 * 
 * ...
 */

翻译成中文：

实现了 Deque 接口的长度可变的数组。 
1. ArrayDeque 没有容量限制，它可以根据实际需要来增加容量。
2. 它不是线程安全的，在没有外部同步的情况下，它们不支持多线程的并发访问。
3. 禁止使用 Null 元素。 
4. 当作为栈使用时，它可能比 Stack 更快；
5. 当作为队列使用时将比 LinkedList更快。

可知，作为队列使用时由于

ArrayDeque

性能比

LinkedList

更快，所以

Dispatcher

中的三个任务容器使用了

ArrayDeque

来实现队列。

为什么

ArrayDeque

性能比

LinkedList

更快呢？因为

ArrayDeque

是用循环数组来实现的，

LinkedList

是用链表实现的，增删改查的操作都比链表高（删除操作比链表高吗？如果是删除数组中间的某个元素，不是的；如果是当成栈或队列使用的场景下，是的。）。

话虽如此，在

Dispatcher

的使用场景下，仍然有删除指定位置元素的操作

public final class Dispatcher {

  private <T> void finished(Deque<T> calls, T call) {
    Runnable idleCallback;
    synchronized (this) {
      if (!calls.remove(call)) throw new AssertionError("Call wasn't in-flight!");
      idleCallback = this.idleCallback;
    }

    ......
  }
}


public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    public boolean remove(Object o) {
        return removeFirstOccurrence(o);
    }
    
    public boolean removeFirstOccurrence(Object o) {
        if (o != null) {
            int mask = elements.length - 1;
            int i = head;
            for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
                if (o.equals(x)) {
                    delete(i);
                    return true;
                }
            }
        }
        return false;
    }

    boolean delete(int i) {
        ......
    }
}

由于删除数组中指定位置的元素可能导致数组中的元素向后或向前移动，所以删除时效率可能比

LinkedList

低，而且由于

Dispatcher

的特性，网络请求的执行和返回顺序并不总是有队列先进先出的顺序，所以删除指定位置元素的操作可能也会频繁进行。

不过既然

Dispatcher

最终还是使用了

ArrayDeque

来实现网络请求队列，可能它的综合性能比较好吧。

处理线程同步

既然

ArrayDeque

不是线程安全的，那

OkHttp

是如何保证线程同步的呢？

public final class Dispatcher {

  /** Ready async calls in the order they'll be run. */
  private final Deque<AsyncCall> readyAsyncCalls = new ArrayDeque<>();

  /** Running asynchronous calls. Includes canceled calls that haven't finished yet. */
  private final Deque<AsyncCall> runningAsyncCalls = new ArrayDeque<>();

  /** Running synchronous calls. Includes canceled calls that haven't finished yet. */
  private final Deque<RealCall> runningSyncCalls = new ArrayDeque<>();
  
  ......
  
  public synchronized void cancelAll() {
     ......
  }

  private boolean promoteAndExecute() {
    
    ......
    
    boolean isRunning;
    synchronized (this) {
      for (Iterator<AsyncCall> i = readyAsyncCalls.iterator(); i.hasNext(); ) {
        AsyncCall asyncCall = i.next();

        if (runningAsyncCalls.size() >= maxRequests) break; // Max capacity.
        if (asyncCall.callsPerHost().get() >= maxRequestsPerHost) continue; // Host max capacity.

        i.remove();
        
        ......
      }
      isRunning = runningCallsCount() > 0;
    }

    ......
     
    return isRunning;
  }

  synchronized void executed(RealCall call) {
    runningSyncCalls.add(call);
  }

  private <T> void finished(Deque<T> calls, T call) {
    Runnable idleCallback;
    synchronized (this) {
      if (!calls.remove(call)) throw new AssertionError("Call wasn't in-flight!");
      idleCallback = this.idleCallback;
    }

    ......
  }

  public synchronized List<Call> queuedCalls() {
     ......
    return Collections.unmodifiableList(result);
  }

  public synchronized List<Call> runningCalls() {
     ......
    return Collections.unmodifiableList(result);
  }

  public synchronized int queuedCallsCount() {
    return readyAsyncCalls.size();
  }

  public synchronized int runningCallsCount() {
    return runningAsyncCalls.size() + runningSyncCalls.size();
  }
  
  ......
}

从源码可知，

Dispatcher

使用了大量的

synchronized

关键字来修饰所有操作

ArrayDeque

的方法，具体来说有两种形式：

  1. 直接使用

    synchronized

     关键字来修饰方法的声明，比如

    executed()

     方法；
  2. 使用

    synchronized

     关键字来修饰代码块，比如

    promoteAndExecute()

     、

    finished()

     方法。

关于

ArrayDeque

的详细介绍请参考：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/4-Stack and Queue.md

参考

[1]：https://zh.wikipedia.org/wiki/双端队列

[2]：https://blog.csdn.net/xiangxizhishi/article/details/79119501

[3]：https://blog.csdn.net/u013309870/article/details/71478120

[4]：https://blog.csdn.net/l540675759/article/details/62893335

[5]：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/4-Stack and Queue.md

源码笔记 okhttp ArrayDeque 双端队列
上一篇: Dubbo——Proxy 层代理分析
下一篇: 基数排序（RADIX SORT

继续阅读