1 /*
   2  * Copyright 2019 Google Inc.  All Rights Reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.openjdk.bench.java.lang;
  24 
  25 import org.openjdk.jmh.annotations.Benchmark;
  26 import org.openjdk.jmh.annotations.BenchmarkMode;
  27 import org.openjdk.jmh.annotations.Mode;
  28 import org.openjdk.jmh.annotations.OutputTimeUnit;
  29 import org.openjdk.jmh.annotations.Param;
  30 import org.openjdk.jmh.annotations.Scope;
  31 import org.openjdk.jmh.annotations.Setup;
  32 import org.openjdk.jmh.annotations.State;
  33 
  34 import java.util.Arrays;
  35 import java.util.concurrent.ThreadLocalRandom;
  36 import java.util.concurrent.TimeUnit;
  37 
  38 /**
  39  * Explores the cost of copying the contents of one array to another, as is
  40  * commonly seen in collection classes that need to resize their backing
  41  * array, like ArrayList.
  42  *
  43  * We have multiple variations on copying, and we explore the cost of
  44  * clearing the old array, which might help for generational GCs.
  45  *
  46  * Benchmarks the operations in the ancient
  47  * JDK-6428387: array clone() much slower than Arrays.copyOf
  48  *
  49  * 2019 results on x86:
  50  *
  51  * The "simple" benchmarks below have the same performance, except that
  52  * simple_copyLoop is surprisingly 5x slower.  The array copying intrinsics
  53  * are very effective and a naive loop does not get optimized the same way.
  54  * OTOH there is no intrinsic for Arrays.fill but the naive array zeroing loop
  55  * *does* get optimized to something a little faster than than arraycopy.
  56  *
  57  * System.arraycopy and Arrays.fill have such outstanding performance that
  58  * one should use them to replace handwritten loops whenever possible.
  59  *
  60  * This benchmark is great for measuring cache effects, e.g. size=10^6 has 5x
  61  * the per-element cost of size=10^3 (See "The Myth of RAM".)
  62  *
  63  * (cd $(hg root) && for size in 3 16 999 999999; do make test TEST="micro:java.lang.ArrayFiddle" MICRO="FORK=2;WARMUP_ITER=4;ITER=4;OPTIONS=-opi $size -p size=$size" |& perl -ne 'print if /^Benchmark/ .. /^Finished running test/'; done)
  64  */
  65 @BenchmarkMode(Mode.AverageTime)
  66 @OutputTimeUnit(TimeUnit.NANOSECONDS)
  67 @State(Scope.Benchmark)
  68 public class ArrayFiddle {
  69     @Param("999")
  70     public int size;
  71 
  72     public int largerSize;
  73     public Object[] data;
  74     public Object[] copy;
  75 
  76     @Setup
  77     public void setup() {
  78         largerSize = size + (size >> 1);
  79 
  80         data = new Object[size];
  81         ThreadLocalRandom rnd = ThreadLocalRandom.current();
  82         for (int i = data.length; i--> 0; )
  83             data[i] = rnd.nextInt(256);
  84 
  85         copy = data.clone();
  86     }
  87 
  88     // --- "simple" benchmarks just make an array clone
  89 
  90     @Benchmark
  91     public Object[] simple_clone() {
  92         return data.clone();
  93     }
  94 
  95     @Benchmark
  96     public Object[] simple_copyOf() {
  97         return Arrays.copyOf(data, data.length);
  98     }
  99 
 100     @Benchmark
 101     public Object[] simple_arraycopy() {
 102         Object[] out = new Object[data.length];
 103         System.arraycopy(data, 0, out, 0, data.length);
 104         return out;
 105     }
 106 
 107     @Benchmark
 108     public Object[] simple_copyLoop() {
 109         final Object[] data = this.data;
 110         int len = data.length;
 111         Object[] out = new Object[len];
 112         for (int i = 0; i < len; i++)
 113             out[i] = data[i];
 114         return out;
 115     }
 116 
 117     // --- "grow" benchmarks have an output array that is larger
 118 
 119     private Object[] input_array() {
 120         System.arraycopy(data, 0, copy, 0, size);
 121         return copy;
 122     }
 123 
 124     @Benchmark
 125     public Object[] grow_copyLoop() {
 126         Object[] in = input_array();
 127         Object[] out = new Object[largerSize];
 128         for (int i = 0, len = in.length; i < len; i++)
 129             out[i] = in[i];
 130         return out;
 131     }
 132 
 133     @Benchmark
 134     public Object[] grow_copyZeroLoop() {
 135         Object[] in = input_array();
 136         Object[] out = new Object[largerSize];
 137         for (int i = 0, len = in.length; i < len; i++) {
 138             out[i] = in[i];
 139             in[i] = null;
 140         }
 141         return out;
 142     }
 143 
 144     @Benchmark
 145     public Object[] grow_arraycopy() {
 146         Object[] in = input_array();
 147         Object[] out = new Object[largerSize];
 148         System.arraycopy(in, 0, out, 0, size);
 149         return out;
 150     }
 151 
 152     @Benchmark
 153     public Object[] grow_arraycopy_fill() {
 154         Object[] in = input_array();
 155         Object[] out = new Object[largerSize];
 156         System.arraycopy(in, 0, out, 0, size);
 157         Arrays.fill(in, null);
 158         return out;
 159     }
 160 
 161     @Benchmark
 162     public Object[] grow_arraycopy_zeroLoop() {
 163         Object[] in = input_array();
 164         Object[] out = new Object[largerSize];
 165         System.arraycopy(in, 0, out, 0, size);
 166         for (int i = 0, len = in.length; i < len; i++)
 167             in[i] = null;
 168         return out;
 169     }
 170 
 171     @Benchmark
 172     public Object[] grow_copyOf() {
 173         Object[] in = input_array();
 174         Object[] out = Arrays.copyOf(in, largerSize);
 175         return out;
 176     }
 177 
 178     @Benchmark
 179     public Object[] grow_copyOf_fill() {
 180         Object[] in = input_array();
 181         Object[] out = Arrays.copyOf(in, largerSize);
 182         Arrays.fill(in, null);
 183         return out;
 184     }
 185 
 186     @Benchmark
 187     public Object[] grow_copyOf_zeroLoop() {
 188         Object[] in = input_array();
 189         Object[] out = Arrays.copyOf(in, largerSize);
 190         for (int i = 0, len = in.length; i < len; i++)
 191             in[i] = null;
 192         return out;
 193     }
 194 
 195 }