caminho mais rápido para ver quantos bytes são iguais entre matrizes de comprimento fixo
https://stackoverflow.com/questions/116485
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho 2 baterias de 16 elementos (caracteres) que eu preciso para "comparar" e ver quantos elementos são iguais entre os dois.
Essa rotina vai ser usado milhões de vezes (uma corrida normal é de cerca de 60 ou 70 milhões de vezes), então eu preciso que ele seja o mais rápido possível. Eu estou trabalhando em C ++ (C ++ Builder 2007, para o registro)
Agora, eu tenho um simples:
matches += array1[0] == array2[0];
repetida 16 vezes (como criação de perfil parece ser 30% mais rápido do que fazê-lo com um loop)
Existe alguma outra forma que poderia trabalhar mais rápido?
Alguns dados sobre o meio ambiente e os dados em si:
- Eu estou usando C ++ Builder, que não tem nenhum otimizações de velocidade a ter em conta. Vou tentar, eventualmente com outro compilador, mas agora eu estou preso com esta.
- Os dados serão diferentes na maioria das vezes. 100% de dados igual é geralmente muito muito raro (talvez menos de 1%)
Solução
UPDATE:. Esta resposta foi modificada para fazer meus comentários coincidir com o código-fonte fornecido abaixo
Há uma otimização disponível se você tiver a capacidade de usar SSE2 e as instruções POPCNT.
16 bytes acontece a encaixar perfeitamente num registo SSE. Usando C ++ e montagem / intrínsecos, carregar as duas matrizes 16 bytes em registos XMM, e da CMP-los. Isso gera uma máscara de bits que representa a verdadeira condição falsa / do comparar. Em seguida, use uma instrução movmsk para carregar uma representação da máscara de bits em um registro de 86 bits; esta torna-se então um campo de bits, onde pode contar todos os 1s para determinar quantos valores verdade que você teve. Uma instrução POPCNT hardware pode ser uma maneira rápida de contar todos os 1s num registo.
Isto requer o conhecimento de montagem / intrinsics e SSE em particular. Você deve ser capaz de encontrar recursos da web para ambos.
Se você executar esse código em uma máquina que não suporta qualquer SSE2 ou POPCNT, você deve, em seguida, percorrer a matrizes e contar as diferenças com a sua abordagem de loop desenrolado.
Boa sorte
Edit: Desde que você indicou que você não sabia montagem, aqui está um código de exemplo para ilustrar a minha resposta:
#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;
}
Algumas notas: Esta função usa instruções SSE2 e uma instrução POPCNT introduzida no processador Phenom (que é a máquina que eu uso). Eu acredito que os processadores maioria dos recentes Intel com SSE4 também têm POPCNT. Esta função não verifica se há suporte instrução com CPUID; a função é indefinido se usado em um processador que não tem SSE2 ou POPCNT (você provavelmente terá uma instrução opcode inválido). Esse código de detecção é um segmento separado.
Eu não cronometrado este código; a razão que eu acho que é mais rápido é porque ele compara 16 bytes de cada vez, sem agência. Você deve modificar isso para ajustar o seu ambiente, e tempo a si mesmo para ver se ele funciona para você. Eu escrevi e testou este no VS2008 SP1.
SSE prefere dados que são alinhadas num limite de 16-byte natural; se você pode garantir que, em seguida, você deve obter melhorias de velocidade adicionais, e você pode alterar as _mm_loadu_si128 instruções para _mm_load_si128, o que requer alinhamento.
Outras dicas
A chave é fazer as comparações usando os maiores registrar seus suportes de CPU, então fallback para bytes, se necessário.
O código abaixo demonstra com o uso de inteiros de 4 bytes, mas se você estiver executando em uma arquitetura SIMD (qualquer chip Intel ou AMD moderna) você pode comparar as duas matrizes em uma instrução antes de cair de volta a um circuito baseado em inteiro. A maioria dos compiladores estes dias têm suporte intrínseco para os tipos de 128 bits para que não exigirá ASM.
(Note-se que para o SIMD comparações suas matrizes teria que ser de 16 bytes alinhados, e alguns processadores (por exemplo MIPS) exigiria as matrizes para ser de 4 bytes alinhados para as comparações baseadas em int.
por exemplo.
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];
}
}
}
Eu não consigo lembrar o que exatamente os suportes compilador MSVC para SIMD, mas você poderia fazer algo assim;
// 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
}
Se você tiver a capacidade de controlar a localização das matrizes, colocando um logo após o outro na memória, por exemplo, pode levá-los a ser carregado para o cache da CPU no primeiro acesso.
Depende da CPU e sua estrutura de cache e irá variar de uma máquina para outra.
Você pode ler sobre hierarquia de memória e cache na de Henessy & Patterson Arquitetura de Computadores: Uma Quantitative aproximar
Se precisar de pegada absoluta menor, eu iria com código de montagem. Eu não fiz isso em um tempo, mas eu aposto MMX (ou, mais provavelmente SSE2 / 3) têm instruções que podem permitir que você faça exatamente isso em poucas instruções.
Se partidas são um caso comum, em seguida, tente carregar os valores como 32 ints em vez de 16 bits para que você possa comparar 2 de uma só vez (e contá-lo como 2 partidas).
Se os dois valores de 32 bits são não o mesmo, então você terá que testá-los separadamente (e fora do valores de bits 16 superior e inferior).
O código será mais complexa, mas deve ser mais rápido.
Se você está direcionando um sistema de 64 bits, você poderia fazer o mesmo truque com 64 ints bits, e se você realmente quer empurrar o limite, em seguida, olhar para cair em assembler e usando as várias instruções baseadas em vetores que permitem que você trabalhe com 128 bits de uma vez.
opções do compilador mágicas irá variar o tempo muito. Em particular tornando-se gerar SSE vetorização provavelmente irá obter-lhe uma enorme aceleração.
Será que isso tem que ser independente de plataforma, ou será que este código sempre executados no mesmo tipo de CPU? Se você restringir-se ao moderno CPUs x86, você pode ser capaz de usar MMX instruções , que deverá permitir-lhe operar em uma matriz de 8 bytes em um pulso de clock. AFAIK, gcc permite embutir montagem em seu código C, e compilador da Intel (ICC) suporta intrínsecos, que são wrappers que permitem que você chamar instruções de montagem específicas diretamente. Outros conjuntos de instruções SIMD, como SSE, também pode ser útil para isso.
Há alguma conexão entre os valores nas matrizes? São alguns bytes mais propensos a ser os mesmos outros, então? Poderia haver alguma ordem intrínseca nos valores? Então você pode otimizar para o caso mais provável.
Se você explicar o que os dados realmente representa, em seguida, pode haver uma maneira totalmente diferente para representar os dados na memória que faria este tipo de força bruta comparar desnecessário. Cuidados para elaborar sobre o que os dados realmente representa ??
É mais rápido como um declaração?
matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;
Se escrever que 16 vezes é mais rápido do que um loop simples, então o compilador quer suga ou você não tem otimização ligado.
curta resposta:. Não há mais rápido a maneira, a menos que você faça operações vetoriais em hardware paralelo
Tente usar ponteiros em vez de matrizes:
p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.
Claro que você deve medir isso contra outras abordagens para ver qual é mais rápido.
E você tem certeza que essa rotina é um gargalo no seu processamento? Você realmente acelerar o desempenho do seu aplicativo como um todo, otimizando isso? Mais uma vez, apenas a medição dirá.
Existe alguma maneira você pode modificar a forma como as matrizes são armazenados? Comparando 1 byte de cada vez é extremamente lento, considerando que você provavelmente está usando um compilador de 32 bits. Em vez disso, se você armazenou os 16 bytes em 4 inteiros (32 bits) ou 2 longs (64 bits), você só precisa executar 4 ou 2 comparações respectivamente.
A questão a se perguntar é quanto é o custo de armazenar os dados como 4-inteiro ou 2-longas matrizes. Quantas vezes você precisa acessar os dados, etc.
Há sempre o bom e velho x86 instrução REPNE CMPS.
Um extra de otimização possível: se você está esperando que na maioria das vezes as matrizes são idênticos, então pode ser um pouco mais rápido para fazer um memcmp () como o primeiro passo, definindo '16' como a resposta se o teste retorna verdadeiro . Se é claro que se você não está esperando as matrizes para ser idênticos muitas vezes que faria apenas retardar as coisas.
