22.1 Vectorization

向量化3，例如循环用两个数组生成一个数组。循环体从输入数组中取值，处理后存储到另一个数组。重要的一点是操作了每一个元素。向量化—同时处理多个元素。

向量化并不是新的技术：本书的作者在1998年使用Cray Y-MP EL“lite”时从Cray Y-MP supercomputer line看到过。

例子：

  1. for (i = 0; i < 1024; i++)
  2. {
  3.     C[i] = A[i]*B[i];
  4. }

这段代码从A和B中取出元素，相乘，并把结果保存到C。

如果每个元素为32位int型，那么可以从A中加载4个元素到128bits XMM寄存器，B加载到另一个XMM寄存器，通过执行PMULID（Multiply Packed Signed Dword Integers and Store Low Result）和PMULHW(Multiply Packed Signed Integers and Store High Result)，一次可以得到4个64位结果。

循环次数从1024变成1024/4，当然更快。

一些简单的情况下某些编译器可以自动向量化，Intel C++5.

函数如下：

  1. int f (int sz, int *ar1, int *ar2, int *ar3)
  2. {
  3.         for (int i=0; i<sz; i++)
  4.                 ar3[i]=ar1[i]+ar2[i];
  5.         return 0;
  6. };

22.1.1 Intel C++

Intel C++ 11.1.051 win32下编译：

icl intel.cpp /QaxSSE2 /Faintel.asm /Ox

可以得到(IDA中):

  1. ; int __cdecl f(int, int *, int *, int *)
  2.                 public ?f@@YAHHPAH00@Z
  3. ?f@@YAHHPAH00@Z proc near
  5. var_10          = dword ptr -10h
  6. sz              = dword ptr 4
  7. ar1             = dword ptr 8
  8. ar2             = dword ptr 0Ch
  9. ar3             = dword ptr 10h
  10.                 push    edi
  11.                 push    esi
  12.                 push    ebx
  13.                 push    esi
  14.                 mov     edx, [esp+10h+sz]
  15.                 test    edx, edx
  16.                 jle     loc_15B
  17.                 mov     eax, [esp+10h+ar3]
  18.                 cmp     edx, 6
  19.                 jle     loc_143
  20.                 cmp     eax, [esp+10h+ar2]
  21.                 jbe     short loc_36
  22.                 mov     esi, [esp+10h+ar2]
  23.                 sub     esi, eax
  24.                 lea     ecx, ds:0[edx*4]
  25.                 neg     esi
  26.                 cmp     ecx, esi
  27.                 jbe     short loc_55
  29. loc_36:                                         ; CODE XREF: f(int,int *,int *,int *)+21
  30.                 cmp     eax, [esp+10h+ar2]
  31.                 jnb     loc_143
  32.                 mov     esi, [esp+10h+ar2]
  33.                 sub     esi, eax
  34.                 lea     ecx, ds:0[edx*4]
  35.                 cmp     esi, ecx
  36.                 jb      loc_143
  37. loc_55: ; CODE XREF: f(int,int *,int *,int *)+34
  38.                 cmp     eax, [esp+10h+ar1]
  39.                 jbe     short loc_67
  40.                 mov     esi, [esp+10h+ar1]
  41.                 sub     esi, eax
  42.                 neg     esi
  43.                 cmp     ecx, esi
  44.                 jbe     short loc_7F
  46. loc_67:                                          ; CODE XREF: f(int,int *,int *,int *)+59
  47.                 cmp     eax, [esp+10h+ar1]
  48.                 jnb     loc_143
  49.                 mov     esi, [esp+10h+ar1]
  50.                 sub     esi, eax
  51.                 cmp     esi, ecx
  52.                 jb      loc_143
  54. loc_7F:                                          ; CODE XREF: f(int,int *,int *,int *)+65
  55.                 mov     edi, eax ; edi = ar1
  56.                 and     edi, 0Fh ; is ar1 16-byte aligned?
  57.                 jz      short loc_9A ; yes
  58.                 test    edi, 3
  59.                 jnz     loc_162
  60.                 neg     edi
  61.                 add     edi, 10h
  62.                 shr     edi, 2
  64. loc_9A:                                          ; CODE XREF: f(int,int *,int *,int *)+84
  65.                 lea     ecx, [edi+4]
  66.                 cmp     edx, ecx
  67.                 jl      loc_162
  68.                 mov     ecx, edx
  69.                 sub     ecx, edi
  70.                 and     ecx, 3
  71.                 neg     ecx
  72.                 add     ecx, edx
  73.                 test    edi, edi
  74.                 jbe     short loc_D6
  75.                 mov     ebx, [esp+10h+ar2]
  76.                 mov     [esp+10h+var_10], ecx
  77.                 mov     ecx, [esp+10h+ar1]
  78.                 xor     esi, esi
  80. loc_C1:                                          ; CODE XREF: f(int,int *,int *,int *)+CD
  81.                 mov     edx, [ecx+esi*4]
  82.                 add     edx, [ebx+esi*4]
  83.                 mov     [eax+esi*4], edx
  84.                 inc     esi
  85.                 cmp     esi, edi
  86.                 jb      short loc_C1
  87.                 mov     ecx, [esp+10h+var_10]
  88.                 mov     edx, [esp+10h+sz]
  90. loc_D6:                                           ; CODE XREF: f(int,int *,int *,int *)+B2
  91.                 mov     esi, [esp+10h+ar2]
  92.                 lea     esi, [esi+edi*4] ; is ar2+i*4 16-byte aligned?
  93.                 test    esi, 0Fh
  94.                 jz      short loc_109 ; yes!
  95.                 mov     ebx, [esp+10h+ar1]
  96.                 mov     esi, [esp+10h+ar2]
  98. loc_ED:                                           ; CODE XREF: f(int,int *,int *,int *)+105
  99.                 movdqu  xmm1, xmmword ptr [ebx+edi*4]
  100.                 movdqu  xmm0, xmmword ptr [esi+edi*4] ; ar2+i*4 is not 16-byte aligned, so load
  101.                 it to   xmm0
  102.                 paddd   xmm1, xmm0
  103.                 movdqa  xmmword ptr [eax+edi*4], xmm1
  104.                 add     edi, 4
  105.                 cmp     edi, ecx
  106.                 jb      short loc_ED
  107.                 jmp     short loc_127
  108. ; ---------------------------------------------------------------------------
  109. loc_109:                                          ; CODE XREF: f(int,int *,int *,int *)+E3
  110.                 mov     ebx, [esp+10h+ar1]
  111.                 mov     esi, [esp+10h+ar2]
  112. loc_111:                                          ; CODE XREF: f(int,int *,int *,int *)+125
  113.                 movdqu  xmm0, xmmword ptr [ebx+edi*4]
  114.                 paddd   xmm0, xmmword ptr [esi+edi*4]
  115.                 movdqa  xmmword ptr [eax+edi*4], xmm0
  116.                 add     edi, 4
  117.                 cmp     edi, ecx
  118.                 jb      short loc_111
  120. loc_127:                                          ; CODE XREF: f(int,int *,int *,int *)+107
  121.                                                   ; f(int,int *,int *,int *)+164
  122.                 cmp     ecx, edx
  123.                 jnb     short loc_15B
  124.                 mov     esi, [esp+10h+ar1]
  125.                 mov     edi, [esp+10h+ar2]
  127. loc_133: ; CODE XREF: f(int,int *,int *,int *)+13F
  128.                 mov     ebx, [esi+ecx*4]
  129.                 add     ebx, [edi+ecx*4]
  130.                 mov     [eax+ecx*4], ebx
  131.                 inc     ecx
  132.                 cmp     ecx, edx
  133.                 jb      short loc_133
  134.                 jmp     short loc_15B
  135. ; ---------------------------------------------------------------------------
  136. loc_143:                                          ; CODE XREF: f(int,int *,int *,int *)+17
  137.                                                   ; f(int,int *,int *,int *)+3A ...
  138.                 mov     esi, [esp+10h+ar1]
  139.                 mov     edi, [esp+10h+ar2]
  140.                 xor     ecx, ecx
  142. loc_14D:                                          ; CODE XREF: f(int,int *,int *,int *)+159
  143.                 mov     ebx, [esi+ecx*4]
  144.                 add     ebx, [edi+ecx*4]
  145.                 mov     [eax+ecx*4], ebx
  146.                 inc     ecx
  147.                 cmp     ecx, edx
  148.                 jb      short loc_14D
  150. loc_15B:                                          ; CODE XREF: f(int,int *,int *,int *)+A
  151.                                                   ; f(int,int *,int *,int *)+129 ...
  152.                 xor     eax, eax
  153.                 pop     ecx
  154.                 pop     ebx
  155.                 pop     esi
  156.                 pop     edi
  157.                 retn
  158. ; ---------------------------------------------------------------------------
  159. loc_162:                                           ; CODE XREF: f(int,int *,int *,int *)+8C
  160.                                                    ; f(int,int *,int *,int *)+9F
  161.                 xor     ecx, ecx
  162.                 jmp     short loc_127
  163. ?f@@YAHHPAH00@Z endp

SSE2相关指令是：

  1. MOVDQU (Move Unaligned Double Quadword)—仅仅从内存加载16个字节到XMM寄存器。
  2. PADDD (Add Packed Integers)—把源存储器与目的寄存器按双字对齐无符号整数普通相加,结果送入目的寄存器,内存变量必须对齐内存16字节.
  3. MOVDQA (Move Aligned Double Quadword)—把源存储器内容值送入目的寄存器,当有m128时,必须对齐内存16字节.

如果工作元素超过4对，并且指针ar3按照16字节对齐，SSE2指令将被执行： 如果ar2按照16字节对齐，则代码如下：

  1. movdqu  xmm0, xmmword ptr [ebx+edi*4] ; ar1+i*4
  2. paddd   xmm0, xmmword ptr [esi+edi*4] ; ar2+i*4
  3. movdqa  xmmword ptr [eax+edi*4], xmm0 ; ar3+i*4

否则,ar2处的值将用MOVDQU加载到XMM0，它不需要对齐指针，代码如下：

  1. movdqu  xmm1, xmmword ptr [ebx+edi*4] ; ar1+i*4
  2. movdqu  xmm0, xmmword ptr [esi+edi*4] ; ar2+i*4 is not 16-byte aligned, so load it to xmm0
  3. paddd   xmm1, xmm0
  4. movdqa  xmmword ptr [eax+edi*4], xmm1 ; ar3+i*4

其他情况，将没有SSE2代码被执行。

22.1.2 GCC

gcc用-O3 选项同时打开SSE2支持: -msse2.

可以得到(GCC 4.4.1):

  1. ; f(int, int *, int *, int *)
  2.                 public _Z1fiPiS_S_
  3. _Z1fiPiS_S_     proc near
  5. var_18          = dword ptr -18h
  6. var_14          = dword ptr -14h
  7. var_10          = dword ptr -10h
  8. arg_0           = dword ptr 8
  9. arg_4           = dword ptr 0Ch
  10. arg_8           = dword ptr 10h
  11. arg_C           = dword ptr 14h
  12.                 push    ebp
  13.                 mov     ebp, esp
  14.                 push    edi
  15.                 push    esi
  16.                 push    ebx
  17.                 sub     esp, 0Ch
  18.                 mov     ecx, [ebp+arg_0]
  19.                 mov     esi, [ebp+arg_4]
  20.                 mov     edi, [ebp+arg_8]
  21.                 mov     ebx, [ebp+arg_C]
  22.                 test    ecx, ecx
  23.                 jle     short loc_80484D8
  24.                 cmp     ecx, 6
  25.                 lea     eax, [ebx+10h]
  26.                 ja      short loc_80484E8
  28. loc_80484C1:                    ; CODE XREF: f(int,int *,int *,int *)+4B
  29.                                 ; f(int,int *,int *,int *)+61 ...
  30.                 xor     eax, eax
  31.                 nop
  32.                 lea     esi, [esi+0]
  33. loc_80484C8:                    ; CODE XREF: f(int,int *,int *,int *)+36
  34.                 mov     edx, [edi+eax*4]
  35.                 add     edx, [esi+eax*4]
  36.                 mov     [ebx+eax*4], edx
  37.                 add     eax, 1
  38.                 cmp     eax, ecx
  39.                 jnz     short loc_80484C8
  41. loc_80484D8:                    ; CODE XREF: f(int,int *,int *,int *)+17
  42.                                 ; f(int,int *,int *,int *)+A5
  43.                 add     esp, 0Ch
  44.                 xor     eax, eax
  45.                 pop     ebx
  46.                 pop     esi
  47.                 pop     edi
  48.                 pop     ebp
  49.                 retn
  50. ; ---------------------------------------------------------------------------
  51.                 align 8
  52. loc_80484E8:                    ; CODE XREF: f(int,int *,int *,int *)+1F
  53.                 test    bl, 0Fh
  54.                 jnz     short loc_80484C1
  55.                 lea     edx, [esi+10h]
  56.                 cmp     ebx, edx
  57.                 jbe     loc_8048578
  59. loc_80484F8:                    ; CODE XREF: f(int,int *,int *,int *)+E0
  60.                 lea     edx, [edi+10h]
  61.                 cmp     ebx, edx
  62.                 ja      short loc_8048503
  63.                 cmp     edi, eax
  64.                 jbe     short loc_80484C1
  66. loc_8048503:                    ; CODE XREF: f(int,int *,int *,int *)+5D
  67.                 mov     eax, ecx
  68.                 shr     eax, 2
  69.                 mov     [ebp+var_14], eax
  70.                 shl     eax, 2
  71.                 test    eax, eax
  72.                 mov     [ebp+var_10], eax
  73.                 jz      short loc_8048547
  74.                 mov     [ebp+var_18], ecx
  75.                 mov     ecx, [ebp+var_14]
  76.                 xor     eax, eax
  77.                 xor     edx, edx
  78.                 nop
  80. loc_8048520:                    ; CODE XREF: f(int,int *,int *,int *)+9B
  81.                 movdqu  xmm1, xmmword ptr [edi+eax]
  82.                 movdqu  xmm0, xmmword ptr [esi+eax]
  83.                 add     edx, 1
  84.                 paddd   xmm0, xmm1
  85.                 movdqa  xmmword ptr [ebx+eax], xmm0
  86.                 add     eax, 10h
  87.                 cmp     edx, ecx
  88.                 jb      short loc_8048520
  89.                 mov     ecx, [ebp+var_18]
  90.                 mov     eax, [ebp+var_10]
  91.                 cmp     ecx, eax
  92.                 jz      short loc_80484D8
  94. loc_8048547:                    ; CODE XREF: f(int,int *,int *,int *)+73
  95.                 lea     edx, ds:0[eax*4]
  96.                 add     esi, edx
  97.                 add     edi, edx
  98.                 add     ebx, edx
  99.                 lea     esi, [esi+0]
  101. loc_8048558:                    ; CODE XREF: f(int,int *,int *,int *)+CC
  102.                 mov     edx, [edi]
  103.                 add     eax, 1
  104.                 add     edi, 4
  105.                 add     edx, [esi]
  106.                 add     esi, 4
  107.                 mov     [ebx], edx
  108.                 add     ebx, 4
  109.                 cmp     ecx, eax
  110.                 jg      short loc_8048558
  111.                 add     esp, 0Ch
  112.                 xor     eax, eax
  113.                 pop     ebx
  114.                 pop     esi
  115.                 pop     edi
  116.                 pop     ebp
  117.                 retn
  118. ; ---------------------------------------------------------------------------
  119. loc_8048578:                    ; CODE XREF: f(int,int *,int *,int *)+52
  120.                 cmp     eax, esi
  121.                 jnb     loc_80484C1
  122.                 jmp     loc_80484F8
  123. _Z1fiPiS_S_     endp

几乎一样，但没有Intel的细致。