“Não está na hora, meus amigos, de balançar em William, veja, nosso Shakespeare? "
Recentemente, li um post sobre um teclado personalizado e mais uma vez pensei que seria bom escrever uma implementação de teclado (ou seja, que não tenha vergonha de assinar com seu nome e colocá-lo em exibição pública). Essa ideia não me vem pela primeira vez, mas, de alguma forma, para na primeira etapa - lendo as informações iniciais, porque quero tornar essa etapa fácil de configurar, conveniente de usar, universal e eficaz, e não gosto da oferta "escolha duas".
Nota necessária - vejo 4 camadas de implementação do teclado: 0 - detecção de eventos, 1 - leitura de dados, 2 - limpeza e armazenamento de dados, 3 - geração de mensagens, 4 - transcodificação, etc. O mais promissor para a camada 1 e a camada 0 associada a mim me parece o uso de modelos Anton Chizhov para trabalhar com pinos MK (baseados na classe Loki) e, talvez, algum dia, o resultado resultante não terá vergonha de compartilhar, mas certamente não hoje. Agora estou pensando na camada 2.
Vamos formular o problema - é necessário armazenar informações sobre um conjunto fixo de comutadores que usam um dos dois valores predefinidos - "fechado" e "não fechado". Os candidatos mais naturais são variáveis booleanas e a biblioteca de bits, como uma maneira de armazenar um conjunto. Como o requisito de eficiência é um imperativo categórico, é desejável avaliar a implementação do módulo deste ponto de vista.
O primeiro pensamento foi examinar os códigos-fonte e tudo ficou imediatamente claro, mas depois de um breve conhecimento deles, percebi que aprender sobre os modelos de outras pessoas não era muito interessante (e não muito produtivo). Além disso, as fontes não fornecem uma avaliação precisa da eficácia da implementação, uma vez que está diretamente fechada ao compilador. De fato, o texto original ainda precisava ser estudado, caso contrário, fazer alterações torna-se um processo muito demorado (a menos que, é claro, tenhamos interesse em obter um determinado resultado), mas esse é o tópico de uma postagem separada.
Portanto, a técnica de estudar a “caixa preta” é adotada - alimentamos vários fragmentos de código e consideramos o assembler gerado. Infelizmente, não é possível usar o site godbolt favorito para a arquitetura familiar do AVR, pois não há biblioteca em estudo nesta implementação. Obviamente, você pode arrastá-lo com canetas, mas não há garantia de que seja o código-fonte correto.
Portanto, veremos uma arquitetura diferente. O x51 não é apresentado para o compilador gcc, eu nunca gostei do x86, o ARM tem um montador não muito conveniente (para uma pessoa) e compreensível, o MIPS é muito específico e não é muito comum, todos os tipos de SPARCs são ainda piores (bem, bem, eu não vou ofender ninguém com sua arquitetura favorita, não é melhor), mas existe um ótimo candidato MSP430, que foi baseado na arquitetura cristalina e elegante do PDP e da TI e não o estragou muito (embora os caras tenham tentado). Uma biblioteca de muitos bits para essa arquitetura é apresentada, para que você possa começar a estudar.
Vamos começar, pois não parece trivial, desde o início, isto é, com o anúncio da multidão. Imediatamente veremos que a memória para armazenamento é alocada em palavras de quatro bytes, apesar do fato de a unidade natural nessa arquitetura ser uma palavra de dois bytes, e é fornecido um trabalho bastante conveniente e eficiente com bytes, o que leva a incidentes estranhos. Você pode entender o autor, a implementação de um número de 32 bits deve estar em toda parte e depender dele com bastante naturalidade, mas nesse caso, 8 bits seria preferível e, para o AVR, 8 bits seria a única solução razoável.
Uma pergunta interessante, mas como você pode determinar a profundidade de bits da arquitetura durante o processo de compilação, será necessário experimentar uint8_t_fast. Observamos uma possível otimização e seguimos em frente.
Além de alocar memória, a inicialização é de interesse - para conjuntos globais é feita da maneira padrão - zerando antes de chamar main, para conjuntos locais também é feita da maneira padrão, ou seja, de maneira alguma se o valor inicial não for especificado explicitamente. Bem, e, como sempre, se é possível descrever um conjunto estático com um valor inicial fora da função, isso deve ser usado para não ativar sinalizadores desnecessários e não gastar tempo de execução com eles. Mas aqui não esperávamos revelações, apenas checávamos as regras gerais.
Vamos começar a modificar o conjunto, para o qual deixamos colchetes e os métodos set e reset. Podemos esperar algo assim para definir o elemento n no conjunto M:
M[n / w] |= (1<<(n % w))
onde w é o número de bits no elemento base que, para uma determinada arquitetura, é definido estaticamente n (por exemplo, 4) e a otimização incluída leva a um código no formato:
bis.w #0x0010, m
De fato, vemos esse código na metade direita da janela e é improvável que alguém arrisque seriamente afirmar que uma solução mais eficaz é possível. Mas isso é apenas para as condições indicadas, para um cenário arbitrário em que a imagem muda completamente, para métodos que observamos a validação do argumento de admissibilidade com a geração da exceção correspondente e para os colchetes vemos a restrição do argumento com uma máscara de bits da faixa permitida com comportamento indefinido completamente previsível, ambos os casos são bastante consistentes com a documentação. Os valores negativos são processados corretamente, pois os índices são considerados como números não assinados.
Chamamos atenção para o fato de que o valor atribuído a um elemento de um conjunto pode ser não apenas 0 e 1, como seria de esperar, mas também qualquer número inteiro ao qual a regra “O que é unidade? Diferente de zero ”, é bastante lógico, mas pouco refletido na documentação. Um pouco estranho, mas os valores booleanos seriam mais naturais, marcariam e seguiriam em frente.
A comparação do código gerado para o caso de um número de elemento estaticamente indeterminado do conjunto mostra que a eficiência do código em ambos os casos ([] e métodos) é muito próxima e pequena, já que uma sub-rotina da biblioteca padrão é chamada para calcular (1 << n), e essa sub-rotina muda. Número de 32 bits 0x00000001, colocado em dois registros. Não podemos ver o texto fonte, mas o próprio fato da ligação leva a pensamentos tristes. O fato é que, na arquitetura em questão, não há deslocamento para a esquerda (e também não há direito) por um número arbitrário de posições, como em todos os (muitos) ARMs amados. Há uma mudança em 1 posição (seria estranho se não existisse), há uma mudança em 2,3,4 posições (mas por um número estritamente fixado no comando, não por um parâmetro), há um prefixo REPT (mas sua velocidade de execução deixa desejar o melhor). Você pode implementar o deslocamento da unidade menor (isso é importante, apenas uma unidade), ou seja, obter uma máscara de bits pelo número de bits em um tempo relativamente curto, através de truques como a troca de tetradas, mas essa será uma parte muito dependente e, em geral, é melhor não fazer isso.
Portanto, um método universal e rápido seria armazenar máscaras de bits em uma matriz e índice, e nessa arquitetura também é muito eficiente, o código fica assim:
M[n/w] |= BitArray[n %w]
ficando montador como:
bis.b BitArray(r0),M(r1)
Como estamos falando de padrões ew é múltiplo do tamanho de um byte, as operações de divisão são implementadas com muita eficiência aqui. Observamos a clara vantagem de um elemento de armazenamento minimamente implementado: para um byte, uma matriz de 8 bytes é necessária para um byte, -2 * 16 = 32 bytes para organização de palavras e 4 * 32 = 128 bytes para uma palavra longa de 32 bits para armazenar todo o necessário máscaras, por que pagar mais se o resultado não mudar. Vamos lembrar mais uma otimização possível e seguir em frente.
Observamos mais um fato - implementações muito mais eficientes de operações com um elemento definido são possíveis se a arquitetura de destino tiver uma região de memória marcada por bits (aqui, novamente, o ARM rejeitado anteriormente é lembrado), onde a operação de instalação do elemento geralmente se transforma em um BitSetAddr [n] = abóbora 1, que se traduz em um único comando assembler para a constante n, mas já existem mudanças efetivas suficientes lá, de modo que essa otimização seria mais redundante, principalmente levando em conta suas limitações. Em princípio, existe uma área de endereçamento de bits semelhante no x51 e no AVR, mas existem comandos eficazes apenas para números constantes de elementos e, no caso geral, nem tudo é tão bom (francamente ruim).
Bem, agora dê uma olhada no código resultante e observe que observamos artefatos associados ao armazenamento do conjunto em palavras duplas. O compilador para a operação de modificar um elemento de um conjunto gera uma sequência de comandos que lê a palavra dupla correspondente da memória em 2 registros (lembro que temos registros de 16 bits), modifica-os e envia os resultados de volta à memória. Se alterarmos apenas um elemento, a máscara de operação conterá exatamente uma unidade dentre 32 possíveis, os zeros restantes. Quando aplicamos um número de elemento definido estaticamente, as operações que não alteram o resultado devem ser excluídas no estágio de otimização. Como regra, isso acontece, mas para vários operandos algo dá errado e os artefatos do formulário vazam para o código final:
bic #0,r0
o que parece especialmente engraçado se você notar que o registro não é gravado de volta na memória, embora seja lido. Estritamente falando, os resultados das otimizações não são regulados em nenhum lugar; portanto, podem ser qualquer coisa e não há nada para se ofender, mas, de qualquer forma, "não é legal como funciona". Não podemos influenciar diretamente esse processo, se não considerarmos seriamente o código-fonte do compilador, então vamos ignorá-lo - ajudaremos o otimizador simplificando sua tarefa.
A propósito, ainda não consigo encontrar a resposta para a pergunta - é possível em C ++ no nível de macro ou modelo definir uma implementação diferente para definida estaticamente no estágio de compilação em relação a um parâmetro estaticamente indefinido. Se alguém conhece o caminho do samurai, diga-me nos comentários, tentei o constexpr, não funcionou.
Continuamos nossa pesquisa e descobrimos que o compilador está otimizando incontrolavelmente as chamadas para o conjunto (é claro, se a otimização estiver ativada), ou seja, a ordem de instalação / limpeza de vários elementos não é totalmente garantida e não está conectada à ordem dos operadores de código-fonte. Mas não consegui criar um conjunto volátil, talvez esteja fazendo algo errado? Como no caso de qualquer otimização local, a chamada para uma função externa força o compilador a forçar todas as operações preparadas para a matriz global, mas essa é uma solução muito forte e não ajuda nas locais. Bem, provavelmente não há nada a ser feito, e você só precisa levar em consideração um recurso semelhante e não usar conjuntos para transferir informações entre fluxos usando interfaces seriais (ou seja, seus equivalentes de software).
Uma conclusão geral pode ser feita: o uso de bitset em sua forma atual para arquiteturas com recursos limitados não pode ser recomendado devido a custos excessivos na memória e no tempo de execução. Uma possível modificação, que leva em consideração todos os dados no texto do comentário, está no Github, todos podem usá-lo. A história da criação deste mod será publicada em breve em Habré, houve momentos engraçados.
Em conclusão, uma pequena observação - a implementação do data warehouse "frontal", mesmo na versão otimizada do conjunto, exigirá N / 8 bytes de memória de dados (para 128 comutadores, 16 bytes serão necessários) e, embora as operações exijam tempo O (1), o multiplicador será muitas unidades ( e até 10 ou mais) ciclos de MK. Portanto, levando em consideração os requisitos do problema e introduzindo certas restrições, podemos oferecer uma implementação alternativa de armazenamento de dados.
Se acreditarmos que não é possível fechar mais de um comutador a qualquer momento (ignoramos todos os outros até que o botão pressionado no momento seja aberto), podemos ignorar um byte (desde que não haja mais que 256 comutadores) e a escrita / leitura levará O (1) ciclos do processador, e o multiplicador será bastante modesto.
Essa abordagem é fácil de expandir e armazenar informações sobre n switches fechados simultaneamente, mas você não deve tornar n muito grande, pois a quantidade necessária de memória aumenta e o tempo para executar operações de inversão aumenta linearmente com um aumento no número de elementos no conjunto, embora permaneça O (1) por em relação ao número de comutadores. O aumento de tempo indicado pode ser reduzido significativamente usando a implementação triangular da árvore binária para O (loq2 (n)), mas para n pequeno, isso não é tão importante. Sim, e é duvidoso que a complexidade do cálculo do próximo índice durante a pesquisa compense a diminuição no número de iterações simples. As desvantagens dessa implementação incluem uma possível falha no registro do elemento do conjunto, que deve ser processado no programa de chamada (rejeitamos a opção com um tamanho de buffer variável imediatamente e com indignação - isso não é para soluções internas).
A implementação desta abordagem será dada lá.