# HG changeset patch # User psandoz # Date 1450343010 -3600 # Node ID 6f0bf592d149f59f78b650b703509bef1c2b67ad # Parent ba6a26f39b86755292784b6c65bc2ae925165c06 8136924: Vectorized support for array equals/compare/mismatch using Unsafe Reviewed-by: plevart, jrose, kvn diff -r ba6a26f39b86 -r 6f0bf592d149 jdk/src/java.base/share/classes/java/util/Arrays.java --- a/jdk/src/java.base/share/classes/java/util/Arrays.java Tue Oct 06 18:42:06 2015 +0200 +++ b/jdk/src/java.base/share/classes/java/util/Arrays.java Thu Dec 17 10:03:30 2015 +0100 @@ -110,7 +110,7 @@ * Checks that {@code fromIndex} and {@code toIndex} are in * the range and throws an exception if they aren't. */ - private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) { + static void rangeCheck(int arrayLength, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); @@ -2579,11 +2579,7 @@ if (a2.length != length) return false; - for (int i=0; i= 0) { + return Boolean.compare(a[i], b[i]); } return a.length - b.length; @@ -5880,11 +5819,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - boolean va = a[aFromIndex++]; - boolean vb = b[bFromIndex++]; - if (va != vb) return Boolean.compare(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Boolean.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -5939,9 +5878,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Byte.compare(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Byte.compare(a[i], b[i]); } return a.length - b.length; @@ -6014,11 +5954,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - byte va = a[aFromIndex++]; - byte vb = b[bFromIndex++]; - if (va != vb) return Byte.compare(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Byte.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6066,9 +6006,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Byte.compareUnsigned(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Byte.compareUnsigned(a[i], b[i]); } return a.length - b.length; @@ -6133,11 +6074,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - byte va = a[aFromIndex++]; - byte vb = b[bFromIndex++]; - if (va != vb) return Byte.compareUnsigned(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Byte.compareUnsigned(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6192,9 +6133,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Short.compare(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Short.compare(a[i], b[i]); } return a.length - b.length; @@ -6267,11 +6209,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - short va = a[aFromIndex++]; - short vb = b[bFromIndex++]; - if (va != vb) return Short.compare(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Short.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6319,9 +6261,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Short.compareUnsigned(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Short.compareUnsigned(a[i], b[i]); } return a.length - b.length; @@ -6385,11 +6328,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - short va = a[aFromIndex++]; - short vb = b[bFromIndex++]; - if (va != vb) return Short.compareUnsigned(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Short.compareUnsigned(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6444,9 +6387,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Character.compare(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Character.compare(a[i], b[i]); } return a.length - b.length; @@ -6519,11 +6463,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - char va = a[aFromIndex++]; - char vb = b[bFromIndex++]; - if (va != vb) return Character.compare(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Character.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6578,9 +6522,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Integer.compare(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Integer.compare(a[i], b[i]); } return a.length - b.length; @@ -6653,11 +6598,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - int va = a[aFromIndex++]; - int vb = b[bFromIndex++]; - if (va != vb) return Integer.compare(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Integer.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6705,9 +6650,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Integer.compareUnsigned(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Integer.compareUnsigned(a[i], b[i]); } return a.length - b.length; @@ -6771,11 +6717,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - int va = a[aFromIndex++]; - int vb = b[bFromIndex++]; - if (va != vb) return Integer.compareUnsigned(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Integer.compareUnsigned(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6830,9 +6776,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Long.compare(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Long.compare(a[i], b[i]); } return a.length - b.length; @@ -6905,11 +6852,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - long va = a[aFromIndex++]; - long vb = b[bFromIndex++]; - if (va != vb) return Long.compare(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Long.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -6957,9 +6904,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return Long.compareUnsigned(a[i], b[i]); + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Long.compareUnsigned(a[i], b[i]); } return a.length - b.length; @@ -7023,11 +6971,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - long va = a[aFromIndex++]; - long vb = b[bFromIndex++]; - if (va != vb) return Long.compareUnsigned(va, vb); + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Long.compareUnsigned(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -7082,13 +7030,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - float va = a[i], vb = b[i]; - if (Float.floatToRawIntBits(va) != Float.floatToRawIntBits(vb)) { - int c = Float.compare(va, vb); - if (c != 0) return c; - } + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Float.compare(a[i], b[i]); } return a.length - b.length; @@ -7161,13 +7106,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - float va = a[aFromIndex++], vb = b[bFromIndex++]; - if (Float.floatToRawIntBits(va) != Float.floatToRawIntBits(vb)) { - int c = Float.compare(va, vb); - if (c != 0) return c; - } + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Float.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -7222,13 +7165,10 @@ if (a == null || b == null) return a == null ? -1 : 1; - int length = Math.min(a.length, b.length); - for (int i = 0; i < length; i++) { - double va = a[i], vb = b[i]; - if (Double.doubleToRawLongBits(va) != Double.doubleToRawLongBits(vb)) { - int c = Double.compare(va, vb); - if (c != 0) return c; - } + int i = ArraysSupport.mismatch(a, b, + Math.min(a.length, b.length)); + if (i >= 0) { + return Double.compare(a[i], b[i]); } return a.length - b.length; @@ -7301,13 +7241,11 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; - int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - double va = a[aFromIndex++], vb = b[bFromIndex++]; - if (Double.doubleToRawLongBits(va) != Double.doubleToRawLongBits(vb)) { - int c = Double.compare(va, vb); - if (c != 0) return c; - } + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + Math.min(aLength, bLength)); + if (i >= 0) { + return Double.compare(a[aFromIndex + i], b[bFromIndex + i]); } return aLength - bLength; @@ -7673,11 +7611,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -7749,11 +7684,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - if (a[aFromIndex++] != b[bFromIndex++]) return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch byte @@ -7804,11 +7738,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -7880,11 +7811,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - if (a[aFromIndex++] != b[bFromIndex++]) return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch char @@ -7935,11 +7865,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -8011,11 +7938,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - if (a[aFromIndex++] != b[bFromIndex++]) return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch short @@ -8066,11 +7992,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -8142,11 +8065,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - if (a[aFromIndex++] != b[bFromIndex++]) return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch int @@ -8197,11 +8119,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -8273,11 +8192,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - if (a[aFromIndex++] != b[bFromIndex++]) return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch long @@ -8328,11 +8246,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - if (a[i] != b[i]) return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -8404,11 +8319,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - if (a[aFromIndex++] != b[bFromIndex++]) return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch float @@ -8459,14 +8373,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - float va = a[i], vb = b[i]; - if (Float.floatToRawIntBits(va) != Float.floatToRawIntBits(vb)) - if (!Float.isNaN(va) || !Float.isNaN(vb)) - return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -8538,14 +8446,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - float va = a[aFromIndex++], vb = b[bFromIndex++]; - if (Float.floatToRawIntBits(va) != Float.floatToRawIntBits(vb)) - if (!Float.isNaN(va) || !Float.isNaN(vb)) - return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch double @@ -8596,14 +8500,8 @@ if (a == b) return -1; - for (int i = 0; i < length; i++) { - double va = a[i], vb = b[i]; - if (Double.doubleToRawLongBits(va) != Double.doubleToRawLongBits(vb)) - if (!Double.isNaN(va) || !Double.isNaN(vb)) - return i; - } - - return a.length != b.length ? length : -1; + int i = ArraysSupport.mismatch(a, b, length); + return (i < 0 && a.length != b.length) ? length : i; } /** @@ -8675,14 +8573,10 @@ int aLength = aToIndex - aFromIndex; int bLength = bToIndex - bFromIndex; int length = Math.min(aLength, bLength); - for (int i = 0; i < length; i++) { - double va = a[aFromIndex++], vb = b[bFromIndex++]; - if (Double.doubleToRawLongBits(va) != Double.doubleToRawLongBits(vb)) - if (!Double.isNaN(va) || !Double.isNaN(vb)) - return i; - } - - return aLength != bLength ? length : -1; + int i = ArraysSupport.mismatch(a, aFromIndex, + b, bFromIndex, + length); + return (i < 0 && aLength != bLength) ? length : i; } // Mismatch objects diff -r ba6a26f39b86 -r 6f0bf592d149 jdk/src/java.base/share/classes/java/util/ArraysSupport.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/java.base/share/classes/java/util/ArraysSupport.java Thu Dec 17 10:03:30 2015 +0100 @@ -0,0 +1,545 @@ +/* + * Copyright (c) 2015, 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. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * 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 java.util; + +import jdk.internal.HotSpotIntrinsicCandidate; +import jdk.internal.misc.Unsafe; + +/** + * Utility methods to find a mismatch between two primitive arrays. + * + *

Array equality and lexicographical comparison can be built on top of + * array mismatch functionality. + * + *

The mismatch method implementation, {@link #vectorizedMismatch}, leverages + * vector-based techniques to access and compare the contents of two arrays. + * The Java implementation uses {@code Unsafe.getLongUnaligned} to access the + * content of an array, thus access is supported on platforms that do not + * support unaligned access. For a byte[] array, 8 bytes (64 bits) can be + * accessed and compared as a unit rather than individually, which increases + * the performance when the method is compiled by the HotSpot VM. On supported + * platforms the mismatch implementation is intrinsified to leverage SIMD + * instructions. So for a byte[] array, 16 bytes (128 bits), 32 bytes + * (256 bits), and perhaps in the future even 64 bytes (512 bits), platform + * permitting, can be accessed and compared as a unit, which further increases + * the performance over the Java implementation. + * + *

None of the mismatch methods perform array bounds checks. It is the + * responsibility of the caller (direct or otherwise) to perform such checks + * before calling this method. + */ +class ArraysSupport { + static final Unsafe U = Unsafe.getUnsafe(); + + private static final boolean BIG_ENDIAN = U.isBigEndian(); + + private static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE); + private static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE); + private static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE); + private static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE); + private static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE); + private static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE); + private static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE); + private static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE); + + private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE); + + private static int exactLog2(int scale) { + if ((scale & (scale - 1)) != 0) + throw new Error("data type scale not a power of two"); + return Integer.numberOfTrailingZeros(scale); + } + + private ArraysSupport() {} + + /** + * Find the relative index of the first mismatching pair of elements in two + * primitive arrays of the same component type. Pairs of elements will be + * tested in order relative to given offsets into both arrays. + * + *

This method does not perform type checks or bounds checks. It is the + * responsibility of the caller to perform such checks before calling this + * method. + * + *

The given offsets, in bytes, need not be aligned according to the + * given log2 size the array elements. More specifically, an + * offset modulus the size need not be zero. + * + * @param a the first array to be tested for mismatch, or {@code null} for + * direct memory access + * @param aOffset the relative offset, in bytes, from the base address of + * the first array to test from, otherwise if the first array is + * {@code null}, an absolute address pointing to the first element to test. + * @param b the second array to be tested for mismatch, or {@code null} for + * direct memory access + * @param bOffset the relative offset, in bytes, from the base address of + * the second array to test from, otherwise if the second array is + * {@code null}, an absolute address pointing to the first element to test. + * @param length the number of array elements to test + * @param log2ArrayIndexScale log2 of the array index scale, that + * corresponds to the size, in bytes, of an array element. + * @return if a mismatch is found a relative index, between 0 (inclusive) + * and {@code length} (exclusive), of the first mismatching pair of elements + * in the two arrays. Otherwise, if a mismatch is not found the bitwise + * compliment of the number of remaining pairs of elements to be checked in + * the tail of the two arrays. + */ + @HotSpotIntrinsicCandidate + static int vectorizedMismatch(Object a, long aOffset, + Object b, long bOffset, + int length, + int log2ArrayIndexScale) { + // assert a.getClass().isArray(); + // assert b.getClass().isArray(); + // assert 0 <= length <= sizeOf(a) + // assert 0 <= length <= sizeOf(b) + // assert 0 <= log2ArrayIndexScale <= 3 + + int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale; + int wi = 0; + for (; wi < length >> log2ValuesPerWidth; wi++) { + long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; + long av = U.getLongUnaligned(a, aOffset + bi); + long bv = U.getLongUnaligned(b, bOffset + bi); + if (av != bv) { + long x = av ^ bv; + int o = BIG_ENDIAN + ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) + : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); + return (wi << log2ValuesPerWidth) + o; + } + } + + // Calculate the tail of remaining elements to check + int tail = length - (wi << log2ValuesPerWidth); + + if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) { + int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale); + // Handle 4 bytes or 2 chars in the tail using int width + if (tail >= wordTail) { + long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; + int av = U.getIntUnaligned(a, aOffset + bi); + int bv = U.getIntUnaligned(b, bOffset + bi); + if (av != bv) { + int x = av ^ bv; + int o = BIG_ENDIAN + ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) + : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); + return (wi << log2ValuesPerWidth) + o; + } + tail -= wordTail; + } + return ~tail; + } + else { + return ~tail; + } + } + + // Booleans + // Each boolean element takes up one byte + + static int mismatch(boolean[] a, + boolean[] b, + int length) { + int i = 0; + if (length > 7) { + i = vectorizedMismatch( + a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, + b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, + length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[i] != b[i]) + return i; + } + return -1; + } + + static int mismatch(boolean[] a, int aFromIndex, + boolean[] b, int bFromIndex, + int length) { + int i = 0; + if (length > 7) { + int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex; + int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex; + i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[aFromIndex + i] != b[bFromIndex + i]) + return i; + } + return -1; + } + + + // Bytes + + /** + * Find the index of a mismatch between two arrays. + * + *

This method does not perform bounds checks. It is the responsibility + * of the caller to perform such bounds checks before calling this method. + * + * @param a the first array to be tested for a mismatch + * @param b the second array to be tested for a mismatch + * @param length the number of bytes from each array to check + * @return the index of a mismatch between the two arrays, otherwise -1 if + * no mismatch. The index will be within the range of (inclusive) 0 to + * (exclusive) the smaller of the two array lengths. + */ + static int mismatch(byte[] a, + byte[] b, + int length) { + // ISSUE: defer to index receiving methods if performance is good + // assert length <= a.length + // assert length <= b.length + + int i = 0; + if (length > 7) { + i = vectorizedMismatch( + a, Unsafe.ARRAY_BYTE_BASE_OFFSET, + b, Unsafe.ARRAY_BYTE_BASE_OFFSET, + length, LOG2_ARRAY_BYTE_INDEX_SCALE); + if (i >= 0) + return i; + // Align to tail + i = length - ~i; +// assert i >= 0 && i <= 7; + } + // Tail < 8 bytes + for (; i < length; i++) { + if (a[i] != b[i]) + return i; + } + return -1; + } + + /** + * Find the relative index of a mismatch between two arrays starting from + * given indexes. + * + *

This method does not perform bounds checks. It is the responsibility + * of the caller to perform such bounds checks before calling this method. + * + * @param a the first array to be tested for a mismatch + * @param aFromIndex the index of the first element (inclusive) in the first + * array to be compared + * @param b the second array to be tested for a mismatch + * @param bFromIndex the index of the first element (inclusive) in the + * second array to be compared + * @param length the number of bytes from each array to check + * @return the relative index of a mismatch between the two arrays, + * otherwise -1 if no mismatch. The index will be within the range of + * (inclusive) 0 to (exclusive) the smaller of the two array bounds. + */ + static int mismatch(byte[] a, int aFromIndex, + byte[] b, int bFromIndex, + int length) { + // assert 0 <= aFromIndex < a.length + // assert 0 <= aFromIndex + length <= a.length + // assert 0 <= bFromIndex < b.length + // assert 0 <= bFromIndex + length <= b.length + // assert length >= 0 + + int i = 0; + if (length > 7) { + int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex; + int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex; + i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_BYTE_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[aFromIndex + i] != b[bFromIndex + i]) + return i; + } + return -1; + } + + + // Chars + + static int mismatch(char[] a, + char[] b, + int length) { + int i = 0; + if (length > 3) { + i = vectorizedMismatch( + a, Unsafe.ARRAY_CHAR_BASE_OFFSET, + b, Unsafe.ARRAY_CHAR_BASE_OFFSET, + length, LOG2_ARRAY_CHAR_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[i] != b[i]) + return i; + } + return -1; + } + + static int mismatch(char[] a, int aFromIndex, + char[] b, int bFromIndex, + int length) { + int i = 0; + if (length > 3) { + int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); + int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); + i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_CHAR_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[aFromIndex + i] != b[bFromIndex + i]) + return i; + } + return -1; + } + + + // Shorts + + static int mismatch(short[] a, + short[] b, + int length) { + int i = 0; + if (length > 3) { + i = vectorizedMismatch( + a, Unsafe.ARRAY_SHORT_BASE_OFFSET, + b, Unsafe.ARRAY_SHORT_BASE_OFFSET, + length, LOG2_ARRAY_SHORT_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[i] != b[i]) + return i; + } + return -1; + } + + static int mismatch(short[] a, int aFromIndex, + short[] b, int bFromIndex, + int length) { + int i = 0; + if (length > 3) { + int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); + int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); + i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_SHORT_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[aFromIndex + i] != b[bFromIndex + i]) + return i; + } + return -1; + } + + + // Ints + + static int mismatch(int[] a, + int[] b, + int length) { + int i = 0; + if (length > 1) { + i = vectorizedMismatch( + a, Unsafe.ARRAY_INT_BASE_OFFSET, + b, Unsafe.ARRAY_INT_BASE_OFFSET, + length, LOG2_ARRAY_INT_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[i] != b[i]) + return i; + } + return -1; + } + + static int mismatch(int[] a, int aFromIndex, + int[] b, int bFromIndex, + int length) { + int i = 0; + if (length > 1) { + int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); + int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); + i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_INT_INDEX_SCALE); + if (i >= 0) + return i; + i = length - ~i; + } + for (; i < length; i++) { + if (a[aFromIndex + i] != b[bFromIndex + i]) + return i; + } + return -1; + } + + + // Floats + + static int mismatch(float[] a, + float[] b, + int length) { + return mismatch(a, 0, b, 0, length); + } + + static int mismatch(float[] a, int aFromIndex, + float[] b, int bFromIndex, + int length) { + int i = 0; + if (length > 1) { + int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); + int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); + i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_FLOAT_INDEX_SCALE); + // Mismatched + if (i >= 0) { + // Check if mismatch is not associated with two NaN values + if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i])) + return i; + + // Mismatch on two different NaN values that are normalized to match + // Fall back to slow mechanism + // ISSUE: Consider looping over vectorizedMismatch adjusting ranges + // However, requires that returned value be relative to input ranges + i++; + } + // Matched + else { + i = length - ~i; + } + } + for (; i < length; i++) { + if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i])) + return i; + } + return -1; + } + + // 64 bit sizes + + // Long + + static int mismatch(long[] a, + long[] b, + int length) { + if (length == 0) { + return -1; + } + int i = vectorizedMismatch( + a, Unsafe.ARRAY_LONG_BASE_OFFSET, + b, Unsafe.ARRAY_LONG_BASE_OFFSET, + length, LOG2_ARRAY_LONG_INDEX_SCALE); + return i >= 0 ? i : -1; + } + + static int mismatch(long[] a, int aFromIndex, + long[] b, int bFromIndex, + int length) { + if (length == 0) { + return -1; + } + int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); + int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); + int i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_LONG_INDEX_SCALE); + return i >= 0 ? i : -1; + } + + + // Double + + static int mismatch(double[] a, + double[] b, + int length) { + return mismatch(a, 0, b, 0, length); + } + + static int mismatch(double[] a, int aFromIndex, + double[] b, int bFromIndex, + int length) { + if (length == 0) { + return -1; + } + int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); + int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); + int i = vectorizedMismatch( + a, aOffset, + b, bOffset, + length, LOG2_ARRAY_DOUBLE_INDEX_SCALE); + if (i >= 0) { + // Check if mismatch is not associated with two NaN values + if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i])) + return i; + + // Mismatch on two different NaN values that are normalized to match + // Fall back to slow mechanism + // ISSUE: Consider looping over vectorizedMismatch adjusting ranges + // However, requires that returned value be relative to input ranges + i++; + for (; i < length; i++) { + if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i])) + return i; + } + } + + return -1; + } +}