c++ - tamaño - La forma más rápida de ver cuántos bytes son iguales entre matrices de longitud fija

solidity tutorial español pdf

Question

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

Esta rutina se usará millones de veces (una ejecución habitual es de 60 o 70 millones de veces), así que necesito que sea lo más rápido posible. Estoy trabajando en C ++ (C ++ Builder 2007, para el registro)

En este momento, tengo un simple:

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

repite 16 veces (ya que el perfilado parece ser un 30% más rápido que hacerlo con un ciclo for)

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

Algunos datos sobre el entorno y los datos en sí:

• Estoy usando C ++ Builder, que no tiene ninguna optimización de velocidad para tener en cuenta. Eventualmente intentaré con otro compilador, pero ahora estoy atascado con este.
• Los datos serán diferentes la mayoría de las veces. El 100% de datos iguales es usualmente muy raro (quizás menos del 1%)

Answer 1

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

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

Answer 2

¿Esto 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 las instrucciones MMX , que le permitirán operar en una matriz de 8 bytes en una marca de un reloj. AFAIK, gcc le permite incrustar el ensamblado en su código C, y el compilador de Intel (icc) admite intrínsecos, que son envoltorios que le permiten llamar instrucciones de ensamblaje específicas directamente. Otros conjuntos de instrucciones SIMD, como SSE, también pueden ser útiles para esto.

Answer 3

¿Hay alguna conexión entre los valores en 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.

Answer 4

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

La pregunta que debe hacerse es cuánto es el costo de almacenar los datos como matrices de 4 o 2 enteros. ¿Con qué frecuencia necesita acceder a los datos, etc.

Answer 5

Intente utilizar punteros en lugar de matrices:

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

Por supuesto, debe medir esto contra 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 como un todo optimizando esto? De nuevo, solo la medición dirá.

Answer 6

La clave es hacer las comparaciones usando el registro más grande que admita tu CPU, luego recurrir a los bytes si es necesario.

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

(Tenga en cuenta que para las comparaciones SIMD sus matrices deberían estar alineadas en 16 bytes, y algunos procesadores (por ejemplo, MIPS) requerirían que las matrices estén alineadas en 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 el compilador MSVC admite para SIMD, pero podría 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
}

Answer 7

Las opciones mágicas del compilador variarán mucho el tiempo. En particular, hacer que genere vectorización SSE probablemente te acelerará enormemente.

Answer 8

Si escribir eso 16 veces es más rápido que un bucle simple, entonces su compilador es una mierda o no tiene la optimización activada.

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

Answer 9

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

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

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

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

Answer 10

Si necesita la huella más baja absoluta, me gustaría ir con el código de ensamblaje. No he hecho esto por un tiempo, pero apuesto a que MMX (o más probablemente SSE2 / 3) tiene instrucciones que pueden permitirle hacer exactamente eso en muy pocas instrucciones.

Answer 11

Si tiene la capacidad de controlar la ubicación de las matrices, por ejemplo, colocar una detrás de la otra en la memoria, podría hacer que se carguen en la memoria caché de la CPU en el primer acceso.

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

Puede leer sobre jerarquía de memoria y caché en Henessy & Patterson''s Computer Architecture: Un enfoque cuantitativo

Answer 12

Siempre está la buena instrucción x86 REPNE CMPS.

Answer 13

Una optimización posible adicional: si está esperando que la mayoría de las veces las matrices sean idénticas, entonces podría ser un poco más rápido hacer un memcmp () como primer paso, estableciendo ''16'' como respuesta si la prueba devuelve verdadero. Por supuesto, si no espera que las matrices sean idénticas muy a menudo, eso solo desaceleraría las cosas.

Answer 14

ACTUALIZACIÓN: esta respuesta se ha modificado para que mis comentarios coincidan con el código fuente proporcionado a continuación.

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

16 bytes encajan muy bien en un registro SSE. Usando c ++ y assembly / intrinsics, cargue las dos matrices de 16 bytes en xmm registers, y cmp them. Esto genera una máscara de bits que representa la condición verdadero / falso de la comparación. A continuación, utiliza una instrucción de movmsk para cargar una representación de bit de la máscara de bits en un registro x86; esto se convierte en un campo de bit donde puedes contar todos los 1 para determinar cuántos valores verdaderos tienes. Una instrucción de hardware emergente puede ser una forma rápida de contar todos los 1 en un registro.

Esto requiere conocimiento 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 o popcnt, debe recorrer las matrices y contar las diferencias con su enfoque de ciclo desenrollado.

Buena suerte

Editar: Como indicaste que no sabías ensamblar, 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 usa 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 verifica el soporte 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 sincronizado 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 sucursales. Debe modificar esto para adaptarlo a su entorno y cronometrarlo 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, lo que requiere una alineación.

Answer 15

Si explica qué representan realmente los datos, entonces podría haber una forma totalmente diferente de representar los datos en la memoria que harían innecesario comparar este tipo de fuerza bruta. ¿Te importa explicar qué representan realmente los datos?