[译]看JVM如何用最酷的x86指令来比较字符串
原文：How the JVM compares your strings using the craziest x86 instruction you've never heard of
译者：杰微刊兼职译者缪晨
我们之前大概都见过Java的字符串比较函数。它通过比较第一个不同的字符来比较字符串，当比较到较短字符串的末尾的时候，则改为比较长度：
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}
但是你知道其实还有第二个神秘的实现么？String.compareTo 是少数几个重要到值得特地手写一个汇编版本的方法。在我的机器上，它是这样的：
# {method} 'compare' '(Ljava/lang/String;Ljava/lang/String;)I' in 'Test'
# parm0: rsi:rsi = 'java/lang/String'
# parm1: rdx:rdx = 'java/lang/String'
# [sp+0x20] (sp of caller)
7fe3ed1159a0: mov %eax,-0x14000(%rsp)
7fe3ed1159a7: push %rbp
7fe3ed1159a8: sub $0x10,%rsp
7fe3ed1159ac: mov 0x10(%rsi),%rdi
7fe3ed1159b0: mov 0x10(%rdx),%r10
7fe3ed1159b4: mov %r10,%rsi
7fe3ed1159b7: add $0x18,%rsi
7fe3ed1159bb: mov 0x10(%r10),%edx
7fe3ed1159bf: mov 0x10(%rdi),%ecx
7fe3ed1159c2: add $0x18,%rdi
7fe3ed1159c6: mov %ecx,%eax
7fe3ed1159c8: sub %edx,%ecx
7fe3ed1159ca: push %rcx
7fe3ed1159cb: cmovle %eax,%edx
7fe3ed1159ce: test %edx,%edx
7fe3ed1159d0: je 0x00007fe3ed115a6f
7fe3ed1159d6: movzwl (%rdi),%eax
7fe3ed1159d9: movzwl (%rsi),%ecx
7fe3ed1159dc: sub %ecx,%eax
7fe3ed1159de: jne 0x00007fe3ed115a72
7fe3ed1159e4: cmp $0x1,%edx
7fe3ed1159e7: je 0x00007fe3ed115a6f
7fe3ed1159ed: cmp %rsi,%rdi
7fe3ed1159f0: je 0x00007fe3ed115a6f
7fe3ed1159f6: mov %edx,%eax
7fe3ed1159f8: and $0xfffffff8,%edx
7fe3ed1159fb: je 0x00007fe3ed115a4f
7fe3ed1159fd: lea (%rdi,%rax,2),%rdi
7fe3ed115a01: lea (%rsi,%rax,2),%rsi
7fe3ed115a05: neg %rax
7fe3ed115a08: vmovdqu (%rdi,%rax,2),%xmm0
7fe3ed115a0d: vpcmpestri $0x19,(%rsi,%rax,2),%xmm0
7fe3ed115a14: jb 0x00007fe3ed115a40
7fe3ed115a16: add $0x8,%rax
7fe3ed115a1a: sub $0x8,%rdx
7fe3ed115a1e: jne 0x00007fe3ed115a08
7fe3ed115a20: test %rax,%rax
7fe3ed115a23: je 0x00007fe3ed115a6f
7fe3ed115a25: mov $0x8,%edx
7fe3ed115a2a: mov $0x8,%eax
7fe3ed115a2f: neg %rax
7fe3ed115a32: vmovdqu (%rdi,%rax,2),%xmm0
7fe3ed115a37: vpcmpestri $0x19,(%rsi,%rax,2),%xmm0
7fe3ed115a3e: jae 0x00007fe3ed115a6f
7fe3ed115a40: add %rax,%rcx
7fe3ed115a43: movzwl (%rdi,%rcx,2),%eax
7fe3ed115a47: movzwl (%rsi,%rcx,2),%edx
7fe3ed115a4b: sub %edx,%eax
7fe3ed115a4d: jmp 0x00007fe3ed115a72
7fe3ed115a4f: mov %eax,%edx
7fe3ed115a51: lea (%rdi,%rdx,2),%rdi
7fe3ed115a55: lea (%rsi,%rdx,2),%rsi
7fe3ed115a59: dec %edx
7fe3ed115a5b: neg %rdx
7fe3ed115a5e: movzwl (%rdi,%rdx,2),%eax
7fe3ed115a62: movzwl (%rsi,%rdx,2),%ecx
7fe3ed115a66: sub %ecx,%eax
7fe3ed115a68: jne 0x00007fe3ed115a72
7fe3ed115a6a: inc %rdx
7fe3ed115a6d: jne 0x00007fe3ed115a5e
7fe3ed115a6f: pop %rax
7fe3ed115a70: jmp 0x00007fe3ed115a73
7fe3ed115a72: pop %rcx
7fe3ed115a73: add $0x10,%rsp
7fe3ed115a77: pop %rbp
7fe3ed115a78: test %eax,0x17ed6582(%rip)
7fe3ed115a7e: retq
macroAssembler_x86.cpp文件中的 MacroAssembler::string_compare 方法生成了上述代码。这个方法注释很好，可以满足你的好奇心。值得一提的是，在使用AVX2指令集（使用256位向量寄存器）的现代系统上有一个更豪华的实现版本，这里并不打算展开讨论。
PCMPESTRI是什么?
在SSE4.2指令集中有介绍， pcmpestri 是字符串比较指令集pcmpxstrx中的一员。通过一个控制字节在区分它们复杂的选项，它们足够复杂可以在x86中断体系中拥有一个自己的子集。Intel为了方便我们查看甚至提供了如下流程图：
现在已经确实加入了CISC!
控制字节的各个选项字位如下表所示：
-------0b 128-bit sources treated as 16 packed bytes.
-------1b 128-bit sources treated as 8 packed words.
------0-b Packed bytes/words are unsigned.
------1-b Packed bytes/words are signed.
----00--b Mode is equal any.
----01--b Mode is ranges.
----10--b Mode is equal each.
----11--b Mode is equal ordered.
---0----b IntRes1 is unmodified.
---1----b IntRes1 is negated (1’s complement).
--0-----b Negation of IntRes1 is for all 16 (8) bits.
--1-----b Negation of IntRes1 is masked by reg/mem validity.
-0------b Index of the least significant, set, bit is used
(regardless of corresponding input element validity).
IntRes2 is returned in least significant bits of XMM0.
-1------b Index of the most significant, set, bit is used
(regardless of corresponding input element validity).
Each bit of IntRes2 is expanded to byte/word.
0-------b This bit currently has no defined effect, should be 0.
1-------b This bit currently has no defined effect, should be 0.
1. 如果想了解更多，指令集参考手册的4.1节对这些选项有更详尽介绍。
compareTo 方法控制字节使用 0x19，这意味着对8个无符号word类型（感谢UTF-16编码！）进行 “逐个相等（equal each）” (即字符串比较) 操作得到一个负结果。这个庞大的指令需要取4个寄存器作为输入：2个字符串本身作为参数，加上他们的长度在 %rax和 %rdx 中(‘e’ 意味着精确的长度——pcmpistri和pcmpistrm指令用之代替查找结尾的null值)。结果 (即由IntRes2生成的索引) 存放在%ecx寄存器中。但即使这样还不够，此外pcmpxstrx 还会重置标志位：
CFlag – Reset if IntRes2 is equal to zero, set otherwise
ZFlag – Set if absolute-value of EDX is < 16 (8), reset otherwise
SFlag – Set if absolute-value of EAX is < 16 (8), reset otherwise
OFlag – IntRes2[0]
AFlag – Reset
PFlag – Reset
尽我们所能，先来看看主循环内容之前的一些设置：
7fe3ed1159f6: mov %edx,%eax
7fe3ed1159f8: and $0xfffffff8,%edx
7fe3ed1159fd: lea (%rdi,%rax,2),%rdi
7fe3ed115a01: lea (%rsi,%rax,2),%rsi
7fe3ed115a05: neg %rax
7fe3ed115a08: vmovdqu (%rdi,%rax,2),%xmm0
7fe3ed115a0d: vpcmpestri $0x19,(%rsi,%rax,2),%xmm0
7fe3ed115a14: jb 0x00007fe3ed115a40
7fe3ed115a16: add $0x8,%rax
7fe3ed115a1a: sub $0x8,%rdx
7fe3ed115a1e: jne 0x00007fe3ed115a08
开始， %rax% 是字符串长度的最小值，另外 %rdx 是这个最小值对~0x7 取掩码(因此是8倍的最大循环次数)。然后对字符数组(%rsi 和 %rdi)使用bump the pointer技术，然后对%rax里的值取相反数，因此主循环里使用的数组索引实际是逆向的。在将第一个字符串的8个字符载入 %xmm0寄存器中后，将其与第二个字符串的8个字符对比，如果CFlag被设置则跳出循环(这时不同字符的下标已经存储在%ecx寄存器中)，然后查看两个长度寄存器判断下这是不是最后一次循环（即查看 %rdx）。一个负数怎么作为一个有效的长度呢？对不起，差点忘了说，事实上pcmpestri 将长度理解为它的绝对值：
每个输入的长度实际都被解释为长度寄存器中的值的绝对值
在主循环之后，当较小的长度不能被8整除时检查余下的字符，然后最后的情况就是当比较到最短的长度的时候。就返回长度差。呼~~
更多类似乐趣
如果这还不能完全满足你，可以快速扫一眼indexOf 的这些实现(根据匹配字符串长短不同有两个不同实现), 控制字节使用 0x0d, “equal ordered”模式 (即子串) 匹配。
一如既往，如果你发现JVM内核的魅力让你无法自拔，来twitter粉我
更多精彩内容：
