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 size 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 size 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 * OutOfMemoryError: Requested array size exceeds VM limit
582 */
583 public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
584
585 /**
586 * Calculates new size of an array to be reallocated.
587 *
588 * The result will be at least {@code X = oldCapacity + growAtLeastBy}.
589 * The result can be greater (normally, up to
590 * {@code oldCapacity + preferredGrowBy}).
591 * This function will not return values greater than
592 * {@link #MAX_ARRAY_SIZE} unless the minimum required size
593 * {@code X} is greater.
594 *
595 * @param oldCapacity current size of the array (must be non negative)
596 * @param growAtLeastBy minimum required growth of the array size (must
597 be positive)
598 * @param preferredGrowBy preferred growth of the array size
599 * @return the new size of the array
600 * @throws OutOfMemoryError if increasing {@code oldCapacity) by
601 * {@code growAtLeastBy} overflows.
602 */
603 public static int newCapacity(int oldCapacity,
604 int growAtLeastBy,
605 int preferredGrowBy) {
606 // assert oldCapacity >= 0
607 // assert growAtLeastBy > 0
608
609 int newCapacity = oldCapacity + Math.max(growAtLeastBy, preferredGrowBy);
610 return (newCapacity - MAX_ARRAY_SIZE > 0)
611 ? hugeCapacity(oldCapacity + growAtLeastBy) : newCapacity;
612 }
613
614 private static int hugeCapacity(int minCapacity) {
615 if (minCapacity < 0) { // overflow
616 throw new OutOfMemoryError("Required array size too large");
617 }
618 return (minCapacity > MAX_ARRAY_SIZE)
619 ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
620 }
621 }
|