# HG changeset patch # User redestad # Date 1546992379 -3600 # Node ID 02e648ae46c35a5c4d4822fc8ced97f7159d1e18 # Parent 28ec06beb091a029b0feedb70cfef99cd4f5294d 8215995: Add specialized toArray methods to immutable collections Reviewed-by: martin, smarks diff -r 28ec06beb091 -r 02e648ae46c3 src/java.base/share/classes/java/util/ImmutableCollections.java --- a/src/java.base/share/classes/java/util/ImmutableCollections.java Tue Jan 08 13:04:04 2019 -0800 +++ b/src/java.base/share/classes/java/util/ImmutableCollections.java Wed Jan 09 01:06:19 2019 +0100 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2016, 2018, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2016, 2019, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -31,6 +31,7 @@ import java.io.ObjectOutputStream; import java.io.ObjectStreamException; import java.io.Serializable; +import java.lang.reflect.Array; import java.util.function.BiFunction; import java.util.function.Function; import java.util.function.Predicate; @@ -357,6 +358,30 @@ throw outOfBounds(index); } } + + @Override + public Object[] toArray() { + Object[] array = new Object[size]; + for (int i = 0; i < size; i++) { + array[i] = get(i); + } + return array; + } + + @Override + @SuppressWarnings("unchecked") + public T[] toArray(T[] a) { + T[] array = a.length >= size ? a : + (T[])java.lang.reflect.Array + .newInstance(a.getClass().getComponentType(), size); + for (int i = 0; i < size; i++) { + array[i] = (T)get(i); + } + if (array.length > size) { + array[size] = null; // null-terminate + } + return array; + } } static final class List12 extends AbstractImmutableList @@ -405,6 +430,30 @@ } } + @Override + public Object[] toArray() { + if (e1 == null) { + return new Object[] { e0 }; + } else { + return new Object[] { e0, e1 }; + } + } + + @Override + @SuppressWarnings("unchecked") + public T[] toArray(T[] a) { + int size = e1 == null ? 1 : 2; + T[] array = a.length >= size ? a : + (T[])Array.newInstance(a.getClass().getComponentType(), size); + array[0] = (T)e0; + if (size == 2) { + array[1] = (T)e1; + } + if (array.length > size) { + array[size] = null; // null-terminate + } + return array; + } } static final class ListN extends AbstractImmutableList @@ -456,6 +505,26 @@ private Object writeReplace() { return new CollSer(CollSer.IMM_LIST, elements); } + + @Override + public Object[] toArray() { + return Arrays.copyOf(elements, elements.length); + } + + @Override + @SuppressWarnings("unchecked") + public T[] toArray(T[] a) { + int size = elements.length; + if (a.length < size) { + // Make a new array of a's runtime type, but my contents: + return (T[]) Arrays.copyOf(elements, size, a.getClass()); + } + System.arraycopy(elements, 0, a, 0, size); + if (a.length > size) { + a[size] = null; // null-terminate + } + return a; + } } // ---------- Set Implementations ---------- @@ -565,8 +634,41 @@ return new CollSer(CollSer.IMM_SET, e0, e1); } } + + @Override + public Object[] toArray() { + if (e1 == null) { + return new Object[] { e0 }; + } else if (SALT >= 0) { + return new Object[] { e1, e0 }; + } else { + return new Object[] { e0, e1 }; + } + } + + @Override + @SuppressWarnings("unchecked") + public T[] toArray(T[] a) { + int size = e1 == null ? 1 : 2; + T[] array = a.length >= size ? a : + (T[])Array.newInstance(a.getClass().getComponentType(), size); + if (size == 1) { + array[0] = (T)e0; + } else if (SALT >= 0) { + array[0] = (T)e1; + array[1] = (T)e0; + } else { + array[0] = (T)e0; + array[1] = (T)e1; + } + if (array.length > size) { + array[size] = null; // null-terminate + } + return array; + } } + /** * An array-based Set implementation. The element array must be strictly * larger than the size (the number of contained elements) so that at @@ -653,7 +755,7 @@ @Override public E next() { - if (hasNext()) { + if (remaining > 0) { E element; // skip null elements while ((element = elements[nextIndex()]) == null) {} @@ -713,6 +815,31 @@ } return new CollSer(CollSer.IMM_SET, array); } + + @Override + public Object[] toArray() { + Object[] array = new Object[size]; + Iterator it = iterator(); + for (int i = 0; i < size; i++) { + array[i] = it.next(); + } + return array; + } + + @Override + @SuppressWarnings("unchecked") + public T[] toArray(T[] a) { + T[] array = a.length >= size ? a : + (T[])Array.newInstance(a.getClass().getComponentType(), size); + Iterator it = iterator(); + for (int i = 0; i < size; i++) { + array[i] = (T)it.next(); + } + if (array.length > size) { + array[size] = null; // null-terminate + } + return array; + } } // ---------- Map Implementations ---------- @@ -915,8 +1042,9 @@ @Override public Map.Entry next() { - if (hasNext()) { - while (table[nextIndex()] == null) {} + if (remaining > 0) { + int idx; + while (table[idx = nextIndex()] == null) {} @SuppressWarnings("unchecked") Map.Entry e = new KeyValueHolder<>((K)table[idx], (V)table[idx+1]); diff -r 28ec06beb091 -r 02e648ae46c3 test/micro/org/openjdk/bench/java/util/ImmutableColls.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/micro/org/openjdk/bench/java/util/ImmutableColls.java Wed Jan 09 01:06:19 2019 +0100 @@ -0,0 +1,257 @@ +/* + * Copyright (c) 2019 Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package org.openjdk.bench.java.util; + +import org.openjdk.jmh.annotations.*; +import org.openjdk.jmh.infra.Blackhole; + +import java.util.*; +import java.util.concurrent.TimeUnit; + +/** + * Micros for the various collections implemented in + * java.util.ImmutableCollections + */ +@State(Scope.Benchmark) +@OutputTimeUnit(TimeUnit.MICROSECONDS) +public class ImmutableColls { + + public static String[] STRINGS = {"hi", "all", "of", "you"}; + + public static List l0 = List.of(); + public static List l1 = List.of(Arrays.copyOf(STRINGS, 1)); + public static List l2 = List.of(Arrays.copyOf(STRINGS, 2)); + public static List l3 = List.of(Arrays.copyOf(STRINGS, 3)); + public static List l4 = List.of(Arrays.copyOf(STRINGS, 4)); + + public static Set s0 = Set.copyOf(l0); + public static Set s1 = Set.copyOf(l1); + public static Set s2 = Set.copyOf(l2); + public static Set s3 = Set.copyOf(l3); + public static Set s4 = Set.copyOf(l4); + + public static Map m0 = Map.of(); + public static Map m1 = Map.of(STRINGS[0], STRINGS[0]); + public static Map m2 = Map.of(STRINGS[0], STRINGS[0], + STRINGS[1], STRINGS[1]); + public static Map m3 = Map.of(STRINGS[0], STRINGS[0], + STRINGS[1], STRINGS[1], + STRINGS[2], STRINGS[2]); + public static Map m4 = Map.of(STRINGS[0], STRINGS[0], + STRINGS[1], STRINGS[1], + STRINGS[2], STRINGS[2], + STRINGS[3], STRINGS[3]); + + public static List a0 = new ArrayList<>(l0); + public static List a1 = new ArrayList<>(l1); + public static List a2 = new ArrayList<>(l2); + public static List a3 = new ArrayList<>(l3); + public static List a4 = new ArrayList<>(l4); + + public static final List fl0 = List.of(); + public static final List fl1 = List.copyOf(l1); + public static final List fl2 = List.copyOf(l2); + public static final List fl3 = List.copyOf(l3); + public static final List fl4 = List.copyOf(l4); + + public static final List fsl0 = fl0.subList(0, 0); + public static final List fsl1 = fl2.subList(1, 2); + public static final List fsl2 = fl3.subList(0, 2); + public static final List fsl3 = fl4.subList(0, 3); + + public static final Set fs0 = Set.copyOf(l0); + public static final Set fs1 = Set.copyOf(l1); + public static final Set fs2 = Set.copyOf(l2); + public static final Set fs3 = Set.copyOf(l3); + public static final Set fs4 = Set.copyOf(l4); + + public static final Map fm0 = Map.copyOf(m0); + public static final Map fm1 = Map.copyOf(m1); + public static final Map fm2 = Map.copyOf(m2); + public static final Map fm3 = Map.copyOf(m3); + public static final Map fm4 = Map.copyOf(m4); + + public static final List fa0 = new ArrayList<>(l0); + public static final List fa1 = new ArrayList<>(l1); + public static final List fa2 = new ArrayList<>(l2); + public static final List fa3 = new ArrayList<>(l3); + public static final List fa4 = new ArrayList<>(l4); + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int sumSizesList() { + return sizeOf(l0) + + sizeOf(l1) + + sizeOf(l2) + + sizeOf(l3) + + sizeOf(l4); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int finalSumSizesList() { + return sizeOf(fl0) + + sizeOf(fl1) + + sizeOf(fl2) + + sizeOf(fl3) + + sizeOf(fl4); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int sumSizesArrayList() { + return sizeOf2(a0) + + sizeOf2(a1) + + sizeOf2(a2) + + sizeOf2(a3) + + sizeOf2(a4); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int finalSumSizesArrayList() { + return sizeOf2(fa0) + + sizeOf2(fa1) + + sizeOf2(fa2) + + sizeOf2(fa3) + + sizeOf2(fa4); + } + + public int sizeOf2(List list) { + return list.size(); + } + + public int sizeOf(List list) { + return list.size(); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int getFromList() { + return get(l1, 0).length() + + get(l2, 1).length() + + get(l3, 2).length() + + get(l4, 3).length(); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int finalGetFromList() { + return get(fl1, 0).length() + + get(fl2, 1).length() + + get(fl3, 2).length() + + get(fl4, 3).length(); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void toArrayFromSet(Blackhole bh) { + bh.consume(fs4.toArray()); + bh.consume(s1.toArray()); + bh.consume(s3.toArray()); + bh.consume(fs2.toArray()); + bh.consume(s0.toArray()); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void toArrayFromMap(Blackhole bh) { + bh.consume(fm4.entrySet().toArray()); + bh.consume(m1.entrySet().toArray()); + bh.consume(m3.entrySet().toArray()); + bh.consume(fm2.entrySet().toArray()); + bh.consume(m0.entrySet().toArray()); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void toArrayFromList(Blackhole bh) { + bh.consume(fl4.toArray()); + bh.consume(fl1.toArray()); + bh.consume(l3.toArray()); + bh.consume(l0.toArray()); + bh.consume(fsl3.toArray()); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void toTypedArrayFromSet(Blackhole bh) { + bh.consume(fs4.toArray(new String[0])); + bh.consume(s1.toArray(new String[0])); + bh.consume(s3.toArray(new String[0])); + bh.consume(fs2.toArray(new String[0])); + bh.consume(s0.toArray(new String[0])); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void toTypedArrayFromMap(Blackhole bh) { + bh.consume(fm4.entrySet().toArray(new Map.Entry[0])); + bh.consume(m1.entrySet().toArray(new Map.Entry[0])); + bh.consume(m3.entrySet().toArray(new Map.Entry[0])); + bh.consume(fm2.entrySet().toArray(new Map.Entry[0])); + bh.consume(m0.entrySet().toArray(new Map.Entry[0])); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void toTypedArrayFromList(Blackhole bh) { + bh.consume(fl4.toArray(new String[0])); + bh.consume(fl1.toArray(new String[0])); + bh.consume(l3.toArray(new String[0])); + bh.consume(l0.toArray(new String[0])); + bh.consume(fsl3.toArray(new String[0])); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public void copyOfLists(Blackhole bh) { + bh.consume(List.copyOf(fl1)); + bh.consume(List.copyOf(fl4)); + bh.consume(List.copyOf(fsl2)); + bh.consume(List.copyOf(fsl3)); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public int finalGetFromArrayList() { + return get2(fa1, 0).length() + + get2(fa2, 1).length() + + get2(fa3, 2).length() + + get2(fa4, 3).length(); + } + + public String get2(List list, int idx) { + return list.get(idx); + } + + public String get(List list, int idx) { + return list.get(idx); + } + + @Benchmark + @CompilerControl(CompilerControl.Mode.DONT_INLINE) + public Set createSetOf() { + return Set.of(STRINGS); + } +}