读HikariCP源码学Java（二）—— 因地制宜的改装ArrayList：FastList

2021-06-13 00:00

前言

如前文所述，HikariCP为了提高性能不遗余力，其中一个比较特别的优化是它没有直接使用ArrayList，而是自己实现了FastList，因地制宜，让数组的读写性能都有了一定程度的提高。

构造方法

FastList：

@SuppressWarnings("unchecked")
public FastList(Class<?> clazz)
{
    this.elementData = (T[]) Array.newInstance(clazz, 32); // ArrayList
    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

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else {
        if (initialCapacity != 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

        this.elementData = EMPTY_ELEMENTDATA;
    }

}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((this.size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            this.elementData = a;
        } else {
            this.elementData = Arrays.copyOf(a, this.size, Object[].class);
        }
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }

}

在无参构造方法中，ArrayList初始化了一个空数组，这是出于节省空间的考虑，但在HikariCP中，可以确认只要创建了FastList就一定会使用，所以直接初始化一个长度为32的数组，以减少FastList的扩容次数。

还有一点不同是FastList的所有构造方法都传入了数组保存的元素的类，这是为了之后的扩容过程中不必使用反射进行类型推导。

添加元素

FastList:

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:

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

    elementData[s] = e;
    this.size = s + 1;
}

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

public void add(int index, E element) {
    this.rangeCheckForAdd(index);
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }

    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}

private Object[] grow() {
    return this.grow(this.size + 1);
}

首先可以注意到的是，ArrayList中除了默认的一个参数的add方法，还有一个带有插入元素下标的整型参数的重载，用于插入到数组的中间位置。但HikariCP中只需要向数组的末尾添加元素，所以不必实现复杂的数组后移操作。

这样的设计带来的另一个好处是可以省去数组越界的判断，因为只会插入到尾部，不会出现不受控制的插入行为。

另外，ArrayList中使用了一个整型变量modCount记录修改的次数。这是一个简单的CAS机制，避免在多线程访问ArrayList（迭代器方式）时，数组发生了结构变化，导致并发问题。

扩容

当添加过程中出现容量不够时，ArrayList和FastList都会进行扩容。二者有如下两点区别：

ArrayList完全依靠泛型系统获知元素的类型，而FastList在实例化数组的时候就传入了元素类型，因此FastList的插入效率要更高一些。
ArrayList扩容的倍数的1.5倍，而FastList是2倍，可见FastList是为了减少扩容次数，降低时间复杂度，牺牲了一点空间复杂度。

删除元素

FastList:

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;
}

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:

public E remove(int index) {
    Objects.checkIndex(index, this.size);
    Object[] es = this.elementData;
    E oldValue = es[index];
    this.fastRemove(es, index);
    return oldValue;
}

public boolean remove(Object o) {
    Object[] es = this.elementData;
    int size = this.size;
    int i = 0;
    if (o == null) {
        while(true) {
            if (i >= size) {
                return false;
            }

            if (es[i] == null) {
                break;
            }

            ++i;
        }
    } else {
        while(true) {
            if (i >= size) {
                return false;
            }

            if (o.equals(es[i])) {
                break;
            }

            ++i;
        }
    }

    this.fastRemove(es, i);
    return true;
}

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

    es[this.size = newSize] = null;
}

FastList和ArrayList的删除都分为两种，一种是删除指定位置的元素，另一种是删除指定元素。

删除指定位置的元素

删除指定位置的元素比较简单，二者都通过向前复制数组实现，区别是ArrayList会对参数做校验，FastList省略了这一步。

删除指定元素

二者的实现也类似，但ArrayList首先进行了判空。

另外，ArrayList删除元素也会修改modCount。

获取元素

FastList:

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

ArrayList:

public E get(int index) {
    Objects.checkIndex(index, this.size);
    this.checkForComodification();
    return this.root.elementData(this.offset + index);
}

ArrayList会做数组越界的校验，FastList不会，其它的没有区别，都是直接取数组指定位置的元素。

迭代器

FastList:

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:

public Iterator<E> iterator() {
    return this.listIterator();
}

public ListIterator<E> listIterator(final int index) {
    this.checkForComodification();
    this.rangeCheckForAdd(index);
    return new ListIterator<E>() {
        int cursor = index;
        int lastRet = -1;
        int expectedModCount;

        {
            this.expectedModCount = SubList.this.modCount;
        }

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

        public E next() {
            this.checkForComodification();
            int i = this.cursor;
            if (i >= SubList.this.size) {
                throw new NoSuchElementException();
            } else {
                Object[] elementData = SubList.this.root.elementData;
                if (SubList.this.offset + i >= elementData.length) {
                    throw new ConcurrentModificationException();
                } else {
                    this.cursor = i + 1;
                    return elementData[SubList.this.offset + (this.lastRet = i)];
                }
            }
        }

        public boolean hasPrevious() {
            return this.cursor != 0;
        }

        public E previous() {
            this.checkForComodification();
            int i = this.cursor - 1;
            if (i < 0) {
                throw new NoSuchElementException();
            } else {
                Object[] elementData = SubList.this.root.elementData;
                if (SubList.this.offset + i >= elementData.length) {
                    throw new ConcurrentModificationException();
                } else {
                    this.cursor = i;
                    return elementData[SubList.this.offset + (this.lastRet = i)];
                }
            }
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            int size = SubList.this.size;
            int i = this.cursor;
            if (i < size) {
                Object[] es = SubList.this.root.elementData;
                if (SubList.this.offset + i >= es.length) {
                    throw new ConcurrentModificationException();
                }

                while(i < size && SubList.this.root.modCount == this.expectedModCount) {
                    action.accept(ArrayList.elementAt(es, SubList.this.offset + i));
                    ++i;
                }

                this.cursor = i;
                this.lastRet = i - 1;
                this.checkForComodification();
            }

        }

        public int nextIndex() {
            return this.cursor;
        }

        public int previousIndex() {
            return this.cursor - 1;
        }

        public void remove() {
            if (this.lastRet < 0) {
                throw new IllegalStateException();
            } else {
                this.checkForComodification();

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

        public void set(E e) {
            if (this.lastRet < 0) {
                throw new IllegalStateException();
            } else {
                this.checkForComodification();

                try {
                    SubList.this.root.set(SubList.this.offset + this.lastRet, e);
                } catch (IndexOutOfBoundsException var3) {
                    throw new ConcurrentModificationException();
                }
            }
        }

        public void add(E e) {
            this.checkForComodification();

            try {
                int i = this.cursor;
                SubList.this.add(i, e);
                this.cursor = i + 1;
                this.lastRet = -1;
                this.expectedModCount = SubList.this.modCount;
            } catch (IndexOutOfBoundsException var3) {
                throw new ConcurrentModificationException();
            }
        }

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

对比ArrayList，FastList的迭代器省去了以下几步流程：

ArrayList利用前文提到的modCount，实现了checkForComodification方法，进行并发安全性校验。
ArrayList在判断数组越界之外增加了一道校验：SubList.this.offset + i >= elementData.length，这也是一道并发安全性校验。
ArrayList在匿名类中实现了方法forEachRemaining，用于lambda调用。

总结

另外，FastList省去了很多不需要的ArrayList的方法，减小了类的体积。

综上，FastList是完全用于内部调用的类，不对外暴露，所以可以减少很多安全性的校验和设计，以提高性能。

缪若尘的闲言碎语

前言

构造方法

添加元素

扩容

删除元素

删除指定位置的元素

删除指定元素

获取元素

迭代器

总结