HikariCP 源码分析 -- FastList

HikariCP 源码分析 --  FastList

在前面的文章 HikariCP 源码分析 — ConcurrentBag 中,D瓜哥分析了一下 HikariCP 中一个非常重要的数据结构 ConcurrentBag

今天,继续再介绍 HikariCP 中另一个很关键的数据结构: FastList

FastList 本身的实现非常简单,要理解它的奥秘,就需要结合 Java 原生集合类的 ArrayList 来比较性地看。

构造函数

先来对比一下两者的构造函数。先来看看 FastList

FastList
public final class FastList<T> implements List<T>, RandomAccess, Serializable
{
   private static final long serialVersionUID = -4598088075242913858L;

   private final Class<?> clazz;
   private T[] elementData;
   private int size;

   /
    * Construct a FastList with a default size of 32.
    * @param clazz the Class stored in the collection
    */
   @SuppressWarnings("unchecked")
   public FastList(Class<?> clazz)
   {
      this.elementData = (T[]) Array.newInstance(clazz, 32);
      this.clazz = clazz;
   }

   /
    * Construct a FastList with a specified size.
    * @param clazz the Class stored in the collection
    * @param capacity the initial size of the FastList
    */
   @SuppressWarnings("unchecked")
   public FastList(Class<?> clazz, int capacity)
   {
      this.elementData = (T[]) Array.newInstance(clazz, capacity);
      this.clazz = clazz;
   }

再来看看 ArrayList

ArrayList
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

    /
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

相同之处是,两者都是通过数组来存放元素的。

两者有如下不同之处:

  1. FastList 没有对容量大小做判断。毕竟是在内部使用,自己不会故意坑自己。所以,也就没必要了。

  2. FastList 保存了元素的类型 Class,在扩容时直接使用即可;而 ArrayList 则要麻烦一些。后面在细讲。

  3. FastList 默认大小为 32,而且直接初始化; ArrayList10,默认是空数组,直到添加元素才创建数组。这里,也要从适用性来说, FastList 是内部使用,创建出来就比如要存放元素。所以,直接初始化比较合适。而 ArrayList 外部使用,不确定是否必须要存放元素,直到确实存放元素时,再初始化比较节省空间。

  4. FastList 只实现了 ListArrayList 实现了 ListCloneable 接口,显示标注出克隆功能。其实,这两个差别不大,毕竟 Object 也有 clone() 方法。

  5. ArrayList 多了一个 public ArrayList(Collection<? extends E> c) 构造函数,方便接受。

总体来讲, FastList 的实现比较克制,够用即可;而 ArrayList 则更多考虑适用性,满足尽可能多的场景。

添加元素

再来看看两者如何处理添加元素的操作。还是先看 FastList 的实现:

FastList
@Override
public boolean add(T element)
{
   if (size < elementData.length) {
      elementData[size++] = element;
   }
   else {
      // overflow-conscious code
      final int oldCapacity = elementData.length;
      final int newCapacity = oldCapacity << 1;
      @SuppressWarnings("unchecked")
      final T[] newElementData = (T[]) Array.newInstance(clazz, newCapacity);
      System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);
      newElementData[size++] = element;
      elementData = newElementData;
   }

   return true;
}

再来看看 ArrayList

ArrayList
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

// grow() 代码不再粘贴,将数组长度

两者有这些地方需要注意:

  1. ArrayList 维护了一个 modCount 变量来保存修改次数。

  2. 在添加元素时,都需要对容量做一个判断:

    1. FastList 在容量 OK 的情况下,直接添加元素;容量不够时,创建一个 2 倍原数组的新数组,使用 System.arraycopy 将已有数据拷贝到新数组,然后再添加新元素。

    2. ArrayList 则是判断数组是否已满,满了就创建一个 1.5 倍大小的新数组,将已有数据拷贝过来再添加新元素。这里需要多说一句,由于 ArrayList 存数据的类型 Class 信息,在扩容时,通过反射获取这个 Class 信息。所以,理论上来说,不如 FastList

获得元素

再来看看获取元素操作。先看 FastList

FastList
@Override
public T get(int index)
{
    return elementData[index];
}

再来看看 ArrayList

ArrayList
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

请注意: FastList 是直接从数组中根据 index 返回数据,没有对 index 做任何校验;而 ArrayList 则先做了校验,合法后才返回元素。所以, FastList 操作更快!

删除元素

来看看删除元素的操作。删除操作有两组:①删除某个元素;②删除指定 index 的元素。

删除某个元素

先看 FastList

FastList
public T removeLast()
{
   T element = elementData[--size];
   elementData[size] = null;
   return element;
}

@Override
public boolean remove(Object element)
{
   for (int index = size - 1; index >= 0; index--) {
      if (element == elementData[index]) {
         final int numMoved = size - index - 1;
         if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
         }
         elementData[--size] = null;
         return true;
      }
   }

   return false;
}

再来看看 ArrayList

ArrayList
public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

两者的处理流程基本相同。不同之处在于 ArrayList 需要处理元素为 null 的情况,而 FastList 不需要。另外, FastList 还对接口做了扩展,增加了 removeLast() 方法。而 ArrayList 维护了一个 modCount 变量来保存修改次数。

删除指定 index 的元素

先看 FastList

FastList
@Override
public T remove(int index)
{
    if (size == 0) {
        return null;
    }

    final T old = elementData[index];

    final int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }

    elementData[--size] = null;

    return old;
}

再来看看 ArrayList

ArrayList
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

请注意: FastList 是直接通过向前复制来删除元素,没有对 index 做任何校验;而 ArrayList 则先做了校验,合法后才通过向前复制来删除元素。所以, FastList 操作更快!

清空元素

来看看删除元素的操作。先看 FastList

FastList
@Override
public void clear()
{
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
    }

    size = 0;
}

再来看看 ArrayList

ArrayList
public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

这两者基本一致。 ArrayList 多了一点操作,维护了一个 modCount 变量来保存修改次数。

遍历

来看看遍历操作。先看 FastList

FastList
@Override
public Iterator<T> iterator()
{
    return new Iterator<T>() {
        private int index;

        @Override
        public boolean hasNext()
        {
        return index < size;
        }

        @Override
        public T next()
        {
            if (index < size) {
                return elementData[index++];
            }

            throw new NoSuchElementException("No more elements in FastList");
        }
    };
}

再来看看 ArrayList

ArrayList
public Iterator<E> iterator() {
    return new Itr();
}

/**
    * An optimized version of AbstractList.Itr
    */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i < size) {
            final Object[] es = elementData;
            if (i >= es.length)
                throw new ConcurrentModificationException();
            for (; i < size && modCount == expectedModCount; i++)
                action.accept(elementAt(es, i));
            // update once at end to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

两者的遍历操作,差别好大:

  1. FastList 只对当前 index 判断,符合要求则直接返回,不符合要求抛出异常。

  2. ArrayList 则要复杂好多:

    1. 通过 checkForComodification() 方法检查当前 ArrayList 对象是否被同步修改;

    2. 除了判断 index 是否小于当前 size,还要判断 index 是否大于等于 elementData.length,以应对同步修改的问题;

    3. 实现了 remove()forEachRemaining(Consumer<? super E> action) 方法。

小结

总体来讲 FastList 通过一下几点来达到提速的目的:

  1. 删除 index 合法性判断; — 这是非常关键的一点。尤其是在获取元素的时候。

  2. 删除修改次数统计;

  3. 保存元素类型 Class 实例,便于扩容;

  4. 空置无用方法,达到瘦身目的。

所以, FastList 相当于给了我们一些优化程序的思路。

关于优化程序,大家有什么自己的看法吗?欢迎留言讨论…