Array equality, comparison and mismatch
Peter Levart
peter.levart at gmail.com
Wed Sep 23 08:09:02 UTC 2015
Hi Paul,
Just some thoughts about nulls...
Simple compare and compareUnsigned methods (without ranges) accept null
arrays. They specify that indirectly by stating that they are consistent
with equals methods that do the same. The equals methods specify that
two null array references are equal and by equal being an equivalence
relation it follows that a null array reference is not equal to non-null
reference (unless all arrays were equal), but compare[Unsigned] methods
do not specify the ordering of null to non-null array reference. The
implementation does order null array reference before any non-null
reference.
With compare methods taking Object[] arrays there is another level of
nullness to consider - the elements. The Arrays boolean equals(Object[]
a, Object[] b) method uses the semantics of Objects.equals for comparing
elements, therefore it allows null elements. So does Arrays <T extends
Comparable<? super T>> int compare(T[] a, T[] b), which considers null
element as the lowest value. This seems ok although in TreeMap, for
example, null keys are not allowed if Comparator is not specified, but
for consistency with Arrays.equals this is a desired property. But
Arrays <T> int compare(T[] a, T[] b, Comparator<? super T> cmp) does the
same - it treats null elements as the lowest value. This is not
consistent with TreeMap, for example, where all decisions on ordering
are delegated to Comparator which can order null elements (or reject
them) as it pleases.
Regards, Peter
On 09/22/2015 06:30 PM, Paul Sandoz wrote:
> Hi,
>
> Please review the following which adds methods to Arrays for performing equality, comparison and mismatch:
>
> https://bugs.openjdk.java.net/browse/JDK-8033148
> http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8033148-Arrays-lexico-compare/webrev/
> http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8033148-Arrays-lexico-compare/specdiff/overview-summary.html
>
> The motivation behind this is the use of Unsafe in popular libraries and frameworks to speed up the lexicographical comparison of byte arrays.
>
> This issue focuses on the API and functional implementations. A follow up issue [1] tracks updating the implementations to use a common method that leverages Unsafe to improve performance. A further issue [2] tracks the intrinsification of that common method to support operating on > 64 bits in width and further improve performance. A further issue, yet to be created, will follow up on updating existing JDK code to use the public and/or internal methods where appropriate. Example candidates include String (compareTo, perhaps add a mismatch method and possibly reviewing existing intrinsics, including those for compact Strings), and managed and direct Buffers.
>
> So far i have only documented the new methods operating on byte[], as that will act as the template for the other methods.
>
> Some points:
>
> - Methods operating on Object[] will compare Object elements using Object.equals or associated comparators (as is the case for the existing equals method operating on Object[]).
>
> - Methods operating on float[] or double[] will check such array elements for equality using the IEEE bit layout (as is the case for the existing equals method operating on float[] or double[]).
>
> - Primitive array element comparison will be performed as if by the boxed primitive type’s compare or compareUnsigned method.
>
> - Range-accepting methods do not support null array values.
>
> - Non-range and range-accepting mismatch methods do not support null array values. (What value should be returned when a mismatch is performed on a null array and an empty array)?
>
> - Speculation: it may be possible that Project Valhalla will enable us to “compress” down methods of certain groups to one “template” method. Even if that is not possible i am not overly concerned about the number of methods added, which represents the maximum set. We could reduce them without a fundamental loss of functionality, but that might have a “semantic” loss requiring developers to roll their own wrappers.
>
> Thanks,
> Paul.
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8136924
> http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8136924-arrays-mismatch-vectorized-unsafe/webrev/
>
> [2] https://bugs.openjdk.java.net/browse/JDK-8044082
>
More information about the core-libs-dev
mailing list