atoi 기능을 최적화하기 위해 SIMD 명령어를 어떻게 사용할 수 있습니까?

SIMD를 사용하여 atoi를 구현하는 방법

이 기사에서는 문자열 표현을 변환하는 atoi 함수를 구현하는 알고리즘을 살펴보겠습니다. SIMD(Single Instruction Multiple Data) 명령어를 사용하여 정수를 숫자 값으로 변환합니다. SIMD를 사용하면 여러 요소를 병렬로 처리하여 성능을 크게 향상시킬 수 있습니다.

알고리즘

제안된 알고리즘은 다음 단계로 구성됩니다.

1. 길이가 N인 벡터를 초기화합니다. 길이가 N인 벡터를 만듭니다. 여기서 N은 지원하려는 최대 자릿수입니다. 10의 거듭제곱을 내림차순으로 나타내는 값으로 벡터를 초기화합니다(예: [10^N, 10^(N-1), ..., 10^1]).
2. 각각 변환 버퍼의 문자를 정수로 변환: 입력 문자열의 각 문자를 해당 정수 값으로 변환하고 다른 문자에 저장합니다. 벡터.
3. 유효 숫자에 10의 거듭제곱을 곱합니다. 유효 숫자 벡터에서 각 요소를 가져와서 10의 거듭제곱 벡터에서 해당 요소와 곱합니다. 결과를 합산합니다. 이러한 곱셈을 통해 문자열의 숫자 값을 얻습니다.

구체적으로, 입력의 각 숫자에 대해 문자열:

• 48에서 ASCII 코드를 빼서 숫자 값(0~9)을 추출합니다.
• 숫자 값에 해당하는 10의 거듭제곱을 곱합니다.
• 이전에 계산된 합계에 결과를 추가합니다. 값.

구현 고려 사항

이 알고리즘을 SIMD 코드로 구현할 때 SIMD 명령의 고유한 병렬성을 활용하여 여러 숫자를 동시에 처리할 수 있습니다. 코드는 사용 중인 특정 SIMD 명령어 세트(예: SSE4.2, AVX2)에 맞게 최적화되어야 합니다.

잠재적 최적화:

더욱 최적화할 수 있습니다. 유효 숫자에 10의 거듭제곱을 곱하기 위한 별도의 루프가 필요하지 않으므로 이 알고리즘을 사용할 수 있습니다. 이는 "벡터"라는 기술을 사용하여 달성할 수 있습니다. 융합된 곱셈-덧셈을 이용한 인덱싱." 이 기술을 사용하면 단일 명령으로 인덱싱과 곱셈을 모두 수행하여 성능을 향상시킬 수 있습니다.

대안 제안

Peter Cordes가 의견에서 제안한 대로, 마지막 두 개의 add xor 명령어에 대한 대안은 imul(정수 곱하기) 명령어를 사용하는 것입니다. 이는 코드 크기와 성능 측면에서 더 효율적일 가능성이 있습니다.

인텔 구문을 사용하여 GNU 어셈블러에서 구현

다음은 알고리즘의 샘플 구현입니다. Intel의 GNU 어셈블러에서 구문:

.intel_syntax noprefix
.data
  .align 64
    ddqDigitRange: .byte  '0','9',0,0,0,0,0,0,0,0,0,0,0,0,0,0
    ddqShuffleMask:.byte  15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 
    ddqFactor1:    .word  1,10,100,1000, 1,10,100,1000  
    ddqFactor2:    .long  1,10000,100000000,0
.text    
_start:
   mov   esi, lpInputNumberString
   /* (**A**) indicate negative number in EDX */
   mov   eax, -1
   xor   ecx, ecx
   xor   edx, edx
   mov   bl,  byte ptr [esi]
   cmp   bl,  '-'
   cmove edx, eax
   cmp   bl,  '+'
   cmove ecx, eax
   sub   esi, edx
   sub   esi, ecx
   /* (**B**)remove leading zeros */
   xor   eax,eax               /* return value ZERO */
  remove_leading_zeros:
   inc   esi
   cmp   byte ptr [esi-1], '0'  /* skip leading zeros */
  je remove_leading_zeros
   cmp   byte ptr [esi-1], 0    /* catch empty string/number */
  je FINISH
   dec   esi
   /* check for valid digit-chars and invert from front to back */
   pxor      xmm2, xmm2         
   movdqa    xmm0, xmmword ptr [ddqDigitRange]
   movdqu    xmm1, xmmword ptr [esi]
   pcmpistri xmm0, xmm1, 0b00010100 /* (**C**) iim8=Unsigned bytes, Ranges, Negative Polarity(-), returns strlen() in ECX */
  jo FINISH             /* if first char is invalid return 0 - prevent processing empty string - 0 is still in EAX */
   mov al , '0'         /* value to subtract from chars */
   sub ecx, 16          /* len-16=negative to zero for shuffle mask */
   movd      xmm0, ecx
   pshufb    xmm0, xmm2 /* broadcast CL to all 16 BYTEs */
   paddb     xmm0, xmmword ptr [ddqShuffleMask] /* Generate permute mask for PSHUFB - all bytes < 0 have highest bit set means place gets zeroed */
   pshufb    xmm1, xmm0 /* (**D**) permute - now from highest to lowest BYTE are factors 10^0, 10^1, 10^2, ... */
   movd      xmm0, eax                         /* AL='0' from above */
   pshufb    xmm0, xmm2                        /* broadcast AL to XMM0 */
   psubusb   xmm1, xmm0                        /* (**1**) */
   movdqa    xmm0, xmm1
   punpcklbw xmm0, xmm2                        /* (**2**) */
   punpckhbw xmm1, xmm2
   pmaddwd   xmm0, xmmword ptr [ddqFactor1]    /* (**3**) */
   pmaddwd   xmm1, xmmword ptr [ddqFactor1]
   phaddd    xmm0, xmm1                        /* (**4**) */
   pmulld    xmm0, xmmword ptr [ddqFactor2]    /* (**5**) */
   pshufd    xmm1, xmm0, 0b11101110            /* (**6**) */
   paddd     xmm0, xmm1
   pshufd    xmm1, xmm0, 0b01010101            /* (**7**) */
   paddd     xmm0, xmm1
   movd      eax, xmm0
   /* negate if negative number */              
   add       eax, edx                          /* (**8**) */
   xor       eax, edx
  FINISH:
   /* EAX is return (u)int value */

결론

atoi 함수의 최적화된 SIMD 구현은 대량의 수치 데이터를 처리할 때 성능을 크게 향상시킬 수 있습니다. SIMD 명령어의 병렬 처리 기능을 활용하면 더 빠른 실행 시간을 달성하고 수치 계산을 더 효율적으로 처리할 수 있습니다.

위 내용은 atoi 기능을 최적화하기 위해 SIMD 명령어를 어떻게 사용할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!