La búsqueda de la implementación más rápida de Hamming Distance C

Quiero encontrar cuántos caracteres diferentes tienen dos cadenas de igual longitud. He encontrado que los algoritmos de xoring se consideran los más rápidos, pero devuelven la distancia expresada en bits. Quiero que los resultados se expresen en caracteres. Supongamos que “pet” y “pit” tienen la distancia 1 expresada en caracteres, pero ‘e’ e ‘i’ pueden tener dos bits diferentes, por lo que xoring devuelve 2.

La función que escribí es:

// na = length of both strings unsigned int HammingDistance(const char* a, unsigned int na, const char* b) { unsigned int num_mismatches = 0; while (na) { if (*a != *b) ++num_mismatches; --na; ++a; ++b; } return num_mismatches; } 

¿Podría ser más rápido? ¿Tal vez usar algunos comandos de nivel inferior o implementar un algoritmo diferente?

Sistema: Gcc 4.7.2 en Intel Xeon X5650

Gracias

Puede hacer que su comparación compare más bytes a la vez haciendo un operador bitwise en el tamaño entero nativo.

En su código, está comparando la igualdad de un byte a la vez, pero su CPU puede comparar al menos una palabra en un solo ciclo, y 8 bytes si es x86-64. Las capacidades de rendimiento exactas dependen de la architecture de la CPU, por supuesto.

Pero si avanzara a través de los dos punteros con un paso del tamaño de 8, seguramente podría ser más rápido en algunos escenarios. Cuando tiene que leer de las cadenas de la memoria principal, el tiempo de carga de la memoria realmente dominará el rendimiento. Pero si las cadenas están en la memoria caché de la CPU, es posible que pueda hacer un XOR e interpretar los resultados comprobando dónde se cambian los bits en el valor de 64 bits.

El conteo de los cubos que no son 0 se puede hacer con una variante del algoritmo SWAR a partir de 0x33333333 en lugar de 0x55555555.

Será más difícil trabajar con el algoritmo, ya que requerirá el uso de punteros uint64_t que tengan la alineación de memoria adecuada. Necesitará un preámbulo y una posdata que cubra los bytes restantes. Tal vez debería leer el ensamblado que el comstackdor produce y ver si no está haciendo algo más inteligente antes de intentar algo más complicado en el código.

En lugar de

 if (*a != *b) ++num_mismatches; 

esto sería más rápido en algunas architectures (con bytes de 8 bits) porque evita la twig:

 int bits = *a ^ *b; bits |= bits >> 4; bits |= bits >> 2; bits |= bits >> 1; num_mismatches += bits & 1; 

¿Qué tal el desenrollado de bucle?

 while (na >= 8){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); num_mismatches += (a[2] != b[2]); num_mismatches += (a[3] != b[3]); num_mismatches += (a[4] != b[4]); num_mismatches += (a[5] != b[5]); num_mismatches += (a[6] != b[6]); num_mismatches += (a[7] != b[7]); a += 8; b += 8; na -= 8; } if (na >= 4){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); num_mismatches += (a[2] != b[2]); num_mismatches += (a[3] != b[3]); a += 4; b += 4; na -= 4; } if (na >= 2){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); a += 2; b += 2; na -= 2; } if (na >= 1){ num_mismatches += (a[0] != b[0]); a += 1; b += 1; na -= 1; } 

Además, si sabe que hay largos tramos de caracteres iguales, puede convertir los punteros en long* y compararlos 4 a la vez, y solo si no es igual a los caracteres individuales. Este código se basa en que memset y memcpy son rápidos. Copia las cadenas en matrices long en 1) elimina los problemas de alineación, y 2) rellena las cadenas con ceros hasta un número entero de s long . Como compara cada par de s long , si no son iguales, lanza los punteros a char* y cuenta los caracteres desiguales. El bucle principal también podría ser desenrollado, similar al anterior.

 long la[BIG_ENOUGH]; long lb[BIG_ENOUGH]; memset(la, 0, sizeof(la)); memset(lb, 0, sizeof(lb)); memcpy(la, a, na); memcpy(lb, b, nb); int nla = (na + 3) & ~3; // assuming sizeof(long) = 4 long *pa = la, *pb = lb; while(nla >= 1){ if (pa[0] != pb[0]){ num_mismatches += (((char*)pa[0])[0] != ((char*)pb[0])[0]) + (((char*)pa[0])[1] != ((char*)pb[0])[1]) + (((char*)pa[0])[2] != ((char*)pb[0])[2]) + (((char*)pa[0])[3] != ((char*)pb[0])[3]) ; } pa += 1;pb += 1; nla -= 1; } 

Si las cadenas se rellenan con cero para que siempre tengan 32 bytes y sus direcciones estén alineadas con 16, podría hacer algo como esto: (código no probado ni perfilado)

 movdqa xmm0, [a] movdqa xmm1, [a + 16] pcmpeqb xmm0, [b] pcmpeqb xmm1, [b + 16] pxor xmm2, xmm2 psadbw xmm0, xmm2 psadbw xmm1, xmm2 pextrw ax, xmm0, 0 pextrw dx, xmm1, 0 add ax, dx movsx eax, ax neg eax 

Pero si las cuerdas suelen ser pequeñas, hace mucho trabajo innecesario y puede que no sea más rápido. Sin embargo, debería ser más rápido si las cadenas suelen ser de (casi) 32 bytes.


Edición: escribí esta respuesta antes de ver tu comentario actualizado: si las cadenas suelen ser tan pequeñas, esto probablemente no sea muy bueno. Sin embargo, una versión de 16 bytes podría ser (quizás) útil (ejecutar la segunda iteración de forma condicional, la twig para eso debería estar bien predicha ya que rara vez se tomará). Pero con estas cadenas cortas, el código normal es difícil de superar.

 movdqa xmm0, [a] pxor xmm1, xmm1 pcmpeqb xmm0, [b] psadbw xmm0, xmm1 pextrw ax, xmm0, 0 movsx eax, ax neg eax