1 /*
2 * Copyright (c) 2015, 2017, 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 find a mismatch between two primitive arrays.
32 *
33 * <p>Array equality and lexicographical comparison can be built on top of
34 * array mismatch functionality.
35 *
36 * <p>The mismatch method implementation, {@link #vectorizedMismatch}, leverages
37 * vector-based techniques to access and compare the contents of two arrays.
38 * The Java implementation uses {@code Unsafe.getLongUnaligned} to access the
39 * content of an array, thus access is supported on platforms that do not
40 * support unaligned access. For a byte[] array, 8 bytes (64 bits) can be
41 * accessed and compared as a unit rather than individually, which increases
42 * the performance when the method is compiled by the HotSpot VM. On supported
43 * platforms the mismatch implementation is intrinsified to leverage SIMD
44 * instructions. So for a byte[] array, 16 bytes (128 bits), 32 bytes
45 * (256 bits), and perhaps in the future even 64 bytes (512 bits), platform
46 * permitting, can be accessed and compared as a unit, which further increases
47 * the performance over the Java implementation.
48 *
49 * <p>None of the mismatch methods perform array bounds checks. It is the
50 * responsibility of the caller (direct or otherwise) to perform such checks
51 * before calling this method.
553 b, bOffset,
554 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
555 }
556 if (i >= 0) {
557 // Check if mismatch is not associated with two NaN values
558 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i]))
559 return i;
560
561 // Mismatch on two different NaN values that are normalized to match
562 // Fall back to slow mechanism
563 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
564 // However, requires that returned value be relative to input ranges
565 i++;
566 for (; i < length; i++) {
567 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
568 return i;
569 }
570 }
571
572 return -1;
573 }
574 }
|
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.
555 b, bOffset,
556 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
557 }
558 if (i >= 0) {
559 // Check if mismatch is not associated with two NaN values
560 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i]))
561 return i;
562
563 // Mismatch on two different NaN values that are normalized to match
564 // Fall back to slow mechanism
565 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
566 // However, requires that returned value be relative to input ranges
567 i++;
568 for (; i < length; i++) {
569 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
570 return i;
571 }
572 }
573
574 return -1;
575 }
576
577 /**
578 * The maximum length of array to allocate (unless necessary).
579 * Some VMs reserve some header words in an array.
580 * Attempts to allocate larger arrays may result in
581 * {@code OutOfMemoryError: Requested array size exceeds VM limit}
582 */
583 public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
584
585 /**
586 * Calculates a new array length given an array's current length, a preferred
587 * growth value, and a minimum growth value. If the preferred growth value
588 * is less than the minimum growth value, the minimum growth value is used in
589 * its place. If the sum of the current length and the preferred growth
590 * value does not exceed {@link #MAX_ARRAY_LENGTH}, that sum is returned.
591 * If the sum of the current length and the minimum growth value does not
592 * exceed {@code MAX_ARRAY_LENGTH}, then {@code MAX_ARRAY_LENGTH} is returned.
593 * If the sum does not overflow an int, then {@code Integer.MAX_VALUE} is
594 * returned. Otherwise, {@code OutOfMemoryError} is thrown.
595 *
596 * @param oldLength current length of the array (must be non negative)
597 * @param minGrowth minimum required growth of the array length (must be
598 * positive)
599 * @param prefGrowth preferred growth of the array length (ignored, if less
600 * then {@code minGrowth})
601 * @return the new length of the array
602 * @throws OutOfMemoryError if increasing {@code oldLength} by
603 * {@code minGrowth} overflows.
604 */
605 public static int calcLength(int oldLength, int minGrowth, int prefGrowth) {
606 // assert oldLength >= 0
607 // assert minGrowth > 0
608
609 int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
610 if (newLength - MAX_ARRAY_LENGTH <= 0) {
611 return newLength;
612 }
613 return hugeLength(oldLength, minGrowth);
614 }
615
616 private static int hugeLength(int oldLength, int minGrowth) {
617 int minLength = oldLength + minGrowth;
618 if (minLength < 0) { // overflow
619 throw new OutOfMemoryError("Required array length too large");
620 }
621 if (minLength <= MAX_ARRAY_LENGTH) {
622 return MAX_ARRAY_LENGTH;
623 }
624 return Integer.MAX_VALUE;
625 }
626 }
|