「譯」JVM是如何使用那些你從未聽過的x86魔幻指令實現String.compareTo的

2020 年 5 月 6 日
筆記
JVM, hotspot

原文//jcdav.is/2016/09/01/How-the-JVM-compares-your-strings/

魔幻的String.compareTo

我們之前可能已經見過Java的String的比較方法，它會找出第一個不同的字元之間的距離，沒找到不同，就返回較兩個字元串長度之差

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生成，裡面有詳細的注釋。值得注意的是其實如果CPU支援AVX256指令集，它還有一個更魔幻的版本，不過這裡不會介紹，只關註上面的實現。

PCMPESTRI是什麼

pcmpestri是SSE4.2中引入的指令，屬於pcmpxstrx向量化字元串比較指令家族。它通過一個控制位元組（Control byte）複雜的功能，由於它們很複雜，x86指令集手冊專門用一個小節來描述它，為了易於理解甚至還提供了一個flow圖

看起來就像是把C語言程式碼放到CISC指令集裡面一樣！

控制位元組的每個bit的功能如下：

-------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.

(如果想要深入了解，可以參見Intel Instruction Set Reference Section 4.1)
compareTo使用0x19(譯註：'0b11001')，即對每8個packed words使用equal each模式(逐個相等比較)比較，結果取反。這個怪物指令使用4個暫存器作為輸入：兩個字元串作為參數，加上%rax和%rdx指定它們的長度（ PCMPESTRI中的E表示顯示指定長度——與之相對的pcmpistri和pcmpistrm表示用null作為結尾符，即不顯示指定長度）。結果（IntRes2）會放到%ecx。有時候這些不夠的情況下pcmpxstrx家族的指令還會設置一些flag：

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）的指針，由於循環前對%rax取反，所以循環實際上是反向進行的。
它載入第一個字元串的8個字元到%xmm0暫存器，然後與第二個字元串的8個字元比較，如果CFlag設置了就跳出（即不同的字元已經找到，下標在%ecx中設置了），然後比較兩個字元串的長度暫存器，並檢測是否是最後一次迭代（即%rdx為0了）。但是一個負數怎麼可能是正確的長度？額，忘記說了，pcmpestri使用長度的絕對值。

在循環之後，還有一個fallthrough分支，如果最短字元串剩下的字元不能被8整除了，那就使用這個分支處理剩下的字元，還有一個final分支，用來處理一個字元串是另一個的子字元串或者完全相同字元串的情況。

更合適的樂趣

如果上面對你來說不是很複雜，那麼可以看看更魔幻的indexOf 實現（有兩個版本，取決於待匹配字元串的長度），它使用控制位元組0x0d，即equal ordered模式進行匹配。

Tags: JVM hotspot