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;
}
}
相同之处是,两者都是通过数组来存放元素的。
两者有如下不同之处:
FastList
没有对容量大小做判断。毕竟是在内部使用,自己不会故意坑自己。所以,也就没必要了。FastList
保存了元素的类型Class
,在扩容时直接使用即可;而ArrayList
则要麻烦一些。后面在细讲。FastList
默认大小为32
,而且直接初始化;ArrayList
是10
,默认是空数组,直到添加元素才创建数组。这里,也要从适用性来说,FastList
是内部使用,创建出来就比如要存放元素。所以,直接初始化比较合适。而ArrayList
外部使用,不确定是否必须要存放元素,直到确实存放元素时,再初始化比较节省空间。FastList
只实现了List
;ArrayList
实现了List
和Cloneable
接口,显示标注出克隆功能。其实,这两个差别不大,毕竟Object
也有clone()
方法。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() 代码不再粘贴,将数组长度
两者有这些地方需要注意:
ArrayList
维护了一个modCount
变量来保存修改次数。在添加元素时,都需要对容量做一个判断:
FastList
在容量 OK 的情况下,直接添加元素;容量不够时,创建一个 2 倍原数组的新数组,使用System.arraycopy
将已有数据拷贝到新数组,然后再添加新元素。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();
}
}
两者的遍历操作,差别好大:
FastList
只对当前index
判断,符合要求则直接返回,不符合要求抛出异常。ArrayList
则要复杂好多:通过
checkForComodification()
方法检查当前ArrayList
对象是否被同步修改;除了判断
index
是否小于当前size
,还要判断index
是否大于等于elementData.length
,以应对同步修改的问题;实现了
remove()
和forEachRemaining(Consumer<? super E> action)
方法。
小结
总体来讲 FastList
通过一下几点来达到提速的目的:
删除
index
合法性判断; — 这是非常关键的一点。尤其是在获取元素的时候。删除修改次数统计;
保存元素类型
Class
实例,便于扩容;空置无用方法,达到瘦身目的。
所以, FastList
相当于给了我们一些优化程序的思路。
关于优化程序,大家有什么自己的看法吗?欢迎留言讨论…