Bug ID: JDK-6302620 Range checks are unnecessary in Arrays.fill() when filling an entire array

Type: Bug
Component: core-libs
Sub-Component: java.util
Affected Version: 6

Priority: P4
Status: Closed
Resolution: Fixed
OS: generic
CPU: generic

Submitted: 2005-07-27
Updated: 2011-05-18
Resolved: 2011-05-18

JDK 7
7 b17Fixed

Arrays.fill() methods that fill an entire array, e.g.,

    public static void fill(long[] a, long val) {
        fill(a, 0, a.length, val);
    }

call the from/to-index form, e.g.,

    public static void fill(long[] a, int fromIndex, int toIndex, long val) {
        rangeCheck(a.length, fromIndex, toIndex);
        for (int i=fromIndex; i<toIndex; i++)
            a[i] = val;
    }

which call rangeCheck(), vis,

    private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                       ") > toIndex(" + toIndex+")");
        if (fromIndex < 0)
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        if (toIndex > arrayLen)
            throw new ArrayIndexOutOfBoundsException(toIndex);
    }

When filling an entire array, none of the exceptions in rangeCheck can happen,
because fromIndex == 0 and toIndex == arrayLen and is always >= 0.

For these fill() methods, the call to rangeCheck can be elided.

EVALUATION Agreed. A bit of benchmarking revealed the disappointing fact that the client compiler is unable to optimize away accesses to a.length; we should do for (int i = 0, len = a.length; i < len; i++) a[i] = val; to avoid performance regressions on long arrays with the client compiler. Here's the microbenchmark: ----------------- import java.util.*; public class FillMicroBenchmark { abstract static class Job { private final String name; Job(String name) { this.name = name; } String name() { return name; } abstract void work() throws Throwable; } private static void collectAllGarbage() { try { for (int i = 0; i < 2; i++) { System.gc(); System.runFinalization(); Thread.sleep(10); } } catch (InterruptedException e) { throw new Error(e); } } /** * Runs each job for long enough that all the runtime compilers * have had plenty of time to warm up, i.e. get around to * compiling everything worth compiling. * Returns array of average times per job per run. */ private static long[] time0(Job ... jobs) throws Throwable { final long warmupNanos = 10L * 1000L * 1000L * 1000L; long[] nanoss = new long[jobs.length]; for (int i = 0; i < jobs.length; i++) { collectAllGarbage(); long t0 = System.nanoTime(); long t; int j = 0; do { jobs[i].work(); j++; } while ((t = System.nanoTime() - t0) < warmupNanos); nanoss[i] = t/j; } return nanoss; } private static void time(Job ... jobs) throws Throwable { long[] warmup = time0(jobs); // Warm up run long[] nanoss = time0(jobs); // Real timing run final String nameHeader = "Method"; int nameWidth = nameHeader.length(); for (Job job : jobs) nameWidth = Math.max(nameWidth, job.name().length()); final String millisHeader = "Millis"; int millisWidth = millisHeader.length(); for (long nanos : nanoss) millisWidth = Math.max(millisWidth, String.format("%d", nanos/(1000L * 1000L)).length()); final String ratioHeader = "Ratio"; int ratioWidth = ratioHeader.length(); String format = String.format("%%-%ds %%%dd %%.3f%%n", nameWidth, millisWidth); String headerFormat = String.format("%%-%ds %%-%ds %%-%ds%%n", nameWidth, millisWidth, ratioWidth); System.out.printf(headerFormat, "Method", "Millis", "Ratio"); // Print out absolute and relative times, calibrated against first job for (int i = 0; i < jobs.length; i++) { long millis = nanoss[i]/(1000L * 1000L); double ratio = (double)nanoss[i] / (double)nanoss[0]; System.out.printf(format, jobs[i].name(), millis, ratio); } } private static int intArg(String[] args, int i, int defaultValue) { return args.length > i ? Integer.parseInt(args[i]) : defaultValue; } public static void main(String[] args) throws Throwable { final int[] shortArray = new int[2]; final int[] longArray = new int[100]; final int iterations = intArg(args, 0, 10000); final Random rnd = new Random(); final int[] array = new int[1000]; for (int i = 0; i < array.length; i+=2) { array[i] = rnd.nextInt(); array[i+1] = array[i]; } time( new Job("short fill") { void work() { for (int i = 0; i < iterations; i++) { for (int j = 0; j < array.length; j+=2) { Arrays.fill(shortArray, array[j]); if (shortArray[0] != array[j+1]) throw new Error();}}}}, new Job("long fill") { void work() { for (int i = 0; i < iterations; i++) { for (int j = 0; j < array.length; j+=2) { Arrays.fill(longArray, array[j]); if (longArray[0] != array[j+1]) throw new Error();}}}} ); } } ----------------- $ pwd; repeat 10 for f in -server -client; do echo $f; /home/mb29450/bin/sun/mergeBench dolphin coll jr $f FillMicroBenchmark.java; done /home/mb29450/src/toy/6302620 -server Merged results for dolphin vs. coll running jr -server FillMicroBenchmark.java ==> javac -Xlint:all FillMicroBenchmark.java ==> java -server -esa -ea FillMicroBenchmark Method Millis Ratio vs. dolphin short fill 189 1.000 1.000 long fill 2397 12.632 1.000 -client Merged results for dolphin vs. coll running jr -client FillMicroBenchmark.java ==> javac -Xlint:all FillMicroBenchmark.java ==> java -client -esa -ea FillMicroBenchmark Method Millis Ratio vs. dolphin short fill 167 1.000 0.497 long fill 2940 17.516 0.934 ..... .....

14-07-2007

SUGGESTED FIX Alternatively, the common code could be placed in a private method called fill0 or uncheckedFill.

27-07-2005

SUGGESTED FIX Replace, e.g., public static void fill(long[] a, long val) { fill(a, 0, a.length, val); } with public static void fill(long[] a, long val) { for (int i=0; i<a.length; i++) a[i] = val; }

27-07-2005