[译]看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粉我

更多精彩内容:

JavaScript里令人惊讶的 “特性”

Python一些常用的爬虫技巧

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容