La forma más rápida de ver cuántos bytes son iguales entre matrices de longitud fija

StackOverflow https://stackoverflow.com/questions/116485

  •  02-07-2019
  •  | 
  •  

Pregunta

Tengo 2 matrices de 16 elementos (caracteres) que necesito "comparar" y ver cuántos elementos son iguales entre los dos.

Esta rutina se utilizará millones de veces (una ejecución habitual es unas 60 o 70 millones de veces), por lo que necesito que sea lo más rápida posible.Estoy trabajando en C++ (C++Builder 2007, para que conste)

Ahora mismo tengo un sencillo:

matches += array1[0] == array2[0];

repetido 16 veces (como perfilado parece ser un 30% más rápido que hacerlo con un bucle for)

¿Hay alguna otra forma que pueda funcionar más rápido?

Algunos datos sobre el medio ambiente y los datos en sí:

  • Estoy usando C++Builder, que no tiene optimizaciones de velocidad a tener en cuenta.Eventualmente lo intentaré con otro compilador, pero ahora mismo estoy estancado con este.
  • Los datos serán diferentes la mayoría de las veces.Los datos 100 % iguales suelen ser muy, muy raros (quizás menos del 1 %)
¿Fue útil?

Solución

ACTUALIZAR:Esta respuesta se ha modificado para que mis comentarios coincidan con el código fuente que se proporciona a continuación.

Hay una optimización disponible si tiene la capacidad de utilizar SSE2 y instrucciones popcnt.

Resulta que 16 bytes encajan muy bien en un registro SSE.Usando c++ y ensamblador/intrínseco, cargue las dos matrices de 16 bytes en registros xmm y cmp.Esto genera una máscara de bits que representa la condición verdadero/falso de la comparación.Luego usa una instrucción movmsk para cargar una representación de bits de la máscara de bits en un registro x86;esto luego se convierte en un campo de bits donde puedes contar todos los unos para determinar cuántos valores verdaderos tenías.Una instrucción popcnt de hardware puede ser una forma rápida de contar todos los unos en un registro.

Esto requiere conocimientos de ensamblaje/intrínsecos y SSE en particular.Debería poder encontrar recursos web para ambos.

Si ejecuta este código en una máquina que no admite SSE2 ni popcnt, debe iterar a través de las matrices y contar las diferencias con su enfoque de bucle desenrollado.

Buena suerte

Editar:Como indicó que no sabía ensamblador, aquí hay un código de muestra para ilustrar mi respuesta:

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

Algunas notas:Esta función utiliza instrucciones SSE2 y una instrucción popcnt introducida en el procesador Phenom (esa es la máquina que uso).Creo que los procesadores Intel más recientes con SSE4 también tienen popcnt.Esta función no comprueba la compatibilidad de instrucciones con CPUID;la función no está definida si se usa en un procesador que no tiene SSE2 o popcnt (probablemente obtendrá una instrucción de código de operación no válida).Ese código de detección es un hilo separado.

No he cronometrado este código;La razón por la que creo que es más rápido es porque compara 16 bytes a la vez, sin ramas.Debe modificar esto para adaptarlo a su entorno y cronometrarlo usted mismo para ver si funciona para usted.Escribí y probé esto en VS2008 SP1.

SSE prefiere datos alineados en un límite natural de 16 bytes;Si puede garantizar eso, entonces debería obtener mejoras de velocidad adicionales y puede cambiar las instrucciones _mm_loadu_si128 a _mm_load_si128, que requiere alineación.

Otros consejos

La clave es hacer las comparaciones utilizando el registro más grande que admita su CPU y luego recurrir a bytes si es necesario.

El siguiente código demuestra el uso de números enteros de 4 bytes, pero si está ejecutando una arquitectura SIMD (cualquier chip Intel o AMD moderno), puede comparar ambas matrices en una instrucción antes de recurrir a un bucle basado en números enteros.La mayoría de los compiladores hoy en día tienen soporte intrínseco para tipos de 128 bits, por lo que NO requerirán ASM.

(Tenga en cuenta que para las comparaciones SIMD sus matrices tendrían que estar alineadas con 16 bytes, y algunos procesadores (por ejemplo, MIPS) requerirían que las matrices estuvieran alineadas con 4 bytes para las comparaciones basadas en int.

P.ej.

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

No recuerdo qué es exactamente lo que admite el compilador MSVC para SIMD, pero podrías hacer algo como;

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}

Si tiene la capacidad de controlar la ubicación de las matrices, colocando una tras otra en la memoria, por ejemplo, es posible que se carguen en la memoria caché de la CPU en el primer acceso.

Depende de la CPU y de su estructura de caché y variará de una máquina a otra.

Puede leer sobre la jerarquía de memoria y el caché en Arquitectura informática de Henessy y Patterson:Un enfoque cuantitativo

Si necesita el menor espacio posible, utilizaría el código ensamblador.No he hecho esto desde hace tiempo, pero apuesto a que MMX (o más probablemente SSE2/3) tiene instrucciones que pueden permitirte hacer exactamente eso en muy pocas instrucciones.

Si las coincidencias son el caso común, intente cargar los valores como enteros de 32 bits en lugar de 16 para poder comparar 2 de una sola vez (y contarlos como 2 coincidencias).

Si los dos valores de 32 bits son no lo mismo, entonces tendrás que probarlos por separado (Y los valores superior e inferior de 16 bits).

El código será más complejo, pero debería ser más rápido.

Si está apuntando a un sistema de 64 bits, puede hacer el mismo truco con entradas de 64 bits, y si realmente desea superar el límite, considere ingresar al ensamblador y usar las diversas instrucciones basadas en vectores que le permitirían trabajar con 128 bits. En seguida.

Las opciones del compilador mágico variarán mucho en el tiempo.En particular, generar vectorización SSE probablemente le brindará una gran aceleración.

¿Tiene que ser independiente de la plataforma o este código siempre se ejecutará en el mismo tipo de CPU?Si se limita a las CPU x86 modernas, es posible que pueda utilizar mmx instrucciones, que deberían permitirle operar en una matriz de 8 bytes en un tic de reloj.AFAIK, gcc le permite incrustar ensamblaje en su código C, y el compilador de Intel (icc) admite intrínsecos, que son contenedores que le permiten llamar instrucciones de ensamblaje específicas directamente.Otros conjuntos de instrucciones SIMD, como SSE, también pueden resultar útiles para esto.

¿Existe alguna conexión entre los valores de las matrices?¿Es más probable que algunos bytes sean iguales que otros?¿Podría haber algún orden intrínseco en los valores?Entonces podrías optimizar para el caso más probable.

Si explica qué representan realmente los datos, entonces podría haber una forma totalmente diferente de representar los datos en la memoria que haría innecesario este tipo de comparación de fuerza bruta.¿Le importaría explicar qué representan realmente los datos?

¿Es más rápido como una sola declaración?

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;

Si escribir eso 16 veces es más rápido que un simple bucle, entonces tu compilador apesta o no tienes la optimización activada.

Respuesta corta:No existe una forma más rápida, a menos que realice operaciones vectoriales en hardware paralelo.

Intente usar punteros en lugar de matrices:

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

Por supuesto, debes comparar esto con otros enfoques para ver cuál es el más rápido.

¿Y estás seguro de que esta rutina es un cuello de botella en tu procesamiento?¿Realmente acelera el rendimiento de su aplicación en su conjunto al optimizar esto?Una vez más, sólo la medición lo dirá.

¿Hay alguna manera de modificar la forma en que se almacenan las matrices?Comparar 1 byte a la vez es extremadamente lento considerando que probablemente estés usando un compilador de 32 bits.En cambio, si almacenó sus 16 bytes en 4 números enteros (32 bits) o 2 largos (64 bits), solo necesitará realizar 4 o 2 comparaciones respectivamente.

La pregunta que debe hacerse es cuánto cuesta almacenar los datos en matrices de 4 números enteros o de 2 longitudes.¿Con qué frecuencia necesita acceder a los datos, etc.?

Siempre existe la vieja instrucción x86 REPNE CMPS.

Una posible optimización adicional:Si espera que la mayor parte del tiempo las matrices sean idénticas, entonces podría ser un poco más rápido realizar memcmp() como primer paso, estableciendo '16' como respuesta si la prueba devuelve verdadero.Por supuesto, si no espera que las matrices sean idénticas con mucha frecuencia, eso solo ralentizaría las cosas.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top