「友人たち、ウィリアムにスイングする時ではありませんか、シェークスピアを理解していますか？ 「。
私は最近、カスタムキーボードに関する投稿を読み、キーボードの実装に関するリファレンス（つまり、名前で署名してパブリックディスプレイに配置することを恥じないもの）を作成するのがいいと思いました。 このアイデアは初めてではありませんが、どういうわけか最初の段階で停止します。初期段階の情報を読むためです。この段階を簡単にカスタマイズでき、使いやすく、普遍的かつ効果的であり、「2つ選択」というオファーは好きではありません。
必要な注意-4つのキーボード実装レイヤーが表示されます：0-イベント検出、1-データ読み取り、2-データのクリーニングと保存、3-メッセージ生成、4-トランスコーディングなど レイヤー1とそれに関連するレイヤー0で最も有望なのは、MKピン（Lokiクラスに基づく）を操作するためにAnton Chizhovテンプレートを使用することで、おそらく、いつか、結果が共有されることを恥じることはないでしょうが、確かに今日ではありません。 今、私はレイヤー2について考えています。
問題を定式化しましょう-「閉じた」と「閉じていない」の2つの定義済みの値のいずれかを取るスイッチの固定セットに関する情報を保存する必要があります。 最も自然な候補は、セットを保存する方法としてのブール変数とビットセットライブラリです。 効率の要件はカテゴリの必須事項であるため、この観点からモジュールの実装を評価することが望ましいです。
最初に考えたのはソースコードを見て、すべてがすぐに明らかになることでしたが、簡単に知り合った後、他の人のテンプレートについて学ぶことはあまり面白くない（そしてあまり生産的ではない）ことに気付きました。 さらに、ソースは、コンパイラに対して直接閉じられているため、実装の有効性の正確な評価を提供しません。 実際、ソーステキストをまだ調査する必要がありました。さもなければ、変更を行うことは非常に長いプロセスになります（もちろん、特定の結果を達成することに関心がない限り）が、これは別の投稿のトピックです。
したがって、「ブラックボックス」を調べる手法が採用されています。さまざまなコードの断片を入力に送り、生成されたアセンブラを検討します。 残念ながら、この実装には研究中のライブラリがないため、おなじみのAVRアーキテクチャにお気に入りのゴッドボルトサイトを使用することはできません。 もちろん、ペンでドラッグすることもできますが、それが正しいソースコードになるという保証はありません。
したがって、別のアーキテクチャを見ていきます。 x51はgccコンパイラーには提示されません。x86は好きではありません。ARMはあまり便利ではなく（人にとって）理解しやすいアセンブラーです。MIPSは非常に特殊で一般的ではありません良くありません）、しかし、PDPのクリスタルクリアでエレガントなアーキテクチャに基づいた素晴らしい候補MSP430があり、TIはそれをあまり損なうことができませんでした（しかし、彼らは試しました）。 このアーキテクチャの多くのビットのライブラリが提示されているので、勉強を始めることができます。
始めから、つまり多数のアナウンスで、些細なことではないように、始めましょう。 このアーキテクチャの自然な単位は2バイトワードであるという事実にもかかわらず、ストレージのメモリは4バイトワードで割り当てられ、バイトの非常に便利で効率的な作業が提供され、奇妙な事件につながることがすぐにわかります。 著者を理解することができます、32ビット数の実装はどこにでもあり、非常に自然にそれに依存する必要がありますが、この場合、8ビットが望ましいでしょうし、AVRの場合、8ビットが唯一の合理的なソリューションです。
興味深い質問ですが、コンパイルプロセス中にアーキテクチャのビット深度をどのように決定できるのか、uint8_t_fastを試してみる必要があります。 最適化の可能性に注意し、次に進みます。
メモリの割り当てに加えて、初期化が重要です-グローバルセットの場合は標準的な方法で行われます-メインを呼び出す前のゼロ化、ローカルセットの場合も標準的な方法で行われます。つまり、初期値が明示的に指定されていない場合は行われません。 さて、そして、いつものように、関数の外部の初期値で静的セットを記述することが可能であれば、不必要なフラグをオンにせず、それらに実行時間を費やさないようにこれを使用する必要があります。 しかし、ここでは啓示を期待していませんでしたが、一般的なルールをチェックしました。
セットの変更を始めましょう。セットの変更には、角括弧とセットおよびリセットメソッドがあります。 セットMの要素nを設定するには、次のようなものが期待できます。
M[n / w] |= (1<<(n % w))
ここで、wはベース要素のビット数です。これは、特定のアーキテクチャに対して、静的に定義されたn（たとえば4）と含まれる最適化により、次の形式のコードになります。
bis.w #0x0010, m
実際、このようなコードはウィンドウの右半分に表示され、より効果的なソリューションが可能であると断言するリスクを誰もが負うことはほとんどありません。 しかし、これは示された条件のみであり、任意のnについては画像が完全に変化し、メソッドについては引数引数の有効性を対応する例外の生成とともに観察し、括弧については引数が完全に予測可能な未定義の動作を伴う許容範囲のビットマスクによって制限されていることがわかります。どちらの場合もドキュメントと非常に一致しています インデックスは符号なしの数値として扱われるため、負の値は非常に正しく処理されます。
セットの要素に割り当てられた値は、予想されるように0と1だけでなく、「ユニットとは何か？ ゼロではありません」、それは非常に論理的ですが、ドキュメントにはあまり反映されていません。 少し奇妙なことをしましたが、ブール値はより自然で、刻みをつけて進みます。
セットの静的に不確定な要素番号の場合に生成されたコードを比較すると、標準ライブラリのサブルーチンが（1 << n）を計算するために呼び出され、このサブルーチンがシフトするため、両方のケース（[]およびメソッド）でコードの効率が非常に近くて小さいことがわかります2つのレジスタに配置された32ビットの数値0x00000001。 私たちはそのソーステキストを見ることができませんが、電話自体の事実は悲しい考えにつながります。 事実、検討中のアーキテクチャでは、すべての（多くの）最愛のARMのように、任意の数の位置による左へのシフトはありません（そして右もありません）。 1桁のシフトがあり（まったく存在しない場合は奇妙です）、2,3,4桁のシフトがあります（ただし、パラメーターではなく、コマンドで厳密に固定された数値による）、REPTプレフィックスがあります（ただし、実行速度は変わります）最高を願うために）。 最小単位のシフトを実装できます（これは重要で、1単位のみです）、つまり、テトラッドの交換などのトリックにより、ビット番号でビットマスクを取得しますが、これは非常に依存する部分であり、一般的な場合は、それを行わない方が良いでしょう。
したがって、普遍的で高速な方法は、ビットマスクを配列とインデックスに格納することです。このアーキテクチャでは、コードも次のようになります。
M[n/w] |= BitArray[n %w]
次のようなアセンブラの取得：
bis.b BitArray(r0),M(r1)
パターンについて説明しており、wは1バイトのサイズの倍数であるため、除算操作はここで非常に効率的に実装されます。 最小限に実装されたストレージ要素の明確な利点に注目してください：1バイトの場合、8バイトの配列が1バイトに必要です-2 * 16 = 32バイトのワード編成、および4 * 32 = 128バイトの32ビットのロングワードに必要なすべてを格納するマスク、しかし結果が変わらないならなぜもっと支払う。 もう1つの可能な最適化を思い出して、次に進みましょう。
もう1つの事実に注目してください。ターゲットアーキテクチャにビットマークされたメモリ領域がある場合、要素のインストール操作が一般的にBitSetAddr [n] = pumpkinに変わる、セット要素による操作のより効果的な実装が可能です。 1、これは定数nの1つのアセンブラーコマンドに変換されますが、既に十分な効果的なシフトがあるため、そのような最適化は、特にその制限を考慮して、より冗長になります。 原則として、x51とAVRの両方に同様のビットアドレス指定領域がありますが、定数要素番号に対してのみ有効なコマンドがあり、一般的な場合、すべてがそれほど良くない（率直に言って悪い）。
さて、結果のコードをよく見て、セットをダブルワードで保存することに関連するアーティファクトを観察していることに注意してください。 セットの要素を変更する操作用のコンパイラーは、メモリから対応するダブルワードを2つのレジスターに読み込む一連のコマンドを生成し（16ビットのレジスターがあることを思い出します）、それらを変更して、結果をメモリーに送り返します。 要素を1つだけ変更した場合、操作マスクには、可能な32個のうち残り1個のゼロだけが含まれます。 静的に定義された要素番号を適用する場合、結果を変更しない操作は最適化段階で除外する必要があります。 原則として、これは起こりますが、さまざまなオペランドに対して何かがおかしくなり、フォームのアーティファクトが最終コードに漏れます。
bic #0,r0
レジスタが読み込まれているにもかかわらず、メモリに書き戻されていないことに気付いた場合は、特におかしく見えます。 厳密に言えば、最適化の結果はどこでも規制されていないため、何でもかまいません。気にすることは何もありませんが、それでも「うまくいかない」。 コンパイラのソースコードを真剣に考慮しない場合、このプロセスに直接影響を与えることはできません。そのため、それをバイパスしましょう-オプティマイザのタスクを簡素化するのに役立ちます。
ところで、私はまだ質問の答えを見つけることができません-C ++でマクロまたはテンプレートレベルで、コンパイル段階で静的に定義されたパラメータと静的に未定義のパラメータの異なる実装を定義することは可能ですか？ 誰かがsaの道を知っているなら、コメントで教えてください、私はconstexprを試してみましたが、うまくいきませんでした。
私たちは調査を続け、コンパイラーがセットへの呼び出しを制御不能に最適化していることを発見しています（もちろん、最適化がオンになっている場合）。つまり、さまざまな要素のインストール/クリーニングの順序は完全に保証されておらず、ソースコード演算子の順序とはまったく関係ありません。 しかし、揮発性セットを作成できませんでした。多分何か間違っているのでしょうか？ ローカル最適化の場合と同様に、外部関数を呼び出すと、コンパイラーはグローバル配列に対して準備されたすべての操作を強制的に実行しますが、これは解決策としては強すぎて、ローカル操作には役立ちません。 まあ、おそらく何もする必要はありません。同様の機能を考慮するだけで、シリアルインターフェイスを使用してストリーム間で情報を転送するためにセットを使用する必要はありません（つまり、対応するソフトウェア）。
一般的な結論を下すことができます。メモリとランタイムの両方で過度のコストが発生するため、リソースが限られたアーキテクチャに現在の形式でビットセットを使用することは推奨できません。 コメントのテキストのすべてのデータを考慮に入れる可能性のある変更はGithubにあり、誰でも使用できます。 このmodの作成の歴史は間もなくHabréに投稿され、面白い瞬間がありました。
結論として、小さな備考-セットの最適化されたバージョンでさえ、データストレージ「ヘッドオン」の実装には、N / 8バイトのデータメモリ（128スイッチの場合、16バイトが必要）が必要であり、操作にはO（1）時間が必要ですが、乗数は多くの単位（さらに最大10個以上のMKティックもあります。 したがって、問題の要件を考慮し、特定の制限を導入して、データストレージの代替実装を提供できます。
いつでも複数のスイッチを閉じることはできないと考えている場合（現在押されているボタンが開くまで、他のすべてを無視します）、1バイトをバイパスできます（256個以下のスイッチがある場合）書き込み/読み取りにはO（1）プロセッササイクルがかかり、乗数はかなり控えめになります。
このアプローチは、同時に閉じられたn個のスイッチに関する情報を簡単に拡張および保存しますが、必要なメモリ量が増加し、反転操作を実行する時間がセット内の要素数の増加とともに線形に増加するため、nを大きくしすぎないでください（ただし、O（1）のままです）スイッチの数に関連して。 示されている時間の増加は、Oへのバイナリツリーの三角形実装（loq2（n））を使用することで大幅に削減できますが、nが小さい場合はそれほど重要ではありません。 はい。検索中に次のインデックスを計算する複雑さが、単純な反復回数の減少を補うことは疑わしいです。 この実装の欠点には、呼び出し元のプログラムで処理する必要があるセットの要素の記録に失敗する可能性があります（バッファーサイズが変更されたオプションを即座に拒否します-これは組み込みソリューションではありません）。
このアプローチの実装はそこで提供されます。