„Ist es nicht an der Zeit, meine Freunde, dass wir William, unseren Shakespeare, angreifen? ".
Ich habe kürzlich einen Beitrag über eine benutzerdefinierte Tastatur gelesen und wieder einmal gedacht, dass es schön wäre, eine Referenz (dh eine, die sich nicht schämt, mit ihrem Namen zu unterschreiben und sie öffentlich anzuzeigen) einer Tastaturimplementierung zu schreiben. Diese Idee kommt mir nicht zum ersten Mal, aber sie hört irgendwie in der ersten Phase auf - beim Lesen der ersten Informationen, weil ich diese Phase einfach anpassbar, benutzerfreundlich, universell und effektiv gestalten möchte und das Angebot "Wähle zwei" nicht mag.
Notwendiger Hinweis - Ich sehe 4 Tastaturimplementierungsebenen: 0 - Ereigniserkennung, 1 - Datenlesen, 2 - Datenbereinigung und -speicherung, 3 - Nachrichtengenerierung, 4 - Transcodierung usw. Das vielversprechendste für Schicht 1 und die damit verbundene Schicht 0 scheint mir die Verwendung von Anton Chizhov-Vorlagen für die Arbeit mit MK-Pins (basierend auf der Loki-Klasse) zu sein, und vielleicht wird sich das resultierende Ergebnis eines Tages nicht schämen, es zu teilen, aber sicherlich nicht heute. Jetzt denke ich an Schicht 2.
Lassen Sie uns das Problem formulieren - es ist notwendig, Informationen über einen festen Satz von Schaltern zu speichern, die einen von zwei vordefinierten Werten annehmen - "geschlossen" und "nicht geschlossen". Die natürlichsten Kandidaten sind boolesche Variablen und die Bitset-Bibliothek, um eine Menge zu speichern. Da das Erfordernis der Effizienz ein kategorisches Gebot ist, ist es wünschenswert, die Implementierung des Moduls unter diesem Gesichtspunkt zu bewerten.
Der erste Gedanke war, sich die Quellcodes anzuschauen, und alles wurde sofort klar, aber nach einer kurzen Bekanntschaft mit ihnen wurde mir klar, dass das Lernen über die Vorlagen anderer Leute nicht sehr interessant (und nicht sehr produktiv) war. Darüber hinaus geben die Quellen keine genaue Einschätzung der Wirksamkeit der Implementierung, da sie direkt für den Compiler geschlossen ist. Tatsächlich musste der Quelltext noch untersucht werden, da sonst Änderungen an ihm sehr langwierig werden (es sei denn, wir sind natürlich daran interessiert, ein bestimmtes Ergebnis zu erzielen), aber dies ist das Thema eines separaten Beitrags.
Daher wird die Technik des Studierens der „Black Box“ übernommen - wir füttern verschiedene Codefragmente und betrachten den generierten Assembler. Leider ist es nicht möglich, die bevorzugte Godbolt-Site für die bekannte AVR-Architektur zu verwenden, da in dieser Implementierung keine Bibliothek untersucht wird. Sie können es natürlich mit Stiften ziehen, aber es gibt keine Garantie dafür, dass es sich um den richtigen Quellcode handelt.
Daher werden wir uns eine andere Architektur ansehen. x51 wird nicht für den gcc-Compiler präsentiert, ich mochte x86 nie, ARM hat einen nicht sehr praktischen (für eine Person) und verständlichen Assembler, MIPS ist sehr spezifisch und nicht sehr verbreitet, alle Arten von SPARCs sind noch schlimmer (na ja, ich werde niemanden mit seiner Lieblingsarchitektur beleidigen). nicht besser), aber es gibt einen großartigen Kandidaten MSP430, der auf der kristallklaren und eleganten Architektur von PDP basiert und TI konnte es nicht viel verderben (obwohl die Jungs es versuchten). Eine Bibliothek mit vielen Bits für diese Architektur wird vorgestellt, damit Sie mit dem Studium beginnen können.
Beginnen wir, da es nicht trivial klingt, von Anfang an, dh mit der Ankündigung der Menge. Wir werden sofort sehen, dass der Speicher für die Speicherung in Vier-Byte-Wörtern zugewiesen wird, obwohl die natürliche Einheit in dieser Architektur ein Zwei-Byte-Wort ist und eine recht bequeme und effiziente Arbeit mit Bytes bereitgestellt wird, was zu seltsamen Vorfällen führt. Sie können den Autor verstehen, die Implementierung einer 32-Bit-Nummer sollte überall sein und sich ganz natürlich darauf verlassen, aber in diesem Fall wäre 8-Bit vorzuziehen, und für AVR wäre 8-Bit die einzig vernünftige Lösung.
Eine interessante Frage, aber wie können Sie die Bittiefe der Architektur während des Kompilierungsprozesses bestimmen? Sie müssen es mit uint8_t_fast versuchen. Wir stellen eine mögliche Optimierung fest und fahren fort.
Neben der Zuweisung von Speicher ist die Initialisierung von Interesse - für globale Mengen erfolgt sie auf die Standardart - Nullstellen vor dem Aufruf von main, für lokale Mengen erfolgt sie auch auf die Standardart, dh in keiner Weise, wenn der Anfangswert nicht explizit angegeben wird. Nun, und wie immer, wenn es möglich ist, eine statische Menge mit einem Anfangswert außerhalb der Funktion zu beschreiben, sollte dies verwendet werden, um keine unnötigen Flags zu aktivieren und keine Ausführungszeit damit zu verbringen. Aber hier haben wir keine Enthüllungen erwartet, wir haben nur die allgemeinen Regeln überprüft.
Beginnen wir mit der Änderung der Menge, für die wir eckige Klammern und Methoden zum Setzen und Zurücksetzen hinterlassen haben. Wir können erwarten, dass so etwas das Element n in der Menge M setzt:
M[n / w] |= (1<<(n % w))
Dabei ist w die Anzahl der Bits im Basiselement, die für eine bestimmte Architektur statisch definiertes n (z. B. 4) und die enthaltene Optimierung zu einem Code der folgenden Form führen:
bis.w #0x0010, m
In der Tat sehen wir einen solchen Code in der rechten Hälfte des Fensters, und es ist unwahrscheinlich, dass jemand ernsthaft riskieren würde, zu behaupten, dass eine effektivere Lösung möglich ist. Dies gilt jedoch nur für die angegebenen Bedingungen, für ein beliebiges n ändert sich das Bild vollständig, für Methoden beobachten wir die Validierung des Zulässigkeitsarguments mit der Erzeugung der entsprechenden Ausnahme, und für die Klammern sehen wir die Einschränkung des Arguments mit einer Bitmaske des zulässigen Bereichs mit vollständig vorhersehbarem undefiniertem Verhalten, beide Fälle stimmen mit der Dokumentation durchaus überein. Negative Werte werden ganz korrekt verarbeitet, da Indizes als vorzeichenlose Zahlen betrachtet werden.
Wir machen darauf aufmerksam, dass der zugewiesene Wert für ein Element einer Menge nicht nur erwartungsgemäß 0 und 1 sein kann, sondern auch eine beliebige Ganzzahl, für die die Regel „Was ist eine Einheit? Nicht Null “, ist es ziemlich logisch, spiegelt sich aber schlecht in der Dokumentation wider. Ein wenig seltsam gemacht, aber Boolesche Werte wären natürlicher, kreuzen an und gehen weiter.
Ein Vergleich des Codes, der für den Fall einer statisch unbestimmten Elementnummer der Menge generiert wurde, zeigt, dass die Effizienz des Codes in beiden Fällen ([] und Methoden) sehr eng und klein ist, da ein Unterprogramm aus der Standardbibliothek zur Berechnung aufgerufen wird (1 << n) und dieses Unterprogramm sich verschiebt 32-Bit-Nummer 0x00000001, in zwei Registern platziert. Wir können den Ausgangstext nicht sehen, aber die Tatsache des Aufrufs führt zu traurigen Gedanken. Tatsache ist, dass es in der betrachteten Architektur keine Verschiebung nach links (und es gibt auch keine nach rechts) um eine beliebige Anzahl von Positionen gibt, wie in allen (vielen) geliebten ARMs. Es gibt eine Verschiebung um 1 Position (es wäre seltsam, wenn es überhaupt nicht existieren würde), es gibt eine Verschiebung um 2,3,4 Positionen (aber um eine im Befehl streng festgelegte Zahl, nicht um einen Parameter), es gibt ein REPT-Präfix (aber seine Ausführungsgeschwindigkeit bleibt bestehen das Beste wünschen). Sie können die Verschiebung der kleinsten Einheit (dies ist wichtig, nur eine Einheit) implementieren, dh durch Tricks wie das Austauschen von Tetraden in relativ kurzer Zeit eine Bitmaske anhand der Bitnummer erhalten. Dies ist jedoch ein sehr abhängiger Teil, und im Allgemeinen ist es besser, dies nicht zu tun.
Eine universelle und schnelle Methode wäre daher das Speichern von Bitmasken in einem Array und einem Index. In dieser Architektur ist der Code auch sehr effizient und sieht dann folgendermaßen aus:
M[n/w] |= BitArray[n %w]
Assembler bekommen wie:
bis.b BitArray(r0),M(r1)
Da es sich um Muster handelt und w ein Vielfaches der Größe eines Bytes ist, werden Divisionsoperationen hier sehr effizient implementiert. Wir stellen den klaren Vorteil eines minimal implementierten Speicherelements fest: Für ein Byte ist ein 8-Byte-Array für ein Byte erforderlich, -2 * 16 = 32 Bytes für die Wortorganisation und 4 * 32 = 128 Bytes für ein langes Wort von 32 Bit, um alle erforderlichen zu speichern Masken, warum mehr bezahlen, wenn sich das Ergebnis nicht ändert. Erinnern wir uns an eine weitere mögliche Optimierung und fahren wir fort.
Wir stellen eine weitere Tatsache fest: Viel effizientere Implementierungen von Operationen mit einem festgelegten Element sind möglich, wenn die Zielarchitektur einen bitmarkierten Speicherbereich hat (auch hier wird der zuvor abgelehnte ARM zurückgerufen), bei dem die Elementinstallationsoperation im Allgemeinen in einen BitSetAddr [n] = Kürbis umgewandelt wird 1, was sich in einem Assembler-Befehl für die Konstante n übersetzt, aber dort gibt es bereits genügend effektive Verschiebungen, so dass eine solche Optimierung redundanter ist, insbesondere unter Berücksichtigung ihrer Einschränkungen. Im Prinzip gibt es sowohl in x51 als auch in AVR einen ähnlichen Bitadressierungsbereich, aber es gibt effektive Befehle nur für konstante Elementnummern, und im allgemeinen Fall ist nicht alles so gut (ehrlich gesagt schlecht).
Schauen Sie sich nun den resultierenden Code genau an und beachten Sie, dass wir Artefakte beobachten, die mit dem Speichern des Sets in doppelten Worten verbunden sind. Der Compiler für die Operation zum Ändern eines Elements einer Menge generiert eine Folge von Befehlen, die das entsprechende Doppelwort aus dem Speicher in 2 Register lesen (ich erinnere mich, dass wir 16-Bit-Register haben), modifiziert sie und sendet die Ergebnisse zurück in den Speicher. Wenn wir nur ein Element ändern, enthält die Operationsmaske genau eine von 32 möglichen Einheiten, die verbleibenden Nullen. Wenn wir eine statisch definierte Elementnummer anwenden, sollten Operationen, die das Ergebnis nicht ändern, in der Optimierungsphase ausgeschlossen werden. In der Regel passiert dies, aber bei verschiedenen Operanden geht etwas schief und Artefakte des Formulars gelangen in den endgültigen Code:
bic #0,r0
Das sieht besonders lustig aus, wenn Sie feststellen, dass das Register nicht zurück in den Speicher geschrieben wird, obwohl es gelesen wird. Genau genommen sind die Ergebnisse von Optimierungen nirgendwo geregelt, daher können sie alles sein, und es gibt nichts, worüber man beleidigt werden könnte, aber trotzdem: "Es ist nicht ordentlich, wie es funktioniert." Wir können diesen Prozess nicht direkt beeinflussen, wenn wir den Quellcode des Compilers nicht ernsthaft berücksichtigen. Lassen Sie uns ihn also umgehen - wir helfen dem Optimierer, indem wir seine Aufgabe vereinfachen.
Übrigens kann ich die Antwort auf die Frage immer noch nicht finden - ist es in C ++ auf Makro- oder Vorlagenebene möglich, eine andere Implementierung für die in der Kompilierungsphase statisch definierten gegenüber dem statisch undefinierten Parameter zu definieren. Wenn jemand den Weg der Samurai kennt, sag es mir in den Kommentaren, ich habe es mit constexpr versucht, es hat nicht funktioniert.
Wir setzen unsere Forschung fort und stellen fest, dass der Compiler die Aufrufe des Sets unkontrolliert optimiert (natürlich, wenn die Optimierung aktiviert ist), dh die Reihenfolge der Installation / Reinigung verschiedener Elemente ist nicht vollständig garantiert und in keiner Weise mit der Reihenfolge der Quellcode-Operatoren verbunden. Aber ich habe es nicht geschafft, ein flüchtiges Set zu erstellen. Vielleicht mache ich etwas falsch? Wie bei jeder lokalen Optimierung zwingt der Aufruf einer externen Funktion den Compiler, alle vorbereiteten Operationen für das globale Array zu erzwingen. Dies ist jedoch eine zu starke Lösung und hilft bei lokalen nicht. Nun, es ist wahrscheinlich nichts zu tun, und Sie müssen nur eine ähnliche Funktion berücksichtigen und keine Sets verwenden, um Informationen zwischen Streams über serielle Schnittstellen (dh deren Software-Gegenstücke) zu übertragen.
Eine allgemeine Schlussfolgerung kann gezogen werden: Die Verwendung von Bitset in seiner aktuellen Form für Architekturen mit begrenzten Ressourcen kann aufgrund übermäßiger Kosten sowohl im Speicher als auch zur Laufzeit nicht empfohlen werden. Eine mögliche Änderung, die alle Daten im Text des Kommentars berücksichtigt, liegt bei Github, jeder kann sie verwenden. Die Entstehungsgeschichte dieses Mods wird bald auf Habré veröffentlicht, es gab lustige Momente.
Abschließend eine kleine Bemerkung: Die Implementierung des Data Warehouse "frontal" erfordert selbst bei der optimierten Version des Satzes N / 8 Byte Datenspeicher (für 128 Switches sind 16 Byte erforderlich), und obwohl Operationen O (1) Zeit erfordern, beträgt der Multiplikator viele Einheiten ( und sogar bis zu 10 oder mehr) Zyklen von MK. Unter Berücksichtigung der Anforderungen des Problems und der Einführung bestimmter Einschränkungen können wir daher eine alternative Implementierung der Datenspeicherung anbieten.
Wenn wir glauben, dass nicht mehr als ein Schalter gleichzeitig geschlossen werden kann (wir ignorieren alle anderen, bis sich die momentan gedrückte Taste öffnet), können wir ein Byte umgehen (vorausgesetzt, es gibt nicht mehr als 256 Schalter). und das Schreiben / Lesen dauert O (1) Prozessorzyklen, und der Multiplikator ist ziemlich bescheiden.
Dieser Ansatz ist einfach zu erweitern und Informationen über gleichzeitig geschlossene n Schalter zu speichern, aber Sie sollten n nicht zu groß machen, da die erforderliche Speichermenge zunimmt und die Zeit für die Durchführung von Inversionsoperationen linear mit einer Zunahme der Anzahl von Elementen in der Menge zunimmt, obwohl sie O (1) um bleibt in Bezug auf die Anzahl der Schalter. Der angegebene Zeitanstieg kann durch die dreieckige Implementierung des Binärbaums auf O (loq2 (n)) signifikant reduziert werden, aber für kleines n ist dies nicht so wichtig. Ja, und es ist zweifelhaft, dass die Komplexität der Berechnung des nächsten Index während der Suche die Verringerung der Anzahl einfacher Iterationen kompensieren würde. Zu den Nachteilen dieser Implementierung gehört ein möglicher Fehler beim Aufzeichnen des Elements der Menge, das im aufrufenden Programm verarbeitet werden soll (wir lehnen die Option mit einer sich sofort ändernden Puffergröße und mit Empörung ab - dies gilt nicht für integrierte Lösungen).
Die Umsetzung dieses Ansatzes wird dort gegeben.