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

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

原文

https://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

不過這些都不在我們的讨論範圍内，讓我們仔細看看循環裡面的代碼，以及一些初始化動作

%rax是較短字元串長度，%rdx與~0x7求與 （即最大循環次數的8倍）。然後它會比較指向兩個字元串數組（%rsi和%rdi）的指針，由于循環前對%rax取反，是以循環實際上是反向進行的。

它加載第一個字元串的8個字元到%xmm0寄存器，然後與第二個字元串的8個字元比較，如果CFlag設定了就跳出（即不同的字元已經找到，下标在%ecx中設定了），然後比較兩個字元串的長度寄存器，并檢測是否是最後一次疊代（即%rdx為0了）。但是一個負數怎麼可能是正确的長度？額，忘記說了，pcmpestri使用長度的絕對值。

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

更合适的樂趣

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

轉載位址

https://www.cnblogs.com/kelthuzadx/p/12837642.html