«N'est-il pas temps, mes amis, que nous nous tournions vers William, vous voyez, notre Shakespeare? ".
J'ai récemment lu un article sur un clavier personnalisé et j'ai encore une fois pensé qu'il serait bien d'écrire une référence (c'est-à-dire qui n'a pas honte de signer avec son nom et de la mettre en exposition publique) une implémentation de clavier. Cette idée ne m'est pas venue pour la première fois, mais elle s'arrête en quelque sorte à la première étape - lire les informations initiales, parce que je veux rendre cette étape facilement personnalisable, pratique à utiliser, universelle et efficace, et je n'aime pas l'offre "choisissez-en deux".
Remarque nécessaire - Je vois 4 couches d'implémentation du clavier: 0 - détection d'événements, 1 - lecture de données, 2 - nettoyage et stockage de données, 3 - génération de messages, 4 - transcodage, etc. Le plus prometteur pour la couche 1 et la couche 0 qui lui est associée me semble l'utilisation de modèles Anton Chizhov pour travailler avec des broches MK (basées sur la classe Loki) et, peut-être un jour, le résultat résultant n'aura pas honte à partager, mais certainement pas aujourd'hui. Maintenant, je pense à la couche 2.
Formulons le problème - il est nécessaire de stocker des informations sur un ensemble fixe de commutateurs qui prennent l'une des deux valeurs prédéfinies - «fermé» et «non fermé». Les candidats les plus naturels sont les variables booléennes et la bibliothèque de bits, comme moyen de stocker un ensemble. Étant donné que l'exigence d'efficacité est un impératif catégorique, il est souhaitable d'évaluer la mise en œuvre du module de ce point de vue.
La première pensée a été de regarder les codes sources et tout est immédiatement devenu clair, mais après une brève connaissance avec eux, j'ai réalisé que l'apprentissage des modèles d'autres personnes n'était pas très intéressant (et pas très productif). De plus, les sources ne donnent pas une évaluation précise de l'efficacité de l'implémentation, car elle est directement fermée au compilateur. En fait, le texte source devait encore être étudié, sinon y apporter des modifications devient un processus très long (à moins, bien sûr, que nous ne soyons intéressés à obtenir un certain résultat), mais c'est un sujet pour un autre article.
Par conséquent, la technique d'étude de la "boîte noire" est adoptée - nous introduisons divers fragments de code à l'entrée et considérons l'assembleur généré. Malheureusement, il n'est pas possible d'utiliser le site Godbolt préféré pour l'architecture AVR familière, car il n'y a pas de bibliothèque à l'étude dans cette implémentation. Vous pouvez bien sûr le faire glisser avec des stylos, mais rien ne garantit que ce sera le bon code source.
Par conséquent, nous examinerons une architecture différente. x51 n'est pas présenté pour le compilateur gcc, je n'ai jamais aimé x86, ARM a un assembleur pas très pratique (pour une personne) et compréhensible, MIPS est très spécifique et pas trop commun, toutes sortes de SPARC sont encore pires (eh bien, eh bien, je n'offenserai personne avec votre architecture préférée, pas mieux), mais il y a un grand candidat MSP430, qui était basé sur l'architecture cristalline et élégante de PDP et TI ne pouvait pas le gâcher beaucoup (bien que les gars aient essayé). Une bibliothèque de plusieurs bits pour cette architecture est présentée, vous pouvez donc commencer à étudier.
Commençons, car cela ne semble pas trivial, dès le début, c'est-à-dire avec l'annonce de la multitude. Nous verrons immédiatement que la mémoire pour le stockage est allouée en mots de quatre octets, malgré le fait que l'unité naturelle dans cette architecture est un mot de deux octets, et un travail assez pratique et efficace avec des octets est fourni, ce qui conduit à des incidents étranges. Vous pouvez comprendre l'auteur, la mise en œuvre d'un nombre 32 bits devrait être partout et s'appuyer sur elle tout naturellement, mais dans ce cas, 8 bits serait préférable, et pour AVR, 8 bits serait la seule solution raisonnable.
Une question intéressante, mais comment déterminer la profondeur de bits de l'architecture pendant le processus de compilation, vous devrez essayer uint8_t_fast. Nous notons une optimisation possible et passons à autre chose.
Outre l'allocation de mémoire, l'initialisation présente un intérêt - pour les ensembles globaux, elle est effectuée de manière standard - la mise à zéro avant d'appeler main, pour les ensembles locaux, elle est également effectuée de manière standard, c'est-à-dire en aucun cas si la valeur initiale n'est pas explicitement spécifiée. Eh bien, et, comme toujours, s'il est possible de décrire un ensemble statique avec une valeur initiale en dehors de la fonction, cela devrait être utilisé pour ne pas activer les indicateurs inutiles et ne pas passer de temps d'exécution sur eux. Mais ici, nous ne nous attendions pas à des révélations, nous avons juste vérifié les règles générales.
Commençons à travailler avec la modification de l'ensemble, pour lequel nous avons laissé des crochets et des méthodes set et reset. Nous pouvons nous attendre à voir quelque chose comme ça pour définir l'élément n dans l'ensemble M:
M[n / w] |= (1<<(n % w))
où w est le nombre de bits dans l'élément de base, qui pour une architecture donnée, défini statiquement n (par exemple, 4) et l'optimisation incluse conduit à un code de la forme:
bis.w #0x0010, m
En effet, nous voyons un tel code dans la moitié droite de la fenêtre, et il est peu probable que quiconque risquerait sérieusement d'affirmer qu'une solution plus efficace est possible. Mais cela ne concerne que les conditions indiquées, pour un arbitraire n l'image change complètement, pour les méthodes nous observons la validation de l'argument de validité avec la génération de l'exception correspondante, et pour les crochets nous voyons la restriction de l'argument avec un masque de bits de la plage acceptable avec un comportement indéfini complètement prévisible, les deux cas sont tout à fait cohérents avec la documentation. Les valeurs négatives sont traitées assez correctement, car les index sont considérés comme des nombres non signés.
Nous attirons l'attention sur le fait que la valeur assignée pour un élément d'un ensemble peut être non seulement 0 et 1, comme on pourrait s'y attendre, mais aussi tout entier auquel la règle «Qu'est-ce que l'unité? Pas zéro », c'est tout à fait logique, mais mal reflété dans la documentation. Un peu étrangement fait, mais les valeurs booléennes seraient plus naturelles, cocher et passer à autre chose.
La comparaison du code généré pour le cas d'un numéro d'élément statiquement indéterminé de l'ensemble montre que l'efficacité du code dans les deux cas ([] et les méthodes) est très proche et petite, puisqu'un sous-programme de la bibliothèque standard est appelé pour calculer (1 << n), et ce sous-programme se déplace Numéro 32 bits 0x00000001, placé dans deux registres. Nous ne pouvons pas voir son texte source, mais le fait même de l'appel conduit à de tristes pensées. Le fait est que dans l'architecture considérée, il n'y a pas de décalage vers la gauche (et il n'y a pas non plus de droite) par un nombre arbitraire de positions, comme dans tous les (nombreux) ARM bien-aimés. Il y a un décalage de 1 position (il serait étrange s'il n'existait pas du tout), il y a un décalage de 2,3,4 positions (mais par un nombre strictement fixé dans la commande, pas par un paramètre), il y a un préfixe REPT (mais sa vitesse d'exécution laisse souhaiter le meilleur). Vous pouvez implémenter le décalage de la plus petite unité (c'est important, une seule unité), c'est-à-dire obtenir un masque de bits par le nombre de bits dans un temps relativement court par des astuces telles que l'échange de tétrades, mais ce sera une partie très dépendante et, dans le cas général, il vaut mieux ne pas le faire.
Par conséquent, une méthode universelle et rapide serait de stocker des masques de bits dans un tableau et un index, et sur cette architecture, il est également très efficace, le code ressemble alors à ceci:
M[n/w] |= BitArray[n %w]
obtenir un assembleur comme:
bis.b BitArray(r0),M(r1)
Puisque nous parlons de modèles et que w est un multiple de la taille d'un octet, les opérations de division sont implémentées très efficacement ici. Nous notons l'avantage évident d'un élément de stockage à implémentation minimale: pour un octet, un tableau de 8 octets est requis pour un octet, -2 * 16 = 32 octets pour l'organisation des mots, et 4 * 32 = 128 octets pour un mot long de 32 bits pour stocker tout le nécessaire masques, pourquoi payer plus si le résultat ne change pas. Souvenons-nous d'une autre optimisation possible et passons.
Nous notons un fait supplémentaire - des implémentations beaucoup plus efficaces des opérations avec un élément défini sont possibles si l'architecture cible a une région de mémoire binaire (ici encore, l'ARM rejeté précédemment est rappelé), où l'opération d'installation d'élément se transforme généralement en BitSetAddr [n] = citrouille 1, ce qui se traduit par une seule commande d'assembleur pour la constante n, mais il y a déjà suffisamment de décalages effectifs, donc une telle optimisation serait plus redondante, surtout en tenant compte de ses limites. En principe, il existe une zone adressable par bit similaire dans les deux x51 et AVR, mais il n'y a des commandes efficaces que pour des nombres d'éléments constants, et dans le cas général, tout n'est pas si bon (franchement mauvais).
Eh bien, regardez maintenant de près le code résultant et notez que nous observons des artefacts associés au stockage de l'ensemble en deux mots. Le compilateur pour l'opération de modification d'un élément d'un ensemble génère une séquence de commandes qui lisent le double mot correspondant de la mémoire dans 2 registres (je me souviens que nous avons des registres 16 bits), les modifie et renvoie les résultats en mémoire. Si nous ne modifions qu'un seul élément, le masque d'opération contiendra exactement une unité sur 32 possibles, les zéros restants. Lorsque nous appliquons un numéro d'élément défini statiquement, les opérations qui ne modifient pas le résultat doivent être exclues au stade de l'optimisation. En règle générale, cela se produit, mais pour divers opérandes, quelque chose ne va pas et des artefacts du formulaire fuient dans le code final:
bic #0,r0
ce qui est particulièrement drôle si vous remarquez que le registre n'est pas réécrit en mémoire, bien qu'il soit lu. À strictement parler, les résultats des optimisations ne sont réglementés nulle part, ils peuvent donc être n'importe quoi, et il n'y a rien à redire, mais quoi qu'il en soit, "ce n'est pas clair comment cela fonctionne". Nous ne pouvons pas influencer directement ce processus, si nous ne considérons pas sérieusement le code source du compilateur, nous allons donc le contourner - nous aiderons l'optimiseur en simplifiant sa tâche.
Soit dit en passant, je ne trouve toujours pas la réponse à la question - est-il possible en C ++ au niveau de la macro ou du modèle de définir une implémentation différente pour une définition statique au stade de la compilation par rapport à un paramètre statiquement indéfini. Si quelqu'un connaît le chemin des samouraïs, dites-moi dans les commentaires, j'ai essayé constexpr, ça n'a pas marché.
Nous poursuivons nos recherches et constatons que le compilateur optimise de manière incontrôlable les appels à l'ensemble (bien sûr, si l'optimisation est activée), c'est-à-dire que l'ordre d'installation / de nettoyage des différents éléments n'est absolument pas garanti et n'est en aucun cas lié à l'ordre des opérateurs de code source. Mais je n'ai pas réussi à créer un ensemble volatile, peut-être que je fais quelque chose de mal? Comme dans le cas de toute optimisation locale, l'appel à une fonction externe force le compilateur à forcer toutes les opérations préparées pour le tableau global, mais c'est une solution trop forte et n'aide pas avec les locales. Eh bien, il n'y a probablement rien à faire, et il vous suffit de prendre en compte une fonctionnalité similaire et de ne pas utiliser d'ensembles pour transférer des informations entre les flux à l'aide d'interfaces série (c'est-à-dire leurs homologues logiciels).
Une conclusion générale peut être tirée: l'utilisation du jeu de bits sous sa forme actuelle pour des architectures aux ressources limitées ne peut pas être recommandée en raison de coûts excessifs en mémoire et en temps d'exécution. Une éventuelle modification, qui prend en compte toutes les données sur le texte du commentaire, se trouve sur Github, tout le monde peut l'utiliser. L'histoire de la création de ce mod sera bientôt publiée sur Habré, il y a eu des moments amusants.
En conclusion, une petite remarque - l'implémentation de l'entrepôt de données "frontale", même sur la version optimisée de l'ensemble, nécessitera N / 8 octets de mémoire de données (pour 128 commutateurs, 16 octets seront nécessaires) et bien que les opérations nécessitent O (1), le multiplicateur sera de nombreuses unités ( et même jusqu'à 10 cycles ou plus) de MK. Par conséquent, en tenant compte des exigences du problème et en introduisant certaines restrictions, nous pouvons proposer une implémentation alternative du stockage de données.
Si nous pensons qu’aucun interrupteur ne peut être fermé à tout moment (nous ignorons tous les autres jusqu’à ce que le bouton qui est actuellement enfoncé soit ouvert), alors nous pouvons contourner un octet (à condition qu’il n’y ait pas plus de 256 interrupteurs) et l'écriture / lecture prendra O (1) cycles de processeur, et le multiplicateur sera assez modeste.
Cette approche est facile à développer et à stocker des informations sur n commutateurs fermés simultanément, mais vous ne devez pas rendre n trop grand, car la quantité de mémoire requise augmente et le temps nécessaire pour effectuer des opérations d'inversion augmente linéairement avec une augmentation du nombre d'éléments dans l'ensemble, bien qu'il reste O (1) par par rapport au nombre de commutateurs. L'augmentation de temps indiquée peut être considérablement réduite en utilisant l'implémentation triangulaire de l'arbre binaire à O (loq2 (n)), mais pour les petits n ce n'est pas si important. Oui, et il est peu probable que la complexité du calcul de l'index suivant lors de la recherche compense la diminution du nombre d'itérations simples. Les inconvénients de cette implémentation incluent un échec possible d'enregistrer l'élément de l'ensemble, qui devrait être traité dans le programme appelant (nous rejetons l'option avec une taille de tampon changeante immédiatement et avec indignation - ce n'est pas pour les solutions intégrées).
La mise en œuvre de cette approche y sera donnée.