Encontrar rapidamente se um valor está presente em uma matriz C?

124

Eu tenho um aplicativo incorporado com um ISR de tempo crítico que precisa percorrer uma matriz de tamanho 256 (de preferência 1024, mas 256 é o mínimo) e verificar se um valor corresponde ao conteúdo das matrizes. A boolserá definido como true, este é o caso.

O microcontrolador é um núcleo NXP LPC4357, ARM Cortex M4, e o compilador é GCC. Eu já combinei o nível de otimização 2 (3 é mais lento) e coloquei a função na RAM, em vez do flash. Também uso aritmética de ponteiro e um forloop, que faz uma contagem decrescente em vez de para cima (verificar se i!=0é mais rápido do que verificar se i<256). Em suma, acabo com uma duração de 12,5 µs, que deve ser reduzida drasticamente para ser viável. Este é o código (pseudo) que eu uso agora:

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

Qual seria a maneira mais rápida de fazer isso? O uso de montagem embutida é permitido. Outros truques 'menos elegantes' também são permitidos.

Wlamers
fonte
28
Existe alguma maneira de armazenar o valor na matriz de maneira diferente? Se você pode ordená-los, uma pesquisa binária certamente será mais rápida. Se os dados a serem armazenados e pesquisados ​​estiverem dentro de um determinado intervalo, eles poderão ser representáveis ​​com um mapa de bits etc.
Remo.D
20
@BitBank: você ficaria surpreso com o quanto os compiladores melhoraram nas últimas três décadas. O ARM é especialmente amigável ao compilador. E eu sei para um fato que a ARM no GCC pode emitir instruções de múltipla carga (desde 2009 pelo menos)
MSalters
8
pergunta incrível, as pessoas esquecem que existem casos do mundo real em que o desempenho é importante. muitas vezes perguntas como esta são respondidas com "stl uso justo"
Kik
14
O título "... iterar através de uma matriz" é enganoso, pois na verdade você está simplesmente procurando por um determinado valor. Iterar sobre uma matriz implica que algo deve ser feito em cada entrada. A classificação, se o custo puder ser amortizado em muitas pesquisas, é de fato uma abordagem eficiente, independente dos problemas de implementação do idioma.
hardmath
8
Tem certeza de que não pode simplesmente usar uma pesquisa binária ou uma tabela de hash? Uma pesquisa binária por 256 itens == 8 comparações. Uma tabela de hash == 1 salto em média (ou 1 salto no máximo, se você tiver um hash perfeito). Você deve recorrer à otimização de montagem somente depois de 1) ter um algoritmo de pesquisa decente ( O(1)ou O(logN)comparado com O(N)) e 2) definir o perfil como gargalo.
Groo

Respostas:

105

Em situações em que o desempenho é de extrema importância, o compilador C provavelmente não produzirá o código mais rápido comparado ao que você pode fazer com a linguagem assembly ajustada manualmente. Costumo seguir o caminho de menor resistência - para rotinas pequenas como essa, apenas escrevo código ASM e tenho uma boa idéia de quantos ciclos serão necessários para executar. Você pode mexer no código C e fazer com que o compilador gere uma boa saída, mas pode acabar perdendo muito tempo ajustando a saída dessa maneira. Os compiladores (especialmente da Microsoft) percorreram um longo caminho nos últimos anos, mas ainda não são tão inteligentes quanto o compilador entre seus ouvidos, porque você está trabalhando em uma situação específica e não apenas em um caso geral. O compilador pode não fazer uso de determinadas instruções (por exemplo, LDM) que podem acelerar isso, e é improvável que seja inteligente o suficiente para desenrolar o loop. Aqui está uma maneira de fazê-lo, que incorpora as três idéias que mencionei no meu comentário: Desenrolamento de loop, pré-busca de cache e uso da instrução de carregamento múltiplo (ldm). A contagem do ciclo de instruções chega a cerca de 3 relógios por elemento da matriz, mas isso não leva em consideração os atrasos de memória.

Teoria da operação: o design da CPU do ARM executa a maioria das instruções em um ciclo de clock, mas as instruções são executadas em um pipeline. Os compiladores C tentarão eliminar os atrasos do pipeline intercalando outras instruções no meio. Quando apresentado com um loop restrito como o código C original, o compilador terá dificuldade em ocultar os atrasos porque o valor lido da memória deve ser comparado imediatamente. Meu código abaixo alterna entre 2 conjuntos de 4 registros para reduzir significativamente os atrasos da própria memória e o pipeline que busca os dados. Em geral, ao trabalhar com grandes conjuntos de dados e seu código não usar a maioria ou todos os registros disponíveis, você não está obtendo o desempenho máximo.

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

Atualização: Há muitos céticos nos comentários que pensam que minha experiência é anedótica / sem valor e requer provas. Usei o GCC 4.8 (do Android NDK 9C) para gerar a seguinte saída com a otimização -O2 (todas as otimizações ativadas, incluindo desenrolamento de loop ). Eu compilei o código C original apresentado na pergunta acima. Aqui está o que o GCC produziu:

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

A saída do GCC não apenas desenrola o loop, mas também desperdiça um relógio em uma paralisação após o LDR. Requer pelo menos 8 relógios por elemento da matriz. É bom usar o endereço para saber quando sair do loop, mas todas as coisas mágicas que os compiladores são capazes de fazer não são encontradas em nenhum lugar neste código. Não executei o código na plataforma de destino (não possuo uma), mas qualquer pessoa com experiência no desempenho de código do ARM pode ver que meu código é mais rápido.

Atualização 2: dei ao Visual Studio 2013 SP2 da Microsoft a chance de fazer melhor com o código. Ele foi capaz de usar as instruções NEON para vetorizar minha inicialização de matriz, mas a pesquisa de valor linear, conforme escrita pelo OP, foi semelhante ao que o GCC gerou (renomeei os rótulos para torná-los mais legíveis):

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

Como eu disse, não possuo o hardware exato do OP, mas testarei o desempenho em uma nVidia Tegra 3 e Tegra 4 das 3 versões diferentes e publicarei os resultados aqui em breve.

Atualização 3: executei meu código e o código ARM compilado da Microsoft em um Tegra 3 e Tegra 4 (Surface RT, Surface RT 2). Eu executei 1000000 iterações de um loop que não consegue encontrar uma correspondência, para que tudo fique em cache e seja fácil de medir.

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns  

Nos dois casos, meu código é executado quase duas vezes mais rápido. A maioria das CPUs ARM modernas provavelmente fornecerá resultados semelhantes.

BitBank
fonte
13
@ LưuVĩnhPhúc - isso geralmente é verdade, mas os ISRs restritos são uma das maiores exceções, pois você geralmente sabe muito mais do que o compilador.
sapi 4/09/14
47
Advogado do diabo: existe alguma evidência quantitativa de que esse código é mais rápido?
Oliver Charlesworth 4/04
11
@BitBank: Isso não é bom o suficiente. Você precisa fazer backup de suas reivindicações com provas .
Lightness Races in Orbit
13
Eu aprendi minha lição anos atrás. Criei um loop interno otimizado incrível para uma rotina de gráficos em um Pentium, usando os tubos U e V da melhor maneira possível. Consegui reduzir para 6 ciclos de clock por loop (calculado e medido) e fiquei muito orgulhosa de mim mesma. Quando eu testei contra a mesma coisa escrita em C, o C foi mais rápido. Eu nunca escrevi outra linha de assembler da Intel novamente.
Rocketmagnet
14
"céticos nos comentários que acham que minha experiência é anedótica / sem valor e exigem provas." Não tome seus comentários excessivamente negativamente. Mostrar a prova apenas torna sua ótima resposta muito melhor.
Cody Gray
87

Existe um truque para otimizá-lo (uma vez me perguntaram isso em uma entrevista de emprego):

  • Se a última entrada na matriz tiver o valor que você está procurando, retorne true
  • Escreva o valor que você está procurando na última entrada na matriz
  • Itere a matriz até encontrar o valor que você está procurando
  • Se você o encontrou antes da última entrada na matriz, retorne true
  • Retorna falso

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

Isso gera uma ramificação por iteração em vez de duas ramificações por iteração.


ATUALIZAR:

Se você tiver permissão para alocar a matriz SIZE+1, poderá se livrar da parte "última entrada de troca":

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

Você também pode se livrar da aritmética adicional incorporada theArray[i], usando o seguinte:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

Se o compilador ainda não o aplicar, esta função o fará com certeza. Por outro lado, pode ser mais difícil para o otimizador desenrolar o loop, portanto, você precisará verificar se no código de montagem gerado ...

barak manos
fonte
2
@ratchetfreak: O OP não fornece detalhes sobre como, onde e quando esse array é alocado e inicializado, por isso dei uma resposta que não depende disso.
Barak manos
3
A matriz está na RAM, mas as gravações não são permitidas.
wlamers
1
legal, mas a matriz não é mais const, o que torna isso não seguro para threads. Parece um preço alto a pagar.
EOF
2
@EOF: Onde foi constmencionado na pergunta?
Barak manos
4
@barakmanos: Se eu passar uma matriz e um valor para você, e perguntar se o valor está na matriz, normalmente não presumo que você esteja modificando a matriz. A pergunta original não menciona constnem tópicos, mas acho justo mencionar essa ressalva.
EOF
62

Você está pedindo ajuda para otimizar seu algoritmo, o que pode levá-lo ao montador. Mas o seu algoritmo (uma pesquisa linear) não é tão inteligente, então você deve considerar mudar seu algoritmo. Por exemplo:

Função hash perfeita

Se seus 256 valores "válidos" forem estáticos e conhecidos em tempo de compilação, você poderá usar uma função de hash perfeita . Você precisa encontrar uma função de hash que mapeie seu valor de entrada para um valor no intervalo 0 .. n , onde não há colisões para todos os valores válidos de que você gosta. Ou seja, não há dois valores "válidos" com o mesmo valor de saída. Ao procurar uma boa função de hash, você visa:

  • Mantenha a função hash razoavelmente rápida.
  • Minimizar n . O menor que você pode obter é 256 (função hash perfeita mínima), mas provavelmente é difícil de conseguir, dependendo dos dados.

Nota para funções de hash eficientes, n geralmente é uma potência de 2, que é equivalente a uma máscara bit a bit de bits baixos (operação AND). Exemplo de funções de hash:

  • CRC de bytes de entrada, módulo n .
  • ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(picking como muitos i, j, k, ..., conforme necessário, com turnos de esquerda ou direita)

Em seguida, você cria uma tabela fixa de n entradas, em que o hash mapeia os valores de entrada para um índice i na tabela. Para valores válidos, a entrada da tabela i contém o valor válido. Para todas as outras entradas da tabela, verifique se cada entrada do índice i contém algum outro valor inválido que não seja hash para i .

Em seguida, na sua rotina de interrupção, com a entrada x :

  1. Hash x para o índice i (que está no intervalo 0..n)
  2. Procure a entrada i na tabela e veja se ela contém o valor x .

Isso será muito mais rápido que uma pesquisa linear de 256 ou 1024 valores.

Eu escrevi algum código Python para encontrar funções de hash razoáveis.

Pesquisa binária

Se você classificar sua matriz de 256 valores "válidos", poderá fazer uma pesquisa binária , em vez de uma pesquisa linear. Isso significa que você deve conseguir pesquisar a tabela de 256 entradas em apenas 8 etapas ( log2(256)) ou uma tabela de 1024 entradas em 10 etapas. Novamente, isso será muito mais rápido que uma pesquisa linear de 256 ou 1024 valores.

Craig McQueen
fonte
Obrigado por isso. A opção de pesquisa binária é a que eu escolhi. Veja também um comentário anterior no primeiro post. Isso faz o truque muito bem sem usar a montagem.
Wlamers
11
De fato, antes de tentar otimizar seu código (como usar assembly ou outros truques), você provavelmente deve ver se pode reduzir a complexidade algorítmica. Normalmente, reduzir a complexidade algorítmica será mais eficiente do que tentar limitar alguns ciclos, mas mantendo a mesma complexidade algorítmica.
ysdx 6/09/14
3
+1 para pesquisa binária. O redesenho algorítmico é a melhor maneira de otimizar.
Rocketmagnet
Uma noção popular é que é preciso muito esforço para encontrar uma rotina de hash eficiente, portanto a "melhor prática" é uma pesquisa binária. Às vezes, porém, a "melhor prática" não é boa o suficiente. Suponha que você esteja roteando o tráfego da rede rapidamente no momento em que o cabeçalho de um pacote chegou (mas não a carga útil): o uso de uma pesquisa binária tornaria seu produto irremediavelmente lento. Os produtos incorporados geralmente têm tais restrições e requisitos que o que é "melhor prática" em, por exemplo, um ambiente de execução x86 é "tomar o caminho mais fácil" na incorporação.
Olof Forshell
60

Mantenha a tabela em ordem classificada e use a pesquisa binária desenrolada do Bentley:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

O ponto é,

  • se você sabe qual é o tamanho da tabela, sabe quantas iterações haverá para poder desenrolá-la completamente.
  • Portanto, não há testes pontuais para o ==caso em cada iteração porque, exceto na última iteração, a probabilidade desse caso é muito baixa para justificar o tempo gasto em testes para ele. **
  • Por fim, expandindo a tabela para uma potência de 2, você adiciona no máximo uma comparação e no máximo um fator de dois armazenamentos.

** Se você não está acostumado a pensar em termos de probabilidades, todo ponto de decisão possui uma entropia , que é a informação média que você aprende ao executá-lo. Para os >=testes, a probabilidade de cada ramificação é de cerca de 0,5 e -log2 (0,5) é 1, o que significa que, se você tomar uma ramificação, aprenderá 1 bit, e se você usar a outra ramificação, aprenderá um pouco e a média é apenas a soma do que você aprendeu em cada filial vezes a probabilidade dessa ramificação. Então 1*0.5 + 1*0.5 = 1, então a entropia do>= teste é 1. Como você tem 10 bits para aprender, são necessárias 10 ramificações. É por isso que é rápido!

Por outro lado, e se o seu primeiro teste for if (key == a[i+512)? A probabilidade de ser verdadeira é 1/1024, enquanto a probabilidade de falso é 1023/1024. Então, se é verdade, você aprende todos os 10 bits! Mas se for falso, você aprende -log2 (1023/1024) = 0,00001 bits, praticamente nada! Portanto, o valor médio que você aprende com esse teste é 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112bits. Cerca de um centésimo de bit. Esse teste não está carregando seu peso!

Mike Dunlavey
fonte
4
Eu realmente gosto desta solução. Ele pode ser modificado para executar em um número fixo de ciclos para evitar análises forenses baseadas em tempo, se o local do valor for uma informação sensível.
OregonTrail
1
@OregonTrail: análise forense baseada em tempo? Problema divertido, mas comentário triste.
Mike Dunlavey
16
Você vê loops desenrolados como este nas bibliotecas de criptografia para evitar ataques de tempo em en.wikipedia.org/wiki/Timing_attack . Aqui está um bom exemplo github.com/jedisct1/libsodium/blob/…. Nesse caso, estamos impedindo que um invasor adivinhe o comprimento de uma string. Geralmente, o invasor coleta vários milhões de amostras de uma chamada de função para executar um ataque de tempo.
OregonTrail
3
+1 Ótimo! Boa pesquisa desenrolada. Eu não tinha visto isso antes. Eu posso usá-lo.
Rocketmagnet
1
@ OregonTrail: Eu apóio seu comentário com base no tempo. Mais de uma vez tive que escrever código criptográfico que é executado em um número fixo de ciclos, para evitar o vazamento de informações para ataques baseados em tempo.
TonyK
16

Se o conjunto de constantes em sua tabela for conhecido antecipadamente, você poderá usar o hash perfeito para garantir que apenas um acesso seja feito à tabela. O hash perfeito determina uma função de hash que mapeia todas as chaves interessantes para um slot exclusivo (essa tabela nem sempre é densa, mas você pode decidir o quão densa pode ser uma mesa, com tabelas menos densas geralmente levando a funções de hash mais simples).

Geralmente, a função de hash perfeita para o conjunto específico de chaves é relativamente fácil de calcular; você não quer que isso seja longo e complicado, porque isso concorre pelo tempo, talvez seja melhor gasto com várias sondas.

O hash perfeito é um esquema "1 sonda no máximo". Pode-se generalizar a idéia, com o pensamento de que se deve trocar a simplicidade de computar o código hash com o tempo que leva para fazer k sondas. Afinal, o objetivo é "menos tempo total para procurar", não menos probes ou mais simples função de hash. No entanto, nunca vi alguém criar um algoritmo de hash k-probes-max. Suspeito que alguém possa fazer isso, mas é provável que seja pesquisa.

Outro pensamento: se o seu processador for extremamente rápido, a única sonda na memória a partir de um hash perfeito provavelmente domina o tempo de execução. Se o processador não for muito rápido, então k> 1 sondas podem ser práticas.

Ira Baxter
fonte
1
Um Cortex-M está longe de ser extremamente rápido .
MSalters
2
De fato, neste caso, ele não precisa de nenhuma tabela de hash. Ele só quer saber se uma determinada chave está no conjunto, ele não deseja mapeá-la para um valor. Portanto, basta que a função hash perfeita mapeie cada valor de 32 bits para 0 ou 1, onde "1" pode ser definido como "está no conjunto".
David Ongaro
1
Bom ponto, se ele conseguir um gerador de hash perfeito para produzir esse mapeamento. Mas isso seria "um conjunto extremamente denso"; Acho que ele pode encontrar um gerador de hash perfeito que faz isso. Ele pode estar melhor tentando obter um hash perfeito que produza um K constante, se no conjunto, e qualquer valor, exceto K, se não estiver no conjunto. Eu suspeito que é difícil obter um hash perfeito, mesmo para o último.
Ira Baxter
@DavidOngaro table[PerfectHash(value)] == valueproduz 1 se o valor estiver no conjunto e 0 se não estiver, e existem maneiras bem conhecidas de produzir a função PerfectHash (consulte, por exemplo, burtleburtle.net/bob/hash/perfect.html ). Tentar encontrar uma função de hash que mapeie diretamente todos os valores no conjunto em 1 e todos os valores que não estão no conjunto como 0 é uma tarefa imprudente.
perfil completo de Jim Balter
@ DavidOngaro: uma função hash perfeita tem muitos "falsos positivos", ou seja, valores que não estão no conjunto teriam o mesmo hash que os valores no conjunto. Portanto, você precisa ter uma tabela indexada pelo valor do hash, contendo o valor de entrada "in-the-set". Portanto, para validar qualquer valor de entrada, você (a) o mistura; (b) use o valor de hash para pesquisar a tabela; (c) verifique se a entrada na tabela corresponde ao valor de entrada.
Craig McQueen
14

Use um conjunto de hash. Isso dará o tempo de pesquisa O (1).

O código a seguir assume que você pode reservar o valor 0como um valor 'vazio', ou seja, não ocorre nos dados reais. A solução pode ser expandida para uma situação em que esse não é o caso.

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

Neste exemplo de implementação, o tempo de pesquisa normalmente será muito baixo, mas, na pior das hipóteses, pode chegar ao número de entradas armazenadas. Para um aplicativo em tempo real, você pode considerar também uma implementação usando árvores binárias, que terão um tempo de pesquisa mais previsível.

jpa
fonte
3
Depende de quantas vezes essa pesquisa deve ser feita para que seja eficaz.
precisa saber é
1
A pesquisa pode ser executada no final da matriz. E esse tipo de hash linear tem altas taxas de colisão - de nenhuma maneira você obterá O (1). Bons conjuntos de hash não são implementados assim.
perfil completo de Jim Balter
@ JimBalter True, código não perfeito. Mais como a ideia geral; poderia ter apenas apontado para o código de conjunto de hash existente. Mas, considerando que essa é uma rotina de serviço de interrupção, pode ser útil demonstrar que a pesquisa não é um código muito complexo.
Jpa1
Você deve consertá-lo para que ele fique em torno de mim.
Jim Balter
O objetivo de uma função de hash perfeita é que ele faz uma análise. Período.
Ira Baxter
10

Nesse caso, pode valer a pena investigar os filtros Bloom . Eles são capazes de estabelecer rapidamente que um valor não está presente, o que é uma coisa boa, pois a maioria dos 2 ^ 32 valores possíveis não está nessa matriz de 1024 elementos. No entanto, existem alguns falsos positivos que precisarão de uma verificação extra.

Como sua tabela é aparentemente estática, você pode determinar quais falsos positivos existem para o seu filtro Bloom e colocá-los em um hash perfeito.

MSalters
fonte
1
Interessante, eu nunca tinha visto filtros da Bloom antes.
Rocketmagnet
8

Supondo que o seu processador funcione a 204 MHz, o que parece ser o máximo para o LPC4357, e também assumindo que o resultado do seu tempo reflete o caso médio (metade da matriz percorrida), obtemos:

  • Frequência da CPU: 204 MHz
  • Período do ciclo: 4.9 ns
  • Duração em ciclos: 12,5 µs / 4,9 ns = 2551 ciclos
  • Ciclos por iteração: 2551/128 = 19,9

Portanto, seu loop de pesquisa gasta cerca de 20 ciclos por iteração. Isso não parece horrível, mas acho que, para torná-lo mais rápido, você precisa olhar para a montagem.

Eu recomendaria soltar o índice e usar uma comparação de ponteiro e fazer todos os ponteiros const.

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

Isso vale pelo menos a pena testar.

descontrair
fonte
1
-1, o ARM possui um modo de endereço indexado, portanto, isso não faz sentido. Quanto a fazer o ponteiro const, o GCC já identifica que não muda. Também constnão adiciona nada.
MSalters
11
@MSalters OK, não verifiquei com o código gerado, o objetivo era expressar algo que o torna mais simples no nível C, e acho que apenas gerenciar ponteiros em vez de ponteiro e índice é mais simples. Simplesmente discordo que " constnão acrescenta nada": diz claramente ao leitor que o valor não muda. Essa é uma informação fantástica.
descontraia
9
Este é um código profundamente incorporado; Até o momento, as otimizações incluíram a mudança do código do flash para a RAM. E, no entanto, ainda precisa ser mais rápido. Neste ponto, a legibilidade não é o objetivo.
MSalters
1
@MSalters "O ARM tem um modo de endereço indexado, então isso não faz sentido" - bem, se você errar completamente o ponto ... o OP escreveu "Eu também uso aritmética de ponteiro e um loop for". O desenrolar não substituiu a indexação por ponteiros, ele apenas eliminou a variável index e, portanto, um subtrato extra em cada iteração de loop. Mas o OP foi sábio (ao contrário de muitas pessoas respondendo e comentando) e acabou fazendo uma pesquisa binária.
Jim Balter
6

Outras pessoas sugeriram reorganizar sua tabela, adicionar um valor sentinela no final ou classificá-lo para fornecer uma pesquisa binária.

Você declara "Eu também uso a aritmética do ponteiro e um loop for, que fazem uma contagem decrescente em vez de para cima (verificar se i != 0é mais rápido do que verificar se i < 256)".

Meu primeiro conselho é: livrar-se da aritmética dos ponteiros e da contagem decrescente. Coisas como

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

tende a ser idiomático para o compilador. O loop é idiomático e a indexação de uma matriz sobre uma variável de loop é idiomática. O malabarismo com a aritmética e os ponteiros do ponteiro tende a ofuscar os idiomas para o compilador e fazer com que ele gere código relacionado ao que você escreveu, e não ao que o escritor do compilador decidiu ser o melhor curso para a tarefa geral .

Por exemplo, o código acima pode ser compilado em um loop executando de -256ou -255para zero, indexando&the_array[256] . Possivelmente coisas que não são expressáveis ​​em C válido, mas que correspondem à arquitetura da máquina para a qual você está gerando.

Portanto , não microoptimize. Você está apenas jogando chaves inglesas nos trabalhos do seu otimizador. Se você quiser ser inteligente, trabalhe nas estruturas e algoritmos de dados, mas não otimize sua expressão. Ele voltará a mordê-lo, se não no compilador / arquitetura atual, e depois no próximo.

Em particular, usar aritmética de ponteiro em vez de matrizes e índices é um veneno para o compilador estar totalmente ciente de alinhamentos, locais de armazenamento, considerações de alias e outras coisas, além de realizar otimizações como redução de força da maneira mais adequada à arquitetura da máquina.

user4015204
fonte
Os loops sobre ponteiros são idiomáticos em C e bons compiladores de otimização podem lidar com eles da mesma forma que a indexação. Mas tudo isso é discutível porque o OP acabou fazendo uma pesquisa binária.
perfil completo de Jim Balter
3

A vetorização pode ser usada aqui, como geralmente ocorre nas implementações do memchr. Você usa o seguinte algoritmo:

  1. Crie uma máscara de sua consulta repetindo, igual em comprimento à contagem de bits do seu sistema operacional (64 bits, 32 bits, etc.). Em um sistema de 64 bits, você repetiria a consulta de 32 bits duas vezes.

  2. Processe a lista como uma lista de vários dados ao mesmo tempo, simplesmente convertendo a lista em uma lista de um tipo de dados maior e retirando valores. Para cada pedaço, faça XOR com a máscara e, em seguida, XOR com 0b0111 ... 1, adicione 1 e depois com uma máscara de 0b1000 ... 0 repetindo. Se o resultado for 0, definitivamente não há correspondência. Caso contrário, pode haver (geralmente com probabilidade muito alta) uma correspondência, portanto, procure o pedaço normalmente.

Exemplo de implementação: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

meisel
fonte
3

Se você pode acomodar o domínio de seus valores com a quantidade de memória disponível para seu aplicativo, a solução mais rápida seria representar sua matriz como uma matriz de bits:

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

EDITAR

Estou impressionado com o número de críticos. O título deste segmento é "Como localizo rapidamente se um valor está presente em uma matriz C?"pelo qual defenderei minha resposta, porque responde exatamente isso. Eu poderia argumentar que esta possui a função hash mais eficiente em velocidade (desde o valor endereço ===). Eu li os comentários e estou ciente das advertências óbvias. Sem dúvida, essas advertências limitam a variedade de problemas que podem ser usados ​​para resolver, mas, para os problemas que soluciona, ele resolve com muita eficiência.

Em vez de rejeitar essa resposta, considere-a como o ponto de partida ideal para o qual você pode evoluir usando funções de hash para obter um melhor equilíbrio entre velocidade e desempenho.

Stephen Quan
fonte
8
Como isso leva a 4 votos positivos? A pergunta afirma que é um Cortex M4. A coisa tem 136 KB de RAM, não 262.144 KB.
MSalters
1
É impressionante quantos votos positivos foram dados a respostas manifestamente erradas, porque o respondente perdeu a floresta em busca das árvores. Para o maior caso do OP O (log n) << O (n).
RSU
3
Fico muito irritado com os programadores que queimam quantidades ridículas de memória, quando existem soluções muito melhores disponíveis. A cada 5 anos, parece que meu PC está ficando sem memória, onde há 5 anos esse valor era suficiente.
Craig McQueen
1
@CraigMcQueen Kids hoje em dia. Desperdiçando memória. Ultrajante, ultrajoso! Nos meus dias, tínhamos 1 MiB de memória e um tamanho de palavra de 16 bits. / s
Cole Johnson
2
O que há com os críticos severos? O OP afirma claramente que a velocidade é absolutamente crítica para essa parte do código, e StephenQuan já mencionou uma "quantidade ridícula de memória".
Bogdan Alexandru
1

Verifique se as instruções ("o pseudocódigo") e os dados ("theArray") estão em memórias separadas (RAM) para que a arquitetura do CM4 Harvard seja utilizada em todo o seu potencial. No manual do usuário:

insira a descrição da imagem aqui

Para otimizar o desempenho da CPU, o ARM Cortex-M4 possui três barramentos para acesso à instrução (código) (I), acesso a dados (D) e acesso ao sistema (S). Quando as instruções e os dados são mantidos em memórias separadas, o acesso ao código e aos dados pode ser feito em paralelo em um ciclo. Quando o código e os dados são mantidos na mesma memória, as instruções que carregam ou armazenam dados podem levar dois ciclos.

francek
fonte
Interessante, o Cortex-M7 possui caches de instruções / dados opcionais, mas antes disso definitivamente não. en.wikipedia.org/wiki/ARM_Cortex-M#Silicon_customization .
Peter Cordes
0

Sinto muito se minha resposta já foi respondida - apenas sou um leitor preguiçoso. Sinta-se livre para votar em seguida)))

1) você pode remover o contador 'i' - basta comparar os ponteiros, ou seja,

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

embora isso não traga nenhuma melhoria significativa, essa otimização provavelmente poderá ser alcançada pelo próprio compilador.

2) Como já foi mencionado por outras respostas, quase todas as CPUs modernas são baseadas em RISC, por exemplo, ARM. Até as modernas CPUs Intel X86 usam núcleos RISC dentro, tanto quanto eu sei (compilando a partir do X86 em tempo real). A principal otimização para o RISC é a otimização de pipeline (e também para a Intel e outras CPUs), minimizando os saltos de código. Um tipo de otimização (provavelmente a principal) é o de "reversão de ciclo". É incrivelmente estúpido e eficiente, até o compilador Intel pode fazer isso AFAIK. Parece que:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

Dessa forma, a otimização é que o pipeline não seja quebrado no pior caso (se compareVal estiver ausente na matriz), portanto, o mais rápido possível (é claro que não contamos as otimizações de algoritmos, como tabelas de hash, matrizes ordenadas etc.) mencionado em outras respostas, que podem dar melhores resultados, dependendo do tamanho da matriz. A abordagem de reversão de ciclos também pode ser aplicada lá, aliás. Estou escrevendo aqui sobre isso e acho que não vi em outras pessoas)

A segunda parte dessa otimização é que esse item da matriz é obtido pelo endereço direto (calculado no estágio de compilação, certifique-se de usar uma matriz estática) e não precisa de uma operação ADD adicional para calcular o ponteiro do endereço base da matriz. Essa otimização pode não ter efeito significativo, pois a arquitetura do AFAIK ARM possui recursos especiais para acelerar o endereçamento de matrizes. Mas enfim, é sempre melhor saber que você fez o melhor apenas no código C diretamente, certo?

A reversão do ciclo pode parecer estranha devido ao desperdício de ROM (sim, você a colocou corretamente em uma parte rápida da RAM, se sua placa suportar esse recurso), mas na verdade é um pagamento justo pela velocidade, baseado no conceito RISC. Este é apenas um ponto geral de otimização de cálculo - você sacrifica espaço por questão de velocidade e vice-versa, dependendo de seus requisitos.

Se você acha que a reversão para uma matriz de 1024 elementos é um sacrifício muito grande para o seu caso, considere 'reversão parcial', por exemplo, dividir a matriz em 2 partes de 512 itens cada, ou 4x256 e assim por diante.

3) a CPU moderna geralmente suporta operações SIMD, por exemplo, conjunto de instruções ARM NEON - permite executar as mesmas operações em paralelo. Francamente falando, não me lembro se é adequado para operações de comparação, mas acho que pode ser, você deve verificar isso. O Google mostra que pode haver alguns truques também, para obter velocidade máxima, consulte https://stackoverflow.com/a/5734019/1028256

Espero que isso possa lhe dar novas idéias.

Mixaz
fonte
O OP ignorou todas as respostas tolas focadas na otimização de loops lineares e, em vez disso, pré-ordenou a matriz e fez a pesquisa binária.
perfil completo de Jim Balter
@ Jim, é óbvio que esse tipo de otimização deve ser feito primeiro. As respostas 'tolas' podem não parecer tão tolas em alguns casos de uso quando, por exemplo, você não tem tempo para classificar a matriz. Ou se a velocidade que você começa, não é suficiente qualquer maneira
Mixaz
"é óbvio que esse tipo de otimização deve ser feito primeiro" - obviamente não para as pessoas que fizeram um grande esforço para desenvolver soluções lineares. "você não tem tempo para classificar a matriz" - não faço ideia do que isso significa. "Ou se a velocidade que você obtiver, não for suficiente, de qualquer maneira" - Uh, se a velocidade de uma pesquisa binária "não for suficiente", fazer uma pesquisa linear otimizada não a melhorará. Agora eu terminei com esse assunto.
Jim Balter
@ JimBalter, se eu tivesse esse problema como OP, certamente consideraria usar algs como pesquisa binária ou algo assim. Eu simplesmente não conseguia pensar que o OP já não considerasse isso. "você não tem tempo para classificar a matriz" significa que a matriz de classificação leva tempo. Se você precisar fazer isso para cada conjunto de dados de entrada, pode levar mais tempo que um loop linear. "Ou se a velocidade que você começa, não é suficiente qualquer maneira" meios seguinte - dicas de otimização acima poderia ser usado para acelerar o código binário de busca ou qualquer
Mixaz
0

Eu sou um grande fã de hash. O problema, é claro, é encontrar um algoritmo eficiente que seja rápido e use uma quantidade mínima de memória (especialmente em um processador incorporado).

Se você souber de antemão os valores que podem ocorrer, poderá criar um programa que seja executado por uma infinidade de algoritmos para encontrar o melhor - ou melhor, os melhores parâmetros para seus dados.

Eu criei um programa que você pode ler neste post e obtive alguns resultados muito rápidos. 16000 entradas são convertidas aproximadamente para 2 ^ 14 ou uma média de 14 comparações para encontrar o valor usando uma pesquisa binária. Procurei explicitamente pesquisas muito rápidas - em média, encontrando o valor em <= 1,5 pesquisas - o que resultou em maiores requisitos de RAM. Acredito que com um valor médio mais conservador (digamos <= 3), muita memória poderia ser salva. Por comparação, o caso médio de uma pesquisa binária nas entradas 256 ou 1024 resultaria em um número médio de comparações de 8 e 10, respectivamente.

Minha pesquisa média exigiu cerca de 60 ciclos (em um laptop com um intel i5) com um algoritmo genérico (utilizando uma divisão por uma variável) e 40-45 ciclos com um especializado (provavelmente utilizando uma multiplicação). Isso deve se traduzir em tempos de pesquisa abaixo de microssegundos no seu MCU, dependendo, é claro, da frequência do relógio em que ele é executado.

Pode ser alterado ainda mais na vida real se a matriz de entradas acompanhar quantas vezes uma entrada foi acessada. Se o array de entrada for classificado do mais para o menos acessado antes que os indeces sejam computados, ele encontrará os valores mais comuns com uma única comparação.

Olof Forshell
fonte
0

Isso é mais um adendo do que uma resposta.

Eu tive um caso semelhante no passado, mas minha matriz era constante em um número considerável de pesquisas.

Na metade deles, o valor pesquisado NÃO estava presente na matriz. Então percebi que poderia aplicar um "filtro" antes de fazer qualquer pesquisa.

Este "filtro" é apenas um número inteiro simples, calculado UMA VEZ e usado em cada pesquisa.

Está em Java, mas é bem simples:

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i];
}

Então, antes de fazer uma pesquisa binária, eu checo o binaryfilter:

// Check binaryfilter vs value with a "Binary AND Operator"
if ((binaryfilter & valuetosearch) != valuetosearch)
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

Você pode usar um algoritmo de hash 'melhor', mas isso pode ser muito rápido, especialmente para grandes números. Pode ser que isso economize ainda mais ciclos.

cristão
fonte