欢迎光临外链建设网站快速建站提升流量与权重!

外链建设

外链建设网站,帮助您快速打造排名!

[译]看JVM如何用最酷的x86指令来比较字符串

作者:jcmp      发布时间:2021-04-15      浏览量:0
原文: How the JVM

原文: 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粉我。

更多精彩内容:

JavaScript里令人惊讶的 “特性”

Python一些常用的爬虫技巧

[原]如何设计一个可用的web容器