RapidJSON中itoa的實現是現在已知最快的么？

01-16

miloyip/itoa-benchmark · GitHub

哈哈這個我要來摻和一下。 @Milo Yip剛放出itoa benchmark的時候我也設計了一個比較奇葩的演算法，而且經過我人肉micro-op分析，理應比milo的sse2版本要快。雖然實際運行結果證明我的演算法並不快（所以這也說明人肉性能分析實在不靠譜），但是我覺得還是可以分享一下。

鑒於sse2版本的itoa已經足夠優秀，要想打敗它，基本上只有一種選擇：完全避開周期較長的乘法指令。這怎麼能夠做到呢，我的做法是，打一張巨大的表。比如若要將0x12345678這個數轉成10進位表示，只需要預先計算出0x12000000, 0x340000, 0x5600, 0x78這四個數字的十進位表示，然後加起來即可，這個加法可以藉助於sse一條指令搞定。注意這裡還有一個問題是需要按10進位傳播進位，但sse是按256進位的，一個小技巧是在每一個lane上額外加上256 - 10 = 246，這樣就可以用sse模擬10進位加法了。完整代碼如下：

__m128i Convert8DigitsSSE4Lut(uint32_t value) { assert(value &<= 99999999); __m128i a = _mm_cvtsi64_si128(gSSEDigitsLUT3[value &>&> 24]); __m128i b = _mm_cvtsi64_si128(gSSEDigitsLUT2[(value &>&> 16) 0xFF]); __m128i c = _mm_cvtsi64_si128(gSSEDigitsLUT1[(value &>&> 8) 0xFF]); __m128i d = _mm_cvtsi32_si128(gSSEDigitsLUT0[value 0xFF]);


	__m128i k = _mm_cvtsi64_si128(kBroadcast);

	__m128i z = _mm_cvtsi64_si128(kAscIIzero);

	__m128i r = _mm_cvtsi64_si128(kRevertMask);
	__m128i x = _mm_add_epi64(a, b);

	__m128i y = _mm_add_epi64(c, d);

	x = _mm_max_epu8(x, _mm_add_epi8(x, k));

	y = _mm_min_epu8(y, _mm_sub_epi8(y, k));

	x = _mm_add_epi64(x, y);

	x = _mm_min_epu8(x, _mm_sub_epi8(x, k));
	x = _mm_shuffle_epi8(x, r);

	x = _mm_add_epi8(x, z);

return x; }

注意上面的每一條指令都只需要1個cycle(LOAD除外)，所有的加起來也不過相當於一條乘法指令的開銷。而進一步跑了一下IACA也基本印證了我的人肉分析：

我的sse4lut： 12 cycles的latency

Latency Analysis Report
---------------------------
Latency: 12 Cycles
| Inst | Resource Delay In Cycles | |
| Num | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | FE | |
-------------------------------------------------------------------------
| 0 | | | | | | | | | | | lea r8, ptr [rip-0x1252]
| 1 | | | | | | | | | | | mov rax, 0xf6f6f6f6f6f6f6f6

| 2 | | | | | | | | | | | movq xmm4, rax
| 3 | | | | | | | | | | | mov eax, ecx
| 4 | | | | | | | | | | | shr rax, 0x10
| 5 | | | | | | | | | | | movzx ecx, al
| 6 | | | | | | | | | 1 | | mov eax, edx
| 7 | | | | | | | 1 | | | | shr rax, 0x18
| 8 | | | | | | | | | | | movq xmm2, qword ptr [r8+rcx*8+0x3b80]
| 9 | | | | | | | | | | | movq xmm0, qword ptr [r8+rax*8+0x3380]
| 10 | | | | | | | | | 2 | CP | mov eax, edx
| 11 | 1 | | | | | | | | | CP | shr rax, 0x8

| 12 | | | | | | | | | | CP | movzx ecx, al
| 13 | | | | | | | | | 3 | | movzx eax, dl
| 14 | | | | | | | | | | | paddq xmm2, xmm0
| 15 | | | | | | | | | | | movd xmm0, dword ptr [r8+rax*4+0x4b80]
| 16 | | | | | | | | | | CP | movq xmm3, qword ptr [r8+rcx*8+0x4380]
| 17 | | | | | | | | | 4 | | mov rax, 0x1020304050607

Milo的sse2 ： 43 cycles的latency

Latency Analysis Report
---------------------------
Latency: 43 Cycles

| Inst | Resource Delay In Cycles | |
| Num | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | FE | |
-------------------------------------------------------------------------
| 0 | | | | | | | | | | CP | movdqa xmm2, xmmword ptr [rip+0x1f6f]
| 1 | | | | | | | | | | | movdqa xmm0, xmmword ptr [rip+0x1f57]
| 2 | | | | | | | | | | | movd xmm1, ebx
| 3 | | | | | | | | | | | inc ebx
| 4 | | | | | | | | | | CP | pmuludq xmm2, xmm1
| 5 | | | | | | | | | | CP | psrlq xmm2, 0x2d
| 6 | | | | | | | | | | CP | pmuludq xmm0, xmm2

| 7 | | | | | | | | | | CP | psubd xmm1, xmm0
| 8 | | | | | | | | | | CP | punpcklwd xmm2, xmm1
| 9 | | | | | | | | | | CP | psllq xmm2, 0x2
| 10 | | | | | | | | | | CP | punpcklwd xmm2, xmm2
| 11 | | | | | | | | | | CP | punpckldq xmm2, xmm2
| 12 | | | | | | | | | 3 | CP | pmulhuw xmm2, xmmword ptr [rip+0x1f17]
| 13 | | | | | | | | | 3 | CP | pmulhuw xmm2, xmmword ptr [rip+0x1eff]
| 14 | | | | | | | | | | CP | movdqa xmm0, xmm2
| 15 | | | 1 | | | | | | 3 | CP | pmullw xmm0, xmmword ptr [rip+0x1ee3]
| 16 | | | | | | | | | | CP | psllq xmm0, 0x10

| 17 | | | | | | | | | | CP | psubw xmm2, xmm0
| 18 | | | | | | | | | | CP | packuswb xmm2, xmm3
| 19 | | | | | | | | | 4 | CP | paddb xmm2, xmmword ptr [rip+0x1ebe]
| 20 | | | | | | | | | 5 | CP | movq qword ptr [rsp+0x20], xmm2
| 21 | | | | | | | | | 4 | | cmp ebx, 0x1f82088
| 22 | | | | | | | | | | | jb 0xffffffffffffff82
| 23 | | | | | | | | | 5 | | lea rcx, ptr [rsp+0x80]

看上去非常有希望是不是，12 cycles VS 43 cycles，簡直完爆啊，可以實際運行結果確是這樣的（我的測試代碼已經儘可能的讓LUT全部L1命中）：

sse4lut: 89.7469
sse2: 70.7487

媽蛋以後再不相信Intel的手冊了。

很難說。benchmark只是特定平台、編譯器下的結果，有可能在某些情況下不是最優，例如或可用到某些CPU提供的指令集。

SSE2版本只在多數位的情況下比branchlut快一點點，所以RapidJSON只使用了後者。

如果發現有更好的實現，可簡單地加入這個benchmark中，並希望能給pull request。

看起來是