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

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.

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.

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 ...

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
• pesquisa binária

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.

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!

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.

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.

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.

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.

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.

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

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.

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:

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.

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.

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.

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.