Ada 202x (27日目) - Iterator_View ================================= .. post:: Dec 27, 2019 :tags: ada, ada_2022 気分を変えて再びイテレータの話。 経緯 ---- 標準ライブラリのコンテナを外部イテレータでループするのは実は割と非効率です。 次の ``Ada.Containers.Vectors`` のインスタンスをループしてみます。 .. code-block:: ada declare package Float_Vectors is new Ada.Containers.Vectors (Positive, Float); C : Float_Vectors.Vector; ``C`` の中身は適当に何か入っているものと思ってください。 ループ自体はAda 2012からのcontainer element iterator(``of`` 形式)で短く書けます。 .. code-block:: ada begin for E of C loop Ada.Float_Text_IO.Put (E); end loop; 次のように展開されます。 .. code-block:: ada begin declare Iter : Float_Vectors.Vector_Iterator_Interfaces .Reversible_Iterator'Class := Float_Vectors.Iterate (C); Cur : Cursor := Float_Vectors.Vector_Iterator_Interfaces.First (Iter); begin while Float_Vectors.Has_Element (Cur) loop declare Ref : Float_Vectors.Reference_Type := Float_Vectors.Reference (C, Cur); E : Float renames Ref.Element.all; begin Ada.Float_Text_IO.Put (E); end; -- Finalize (Ref) Cur := Float_Vectors.Vector_Iterator_Interfaces.Next (Iter, Cur); end loop; end; ループの中だけに注目しても1回ごとに次のものが暗黙のうちに呼ばれています。 1. ``Has_Element`` 2. ``Reference`` 3. ``Finalize`` 4. ``Vector_Iterator_Interfaces.Next`` 1, 2, 4が必要なのは間違いありませんが、3は必要でしょうか? ``Reference_Type`` は要素に対するユーザー定義参照型ですが、なぜ終了処理が? 実は標準コンテナは参照が残っているうちは参照先を破壊するような操作を禁止するチェックを実装しなければなりません。 このチェックはtampering checkと呼ばれます。 ですので2の ``Reference`` でロックして参照の終了処理でアンロックしています。 ということは(ゼロコスト例外でなければ)例外フレームも作られループの中で出たり入ったりしているわけです。 もっと言えば4の ``Next`` も ``Iterate`` が返す型 ``Reversible_Iterator'Class`` がclass-wide型のため動的ディスパッチされています。 リンク時最適化でもしない限りはインライン化できません。 なんとかして最適化したいわけです。 GNATの「最適化」 ---------------- これに関しては2015年とAda 2012が正式に決まってから割と早い時期にGNATが独自に「最適化」を実装してしまっています。 (括弧を付けていますのはこんなものを最適化とは呼びたくないからです。) ドキュメントには記載されていない機能ですがソースツリーの ``exp_ch5.adb`` に説明はあります。 (``Ada.Containers.Vectors`` の実装a-convec.adsには「See Exp_Ch5 for details.」みたいなコメントがあります。 ライブラリのソースを覗くとコンパイラのソース読めって書かれてるわけですよ……。) この「最適化」はコンテナのパッケージで ``Reference_Control_Type`` と ``Pseudo_Reference`` が宣言されているときに実行されます。 それらのエンティティが存在すると先のループは次のように展開されます。 .. code-block:: ada begin declare Iter : Float_Vectors.Vector_Iterator_Interfaces .Reversible_Iterator'Class := Float_Vectors.Iterate (C); Cur : Cursor := Float_Vectors.Vector_Iterator_Interfaces.First (Iter); Control : Float_Vectors.Reference_Control_Type := Float_Vectors.Pseudo_Reference (C); begin while Float_Vectors.Has_Element (Cur) loop declare E : Float renames Get_Element_Access (Cur).all; begin Ada.Float_Text_IO.Put (E); end; Next (Cur); end loop; end; -- Finalize (Control) ループの中で暗黙に呼ばれるものが次のように変わりました。 1. ``Has_Element`` 2. ``Get_Element_Access`` 3. ``Next`` tampering checkのためのロックはループの外に移動されて ``Reference_Control_Type`` が担っています。 そのため要素に対する参照はユーザー定義参照型からただの ``access`` 型となり、取得のための関数も ``Get_Element_Access`` に変わっています。 また ``Next`` も引数にイテレータオブジェクトを取らないものに変わっています。 そのため静的にディスパッチできるようになりインライン化も可能です。 この「最適化」は可視性を無視します。 ``Reference_Control_Type`` 、 ``Pseudo_Reference`` 、``Get_Element_Access`` はパッケージのprivate部にあっても構いません。 酷いですよね。 いやま、これは私の感想に過ぎませんので「これは素晴らしい!」と思ってくださっても構わないですが……。 あとそれからGNATでは ``pragma Suppress (Tampering_Check);`` でtampering checkそのものを抑制できるようになっています。 Ada 202xでの改善 ---------------- Iterator_Viewアスペクト +++++++++++++++++++++++ ``Iterator_View`` アスペクトが追加されました。 このアスペクトには自身の型への ``access`` 型をdiscriminantとして持った別の型を指定します。 言葉で書くと分かり辛いですがこんな感じです。 .. code-block:: ada declare type My_Container is private with Iterator_View => My_Iterator_View; type My_Iterator_View (Ref : not null access My_Container) is private; -- 実装は省略 標準コンテナにも ``Iterator_View`` は指定されています。 ``Vector`` でしたら入れ子になったパッケージ ``Stable`` にある ``Stable.Vector`` が指定されています。 | http://www.ada-auth.org/standards/2xrm/html/RM-A-18-2.html#p8 | http://www.ada-auth.org/standards/2xrm/html/RM-A-18-2.html#p78.2 container element iteratorの展開において ``Iterator_View`` で指定した型が代わりに使われます。 それによりループは次のように展開されます。 .. code-block:: ada begin declare View : Float_Vectors.Stable.Vector (C'Access); -- Initialize (View) Iter : Float_Vectors.Stable.Vector_Iterator_Interfaces .Reversible_Iterator'Class := Float_Vectors.Stable.Iterate (View); Cur : Cursor := Float_Vectors.Stable.Vector_Iterator_Interfaces.First (Iter); begin while Float_Vectors.Stable.Has_Element (Cur) loop declare Ref : Float_Vectors.Stable.Reference_Type := Float_Vectors.Stable.Reference (View, Cur); E : Float renames Ref.Element.all; begin Ada.Float_Text_IO.Put (E); end; Cur := Float_Vectors.Stable.Vector_Iterator_Interfaces.Next (Iter, Cur); end loop; end; -- Finalize (View) ループの中で暗黙に呼ばれるものが次のように変わりました。 1. ``Stable.Has_Element`` 2. ``Stable.Reference`` 3. ``Stable.Vector_Iterator_Interfaces.Next`` tampering checkのためのロックはループの外に移動されて ``Stable.Vector`` が担っています。 初期化時にdiscriminantとして渡された ``Vector`` をロック、終了処理でアンロックします。 ``Stable.Vector`` にはループや要素の参照に必要な一通りのものが再定義されています。 ただし要素の追加や削除を行う操作は用意されていません。 そのため ``Stable.Vector`` を通している限りはtampering checkのための処理は不要です。 ``Stable.Reference_Type`` は ``Vector`` 本体の ``Reference_Type`` と異なり終了処理は必要ありません。 酷いですよね。 いやま、これは私の感想に過ぎませんので「これは素晴らしい!」と思ってくださっても構わないですが……。 あとそれからAda 202xでは ``pragma Suppress (Containers_Assertion_Check);`` でtampering checkや契約等を含めた標準コンテナのチェックを抑制できるようになっています。 関連AI ------ - `AI12-0111-1`_ **Stable Containers to reduce tampering checks** - `AI12-0311-1`_ **Suppressing client-side assertions for language-defined units** 所感 ---- 酷いですよね。 いやま、これは私の感想に過ぎませんので「これは素晴らしい!」と思ってくださっても構わないですが……。 大事なことではありませんけれども3回書きました。 .. _`AI12-0111-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0111-1.txt .. _`AI12-0311-1`: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0311-1.txt