1 /* 2 * Copyright (c) 2015, 2019, Oracle and/or its affiliates. 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package jdk.internal.util; 26 27 import jdk.internal.HotSpotIntrinsicCandidate; 28 import jdk.internal.misc.Unsafe; 29 30 /** 31 * Utility methods to work with arrays. This includes a set of methods 32 * to find a mismatch between two primitive arrays. Also included is 33 * a method to calculate the new length of an array to be reallocated. 34 * 35 * <p>Array equality and lexicographical comparison can be built on top of 36 * array mismatch functionality. 37 * 38 * <p>The mismatch method implementation, {@link #vectorizedMismatch}, leverages 39 * vector-based techniques to access and compare the contents of two arrays. 40 * The Java implementation uses {@code Unsafe.getLongUnaligned} to access the 41 * content of an array, thus access is supported on platforms that do not 42 * support unaligned access. For a byte[] array, 8 bytes (64 bits) can be 43 * accessed and compared as a unit rather than individually, which increases 44 * the performance when the method is compiled by the HotSpot VM. On supported 45 * platforms the mismatch implementation is intrinsified to leverage SIMD 46 * instructions. So for a byte[] array, 16 bytes (128 bits), 32 bytes 47 * (256 bits), and perhaps in the future even 64 bytes (512 bits), platform 48 * permitting, can be accessed and compared as a unit, which further increases 49 * the performance over the Java implementation. 50 * 51 * <p>None of the mismatch methods perform array bounds checks. It is the 52 * responsibility of the caller (direct or otherwise) to perform such checks 53 * before calling this method. 54 */ 55 public class ArraysSupport { 56 static final Unsafe U = Unsafe.getUnsafe(); 57 58 private static final boolean BIG_ENDIAN = U.isBigEndian(); 59 60 public static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE); 61 public static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE); 62 public static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE); 63 public static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE); 64 public static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE); 65 public static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE); 66 public static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE); 67 public static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE); 68 69 private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE); 70 exactLog2(int scale)71 private static int exactLog2(int scale) { 72 if ((scale & (scale - 1)) != 0) 73 throw new Error("data type scale not a power of two"); 74 return Integer.numberOfTrailingZeros(scale); 75 } 76 ArraysSupport()77 private ArraysSupport() {} 78 79 /** 80 * Find the relative index of the first mismatching pair of elements in two 81 * primitive arrays of the same component type. Pairs of elements will be 82 * tested in order relative to given offsets into both arrays. 83 * 84 * <p>This method does not perform type checks or bounds checks. It is the 85 * responsibility of the caller to perform such checks before calling this 86 * method. 87 * 88 * <p>The given offsets, in bytes, need not be aligned according to the 89 * given log<sub>2</sub> size the array elements. More specifically, an 90 * offset modulus the size need not be zero. 91 * 92 * @param a the first array to be tested for mismatch, or {@code null} for 93 * direct memory access 94 * @param aOffset the relative offset, in bytes, from the base address of 95 * the first array to test from, otherwise if the first array is 96 * {@code null}, an absolute address pointing to the first element to test. 97 * @param b the second array to be tested for mismatch, or {@code null} for 98 * direct memory access 99 * @param bOffset the relative offset, in bytes, from the base address of 100 * the second array to test from, otherwise if the second array is 101 * {@code null}, an absolute address pointing to the first element to test. 102 * @param length the number of array elements to test 103 * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale, that 104 * corresponds to the size, in bytes, of an array element. 105 * @return if a mismatch is found a relative index, between 0 (inclusive) 106 * and {@code length} (exclusive), of the first mismatching pair of elements 107 * in the two arrays. Otherwise, if a mismatch is not found the bitwise 108 * compliment of the number of remaining pairs of elements to be checked in 109 * the tail of the two arrays. 110 */ 111 @HotSpotIntrinsicCandidate vectorizedMismatch(Object a, long aOffset, Object b, long bOffset, int length, int log2ArrayIndexScale)112 public static int vectorizedMismatch(Object a, long aOffset, 113 Object b, long bOffset, 114 int length, 115 int log2ArrayIndexScale) { 116 // assert a.getClass().isArray(); 117 // assert b.getClass().isArray(); 118 // assert 0 <= length <= sizeOf(a) 119 // assert 0 <= length <= sizeOf(b) 120 // assert 0 <= log2ArrayIndexScale <= 3 121 122 int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale; 123 int wi = 0; 124 for (; wi < length >> log2ValuesPerWidth; wi++) { 125 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 126 long av = U.getLongUnaligned(a, aOffset + bi); 127 long bv = U.getLongUnaligned(b, bOffset + bi); 128 if (av != bv) { 129 long x = av ^ bv; 130 int o = BIG_ENDIAN 131 ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 132 : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 133 return (wi << log2ValuesPerWidth) + o; 134 } 135 } 136 137 // Calculate the tail of remaining elements to check 138 int tail = length - (wi << log2ValuesPerWidth); 139 140 if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) { 141 int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale); 142 // Handle 4 bytes or 2 chars in the tail using int width 143 if (tail >= wordTail) { 144 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 145 int av = U.getIntUnaligned(a, aOffset + bi); 146 int bv = U.getIntUnaligned(b, bOffset + bi); 147 if (av != bv) { 148 int x = av ^ bv; 149 int o = BIG_ENDIAN 150 ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 151 : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 152 return (wi << log2ValuesPerWidth) + o; 153 } 154 tail -= wordTail; 155 } 156 return ~tail; 157 } 158 else { 159 return ~tail; 160 } 161 } 162 163 /** 164 * Mismatch over long lengths. 165 */ vectorizedMismatchLargeForBytes(Object a, long aOffset, Object b, long bOffset, long length)166 public static long vectorizedMismatchLargeForBytes(Object a, long aOffset, 167 Object b, long bOffset, 168 long length) { 169 long off = 0; 170 long remaining = length; 171 int i, size; 172 boolean lastSubRange = false; 173 while (remaining > 7 && !lastSubRange) { 174 if (remaining > Integer.MAX_VALUE) { 175 size = Integer.MAX_VALUE; 176 } else { 177 size = (int) remaining; 178 lastSubRange = true; 179 } 180 i = vectorizedMismatch( 181 a, aOffset + off, 182 b, bOffset + off, 183 size, LOG2_ARRAY_BYTE_INDEX_SCALE); 184 if (i >= 0) 185 return off + i; 186 187 i = size - ~i; 188 off += i; 189 remaining -= i; 190 } 191 return ~remaining; 192 } 193 194 // Booleans 195 // Each boolean element takes up one byte 196 mismatch(boolean[] a, boolean[] b, int length)197 public static int mismatch(boolean[] a, 198 boolean[] b, 199 int length) { 200 int i = 0; 201 if (length > 7) { 202 if (a[0] != b[0]) 203 return 0; 204 i = vectorizedMismatch( 205 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 206 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 207 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 208 if (i >= 0) 209 return i; 210 i = length - ~i; 211 } 212 for (; i < length; i++) { 213 if (a[i] != b[i]) 214 return i; 215 } 216 return -1; 217 } 218 mismatch(boolean[] a, int aFromIndex, boolean[] b, int bFromIndex, int length)219 public static int mismatch(boolean[] a, int aFromIndex, 220 boolean[] b, int bFromIndex, 221 int length) { 222 int i = 0; 223 if (length > 7) { 224 if (a[aFromIndex] != b[bFromIndex]) 225 return 0; 226 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex; 227 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex; 228 i = vectorizedMismatch( 229 a, aOffset, 230 b, bOffset, 231 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 232 if (i >= 0) 233 return i; 234 i = length - ~i; 235 } 236 for (; i < length; i++) { 237 if (a[aFromIndex + i] != b[bFromIndex + i]) 238 return i; 239 } 240 return -1; 241 } 242 243 244 // Bytes 245 246 /** 247 * Find the index of a mismatch between two arrays. 248 * 249 * <p>This method does not perform bounds checks. It is the responsibility 250 * of the caller to perform such bounds checks before calling this method. 251 * 252 * @param a the first array to be tested for a mismatch 253 * @param b the second array to be tested for a mismatch 254 * @param length the number of bytes from each array to check 255 * @return the index of a mismatch between the two arrays, otherwise -1 if 256 * no mismatch. The index will be within the range of (inclusive) 0 to 257 * (exclusive) the smaller of the two array lengths. 258 */ mismatch(byte[] a, byte[] b, int length)259 public static int mismatch(byte[] a, 260 byte[] b, 261 int length) { 262 // ISSUE: defer to index receiving methods if performance is good 263 // assert length <= a.length 264 // assert length <= b.length 265 266 int i = 0; 267 if (length > 7) { 268 if (a[0] != b[0]) 269 return 0; 270 i = vectorizedMismatch( 271 a, Unsafe.ARRAY_BYTE_BASE_OFFSET, 272 b, Unsafe.ARRAY_BYTE_BASE_OFFSET, 273 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 274 if (i >= 0) 275 return i; 276 // Align to tail 277 i = length - ~i; 278 // assert i >= 0 && i <= 7; 279 } 280 // Tail < 8 bytes 281 for (; i < length; i++) { 282 if (a[i] != b[i]) 283 return i; 284 } 285 return -1; 286 } 287 288 /** 289 * Find the relative index of a mismatch between two arrays starting from 290 * given indexes. 291 * 292 * <p>This method does not perform bounds checks. It is the responsibility 293 * of the caller to perform such bounds checks before calling this method. 294 * 295 * @param a the first array to be tested for a mismatch 296 * @param aFromIndex the index of the first element (inclusive) in the first 297 * array to be compared 298 * @param b the second array to be tested for a mismatch 299 * @param bFromIndex the index of the first element (inclusive) in the 300 * second array to be compared 301 * @param length the number of bytes from each array to check 302 * @return the relative index of a mismatch between the two arrays, 303 * otherwise -1 if no mismatch. The index will be within the range of 304 * (inclusive) 0 to (exclusive) the smaller of the two array bounds. 305 */ mismatch(byte[] a, int aFromIndex, byte[] b, int bFromIndex, int length)306 public static int mismatch(byte[] a, int aFromIndex, 307 byte[] b, int bFromIndex, 308 int length) { 309 // assert 0 <= aFromIndex < a.length 310 // assert 0 <= aFromIndex + length <= a.length 311 // assert 0 <= bFromIndex < b.length 312 // assert 0 <= bFromIndex + length <= b.length 313 // assert length >= 0 314 315 int i = 0; 316 if (length > 7) { 317 if (a[aFromIndex] != b[bFromIndex]) 318 return 0; 319 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex; 320 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex; 321 i = vectorizedMismatch( 322 a, aOffset, 323 b, bOffset, 324 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 325 if (i >= 0) 326 return i; 327 i = length - ~i; 328 } 329 for (; i < length; i++) { 330 if (a[aFromIndex + i] != b[bFromIndex + i]) 331 return i; 332 } 333 return -1; 334 } 335 336 337 // Chars 338 mismatch(char[] a, char[] b, int length)339 public static int mismatch(char[] a, 340 char[] b, 341 int length) { 342 int i = 0; 343 if (length > 3) { 344 if (a[0] != b[0]) 345 return 0; 346 i = vectorizedMismatch( 347 a, Unsafe.ARRAY_CHAR_BASE_OFFSET, 348 b, Unsafe.ARRAY_CHAR_BASE_OFFSET, 349 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 350 if (i >= 0) 351 return i; 352 i = length - ~i; 353 } 354 for (; i < length; i++) { 355 if (a[i] != b[i]) 356 return i; 357 } 358 return -1; 359 } 360 mismatch(char[] a, int aFromIndex, char[] b, int bFromIndex, int length)361 public static int mismatch(char[] a, int aFromIndex, 362 char[] b, int bFromIndex, 363 int length) { 364 int i = 0; 365 if (length > 3) { 366 if (a[aFromIndex] != b[bFromIndex]) 367 return 0; 368 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 369 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 370 i = vectorizedMismatch( 371 a, aOffset, 372 b, bOffset, 373 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 374 if (i >= 0) 375 return i; 376 i = length - ~i; 377 } 378 for (; i < length; i++) { 379 if (a[aFromIndex + i] != b[bFromIndex + i]) 380 return i; 381 } 382 return -1; 383 } 384 385 386 // Shorts 387 mismatch(short[] a, short[] b, int length)388 public static int mismatch(short[] a, 389 short[] b, 390 int length) { 391 int i = 0; 392 if (length > 3) { 393 if (a[0] != b[0]) 394 return 0; 395 i = vectorizedMismatch( 396 a, Unsafe.ARRAY_SHORT_BASE_OFFSET, 397 b, Unsafe.ARRAY_SHORT_BASE_OFFSET, 398 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 399 if (i >= 0) 400 return i; 401 i = length - ~i; 402 } 403 for (; i < length; i++) { 404 if (a[i] != b[i]) 405 return i; 406 } 407 return -1; 408 } 409 mismatch(short[] a, int aFromIndex, short[] b, int bFromIndex, int length)410 public static int mismatch(short[] a, int aFromIndex, 411 short[] b, int bFromIndex, 412 int length) { 413 int i = 0; 414 if (length > 3) { 415 if (a[aFromIndex] != b[bFromIndex]) 416 return 0; 417 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 418 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 419 i = vectorizedMismatch( 420 a, aOffset, 421 b, bOffset, 422 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 423 if (i >= 0) 424 return i; 425 i = length - ~i; 426 } 427 for (; i < length; i++) { 428 if (a[aFromIndex + i] != b[bFromIndex + i]) 429 return i; 430 } 431 return -1; 432 } 433 434 435 // Ints 436 mismatch(int[] a, int[] b, int length)437 public static int mismatch(int[] a, 438 int[] b, 439 int length) { 440 int i = 0; 441 if (length > 1) { 442 if (a[0] != b[0]) 443 return 0; 444 i = vectorizedMismatch( 445 a, Unsafe.ARRAY_INT_BASE_OFFSET, 446 b, Unsafe.ARRAY_INT_BASE_OFFSET, 447 length, LOG2_ARRAY_INT_INDEX_SCALE); 448 if (i >= 0) 449 return i; 450 i = length - ~i; 451 } 452 for (; i < length; i++) { 453 if (a[i] != b[i]) 454 return i; 455 } 456 return -1; 457 } 458 mismatch(int[] a, int aFromIndex, int[] b, int bFromIndex, int length)459 public static int mismatch(int[] a, int aFromIndex, 460 int[] b, int bFromIndex, 461 int length) { 462 int i = 0; 463 if (length > 1) { 464 if (a[aFromIndex] != b[bFromIndex]) 465 return 0; 466 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 467 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 468 i = vectorizedMismatch( 469 a, aOffset, 470 b, bOffset, 471 length, LOG2_ARRAY_INT_INDEX_SCALE); 472 if (i >= 0) 473 return i; 474 i = length - ~i; 475 } 476 for (; i < length; i++) { 477 if (a[aFromIndex + i] != b[bFromIndex + i]) 478 return i; 479 } 480 return -1; 481 } 482 483 484 // Floats 485 mismatch(float[] a, float[] b, int length)486 public static int mismatch(float[] a, 487 float[] b, 488 int length) { 489 return mismatch(a, 0, b, 0, length); 490 } 491 mismatch(float[] a, int aFromIndex, float[] b, int bFromIndex, int length)492 public static int mismatch(float[] a, int aFromIndex, 493 float[] b, int bFromIndex, 494 int length) { 495 int i = 0; 496 if (length > 1) { 497 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) { 498 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 499 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 500 i = vectorizedMismatch( 501 a, aOffset, 502 b, bOffset, 503 length, LOG2_ARRAY_FLOAT_INDEX_SCALE); 504 } 505 // Mismatched 506 if (i >= 0) { 507 // Check if mismatch is not associated with two NaN values 508 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i])) 509 return i; 510 511 // Mismatch on two different NaN values that are normalized to match 512 // Fall back to slow mechanism 513 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 514 // However, requires that returned value be relative to input ranges 515 i++; 516 } 517 // Matched 518 else { 519 i = length - ~i; 520 } 521 } 522 for (; i < length; i++) { 523 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i])) 524 return i; 525 } 526 return -1; 527 } 528 529 // 64 bit sizes 530 531 // Long 532 mismatch(long[] a, long[] b, int length)533 public static int mismatch(long[] a, 534 long[] b, 535 int length) { 536 if (length == 0) { 537 return -1; 538 } 539 if (a[0] != b[0]) 540 return 0; 541 int i = vectorizedMismatch( 542 a, Unsafe.ARRAY_LONG_BASE_OFFSET, 543 b, Unsafe.ARRAY_LONG_BASE_OFFSET, 544 length, LOG2_ARRAY_LONG_INDEX_SCALE); 545 return i >= 0 ? i : -1; 546 } 547 mismatch(long[] a, int aFromIndex, long[] b, int bFromIndex, int length)548 public static int mismatch(long[] a, int aFromIndex, 549 long[] b, int bFromIndex, 550 int length) { 551 if (length == 0) { 552 return -1; 553 } 554 if (a[aFromIndex] != b[bFromIndex]) 555 return 0; 556 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 557 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 558 int i = vectorizedMismatch( 559 a, aOffset, 560 b, bOffset, 561 length, LOG2_ARRAY_LONG_INDEX_SCALE); 562 return i >= 0 ? i : -1; 563 } 564 565 566 // Double 567 mismatch(double[] a, double[] b, int length)568 public static int mismatch(double[] a, 569 double[] b, 570 int length) { 571 return mismatch(a, 0, b, 0, length); 572 } 573 mismatch(double[] a, int aFromIndex, double[] b, int bFromIndex, int length)574 public static int mismatch(double[] a, int aFromIndex, 575 double[] b, int bFromIndex, 576 int length) { 577 if (length == 0) { 578 return -1; 579 } 580 int i = 0; 581 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) { 582 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 583 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 584 i = vectorizedMismatch( 585 a, aOffset, 586 b, bOffset, 587 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE); 588 } 589 if (i >= 0) { 590 // Check if mismatch is not associated with two NaN values 591 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i])) 592 return i; 593 594 // Mismatch on two different NaN values that are normalized to match 595 // Fall back to slow mechanism 596 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 597 // However, requires that returned value be relative to input ranges 598 i++; 599 for (; i < length; i++) { 600 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i])) 601 return i; 602 } 603 } 604 605 return -1; 606 } 607 608 /** 609 * The maximum length of array to allocate (unless necessary). 610 * Some VMs reserve some header words in an array. 611 * Attempts to allocate larger arrays may result in 612 * {@code OutOfMemoryError: Requested array size exceeds VM limit} 613 */ 614 public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8; 615 616 /** 617 * Calculates a new array length given an array's current length, a preferred 618 * growth value, and a minimum growth value. If the preferred growth value 619 * is less than the minimum growth value, the minimum growth value is used in 620 * its place. If the sum of the current length and the preferred growth 621 * value does not exceed {@link #MAX_ARRAY_LENGTH}, that sum is returned. 622 * If the sum of the current length and the minimum growth value does not 623 * exceed {@code MAX_ARRAY_LENGTH}, then {@code MAX_ARRAY_LENGTH} is returned. 624 * If the sum does not overflow an int, then {@code Integer.MAX_VALUE} is 625 * returned. Otherwise, {@code OutOfMemoryError} is thrown. 626 * 627 * @param oldLength current length of the array (must be non negative) 628 * @param minGrowth minimum required growth of the array length (must be 629 * positive) 630 * @param prefGrowth preferred growth of the array length (ignored, if less 631 * then {@code minGrowth}) 632 * @return the new length of the array 633 * @throws OutOfMemoryError if increasing {@code oldLength} by 634 * {@code minGrowth} overflows. 635 */ newLength(int oldLength, int minGrowth, int prefGrowth)636 public static int newLength(int oldLength, int minGrowth, int prefGrowth) { 637 // assert oldLength >= 0 638 // assert minGrowth > 0 639 640 int newLength = Math.max(minGrowth, prefGrowth) + oldLength; 641 if (newLength - MAX_ARRAY_LENGTH <= 0) { 642 return newLength; 643 } 644 return hugeLength(oldLength, minGrowth); 645 } 646 hugeLength(int oldLength, int minGrowth)647 private static int hugeLength(int oldLength, int minGrowth) { 648 int minLength = oldLength + minGrowth; 649 if (minLength < 0) { // overflow 650 throw new OutOfMemoryError("Required array length too large"); 651 } 652 if (minLength <= MAX_ARRAY_LENGTH) { 653 return MAX_ARRAY_LENGTH; 654 } 655 return Integer.MAX_VALUE; 656 } 657 } 658