歡迎光臨
每天分享高質量文章

【追光者系列】HikariCP原始碼分析之FastList

摘自【工匠小豬豬的技術世界】 1.這是一個系列,有興趣的朋友可以持續關註 2.如果你有HikariCP使用上的問題,可以給我留言,我們一起溝通討論 3.希望大家可以提供我一些案例,我也希望可以支援你們做一些調優


概述

在Down-the-Rabbit-Hole中,作者提到了一些 Micro-optimizations,表達了作者追求極致的態度。

HikariCP contains many micro-optimizations that individually are barely measurable, but together combine as a boost to overall performance. Some of these optimizations are measured in fractions of a millisecond amortized over millions of invocations.

其中第一條就提到了ArrayList的最佳化

One non-trivial (performance-wise) optimization was eliminating the use of an ArrayList instance in the ConnectionProxy used to track open Statement instances. When a Statement is closed, it must be removed from this collection, and when the Connection is closed it must iterate the collection and close any open Statement instances, and finally must clear the collection. The Java ArrayList, wisely for general purpose use, performs a range check upon every get(int index) call. However, because we can provide guarantees about our ranges, this check is merely overhead.

Additionally, the remove(Object) implementation performs a scan from head to tail, however common patterns in JDBC programming are to close Statements immediately after use, or in reverse order of opening. For these cases, a scan that starts at the tail will perform better. Therefore, ArrayList was replaced with a custom class FastList which eliminates range checking and performs removal scans from tail to head.

FastList是一個List介面的精簡實現,只實現了介面中必要的幾個方法。JDK ArrayList每次呼叫get()方法時都會進行rangeCheck檢查索引是否越界,FastList的實現中去除了這一檢查,只要保證索引合法那麼rangeCheck就成為了不必要的計算開銷(當然開銷極小)。此外,HikariCP使用List來儲存開啟的Statement,當Statement關閉或Connection關閉時需要將對應的Statement從List中移除。通常情況下,同一個Connection建立了多個Statement時,後開啟的Statement會先關閉。ArrayList的remove(Object)方法是從頭開始遍歷陣列,而FastList是從陣列的尾部開始遍歷,因此更為高效。

簡而言之就是 自定義陣列型別(FastList)代替ArrayList:避免每次get()呼叫都要進行range check,避免呼叫remove()時的從頭到尾的掃描

原始碼分析

java.util.ArrayList

  1. public class ArrayList<E> extends AbstractList<E>

  2.        implements List<E>, RandomAccess, Cloneable, java.io.Serializablecode>

  3. com.zaxxer.hikari.util.FastList

  4. <code class="">public final class FastList<T> implements List<T>, RandomAccess, Serializable

我們先看一下java.util.ArrayList的get方法

  1.   /**

  2.     * Returns the element at the specified position in this list.

  3.     *

  4.     * @param  index index of the element to return

  5.     * @return the element at the specified position in this list

  6.     * @throws IndexOutOfBoundsException {@inheritDoc}

  7.     */

  8.    public E get(int index) {

  9.        rangeCheck(index);

  10.        return elementData(index);

  11.    }

我們可以看到每次get的時候都會進行rangeCheck

  1.    /**

  2.     * Checks if the given index is in range.  If not, throws an appropriate

  3.     * runtime exception.  This method does *not* check if the index is

  4.     * negative: It is always used immediately prior to an array access,

  5.     * which throws an ArrayIndexOutOfBoundsException if index is negative.

  6.     */

  7.    private void rangeCheck(int index) {

  8.        if (index >= size)

  9.            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  10.    }

我們對比一下com.zaxxer.hikari.util.FastList的get方法,可以看到取消了rangeCheck,一定程度下追求了極致

  1.   /**

  2.    * Get the element at the specified index.

  3.    *

  4.    * @param index the index of the element to get

  5.    * @return the element, or ArrayIndexOutOfBounds is thrown if the index is invalid

  6.    */

  7.   @Override

  8.   public T get(int index) {

  9.      return elementData[index];

  10.   }

我們再來看一下ArrayList的remove(Object)方法

  1.   /**

  2.     * Removes the first occurrence of the specified element from this list,

  3.     * if it is present.  If the list does not contain the element, it is

  4.     * unchanged.  More formally, removes the element with the lowest index

  5.     * i such that

  6.     * (o==null ? get(i)==null : o.equals(get(i)))

  7.     * (if such an element exists).  Returns true if this list

  8.     * contained the specified element (or equivalently, if this list

  9.     * changed as a result of the call).

  10.     *

  11.     * @param o element to be removed from this list, if present

  12.     * @return true if this list contained the specified element

  13.     */

  14.    public boolean remove(Object o) {

  15.        if (o == null) {

  16.            for (int index = 0; index < size; index++)

  17.                if (elementData[index] == null) {

  18.                    fastRemove(index);

  19.                    return true;

  20.                }

  21.        } else {

  22.            for (int index = 0; index < size; index++)

  23.                if (o.equals(elementData[index])) {

  24.                    fastRemove(index);

  25.                    return true;

  26.                }

  27.        }

  28.        return false;

  29.    }

再對比看一下FastList的remove(Object方法)

  1.  /**

  2.    * This remove method is most efficient when the element being removed

  3.    * is the last element.  Equality is identity based, not equals() based.

  4.    * Only the first matching element is removed.

  5.    *

  6.    * @param element the element to remove

  7.    */

  8.   @Override

  9.   public boolean remove(Object element) {

  10.      for (int index = size - 1; index >= 0; index--) {

  11.         if (element == elementData[index]) {

  12.            final int numMoved = size - index - 1;

  13.            if (numMoved > 0) {

  14.               System.arraycopy(elementData, index + 1, elementData, index, numMoved);

  15.            }

  16.            elementData[--size] = null;

  17.            return true;

  18.         }

  19.      }

  20.      return false;

  21.   }

好了,今天的文章就是這麼簡短,最後附一下FastList的原始碼,內容真的是十分精簡的。

  1. /*

  2. * Copyright (C) 2013, 2014 Brett Wooldridge

  3. *

  4. * Licensed under the Apache License, Version 2.0 (the "License");

  5. * you may not use this file except in compliance with the License.

  6. * You may obtain a copy of the License at

  7. *

  8. * http://www.apache.org/licenses/LICENSE-2.0

  9. *

  10. * Unless required by applicable law or agreed to in writing, software

  11. * distributed under the License is distributed on an "AS IS" BASIS,

  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

  13. * See the License for the specific language governing permissions and

  14. * limitations under the License.

  15. */

  16. package com.zaxxer.hikari.util;

  17. import java.io.Serializable;

  18. import java.lang.reflect.Array;

  19. import java.util.Collection;

  20. import java.util.Comparator;

  21. import java.util.Iterator;

  22. import java.util.List;

  23. import java.util.ListIterator;

  24. import java.util.NoSuchElementException;

  25. import java.util.RandomAccess;

  26. import java.util.Spliterator;

  27. import java.util.function.Consumer;

  28. import java.util.function.Predicate;

  29. import java.util.function.UnaryOperator;

  30. /**

  31. * Fast list without range checking.

  32. *

  33. * @author Brett Wooldridge

  34. */

  35. public final class FastList<T> implements List<T>, RandomAccess, Serializable {

  36.   private static final long serialVersionUID = -4598088075242913858L;

  37.   private final Class> clazz;

  38.   private T[] elementData;

  39.   private int size;

  40.   /**

  41.    * Construct a FastList with a default size of 32.

  42.    * @param clazz the Class stored in the collection

  43.    */

  44.   @SuppressWarnings("unchecked")

  45.   public FastList(Class> clazz) {

  46.      this.elementData = (T[]) Array.newInstance(clazz, 32);

  47.      this.clazz = clazz;

  48.   }

  49.   /**

  50.    * Construct a FastList with a specified size.

  51.    * @param clazz the Class stored in the collection

  52.    * @param capacity the initial size of the FastList

  53.    */

  54.   @SuppressWarnings("unchecked")

  55.   public FastList(Class> clazz, int capacity) {

  56.      this.elementData = (T[]) Array.newInstance(clazz, capacity);

  57.      this.clazz = clazz;

  58.   }

  59.   /**

  60.    * Add an element to the tail of the FastList.

  61.    *

  62.    * @param element the element to add

  63.    */

  64.   @Override

  65.   public boolean add(T element) {

  66.      if (size < elementData.length) {

  67.         elementData[size++] = element;

  68.      }

  69.      else {

  70.         // overflow-conscious code

  71.         final int oldCapacity = elementData.length;

  72.         final int newCapacity = oldCapacity << 1;

  73.         @SuppressWarnings("unchecked")

  74.         final T[] newElementData = (T[]) Array.newInstance(clazz, newCapacity);

  75.         System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);

  76.         newElementData[size++] = element;

  77.         elementData = newElementData;

  78.      }

  79.      return true;

  80.   }

  81.   /**

  82.    * Get the element at the specified index.

  83.    *

  84.    * @param index the index of the element to get

  85.    * @return the element, or ArrayIndexOutOfBounds is thrown if the index is invalid

  86.    */

  87.   @Override

  88.   public T get(int index) {

  89.      return elementData[index];

  90.   }

  91.   /**

  92.    * Remove the last element from the list.  No bound check is performed, so if this

  93.    * method is called on an empty list and ArrayIndexOutOfBounds exception will be

  94.    * thrown.

  95.    *

  96.    * @return the last element of the list

  97.    */

  98.   public T removeLast() {

  99.      T element = elementData[--size];

  100.      elementData[size] = null;

  101.      return element;

  102.   }

  103.   /**

  104.    * This remove method is most efficient when the element being removed

  105.    * is the last element.  Equality is identity based, not equals() based.

  106.    * Only the first matching element is removed.

  107.    *

  108.    * @param element the element to remove

  109.    */

  110.   @Override

  111.   public boolean remove(Object element) {

  112.      for (int index = size - 1; index >= 0; index--) {

  113.         if (element == elementData[index]) {

  114.            final int numMoved = size - index - 1;

  115.            if (numMoved > 0) {

  116.               System.arraycopy(elementData, index + 1, elementData, index, numMoved);

  117.            }

  118.            elementData[--size] = null;

  119.            return true;

  120.         }

  121.      }

  122.      return false;

  123.   }

  124.   /**

  125.    * Clear the FastList.

  126.    */

  127.   @Override

  128.   public void clear() {

  129.      for (int i = 0; i < size; i++) {

  130.         elementData[i] = null;

  131.      }

  132.      size = 0;

  133.   }

  134.   /**

  135.    * Get the current number of elements in the FastList.

  136.    *

  137.    * @return the number of current elements

  138.    */

  139.   @Override

  140.   public int size() {

  141.      return size;

  142.   }

  143.   /** {@inheritDoc} */

  144.   @Override

  145.   public boolean isEmpty() {

  146.      return size == 0;

  147.   }

  148.   /** {@inheritDoc} */

  149.   @Override

  150.   public T set(int index, T element) {

  151.      T old = elementData[index];

  152.      elementData[index] = element;

  153.      return old;

  154.   }

  155.   /** {@inheritDoc} */

  156.   @Override

  157.   public T remove(int index) {

  158.      if (size == 0) {

  159.         return null;

  160.      }

  161.      final T old = elementData[index];

  162.      final int numMoved = size - index - 1;

  163.      if (numMoved > 0) {

  164.         System.arraycopy(elementData, index + 1, elementData, index, numMoved);

  165.      }

  166.      elementData[--size] = null;

  167.      return old;

  168.   }

  169.   /** {@inheritDoc} */

  170.   @Override

  171.   public boolean contains(Object o) {

  172.      throw new UnsupportedOperationException();

  173.   }

  174.   /** {@inheritDoc} */

  175.   @Override

  176.   public Iterator<T> iterator() {

  177.      return new Iterator<T>() {

  178.         private int index;

  179.         @Override

  180.         public boolean hasNext() {

  181.            return index < size;

  182.         }

  183.         @Override

  184.         public T next() {

  185.            if (index < size) {

  186.               return elementData[index++];

  187.            }

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

  189.         }

  190.      };

  191.   }

  192.   /** {@inheritDoc} */

  193.   @Override

  194.   public Object[] toArray()

  195.   {

  196.      throw new UnsupportedOperationException();

  197.   }

  198.   /** {@inheritDoc} */

  199.   @Override

  200.   public <E> E[] toArray(E[] a)

  201.   {

  202.      throw new UnsupportedOperationException();

  203.   }

  204.   /** {@inheritDoc} */

  205.   @Override

  206.   public boolean containsAll(Collection> c) {

  207.      throw new UnsupportedOperationException();

  208.   }

  209.   /** {@inheritDoc} */

  210.   @Override

  211.   public boolean addAll(Collection extends T> c) {

  212.      throw new UnsupportedOperationException();

  213.   }

  214.   /** {@inheritDoc} */

  215.   @Override

  216.   public boolean addAll(int index, Collection extends T> c) {

  217.      throw new UnsupportedOperationException();

  218.   }

  219.   /** {@inheritDoc} */

  220.   @Override

  221.   public boolean removeAll(Collection> c) {

  222.      throw new UnsupportedOperationException();

  223.   }

  224.   /** {@inheritDoc} */

  225.   @Override

  226.   public boolean retainAll(Collection> c) {

  227.      throw new UnsupportedOperationException();

  228.   }

  229.   /** {@inheritDoc} */

  230.   @Override

  231.   public void add(int index, T element) {

  232.      throw new UnsupportedOperationException();

  233.   }

  234.   /** {@inheritDoc} */

  235.   @Override

  236.   public int indexOf(Object o) {

  237.      throw new UnsupportedOperationException();

  238.   }

  239.   /** {@inheritDoc} */

  240.   @Override

  241.   public int lastIndexOf(Object o) {

  242.      throw new UnsupportedOperationException();

  243.   }

  244.   /** {@inheritDoc} */

  245.   @Override

  246.   public ListIterator<T> listIterator() {

  247.      throw new UnsupportedOperationException();

  248.   }

  249.   /** {@inheritDoc} */

  250.   @Override

  251.   public ListIterator<T> listIterator(int index) {

  252.      throw new UnsupportedOperationException();

  253.   }

  254.   /** {@inheritDoc} */

  255.   @Override

  256.   public List<T> subList(int fromIndex, int toIndex) {

  257.      throw new UnsupportedOperationException();

  258.   }

  259.   /** {@inheritDoc} */

  260.   @Override

  261.   public Object clone() {

  262.      throw new UnsupportedOperationException();

  263.   }

  264.   /** {@inheritDoc} */

  265.   @Override

  266.   public void forEach(Consumer super T> action) {

  267.      throw new UnsupportedOperationException();

  268.   }

  269.   /** {@inheritDoc} */

  270.   @Override

  271.   public Spliterator<T> spliterator() {

  272.      throw new UnsupportedOperationException();

  273.   }

  274.   /** {@inheritDoc} */

  275.   @Override

  276.   public boolean removeIf(Predicate super T> filter) {

  277.      throw new UnsupportedOperationException();

  278.   }

  279.   /** {@inheritDoc} */

  280.   @Override

  281.   public void replaceAll(UnaryOperator<T> operator) {

  282.      throw new UnsupportedOperationException();

  283.   }

  284.   /** {@inheritDoc} */

  285.   @Override

  286.   public void sort(Comparator super T> c) {

  287.      throw new UnsupportedOperationException();

  288.   }

  289. }

參考資料

  • https://github.com/brettwooldridge/HikariCP/wiki/Down-the-Rabbit-Hole

END

贊(0)

分享創造快樂

© 2024 知識星球   網站地圖