changeset 54262:02e648ae46c3

8215995: Add specialized toArray methods to immutable collections Reviewed-by: martin, smarks
author redestad
date Wed, 09 Jan 2019 01:06:19 +0100
parents 28ec06beb091
children 7d8676b2487f
files src/java.base/share/classes/java/util/ImmutableCollections.java test/micro/org/openjdk/bench/java/util/ImmutableColls.java
diffstat 2 files changed, 389 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- 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> 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<E> extends AbstractImmutableList<E>
@@ -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> 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<E> extends AbstractImmutableList<E>
@@ -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> 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> 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<E> it = iterator();
+            for (int i = 0; i < size; i++) {
+                array[i] = it.next();
+            }
+            return array;
+        }
+
+        @Override
+        @SuppressWarnings("unchecked")
+        public <T> T[] toArray(T[] a) {
+            T[] array = a.length >= size ? a :
+                    (T[])Array.newInstance(a.getClass().getComponentType(), size);
+            Iterator<E> 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<K,V> next() {
-                if (hasNext()) {
-                    while (table[nextIndex()] == null) {}
+                if (remaining > 0) {
+                    int idx;
+                    while (table[idx = nextIndex()] == null) {}
                     @SuppressWarnings("unchecked")
                     Map.Entry<K,V> e =
                             new KeyValueHolder<>((K)table[idx], (V)table[idx+1]);
--- /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<String> l0 = List.of();
+    public static List<String> l1 = List.of(Arrays.copyOf(STRINGS, 1));
+    public static List<String> l2 = List.of(Arrays.copyOf(STRINGS, 2));
+    public static List<String> l3 = List.of(Arrays.copyOf(STRINGS, 3));
+    public static List<String> l4 = List.of(Arrays.copyOf(STRINGS, 4));
+
+    public static Set<String> s0 = Set.copyOf(l0);
+    public static Set<String> s1 = Set.copyOf(l1);
+    public static Set<String> s2 = Set.copyOf(l2);
+    public static Set<String> s3 = Set.copyOf(l3);
+    public static Set<String> s4 = Set.copyOf(l4);
+
+    public static Map<String, String> m0 = Map.of();
+    public static Map<String, String> m1 = Map.of(STRINGS[0], STRINGS[0]);
+    public static Map<String, String> m2 = Map.of(STRINGS[0], STRINGS[0],
+                                                  STRINGS[1], STRINGS[1]);
+    public static Map<String, String> m3 = Map.of(STRINGS[0], STRINGS[0],
+                                                  STRINGS[1], STRINGS[1],
+                                                  STRINGS[2], STRINGS[2]);
+    public static Map<String, String> m4 = Map.of(STRINGS[0], STRINGS[0],
+                                                  STRINGS[1], STRINGS[1],
+                                                  STRINGS[2], STRINGS[2],
+                                                  STRINGS[3], STRINGS[3]);
+
+    public static List<String> a0 = new ArrayList<>(l0);
+    public static List<String> a1 = new ArrayList<>(l1);
+    public static List<String> a2 = new ArrayList<>(l2);
+    public static List<String> a3 = new ArrayList<>(l3);
+    public static List<String> a4 = new ArrayList<>(l4);
+
+    public static final List<String> fl0 = List.of();
+    public static final List<String> fl1 = List.copyOf(l1);
+    public static final List<String> fl2 = List.copyOf(l2);
+    public static final List<String> fl3 = List.copyOf(l3);
+    public static final List<String> fl4 = List.copyOf(l4);
+
+    public static final List<String> fsl0 = fl0.subList(0, 0);
+    public static final List<String> fsl1 = fl2.subList(1, 2);
+    public static final List<String> fsl2 = fl3.subList(0, 2);
+    public static final List<String> fsl3 = fl4.subList(0, 3);
+
+    public static final Set<String> fs0 = Set.copyOf(l0);
+    public static final Set<String> fs1 = Set.copyOf(l1);
+    public static final Set<String> fs2 = Set.copyOf(l2);
+    public static final Set<String> fs3 = Set.copyOf(l3);
+    public static final Set<String> fs4 = Set.copyOf(l4);
+
+    public static final Map<String, String> fm0 = Map.copyOf(m0);
+    public static final Map<String, String> fm1 = Map.copyOf(m1);
+    public static final Map<String, String> fm2 = Map.copyOf(m2);
+    public static final Map<String, String> fm3 = Map.copyOf(m3);
+    public static final Map<String, String> fm4 = Map.copyOf(m4);
+
+    public static final List<String> fa0 = new ArrayList<>(l0);
+    public static final List<String> fa1 = new ArrayList<>(l1);
+    public static final List<String> fa2 = new ArrayList<>(l2);
+    public static final List<String> fa3 = new ArrayList<>(l3);
+    public static final List<String> 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<String> list) {
+        return list.size();
+    }
+
+    public int sizeOf(List<String> 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<String> list, int idx) {
+        return list.get(idx);
+    }
+
+    public String get(List<String> list, int idx) {
+        return list.get(idx);
+    }
+
+    @Benchmark
+    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
+    public Set<String> createSetOf() {
+        return Set.of(STRINGS);
+    }
+}