8225339: Optimize HashMap.keySet()/HashMap.values()/HashSet toArray() methods
Reviewed-by: rriggs, redestad, smarks
--- a/src/java.base/share/classes/java/util/HashMap.java Thu Jun 13 16:39:20 2019 -0700
+++ b/src/java.base/share/classes/java/util/HashMap.java Fri Jun 14 05:02:58 2019 +0000
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -911,6 +911,74 @@
return ks;
}
+ /**
+ * Prepares the array for {@link Collection#toArray(Object[])} implementation.
+ * If supplied array is smaller than this map size, a new array is allocated.
+ * If supplied array is bigger than this map size, a null is written at size index.
+ *
+ * @param a an original array passed to {@code toArray()} method
+ * @param <T> type of array elements
+ * @return an array ready to be filled and returned from {@code toArray()} method.
+ */
+ @SuppressWarnings("unchecked")
+ final <T> T[] prepareArray(T[] a) {
+ int size = this.size;
+ if (a.length < size) {
+ return (T[]) java.lang.reflect.Array
+ .newInstance(a.getClass().getComponentType(), size);
+ }
+ if (a.length > size) {
+ a[size] = null;
+ }
+ return a;
+ }
+
+ /**
+ * Fills an array with this map keys and returns it. This method assumes
+ * that input array is big enough to fit all the keys. Use
+ * {@link #prepareArray(Object[])} to ensure this.
+ *
+ * @param a an array to fill
+ * @param <T> type of array elements
+ * @return supplied array
+ */
+ <T> T[] keysToArray(T[] a) {
+ Object[] r = a;
+ Node<K,V>[] tab;
+ int idx = 0;
+ if (size > 0 && (tab = table) != null) {
+ for (Node<K,V> e : tab) {
+ for (; e != null; e = e.next) {
+ r[idx++] = e.key;
+ }
+ }
+ }
+ return a;
+ }
+
+ /**
+ * Fills an array with this map values and returns it. This method assumes
+ * that input array is big enough to fit all the values. Use
+ * {@link #prepareArray(Object[])} to ensure this.
+ *
+ * @param a an array to fill
+ * @param <T> type of array elements
+ * @return supplied array
+ */
+ <T> T[] valuesToArray(T[] a) {
+ Object[] r = a;
+ Node<K,V>[] tab;
+ int idx = 0;
+ if (size > 0 && (tab = table) != null) {
+ for (Node<K,V> e : tab) {
+ for (; e != null; e = e.next) {
+ r[idx++] = e.value;
+ }
+ }
+ }
+ return a;
+ }
+
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
@@ -922,6 +990,15 @@
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
+
+ public Object[] toArray() {
+ return keysToArray(new Object[size]);
+ }
+
+ public <T> T[] toArray(T[] a) {
+ return keysToArray(prepareArray(a));
+ }
+
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
@@ -970,6 +1047,15 @@
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
+
+ public Object[] toArray() {
+ return valuesToArray(new Object[size]);
+ }
+
+ public <T> T[] toArray(T[] a) {
+ return valuesToArray(prepareArray(a));
+ }
+
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
--- a/src/java.base/share/classes/java/util/HashSet.java Thu Jun 13 16:39:20 2019 -0700
+++ b/src/java.base/share/classes/java/util/HashSet.java Fri Jun 14 05:02:58 2019 +0000
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -358,4 +358,14 @@
public Spliterator<E> spliterator() {
return new HashMap.KeySpliterator<>(map, 0, -1, 0, 0);
}
+
+ @Override
+ public Object[] toArray() {
+ return map.keysToArray(new Object[map.size()]);
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a) {
+ return map.keysToArray(map.prepareArray(a));
+ }
}
--- a/src/java.base/share/classes/java/util/LinkedHashMap.java Thu Jun 13 16:39:20 2019 -0700
+++ b/src/java.base/share/classes/java/util/LinkedHashMap.java Fri Jun 14 05:02:58 2019 +0000
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -536,6 +536,26 @@
return ks;
}
+ @Override
+ final <T> T[] keysToArray(T[] a) {
+ Object[] r = a;
+ int idx = 0;
+ for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
+ r[idx++] = e.key;
+ }
+ return a;
+ }
+
+ @Override
+ final <T> T[] valuesToArray(T[] a) {
+ Object[] r = a;
+ int idx = 0;
+ for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
+ r[idx++] = e.value;
+ }
+ return a;
+ }
+
final class LinkedKeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
@@ -551,6 +571,15 @@
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
+
+ public Object[] toArray() {
+ return keysToArray(new Object[size]);
+ }
+
+ public <T> T[] toArray(T[] a) {
+ return keysToArray(prepareArray(a));
+ }
+
public final void forEach(Consumer<? super K> action) {
if (action == null)
throw new NullPointerException();
@@ -600,6 +629,15 @@
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED);
}
+
+ public Object[] toArray() {
+ return valuesToArray(new Object[size]);
+ }
+
+ public <T> T[] toArray(T[] a) {
+ return valuesToArray(prepareArray(a));
+ }
+
public final void forEach(Consumer<? super V> action) {
if (action == null)
throw new NullPointerException();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/jdk/java/util/HashMap/ToArray.java Fri Jun 14 05:02:58 2019 +0000
@@ -0,0 +1,155 @@
+/*
+ * 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.
+ */
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.LongStream;
+
+/*
+ * @test
+ * @summary HashMap.toArray() behavior tests
+ * @author tvaleev
+ */
+public class ToArray {
+ public static void main(String[] args) {
+ checkMap(false);
+ checkMap(true);
+ checkSet(false);
+ checkSet(true);
+ }
+
+ private static <T extends Comparable<T>> void checkToArray(String message, T[] expected, Collection<T> collection,
+ boolean ignoreOrder) {
+ if (ignoreOrder) {
+ Arrays.sort(expected);
+ }
+ checkToObjectArray(message, expected, collection, ignoreOrder);
+ checkToTypedArray(message, expected, Arrays.copyOf(expected, 0), collection, ignoreOrder);
+ checkToTypedArray(message, expected, expected.clone(), collection, ignoreOrder);
+ if (expected.length > 0) {
+ T[] biggerArray = Arrays.copyOf(expected, expected.length * 2);
+ System.arraycopy(expected, 0, biggerArray, expected.length, expected.length);
+ checkToTypedArray(message, expected, biggerArray, collection, ignoreOrder);
+ }
+ }
+
+ private static <T extends Comparable<T>> void checkToTypedArray(String message, T[] expected, T[] inputArray,
+ Collection<T> collection, boolean ignoreOrder) {
+ T[] res = collection.toArray(inputArray);
+ if (expected.length <= inputArray.length && res != inputArray) {
+ throw new AssertionError(message + ": not the same array returned");
+ }
+ if (res.getClass() != expected.getClass()) {
+ throw new AssertionError(message + ": wrong class returned: " + res.getClass());
+ }
+ if (res.length < expected.length) {
+ throw new AssertionError(message + ": length is smaller than expected: " + res.length + " < " + expected.length);
+ }
+ if (ignoreOrder) {
+ Arrays.sort(res, 0, Math.min(res.length, expected.length));
+ }
+ if (inputArray.length <= expected.length) {
+ if (!Arrays.equals(res, expected)) {
+ throw new AssertionError(message + ": not equal: " + Arrays.toString(expected) + " != " +
+ Arrays.toString(res));
+ }
+ } else {
+ int mismatch = Arrays.mismatch(expected, res);
+ if (mismatch != expected.length) {
+ throw new AssertionError(message + ": mismatch at " + mismatch);
+ }
+ if (res[expected.length] != null) {
+ throw new AssertionError(message + ": no null at position " + expected.length);
+ }
+ // The tail of bigger array after expected.length position must be untouched
+ mismatch = Arrays
+ .mismatch(expected, 1, expected.length, res, expected.length + 1, res.length);
+ if (mismatch != -1) {
+ throw new AssertionError(message + ": mismatch at " + mismatch);
+ }
+ }
+ }
+
+ private static <T extends Comparable<T>> void checkToObjectArray(String message, T[] expected,
+ Collection<T> collection, boolean ignoreOrder) {
+ Object[] objects = collection.toArray();
+ if (objects.getClass() != Object[].class) {
+ throw new AssertionError(message + ": wrong class returned: " + objects.getClass());
+ }
+ if (ignoreOrder) {
+ Arrays.sort(objects);
+ }
+ int mismatch = Arrays.mismatch(expected, objects);
+ if (mismatch != -1) {
+ throw new AssertionError(message + ": mismatch at " + mismatch);
+ }
+ }
+
+ private static void checkMap(boolean ordered) {
+ Map<String, String> map = ordered ? new LinkedHashMap<>() : new HashMap<>();
+ checkToArray("Empty-keys", new String[0], map.keySet(), !ordered);
+ checkToArray("Empty-values", new String[0], map.values(), !ordered);
+
+ List<String> keys = new ArrayList<>();
+ List<String> values = new ArrayList<>();
+ for (int i = 0; i < 100; i++) {
+ keys.add(String.valueOf(i));
+ values.add(String.valueOf(i * 2));
+ map.put(String.valueOf(i), String.valueOf(i * 2));
+ checkToArray(i + "-keys", keys.toArray(new String[0]), map.keySet(), !ordered);
+ checkToArray(i + "-values", values.toArray(new String[0]), map.values(), !ordered);
+ }
+ map.clear();
+ checkToArray("Empty-keys", new String[0], map.keySet(), !ordered);
+ checkToArray("Empty-values", new String[0], map.values(), !ordered);
+ }
+
+ private static void checkSet(boolean ordered) {
+ Collection<String> set = ordered ? new LinkedHashSet<>() : new HashSet<>();
+ checkToArray("Empty", new String[0], set, !ordered);
+ set.add("foo");
+ checkToArray("One", new String[]{"foo"}, set, !ordered);
+ set.add("bar");
+ checkToArray("Two", new String[]{"foo", "bar"}, set, !ordered);
+
+ Collection<Long> longSet = ordered ? new LinkedHashSet<>() : new HashSet<>();
+ for (int x = 0; x < 100; x++) {
+ longSet.add((long) x);
+ }
+ checkToArray("100", LongStream.range(0, 100).boxed().toArray(Long[]::new), longSet, !ordered);
+ longSet.clear();
+ checkToArray("After clear", new Long[0], longSet, !ordered);
+ for (int x = 0; x < 100; x++) {
+ longSet.add(((long) x) | (((long) x) << 32));
+ }
+ checkToArray("Collisions", LongStream.range(0, 100).mapToObj(x -> x | (x << 32))
+ .toArray(Long[]::new), longSet, !ordered);
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/micro/org/openjdk/bench/java/util/HashMapToArray.java Fri Jun 14 05:02:58 2019 +0000
@@ -0,0 +1,95 @@
+/*
+ * 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.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.concurrent.TimeUnit;
+
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.NANOSECONDS)
+@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
+@Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS)
+@Fork(3)
+@State(Scope.Thread)
+public class HashMapToArray {
+
+ @Param({"0", "1", "10", "1000", "100000"})
+ public int size;
+
+ @Param({"HashMap", "LinkedHashMap"})
+ public String mapType;
+
+ private Map<Integer, Integer> map;
+
+ @Setup
+ public void setup() {
+ switch (mapType) {
+ case "HashMap":
+ map = new HashMap<>();
+ break;
+ case "LinkedHashMap":
+ map = new LinkedHashMap<>();
+ break;
+ default:
+ throw new IllegalStateException();
+ }
+ for (int i = 0; i < size; i++) {
+ map.put(i, i * i);
+ }
+ }
+
+ @Benchmark
+ public Object[] testKeySetToArray() {
+ return map.keySet().toArray();
+ }
+
+ @Benchmark
+ public Object[] testKeySetToArrayTyped() {
+ return map.keySet().toArray(new Integer[0]);
+ }
+
+ @Benchmark
+ public Object[] testValuesToArray() {
+ return map.values().toArray();
+ }
+
+ @Benchmark
+ public Object[] testValuesToArrayTyped() {
+ return map.values().toArray(new Integer[0]);
+ }
+}