ほとんどのジャビストは、 java.util.ArrayList
がJavaの世界で最も使用されているコレクションであることに同意すると思います。 ほとんどの場合、その機能は日常の作業に十分であるため、バージョン1.2で登場し、すぐに「デフォルトのコレクション」になりました。 このクラスをできるだけ生産的にするために、このクラスには多くの変更が加えられています（たとえば、 JDK 8リポジトリの変更履歴を参照）。 この記事では、 ArrayList
ようなポンプされたコンポーネントでさえ、改善の余地があることを示します。
リストの一部を配列に変換する必要があるとします。 これを行うには、メソッドを説明します。
public T[] toSubArray(ArrayList<T> list, int from, int to) { return list .subList(from, to) .toArray(new T[0]); }
元のリストの配列への変換と比較して、そのパフォーマンスを評価してみましょう。
@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"}) public class SubListToArrayBenchmark { /** * baseline */ @Benchmark public Integer[] list(Data data) { return data.list.toArray(new Integer[0]); } @Benchmark public Integer[] subList(Data data) { return data.list.subList(0, data.size).toArray(new Integer[0]); } @State(Scope.Thread) public static class Data { ArrayList<Integer> list; @Param({"0", "10", "100", "1000"}) int size; @Setup public void setup() { list = IntStream .range(0, size) .boxed() .collect(toCollection(ArrayList::new)); } } }
測定が完了すると、 subList()
メソッドのパフォーマンスはベースラインのパフォーマンスよりも著しく劣ることがわかります。
| ベンチマーク | サイズ | 得点 | エラー | 単位 |
|---|---|---|---|---|
| リスト | 0 | 7.2 | 0.1 | ns / op |
| subList | 0 | 12.8 | 0.2 | ns / op |
| リスト | 10 | 34.6 | 3.9 | ns / op |
| subList | 10 | 44.7 | 1,0 | ns / op |
| リスト | 100 | 141.9 | 2.2 | ns / op |
| subList | 100 | 252.1 | 4.9 | ns / op |
| リスト | 1000 | 1201.6 | 21.0 | ns / op |
| subList | 1000 | 2310.4 | 53.0 | ns / op |
どちらの場合も同じ量のデータが移動するという事実を考えると、この大きな違いは驚くべきことです。
キーはArrayList
クラスにあります。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //... public Object[] toArray() { return Arrays.copyOf(elementData, size); } public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } //... }
どちらのメソッドも、 Arrays.copyOf()
およびSystem.arraycopy()
を使用してデータを移動し、配列に直接アクセスします。 中を見てみましょう：
public class Arrays { //... @HotSpotIntrinsicCandidate // since Java 9 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } //... }
public final class System { //... @HotSpotIntrinsicCandidate // since Java 9 public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); //... }
指定されたメソッドは@HotSpotIntrinsicCandidate
としてマークされ、VMを許可します それらのための高性能マシンコードを作成する 実装を高性能マシンコードに置き換えて、最高のパフォーマンスを実現します。
さて、 subList()
メソッドを見てみましょう。
public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList<>(this, fromIndex, toIndex); }
ご覧のとおり、 ArrayList
はこのメソッドの独自の実装があり、さらに重要なこととして、リスト部分のプレゼンテーションの独自の実装があります。
private static class SubList<E> extends AbstractList<E> implements RandomAccess { private final ArrayList<E> root; private final SubList<E> parent; private final int offset; private int size; //... }
主なもの： SubList
RandomAccess
としてマークされ、 root
フィールドを介して配列に直接アクセスできますが、 toArray()
およびtoArray(T[])
メソッドの独自の実装はありません 。 もしそうなら、 AbstractCollection
クラスの継承されたメソッドが使用されます：
public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()]; Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; } public <T> T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) { // fewer elements than expected if (a == r) { r[i] = null; // null-terminate } else if (a.length < i) { return Arrays.copyOf(r, i); } else { System.arraycopy(r, 0, a, 0, i); if (a.length > i) { a[i] = null; } } return a; } r[i] = (T)it.next(); } // more elements than expected return it.hasNext() ? finishToArray(r, it) : r; }
ここで、配列はイテレータを使用してループで埋められます。これは、 Arrays.copyOf()
およびSystem.arraycopy()
を使用したデータ転送よりも遅くなります。 したがって、パフォーマンスを改善するには、 toArray()
およびtoArray(T[])
をオーバーライドし、 ArrayList
と同じアプローチを使用する必要があります。 補足：
private static class SubList<E> extends AbstractList<E> implements RandomAccess { private final ArrayList<E> root; private final SubList<E> parent; private final int offset; private int size; //... @Override public Object[] toArray() { return Arrays.copyOfRange(root.elementData, offset, offset + size); } @Override public <T> T[] toArray(T[] a) { if (a.length < size) return (T[]) Arrays.copyOfRange(root.elementData, offset, offset + size, a.getClass()); System.arraycopy(root.elementData, offset, a, 0, size); if (a.length > size) a[size] = null; return a; } //... }
私たちはすべて正しいことをしましたか？ いや！ オーバーライドしたメソッドは、 subList()
メソッドがsubList()
れた後に元のリストが変更される可能性を考慮していません。 この機会を考慮に入れなければなりません。 したがって、オーバーライドされた各メソッドの先頭にチェックを追加します。
@Override public Object[] toArray() { checkForComodification(); // <-- return Arrays.copyOfRange(root.elementData, offset, offset + size); } @Override public <T> T[] toArray(T[] a) { checkForComodification(); // <-- if (a.length < size) return (T[]) Arrays.copyOfRange(root.elementData, offset, offset + size, a.getClass()); System.arraycopy(root.elementData, offset, a, 0, size); if (a.length > size) a[size] = null; return a; }
変更されたArrayList
subList()
ベンチマークsubList()
と、 subList()
メソッドのパフォーマンスはベースラインのパフォーマンスよりわずかに劣っていることがわかります。 わずかな遅れは、サブリストの作成と、 toArray(T[])
メソッドの開始時のcheckForComodification()
呼び出しによるものです。
| ベンチマーク | サイズ | 得点 | エラー | 単位 |
|---|---|---|---|---|
| リスト | 0 | 7.2 | 0.1 | ns / op |
| subList | 0 | 7.5 | 0.2 | ns / op |
| リスト | 10 | 24.5 | 0.5 | ns / op |
| subList | 10 | 25,4 | 0.6 | ns / op |
| リスト | 100 | 142.8 | 4,5 | ns / op |
| subList | 100 | 141.6 | 2.5 | ns / op |
| リスト | 1000 | 1243.6 | 28.5 | ns / op |
| subList | 1000 | 1247.8 | 23.7 | ns / op |
乾燥残渣中：
チケットとパッチへのリンク （おそらくJava 11で終了します）
読むべきもの：
VMプールの黒魔術に関する長く複雑で非常に役立つ記事
メモのトピックに関する元の対応： ここにあります
結論
- 苦痛に馴染みのあるクラスでさえ欠陥を隠すことができます
- 抽象コレクションは、可能な限り多くのケースをカバーし、一般化されたアルゴリズムを提供するように記述されているため、特定の実装を作成するときに、データ構造の特性に合わせてより生産的なコードを記述することができます
- 変更を行うためにOracleの従業員である必要はありません。 実証済みのエラーを排除するか、具体的な改善をもたらすパッチがある場合、検討のために受け入れられます
- プラットフォームコードをより頻繁に確認します。JavistはJDKについてあまり知りません。
PSチケットはクローズされ、変更が注がれています。