isdigit - string to int c++

¿Cómo implementar atoi usando SIMD? (2)

Me gustaría intentar escribir una implementación atoi usando las instrucciones SIMD, que se incluirán en RapidJSON (una biblioteca de lectura / RapidJSON C ++ JSON). Actualmente tiene algunas optimizaciones SSE2 y SSE4.2 en otros lugares.

Si se trata de una ganancia de velocidad, se pueden hacer múltiples resultados atoi en paralelo. Las cadenas provienen originalmente de un búfer de datos JSON, por lo que una función multi-atoi tendrá que hacer cualquier swizzling requerido.

El algoritmo que se me ocurrió es el siguiente:

Puedo inicializar un vector de longitud N de la siguiente manera: [10 ^ N..10 ^ 1]
Convierto cada carácter del búfer en un entero y los coloco en otro vector.
Tomo cada número en el vector de dígitos significativos y lo multiplico por el número correspondiente en el vector de números y sumo los resultados.

Estoy apuntando a arquitecturas x86 y x86-64.

Sé que AVX2 es compatible con tres operandos Fusionados-Sumados, así que podré realizar Sum = Number * Significant Digit + Sum.
Ahí es donde llegué hasta ahora.
¿Es correcto mi algoritmo? ¿Hay una mejor manera?
¿Existe una implementación de referencia para atoi usando algún conjunto de instrucciones SIMD?

Abordaría este problema así:

Inicialice el acumulador a 0.
Cargue los siguientes cuatro caracteres de la cadena en un registro SSE.
Resta el valor ''0'' de cada personaje.
Encuentre el primer valor en el vector cuyo valor sin signo es mayor que 9 .
Si se encontró un valor, desplace los componentes del vector hacia la derecha para que el valor encontrado en el paso anterior se haya desplazado.
Cargue un vector que contenga potencias de diez ( 1000 , 100 , 10 , 1 ) y multiplique por eso.
Calcule la suma de todas las entradas en el vector.
Multiplique el acumulador con un valor apropiado (dependiendo del número de cambios en el paso 5) y agregue el vector. Puede usar una instrucción FMA para eso, pero no sé si existe tal instrucción para enteros.
Si no se encontró un valor superior a 9 en el paso cuatro, vaya al paso 2.
Devuelve el acumulador.

Puede simplificar el algoritmo al poner a cero todas las entradas que comienzan con la incorrecta en el paso 5 en lugar de cambiar y luego dividir por una potencia apropiada de diez al final.

Tenga en cuenta que este algoritmo lee más allá del final de la cadena y, por lo tanto, no es un reemplazo atoi para atoi .

El algoritmo y su implementación están terminados ahora. Está completo y (moderadamente) probado ( actualizado para un uso de memoria menos constante y tolerando plus-char ).

Las propiedades de este código son las siguientes:

Funciona para int y uint , desde MIN_INT=-2147483648 hasta MAX_INT=2147483647 y desde MIN_UINT=0 hasta MAX_UINT=4294967295
Un carácter principal ''-'' indica un número negativo (como sensible), un carácter principal ''+'' se ignora
Los ceros iniciales (con o sin signo de caracteres) se ignoran
El desbordamiento se ignora: los números más grandes simplemente se envuelven
Las cadenas de longitud cero dan como resultado el valor 0 = -0
Los caracteres no válidos se reconocen y la conversión termina en el primer carácter no válido
Al menos 16 bytes después del último cero inicial deben ser accesibles y las posibles implicaciones de seguridad de la lectura después de que EOS se dejan a la persona que llama
Solo se necesita SSE4.2

Sobre esta implementación:

Este ejemplo de código se puede ejecutar con GNU Assembler ( as ) usando .intel_syntax noprefix al principio
La huella de datos para las constantes es de 64 bytes (XMM de 4 * 128 bits), lo que equivale a una línea de caché.
La huella del código es de 46 instrucciones con 51 micro-operaciones y 64 ciclos de latencia
Un bucle para eliminar los ceros iniciales, de lo contrario no hay saltos, excepto para el manejo de errores, así que ...
La complejidad del tiempo es O (1)

El enfoque del algoritmo:

- Pointer to number string is expected in ESI - Check if first char is ''-'', then indicate if negative number in EDX (**A**) - Check for leading zeros and EOS (**B**) - Check string for valid digits and get strlen() of valid chars (**C**) - Reverse string so that power of 10^0 is always at BYTE 15 10^1 is always at BYTE 14 10^2 is always at BYTE 13 10^3 is always at BYTE 12 10^4 is always at BYTE 11 ... and mask out all following chars (**D**) - Subtract saturated ''0'' from each of the 16 possible chars (**1**) - Take 16 consecutive byte-values and and split them to WORDs in two XMM-registers (**2**) P O N M L K J I | H G F E D C B A -> H G F E | D C B A (XMM0) P O N M | L K J I (XMM1) - Multiply each WORD by its place-value modulo 10000 (1,10,100,1000) (factors smaller then MAX_WORD, 4 factors per QWORD/halfXMM) (**2**) so we can horizontally combine twice before another multiply. The PMADDWD instruction can do this and the next step: - Horizontally add adjacent WORDs to DWORDs (**3**) H*1000+G*100 F*10+E*1 | D*1000+C*100 B*10+A*1 (XMM0) P*1000+O*100 N*10+M*1 | L*1000+K*100 J*10+I*1 (XMM1) - Horizontally add adjacent DWORDs from XMM0 and XMM1 to XMM0 (**4**) xmmDst[31-0] = xmm0[63-32] + xmm0[31-0] xmmDst[63-32] = xmm0[127-96] + xmm0[95-64] xmmDst[95-64] = xmm1[63-32] + xmm1[31-0] xmmDst[127-96] = xmm1[127-96] + xmm1[95-64] - Values in XMM0 are multiplied with the factors (**5**) P*1000+O*100+N*10+M*1 (DWORD factor 1000000000000 = too big for DWORD, but possibly useful for QWORD number strings) L*1000+K*100+J*10+I*1 (DWORD factor 100000000) H*1000+G*100+F*10+E*1 (DWORD factor 10000) D*1000+C*100+B*10+A*1 (DWORD factor 1) - The last step is adding these four DWORDs together with 2*PHADDD emulated by 2*(PSHUFD+PADDD) - xmm0[31-0] = xmm0[63-32] + xmm0[31-0] (**6**) xmm0[63-32] = xmm0[127-96] + xmm0[95-64] (the upper QWORD contains the same and is ignored) - xmm0[31-0] = xmm0[63-32] + xmm0[31-0] (**7**) - If the number is negative (indicated in EDX by 000...0=pos or 111...1=neg), negate it(**8**)

Y la implementación de muestra en GNU Assembler con sintaxis de Intel:

.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 */

El resultado del Análisis de rendimiento Intel-IACA para Haswell de 32 bits:

Throughput Analysis Report -------------------------- Block Throughput: 16.10 Cycles Throughput Bottleneck: InterIteration Port Binding In Cycles Per Iteration: --------------------------------------------------------------------------------------- | Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | --------------------------------------------------------------------------------------- | Cycles | 9.5 0.0 | 10.0 | 4.5 4.5 | 4.5 4.5 | 0.0 | 11.1 | 11.4 | 0.0 | --------------------------------------------------------------------------------------- N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0) D - Data fetch pipe (on ports 2 and 3), CP - on a critical path F - Macro Fusion with the previous instruction occurred * - instruction micro-ops not bound to a port ^ - Micro Fusion happened # - ESP Tracking sync uop was issued @ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected ! - instruction not supported, was not accounted in Analysis | Num Of | Ports pressure in cycles | | | Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | | --------------------------------------------------------------------------------- | 0* | | | | | | | | | | xor eax, eax | 0* | | | | | | | | | | xor ecx, ecx | 0* | | | | | | | | | | xor edx, edx | 1 | | 0.1 | | | | | 0.9 | | | dec eax | 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | CP | mov bl, byte ptr [esi] | 1 | | | | | | | 1.0 | | CP | cmp bl, 0x2d | 2 | 0.1 | 0.2 | | | | | 1.8 | | CP | cmovz edx, eax | 1 | 0.1 | 0.5 | | | | | 0.4 | | CP | cmp bl, 0x2b | 2 | 0.5 | 0.2 | | | | | 1.2 | | CP | cmovz ecx, eax | 1 | 0.2 | 0.5 | | | | | 0.2 | | CP | sub esi, edx | 1 | 0.2 | 0.5 | | | | | 0.3 | | CP | sub esi, ecx | 0* | | | | | | | | | | xor eax, eax | 1 | 0.3 | 0.1 | | | | | 0.6 | | CP | inc esi | 2^ | 0.3 | | 0.5 0.5 | 0.5 0.5 | | | 0.6 | | | cmp byte ptr [esi-0x1], 0x30 | 0F | | | | | | | | | | jz 0xfffffffb | 2^ | 0.6 | | 0.5 0.5 | 0.5 0.5 | | | 0.4 | | | cmp byte ptr [esi-0x1], 0x0 | 0F | | | | | | | | | | jz 0x8b | 1 | 0.1 | 0.9 | | | | | | | CP | dec esi | 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | | movdqa xmm0, xmmword ptr [0x80492f0] | 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | CP | movdqu xmm1, xmmword ptr [esi] | 0* | | | | | | | | | | pxor xmm2, xmm2 | 3 | 2.0 | 1.0 | | | | | | | CP | pcmpistri xmm0, xmm1, 0x14 | 1 | | | | | | | 1.0 | | | jo 0x6e | 1 | | 0.4 | | | | 0.1 | 0.5 | | | mov al, 0x30 | 1 | 0.1 | 0.5 | | | | 0.1 | 0.3 | | CP | sub ecx, 0x10 | 1 | | | | | | 1.0 | | | CP | movd xmm0, ecx | 1 | | | | | | 1.0 | | | CP | pshufb xmm0, xmm2 | 2^ | | 1.0 | 0.5 0.5 | 0.5 0.5 | | | | | CP | paddb xmm0, xmmword ptr [0x80492c0] | 1 | | | | | | 1.0 | | | CP | pshufb xmm1, xmm0 | 1 | | | | | | 1.0 | | | | movd xmm0, eax | 1 | | | | | | 1.0 | | | | pshufb xmm0, xmm2 | 1 | | 1.0 | | | | | | | CP | psubusb xmm1, xmm0 | 0* | | | | | | | | | CP | movdqa xmm0, xmm1 | 1 | | | | | | 1.0 | | | CP | punpcklbw xmm0, xmm2 | 1 | | | | | | 1.0 | | | | punpckhbw xmm1, xmm2 | 2^ | 1.0 | | 0.5 0.5 | 0.5 0.5 | | | | | CP | pmaddwd xmm0, xmmword ptr [0x80492d0] | 2^ | 1.0 | | 0.5 0.5 | 0.5 0.5 | | | | | | pmaddwd xmm1, xmmword ptr [0x80492d0] | 3 | | 1.0 | | | | 2.0 | | | CP | phaddd xmm0, xmm1 | 3^ | 2.0 | | 0.5 0.5 | 0.5 0.5 | | | | | CP | pmulld xmm0, xmmword ptr [0x80492e0] | 1 | | | | | | 1.0 | | | CP | pshufd xmm1, xmm0, 0xee | 1 | | 1.0 | | | | | | | CP | paddd xmm0, xmm1 | 1 | | | | | | 1.0 | | | CP | pshufd xmm1, xmm0, 0x55 | 1 | | 1.0 | | | | | | | CP | paddd xmm0, xmm1 | 1 | 1.0 | | | | | | | | CP | movd eax, xmm0 | 1 | | | | | | | 1.0 | | CP | add eax, edx | 1 | | | | | | | 1.0 | | CP | xor eax, edx Total Num Of Uops: 51

El resultado del Análisis de latencia Intel-IACA para Haswell de 32 bits:

Latency Analysis Report --------------------------- Latency: 64 Cycles N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0) D - Data fetch pipe (on ports 2 and 3), CP - on a critical path F - Macro Fusion with the previous instruction occurred * - instruction micro-ops not bound to a port ^ - Micro Fusion happened # - ESP Tracking sync uop was issued @ - Intel(R) AVX to Intel(R) SSE code switch, dozens of cycles penalty is expected ! - instruction not supported, was not accounted in Analysis The Resource delay is counted since all the sources of the instructions are ready and until the needed resource becomes available | Inst | Resource Delay In Cycles | | | Num | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | FE | | ------------------------------------------------------------------------- | 0 | | | | | | | | | | | xor eax, eax | 1 | | | | | | | | | | | xor ecx, ecx | 2 | | | | | | | | | | | xor edx, edx | 3 | | | | | | | | | | | dec eax | 4 | | | | | | | | | 1 | CP | mov bl, byte ptr [esi] | 5 | | | | | | | | | | CP | cmp bl, 0x2d | 6 | | | | | | | | | | CP | cmovz edx, eax | 7 | | | | | | | | | | CP | cmp bl, 0x2b | 8 | | | | | | | 1 | | | CP | cmovz ecx, eax | 9 | | | | | | | | | | CP | sub esi, edx | 10 | | | | | | | | | | CP | sub esi, ecx | 11 | | | | | | | | | 3 | | xor eax, eax | 12 | | | | | | | | | | CP | inc esi | 13 | | | | | | | | | | | cmp byte ptr [esi-0x1], 0x30 | 14 | | | | | | | | | | | jz 0xfffffffb | 15 | | | | | | | | | | | cmp byte ptr [esi-0x1], 0x0 | 16 | | | | | | | | | | | jz 0x8b | 17 | | | | | | | | | | CP | dec esi | 18 | | | | | | | | | 4 | | movdqa xmm0, xmmword ptr [0x80492f0] | 19 | | | | | | | | | | CP | movdqu xmm1, xmmword ptr [esi] | 20 | | | | | | | | | 5 | | pxor xmm2, xmm2 | 21 | | | | | | | | | | CP | pcmpistri xmm0, xmm1, 0x14 | 22 | | | | | | | | | | | jo 0x6e | 23 | | | | | | | | | 6 | | mov al, 0x30 | 24 | | | | | | | | | | CP | sub ecx, 0x10 | 25 | | | | | | | | | | CP | movd xmm0, ecx | 26 | | | | | | | | | | CP | pshufb xmm0, xmm2 | 27 | | | | | | | | | 7 | CP | paddb xmm0, xmmword ptr [0x80492c0] | 28 | | | | | | | | | | CP | pshufb xmm1, xmm0 | 29 | | | | | | 1 | | | | | movd xmm0, eax | 30 | | | | | | 1 | | | | | pshufb xmm0, xmm2 | 31 | | | | | | | | | | CP | psubusb xmm1, xmm0 | 32 | | | | | | | | | | CP | movdqa xmm0, xmm1 | 33 | | | | | | | | | | CP | punpcklbw xmm0, xmm2 | 34 | | | | | | | | | | | punpckhbw xmm1, xmm2 | 35 | | | | | | | | | 9 | CP | pmaddwd xmm0, xmmword ptr [0x80492d0] | 36 | | | | | | | | | 9 | | pmaddwd xmm1, xmmword ptr [0x80492d0] | 37 | | | | | | | | | | CP | phaddd xmm0, xmm1 | 38 | | | | | | | | | 10 | CP | pmulld xmm0, xmmword ptr [0x80492e0] | 39 | | | | | | | | | | CP | pshufd xmm1, xmm0, 0xee | 40 | | | | | | | | | | CP | paddd xmm0, xmm1 | 41 | | | | | | | | | | CP | pshufd xmm1, xmm0, 0x55 | 42 | | | | | | | | | | CP | paddd xmm0, xmm1 | 43 | | | | | | | | | | CP | movd eax, xmm0 | 44 | | | | | | | | | | CP | add eax, edx | 45 | | | | | | | | | | CP | xor eax, edx Resource Conflict on Critical Paths: ----------------------------------------------------------------- | Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | ----------------------------------------------------------------- | Cycles | 0 0 | 0 | 0 0 | 0 0 | 0 | 0 | 1 | 0 | ----------------------------------------------------------------- List Of Delays On Critical Paths ------------------------------- 6 --> 8 1 Cycles Delay On Port6

Un manejo alternativo sugerido en los comentarios de Peter Cordes es reemplazar las dos últimas instrucciones add+xor por un imul . Es probable que esta concentración de OpCodes sea superior. Lamentablemente, IACA no admite esa instrucción y lanza un ! - instruction not supported, was not accounted in Analysis ! - instruction not supported, was not accounted in Analysis comentario de ! - instruction not supported, was not accounted in Analysis . Sin embargo, aunque me gusta la reducción de OpCodes y la reducción de (2uops, 2c latencia) a (1 uop, 3c latencia - "peor latencia, pero aún un m-op en AMD"), prefiero dejarlo al implementador que forma de elegir No he comprobado si el siguiente código es suficiente para analizar cualquier número. Solo se menciona para completar y pueden ser necesarias modificaciones de código en otras partes (especialmente el manejo de números positivos).

La alternativa puede ser reemplazar las dos últimas líneas con:

... /* negate if negative number */ imul eax, edx FINISH: /* EAX is return (u)int value */