博客發(fā)表于：Ghamster Blog
轉(zhuǎn)載請(qǐng)注明出處
概述
-
Arrays類是Java中用于數(shù)組操作的工具類，實(shí)現(xiàn)了比較臂港、復(fù)制森枪、查找和排序等常用操作 -
equals方法用于判斷數(shù)組是否相等视搏，包含了各種基本類型和Object類型的重載版本，對(duì)于Object[]會(huì)判斷對(duì)象非空疲恢，并調(diào)用Object.equals判斷對(duì)象是否相等 -
ArraysSupport類是jdk11（似乎是在jdk9引入）的工具類凶朗，提供了mismatch方法和vectorizedMismatch。mismatch方法可以返回兩個(gè)被判定的數(shù)組對(duì)象中显拳，首個(gè)不相等元素的下標(biāo) -
jdk11中使用mismatch方法修改了equals方法的實(shí)現(xiàn)邏輯
Arrays類的equals方法實(shí)現(xiàn)
jdk8中棚愤，數(shù)組判等的邏輯是：遍歷數(shù)組中的元素，依次對(duì)每個(gè)元素判等
以int[]為例杂数，源碼如下：
public static boolean equals(int[] a, int[] a2) {
if (a==a2)
return true;
if (a==null || a2==null)
return false;
int length = a.length;
if (a2.length != length)
return false;
for (int i=0; i<length; i++)
if (a[i] != a2[i])
return false;
return true;
}
jdk11中宛畦，修改了所有用于基本數(shù)據(jù)類型的數(shù)組的equals方法，使用mismatch方法實(shí)現(xiàn)
以int[]為例揍移，源碼如下：
public static boolean equals(int[] a, int[] a2) {
if (a==a2)
return true;
if (a==null || a2==null)
return false;
int length = a.length;
if (a2.length != length)
return false;
return ArraysSupport.mismatch(a, a2, length) < 0;
}
mismatch和vectorizedMismatch
為了探究jdk11中equals的魔法次和，必須看看mismatch方法到底做了什么。mismatch方法也擁有各種基本數(shù)據(jù)類型數(shù)組的重載版本那伐，以int[]版本為例
mismatch方法
mismatch方法返回給定的兩個(gè)數(shù)組中踏施，首個(gè)不相同元素的下標(biāo)，當(dāng)完全匹配（0到length-1）時(shí)罕邀，返回-1畅形，源碼如下：
public static int mismatch(int[] a,
int[] b,
int length) {
int i = 0;
if (length > 1) {
if (a[0] != b[0])
return 0;
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;
}
方法主要可以分為兩個(gè)部分：
- 調(diào)用
vectorizedMismatch方法，對(duì)兩個(gè)數(shù)組對(duì)象匹配诉探，若方法返回正值日熬，則表示找到了未匹配的元素，返回值為該元素在數(shù)組中的索引肾胯；若方法返回負(fù)值竖席，則表示未找到不相等元素，但需要注意的是敬肚，vectorizedMismatch方法可能沒有處理完數(shù)組中的所有元素毕荐，對(duì)返回值取反，得到還需處理的數(shù)組元素個(gè)數(shù) - 對(duì)
vectorizedMismatch返回值取反艳馒，對(duì)剩余元素逐個(gè)驗(yàn)證
vectorizedMismatch
該方法標(biāo)注了 @HotSpotIntrinsicCandidate 注解东跪，即jvm可以有自己的優(yōu)化實(shí)現(xiàn)方式，所以...懂吧...?
該方法的核心思想是以long數(shù)據(jù)格式對(duì)比對(duì)象（不一定是數(shù)組）中的數(shù)據(jù)鹰溜，即每次循環(huán)處理數(shù)據(jù)長(zhǎng)度為8個(gè)字節(jié)，而不考慮對(duì)象是long[]還是int[]或short[]等丁恭。方法的源碼如下：
@HotSpotIntrinsicCandidate
public 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;
}
}
首先簡(jiǎn)單看一下方法的入?yún)ⅲ?/p>
-
Object a,Object b：需要對(duì)比的對(duì)象 -
long aOffset,long bOffset：起始Offset曹动，即從對(duì)象的第幾個(gè)字節(jié)開始對(duì)比。比如本例中牲览，被mismatch方法調(diào)用時(shí)墓陈，傳入的參數(shù)為Unsafe.ARRAY_INT_BASE_OFFSET，通過debug發(fā)現(xiàn)在當(dāng)前平臺(tái)上該值為16，因?yàn)閺牡?6字節(jié)開始贡必，才是數(shù)組中的數(shù)據(jù)（0-15字節(jié)存儲(chǔ)的應(yīng)該是數(shù)組的length等信息） -
length：需要對(duì)比的長(zhǎng)度兔港。該方法并不提供數(shù)組下標(biāo)越界檢查，因此length必須是合理的數(shù)值 -
log2ArrayIndexScale：數(shù)組下標(biāo)縮放仔拟，與length共同確定需要對(duì)比的字節(jié)長(zhǎng)度衫樊。以int[]為例，int型數(shù)據(jù)占4個(gè)字節(jié)利花，即1<<2科侈，所以log2ArrayIndexScale為2，方法需要處理的字節(jié)長(zhǎng)度為length*(1<<2)=4*length
方法操作邏輯如下(逐行炒事；接上節(jié)臀栈，以int[]為例)：
- 12行：
log2ValuesPerWidth可以理解為相對(duì)縮放。LOG2_ARRAY_LONG_INDEX_SCALE長(zhǎng)整型數(shù)組下標(biāo)縮放為3挠乳，即長(zhǎng)8字節(jié)权薯；int[]縮放為2，即長(zhǎng)4字節(jié)睡扬；所以相對(duì)縮放為1 - 13行：
wi盟蚣，將對(duì)象視為long[]遍歷時(shí)，當(dāng)前數(shù)組下標(biāo) - 14行：
for循環(huán)威蕉，每次wi++刁俭，即每次循環(huán)步進(jìn)8個(gè)字節(jié)。length為數(shù)組包含的int數(shù)據(jù)個(gè)數(shù)韧涨，將素組視為long時(shí)牍戚，循環(huán)length>>log2ArrayIndexScale即可遍歷數(shù)組 - 15行：
bi數(shù)組下標(biāo)為wi的元素在long數(shù)組中的相對(duì)位置（字節(jié)） - 16-17行： 調(diào)用
UnSafe.getLongUnaligned方法，讀取一個(gè)long值。
在Java中业岁，數(shù)據(jù)是對(duì)齊存放的岁诉，即long類型的數(shù)據(jù)存放時(shí)，起始地址只能是8的整數(shù)倍第晰，int類型數(shù)據(jù)存放的起始地址只能是4的整數(shù)倍……
而getLongUnaligned方法顧名思義，可以讀取非對(duì)齊存放的數(shù)據(jù)彬祖。該方法接收一個(gè)Object對(duì)象和一個(gè)long類型的offset：若offset為8的整數(shù)倍茁瘦，即(offset & 7) == 0,則直接調(diào)用getLong返回長(zhǎng)整型數(shù)據(jù)；若offset為4的整數(shù)倍储笑，則直接分別對(duì)offset和offset+4調(diào)用getInt返回兩個(gè)整型數(shù)據(jù)甜熔，然后通過<<4和&操作，將兩個(gè)int型數(shù)據(jù)合并成一個(gè)long突倍；若offset為2的整數(shù)倍…… - 18-24行： 判定兩個(gè)數(shù)組的值
av==bv是否成立腔稀，相同則繼續(xù)下一次循環(huán)盆昙；不同是使用^按位與或，并根據(jù)系統(tǒng)采用大端存儲(chǔ)還是小端存儲(chǔ)決定從頭(numberOfLeadingZeros)還是尾(numberOfTrailingZeros)找到第一個(gè)不匹配的位焊虏。然后根據(jù)log2ArrayIndexScale的值淡喜，還原這個(gè)位在原數(shù)組int[]中對(duì)應(yīng)的索引。LOG2_BYTE_BIT_SIZE值為3诵闭，表示一個(gè)字節(jié)共8位 - 27-50行： 用于處理數(shù)組類型為
byte[]和char[]炼团，且剩余未處理長(zhǎng)度大于4字節(jié)（一個(gè)int）的情況，原理與前面類似涂圆。
tail表示剩余未處理的元素個(gè)數(shù)们镜，由于UnSafe.getIntUnaligned只能一次處理4個(gè)字節(jié)，因此可能剩余1-3個(gè)byte或1個(gè)char
性能測(cè)試
下面通過簡(jiǎn)單代碼測(cè)試一下相對(duì)于jdk8润歉，jdk11是否有性能的提升模狭，測(cè)試代碼如下：
package main.test;
import java.util.Arrays;
import java.util.Random;
public class TestLegacyArrays {
private static Random r = new Random();
private static class LegacyArrays {
private LegacyArrays() {}
public static boolean equals(int[] a, int[] a2) {
if (a==a2)
return true;
if (a==null || a2==null)
return false;
int length = a.length;
if (a2.length != length)
return false;
for (int i=0; i<length; i++)
if (a[i] != a2[i])
return false;
return true;
}
}
private static void test(int size, int fill){
int[] a = new int[size];
Arrays.fill(a, fill);
int[] b = new int[size];
Arrays.fill(b, fill);
boolean isEqual;
long now, finish;
System.out.println("=> TestLegacyArrays: array size "+size);
now = System.nanoTime();
isEqual = LegacyArrays.equals(a,b);
finish = System.nanoTime();
System.out.println(" LegacyArrays: "+isEqual+" time: "+(finish-now));
now = System.nanoTime();
isEqual = Arrays.equals(a,b);
finish = System.nanoTime();
System.out.println(" Arrays: "+isEqual+" time: "+(finish-now));
System.out.println();
}
public static void main(String[] args) {
test(10, r.nextInt());
test(100, r.nextInt());
test(1000, r.nextInt());
test(10000, r.nextInt());
test(100000, r.nextInt());
}
}
代碼輸出如下：
=> TestLegacyArrays: array size 10
LegacyArrays: true time: 373700
Arrays: true time: 193700
=> TestLegacyArrays: array size 100
LegacyArrays: true time: 2000
Arrays: true time: 10200
=> TestLegacyArrays: array size 1000
LegacyArrays: true time: 15400
Arrays: true time: 186500
=> TestLegacyArrays: array size 10000
LegacyArrays: true time: 148900
Arrays: true time: 286800
=> TestLegacyArrays: array size 100000
LegacyArrays: true time: 1233700
Arrays: true time: 2424000
Process finished with exit code 0
emmmmmmmmmmmmmmm...................
所以這次的更新，或許是出于流式計(jì)算或者多線程或者其他因素的考量踩衩，又或者我的測(cè)試方法有問題嚼鹉？。驱富。锚赤。
