2012年夏のプログラミング・シンポジウム.indd

Size: px

Start display at page:

Download "2012年夏のプログラミング・シンポジウム.indd"

わんどたもん
5 years ago
Views:

1 1 x86/x64 CPU Intel CPU C++ x86/x64 CPU An optimization technique for x86/x64 CPU by rich assembler MITSUNARI Shigeo We propose a just-in-time assembler for x86/x64 using C++ and use it for code-generation, fast string processing, and some elementary functions. 1. x86/x64 C++ 64bit Visual Studio NASM YASM gas LLVM GNU lightning x86/x64 x86/x64 x86/x64 Xbyak C++ C++ Cybozu Labs, Inc. C++ C++ NASM YASM JIT CPU 2. Xbyak Xbyak x86/x64 Windows, Linux, Mac OS X Visual Studio/gcc/clang C++ MASM Xbyak C++ C++ DSL MASM Intel C++ 1 ptr [...] dword [...] C++ 59

2 // add(ptr [ecx + edx * 4], eax); movzx(rax, byte [rsp + rdi + 12]); int main(int argc, char *argv[]) { int n = argc == 1? 0 : atoi(argv[1]); Code code(n); int (*add)(int) // template<size_t N> = (int (*)(int))code.getcode(); printf("%d\n", add(3)); struct BoxT { int w[n]; int h[n]; ; typedef BoxT<20> Box; mov(eax, dword [esp+offsetof(box, h)]); add offsetof 4. add stddef.h mov eax, dword ptr [esp+4] add eax, 7 ret int uint32 t 3. Xbyak C++ n n 2 Xbyak::CodeGenerator x86/x ) 8 BitBlt 5 #include <xbyak/xbyak.h> switch struct Code : Xbyak::CodeGenerator { op Code(int n) { // 32bit OS op op mov(eax, ptr [esp + 4]); add(eax, n); ret(); 1985 Windows op ; Code 6 switch C/C++ 60

3 3 5. BitBltC 4.1 for (int i = 0; i < y; i++) { for (int j = 0; j < x; j++) { switch (op) { case 0: *dst = 0; break; case 1: *dst &= *src; break; case 2: *dst ^= *src; break; case 3: *dst = *src; break;... C \0 char C \0 char L C++ std::string L SSE4.1 C L ecx xmm0 4 1 dst++; src++; 1 C L 6. Xbyak BitBlt ecx pcmpistri pcmpestri xmm0 pcmpistrm pcmpestrm L(".lp"); switch (op) { pcmpxstry case 0: mov(ptr [dst], eax); break; pcmpxstry xmm, xmm/mem, imm8 case 1: mov(eax, ptr [src]); mov(ptr [dst], eax); break; case 2: mov(eax, ptr [src]); xor(ptr [dst], eax); break; case 3: SSE mem 16byte imm8 8bit 8bit/16bit // / (2) mov(eax, ptr [src]); 4.2 strstr or(ptr [dst], eax); break; strstr strstr add(dst, 4); add(src, 4); sub(n, 1); jnz(".lp"); C text C key NULL 7. strstr JIT Regen 3) JavaScript 1. movdqu(xmm0, ptr [key]); iv 4) 2 2. L(".lp"); PCSX2 5) Xbyak 3. pcmpistri(xmm0, ptr [text], 12); 4. lea(text, ptr [text + 16]); 5. ja(".lp"); jnc(".notfound"); Intel Penryn Core2 CPU 7. // C strlen strstr 7 strstr text pcmpestri, pcmpistri : key xmm0 key 16byte 1 text 16byte key 3 12 C text 16byte 61

4 4 4 5 text \0 6 key 16byte key 7 pcmpistri pcmpestri edx/eax text key, C strstr L GNU memmem \0 16byte 16byte 4.3 strstr strstr std::find find template 2 [cycle] find 1 strstr 2 strstrc qs 3 bm 4 asm 5 a ab AB...Z std::string find 2 gcc strstr SSE4.1 3 Quick Search BM 4 boost 1.51 algorithm::boyer moore A Z 27 asm 10 strstr 8 strstrc key ASCII strstrc gcc strstr SSE4.1 ubuntu server(64bit) + Xeon X gcc gcc strstrc gcc strstr SSE4.1 gcc strchr SSE4.1 boost 1.51 algorithm::boyer moore BM quick search BM VC Intel C strstr gcc strstrc 8 std::find Visual 8. strstrc Studio 2012 UTF-8 const char *strstr_c(const char *str, 0xe3 key const char *key) { strstrc byte 0xe3 size_t len = strlen(key); memcmp while (*str) { const char *p = strchr(str, key[0]); Quick Search BM if (p == 0) return 0; if (memcmp(p + 1, key + 1, len - 1) AB...Z asm == 0) return p; 2 qs bm str = p + 1; CPU return 0; asm 1byte 1cycle 130MiB UTF-8 imm8 key strchr byte CPU [a-z][0-9] 2 findchar range 6) herumi/mie/tree/master/test/string 62

5 4.4 strcasestr issandybridge CPU ASCII strcasestr key text CPU Xbyak 7 3 pcmpistri text 16byte 5. 1 c if ( A <= c && c <= Z ) { c += a - A ; 1byte if byte 0xff 0 int gt(x, y) { return x > y? 0xff : 0; rank n(< 2 32 ) v, i (0 i < n) v[i](=0 or 1). rank rank(k) := # { i 0 <= i <= k, v[i] = 1 rank 32bit b1 8bit b2 b1 256bit 1 b2 64bit 256bit 0 256bit 1 8bit c += gt(c, A -1) & gt( Z +1,c) & ( a - Z ); 11. rank1 for (int i = 0; i < n / 256; i++) { 16byte byte gt(x, y) pcmpgtb 16byte strcasestr strstr 70% b1[i] = rank(i * 256); for (int i = 0; i < n / 64; i++) { b2[i] = rank(i*64) - rank((i&~3)*64); 4.5 CPU strstr 7 Sandy- Bridge Xeon X lea add Xeon X % CPU bool issandybridge CPU SandyBridge true uint32_t rank(uint32_t i) const { uint64_t mask = (2ULL<<(i & 63))-1; return a_[i / 256] + b_[i / 64] + popcnt(org_[i / 64] & mask); popcnt SSE4.2 64bit if (issandybridge) { lea(a, ptr [a + 16]); ja(".lp"); else { jbe(".headcmp"); add(a, 16); jmp(".lp"); L(".headCmp"); 1bit ( )/256 = 1/4 b1 b2 7) rank1 1bit 256bit 512bit b bit b2 b2 64bit 8bit 8 256bit 5 63

6 6 128bit psadbw SSE 8 byte 12. rank2 pasdbw(x, y) := sum[abs(x[i]-y[i]) i=0..7] for (int i = 0; i < n / 512; i++) { b1[i] = rank(i * 512); 15 10cycle b2[0] = 0; for (int i = 1; i < n / 128; i++) { b2[i] = rank(i*128)-rank((i-1)*128); 15. psadbw n union { uint8_t data[4]; uint32_t s; ci; rank 0 n < 4 uint8 t 13 x = ci.s & ((1U << (n * 8)) - 1); movd(xmm0, x); // xmm0 = x pxor(xmm1, xmm1); // zero clear psadbw(xmm0, xmm1); // sum 13. n(0 n < 4) int sum1(uint8_t data[4], int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += data[i]; 128bit popcnt 128bit [H:L] H L 64bit n 0 n < 128 popcnt mask n 64 return sum; bit // input [L:H] uint64_t mask = 2 << (n & 63) - 1; Xeon X gcc XorShift uint64_t ml = (n & 64)? -1 : mask; 35cycle uint64_t mh = (n & 64)? mask : 0; 26cycle L &= ml; 14 H &= mh; 14. switch n 16 gcc int sum2(uint8_t data[4], int n) { int sum = 0; 17 switch (n) { case 3: sum += data[2]; 17. cmovz 128bit case 2: sum += data[1]; case 1: sum += data[0]; or(ml, -1); return sum; and(n, 64); cmovz(ml, mask); cmovz(mask, n); n switch 25% cmovz 1 mov 1 and(n, 64) 20cycle 15cycle x86/x64 MPEG 0 n < 64 cmovz cmovz rank2 64

7 7 i rank(i) cycle sdsl 8) rank2 3 rank [cycle] rank1 rank2 sdsl 0.06M M M M M M M M M rank1 sdsl sdsl sdsl 6. exp e x float double 10) double 1e double expd A, B, C2 6.1 exp(x + y) = exp(x) exp(y) exp(x) = 1 + x + x 2 /2 + x 3 /6 + x 4 /24 + x s union di { 18. expd uint64_t i; double d; ; double expd(double x) { const double A = 2048/log(2); const double B = 3ULL << 51; const double RA = 1 / A; const C2 = ; const C3 = ; di di; di.d = x * A + B; uint64_t iax = tbl[di.i & 2047]; double t = (di.d - B) * RA - x; uint64_t u = ((di.i ) >> 11) << 52; double y = (C3 - t) * (t * t) * C2 - t + 1; di.i = u iax; return y * di.d; t x = s + t, exp(x) = exp(s) exp(t). t t < 2 12 t 4 /24 < double 53bit 3 round(x) x x = round(x) + (x round(x)). s = round(x) t = x s t 1/2 t < 2 12 x = 2048x x = s +t x = round(2048x)/ t /2048. n = round(2048x) exp(n/2048) exp(x) = 0 x log(dbl MIN) = 708 exp(x) = Inf x log(dbl MAX) = 709 n ( ) = 22MiB

8 exp(n/α) = 2 n/2β α β α = 2048/(log 2) β = 12 α 18 A n 2048 q r (n = 2048q+r) exp(n/α) = 2 n/2048 = 2 q 2 r/ r < r/ = 16KiB round SSE4.1 roundpd double x 2 52 x B C2, C3 1 + x + x 2 /2 + x 3 /6 = 1 + x + (1/6)x 2 (3 + x) 1/6 C2 = C3 = % α = log(2)/4096 α ( I := exp(x) (a + x + cx 2 + dx 3 ) ) 2 dx 0 (a, c, d) 6.2 float, double std::exp fmath::exp, fmath::expd 10) Xeon X gcc exp [cycle] cycle std::exp(float) fmath::exp e-8 std::exp(double) fmath::expd e C++ x86/x64 JIT C Xbyak C++ LLVM Xbyak x86/x64 CPU Xbyak CPU glibc strstr Xbyak strstr exp CPU 8. Q.? A. Q.? A. Q. SDSL? A. SDSL Q. Xbyak C++ A. Xbyak 66

9 9 (11) 10% 1) Andy Oram, Greg Wilson Brian Kernighan, Jon Bentley, (2008). 2) Intel : /www/us/en/processors/architectures -software-developer-manuals.html 3) 53 (2012). 4) Constellation : 5) 6) /master/include/mie/string.hpp 7) Takeshi Yamamuro : A x86-optimized rank & select dictionary for bit sequences /a-x86optimized-rankselect-dictionary -for-bit-sequences 8) 9) exp /exp ) 11) B. Jean-Luc, G. Jorge E, M. Shigeo, O. Eiji, R. Francisco, T. Tadanori : High-speed software implementation of the optimal ate pairing over Barreto-Naehrig curves, pp , Pairing 10(2010). /crypt/ate-pairing.html 67

£Ã¥×¥í¥°¥é¥ß¥ó¥°ÆþÌç (2018) - Âè£µ²ó ¨¡ À©¸æ¹½Â¤¡§¾ò·ïÊ¬´ô ¨¡

£Ã¥×¥í¥°¥é¥ß¥ó¥°ÆþÌç (2018) - Âè£µ²ó ¨¡ À©¸æ¹½Â¤¡§¾ò·ïÊ¬´ô ¨¡ (2018) 2018 5 17 0 0 if switch if if ( ) if ( 0) if ( ) if ( 0) if ( ) (0) if ( 0) if ( ) (0) ( ) ; if else if ( ) 1 else 2 if else ( 0) 1 if ( ) 1 else 2 if else ( 0) 1 if ( ) 1 else 2 (0) 2 if else