chr_replace

Implantation de la fonction suivante et comparaison avec une implantation SSE.

int chr_replace(char *src, char *dst, int n, char c, char d) {
	int changes=0;
	for (int i=0; i < n; ++i) {
		if (src[i] == c) {
			dst[i] = d;
			++changes;
		} else {
			dst[i] = src[i];
		}
	}
	return changes;
}

Les figures qui suivent affichent le temps d'exécution de la fonction de remplacement d'un caractère pour différentes longueurs de chaines (1024, 2048, 4096, 8192). On fait figurer :

Intel Core i5 4570 - 3.2 Ghz (Haswell)

Intel Core i5 3570k - 3.5 Ghz (Ivy Bridge)

Intel Core i7 2600k - 3.4 Ghz (Sandy Bridge)

Intel Core i7 860 - 2.8 Ghz (Lynnfield)

Intel Atom N450 - 1.66 Ghz (Diamondville)

AMD Phenom II X6 1090T - 3,2 Ghz (Thuban)

Intel Core Quad 9300 - 2.5 Ghz (Yorkfield)

Intel Core Quad 6600 - 2.4 Ghz (Kentsfield)

Intel Core 2 Duo E8400 - 3.0 Ghz (Dual Core - Wolfdale)

Le code

  1. /*
  2.  * char_replace_sse42i.cpp
  3.  *
  4.  *  Created on: Mar 8, 2017
  5.  *      Author: richer
  6.  */
  7.  
  8.  
  9.  
  10. int char_replace_sse42i(char *dst, char *src, int size, char c, char d) {
  11.     int i, changes=0;
  12.     __m128i v_src, v_c, v_d, v_cmp,  v_res;
  13.  
  14.     // create a vector of 16 bytes containing c
  15.     v_c = _mm_cvtsi32_si128(c * 0x01010101);
  16.     v_c = _mm_shuffle_epi32(v_c, 0x00);
  17.    
  18.     // create a vector of 16 bytes containing d
  19.     v_d = _mm_cvtsi32_si128(d * 0x01010101);
  20.     v_d = _mm_shuffle_epi32(v_d, 0x00);
  21.  
  22.     // make loop a multiple of 16 bytes
  23.     // and treat the remaining later
  24.     for (i = 0; i < (size & ~15); i+= 16) {
  25.         // load source data
  26.         v_src = _mm_load_si128( (__m128i *) &src[i]);
  27.        
  28.         // compare to v_c
  29.         v_cmp = _mm_cmpeq_epi8(v_src, v_c);
  30.  
  31.         // move comparison data to GPR
  32.         int local_changes = _mm_movemask_epi8(v_cmp);
  33.        
  34.         // count number of differences
  35. #ifdef CPP_POPCOUNT_COMPLIANT
  36. #ifdef CPP_ARCHITECTURE_32_BITS
  37.         changes += _mm_popcnt_u32(local_changes);
  38. #else
  39.         changes += _mm_popcnt_u64(local_changes);
  40. #endif
  41.  
  42. #else
  43.         changes += __builtin_popcount(local_changes);
  44. #endif
  45.  
  46.         // conditionally copy bytes
  47.         v_res = _mm_blendv_epi8(v_src, v_d, v_cmp);
  48.  
  49.         // store result
  50.         _mm_store_si128( (__m128i *) &dst[i], v_res);
  51.     }
  52.  
  53.  
  54.     // treat remaining data
  55.     while (i<size) {
  56.         if (src[i] == c) {
  57.             dst[i] = d;
  58.             ++changes;
  59.         } else {
  60.             dst[i] = src[i];
  61.         }
  62.         ++i;
  63.     }
  64.  
  65.     return changes;
  66. }
  67.  
  68.  
  69.  
  1. global char_replace_sse20
  2.  
  3. section .text
  4.  
  5. ; int char_replace_sse2(char *dst, char *src, int n, char c, char d);
  6. ; esi, xmm3 = src
  7. ; edi = dst,
  8. ; edx = n / 4
  9. ; xmm0 = 0xff....ff
  10. ; xmm2 = c
  11. ; xmm3 = d
  12. ; eax = changes
  13.  
  14. char_replace_sse20:
  15.     push    ebp
  16.     mov     ebp,esp
  17.  
  18.     push    esi
  19.     push    edi
  20.     push    ebx
  21.    
  22.     movzx   eax, byte PARAM_C
  23. ;   mov     ah,al
  24. ;   mov     cx,ax
  25. ;   shl     eax, 16
  26. ;   or      ax, cx
  27. ;   movd    xmm2, eax
  28. ;   pshufd  xmm2,xmm2,0
  29.  
  30.     movd        xmm2, eax
  31.     punpcklbw   xmm2, xmm2
  32.     punpcklbw   xmm2, xmm2
  33.     pshufd      xmm2, xmm2, 0
  34.  
  35.     movzx   eax, byte PARAM_D
  36. ;   mov     ah,al
  37. ;   mov     cx,ax
  38. ;   shl     eax, 16
  39. ;   or      ax, cx
  40. ;   movd    xmm3, eax
  41. ;   pshufd  xmm3,xmm3,0
  42.  
  43.     movd        xmm3, eax
  44.     punpcklbw   xmm3, xmm3
  45.     punpcklbw   xmm3, xmm3
  46.     pshufd      xmm3, xmm3, 0
  47.    
  48.     xor     eax, eax
  49.     xor     ecx, ecx
  50.     mov     esi, PARAM_SRC
  51.     mov     edi, PARAM_DST
  52.  
  53.     mov     edx, PARAM_SIZE
  54.     shr     edx, 4
  55.     test    edx, edx
  56.     jz      .next_x1
  57.  
  58. .loop_x16:
  59.     movdqa      xmm0, [esi]         ; xmm0 = src[i:i+15]
  60.     movdqa      xmm1, xmm0          ; make a copy in xmm1
  61.    
  62.     ;
  63.     ; compare xmm0 == xmm2 [c,...,c]
  64.     ; if xmm0[i] == xmm2[i] then xmm0[i] = 0xFF else xmm0[i] = 0x00
  65.     ;
  66.     pcmpeqb     xmm0, xmm2
  67.    
  68.     ; move mask to ebx
  69.     ; if xmm0 = [ 0xFF, 0x00, 0xFF, 0xFF, 0x00, 0xFF, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00]
  70.     ; then ebx = 0000.0000.0000.0000.1011.0100.1111.0000_b = 000B4F0_h
  71.     pmovmskb    ebx, xmm0
  72.  
  73.     movdqa      xmm4, xmm0
  74.  
  75.     pand        xmm0, xmm3
  76.     ; PANDN xmm1, xmm2 => xmm1 = NOT(xmm1) & xmm2
  77.     pandn       xmm4, xmm1
  78.     por         xmm0, xmm4
  79.  
  80.     movdqa      [edi], xmm0
  81.    
  82.     popcnt  ebx, ebx
  83.     add     eax, ebx
  84.  
  85.     add     edi, 16
  86.     add     esi, 16
  87.     dec     edx
  88.     jnz     .loop_x16
  89.  
  90. .next_x1:  
  91.     mov     edx, PARAM_SIZE
  92.     and     edx, 15
  93.     test    edx, edx
  94.     jz  .end
  95.  
  96.  
  97. .loop_x1:
  98.     mov     cl, byte [esi]
  99.     cmp     cl, byte PARAM_C
  100.     jne     .next
  101.  
  102.         mov     cl, byte PARAM_D
  103.         add     eax, 1
  104.  
  105. .next:
  106.     mov     byte [edi], cl
  107.     inc     esi
  108.     inc     edi
  109.     dec     edx
  110.     jnz     .loop_x1
  111.  
  112. .end:
  113.  
  114.     pop     ebx
  115.     pop     edi
  116.     pop     esi
  117.    
  118.     mov     esp,ebp
  119.     pop     ebp
  120.     ret
  121.  
  122.  

The PUNPCKLBW instruction interleaves the low-order bytes of the source and destination operands : 


mov       eax, 48
movd      xmm2, eax      [48,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
punpcklbw xmm2, xmm2     [48, 48,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
punpcklbw xmm2, xmm2     [48, 48, 48, 48,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
pshufd    xmm2, xmm2, 0  [48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48]

La corps de la fonction principale réalise le traitement qui suit. On remplace 30_h par 40_h, le principe repose sur l'utilisation d'un masque :

             
movdqa    xmm0, [esi]  [30, 31, 32, 33 | 30, 30, 31, 31 | 31, 30, 30, 30 | 30, 31, 30, 30]
movdqa    xmm1, xmm0

pcmpeqb   xmm0, xmm2   [FF, 00, 00, 00 | FF, FF, 00, 00 | 00, FF, FF, FF | FF, 00, FF, FF] 
pmovmskb  ebx,  xmm0   DE31_h = 1101.1110.0011.0001 (lire xmm2 à l'envers) 
movdqa    xmm4, xmm0   [FF, 00, 00, 00 | FF, FF, 00, 00 | 00, FF, FF, FF | FF, 00, FF, FF] 
pand      xmm0, xmm3   [40, 00, 00, 00 | 40, 40, 00, 00 | 00, 40, 40, 40 | 40, 00, 40, 40] 
pandn     xmm4, xmm1   [00, 31, 32, 33 | 00, 00, 31, 31 | 31, 00, 00, 00 | 00, 31, 00, 00]
por       xmm0, xmm4   [40, 31, 32, 33 | 40, 40, 31, 31 | 31, 40, 40, 40 | 00, 31, 40, 40]