Ada 202x (27日目) - Iterator_View¶
気分を変えて再びイテレータの話。
経緯¶
標準ライブラリのコンテナを外部イテレータでループするのは実は割と非効率です。
次の Ada.Containers.Vectors のインスタンスをループしてみます。
declare
package Float_Vectors is new Ada.Containers.Vectors (Positive, Float);
C : Float_Vectors.Vector;
C の中身は適当に何か入っているものと思ってください。
ループ自体はAda 2012からのcontainer element iterator(of 形式)で短く書けます。
begin
for E of C loop
Ada.Float_Text_IO.Put (E);
end loop;
次のように展開されます。
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回ごとに次のものが暗黙のうちに呼ばれています。
Has_ElementReferenceFinalizeVector_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 が宣言されているときに実行されます。
それらのエンティティが存在すると先のループは次のように展開されます。
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)
ループの中で暗黙に呼ばれるものが次のように変わりました。
Has_ElementGet_Element_AccessNext
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として持った別の型を指定します。
言葉で書くと分かり辛いですがこんな感じです。
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 が指定されています。
container element iteratorの展開において Iterator_View で指定した型が代わりに使われます。
それによりループは次のように展開されます。
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)
ループの中で暗黙に呼ばれるものが次のように変わりました。
Stable.Has_ElementStable.ReferenceStable.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回書きました。