問題タブ [expression-templates]

動的プログラミングを使用した行列のネストされた積の最適化に関する記事を読み、boost::uBLAS での実装方法を知りたいと思いました。

ドキュメントを理解したかどうかはわかりませんが(ページの最後で説明されています)、この問題を処理しているようです。を記述すると、ライブラリは、 、およびのサイズに応じてまたはをR = prod(A, prod(B,C));計算します。A x (B x C)(A x B) x CABC

どうすれば達成できますか？ライブラリはどのように「ブラケットを移動」できますか? prodこのようなコード行を書くとき、引数が評価されてから関数が実行されると思っていました。

FAQでは、式テンプレートの概念について言及しています。リンクされていますか？

ウィキペディアの記事では、いくつかのテンプレート クラスを提供しています。実際のコードで使用したい。どうやってやるの？Vecオブジェクトをインスタンス化する方法はほとんどないことがわかりました。

式テンプレートを作成しようとしていますが、解決方法がわからない問題に遭遇しました。C++ Templates: The Complete Guide を読みましたが、この質問に対処していないようです。

例として、(整数の) セット型の式テンプレートを考えてみましょう。これにはset、標準的なセット操作の交差、和集合、否定、xor、差などがあります。これらの関数はすべて反復子に関して効率的な実装を備えているため、式テンプレートが必要です。イテレータのようなインターフェースを持つクラス。例えば、

次に、式テンプレートクラスset_expr_unionなどがあります。問題は、式テンプレート式に対応して作成されたオブジェクトはすべて一時的であるため、const ですが、式を評価するには、値を反復処理する必要があります ( and を呼び出す++) val、およびこれら非定数です。set::operator = (set_expr &)一時変数は非定数パラメーターをバインドしないため、非定数として宣言することはできません。の const 性を取り除くこともできますoperator =が、それは適切な解決策とは思えません。

私の例には、問題を明確にするのに十分な詳細がありません。喜んで明確にします。

編集：ここにいくつかの詳細があります。上記のインターフェースもあると仮定set_expr_unionします: 、および。また、私が持っているとしますset_expr_intersectionoperator ++valoperator bool

ここで、 T はset_expr_unionなどのいずれかであり、のインターフェースset_exprもエクスポートします。t++, val, bool

式テンプレート オブジェクトは、次のようなさまざまな演算子によって生成されます。

実際、オペレーターからの戻り値に対応する一時的な部分に問題があります。

では、考えてみましょう

のようなもので使用したいset3 = set1 & set2。

これは私が書きたいコードです。

ベクトル/行列/クォータニオンなどのように普及しているものの時間をコンパイルするために表現テンプレートがひどいことをすることを想像できますが、それが非常に高速な場合、ゲームはそれを使用しないのはなぜですか? SIMD 命令がデータ レベルの並列処理を有効に活用できることは明らかです。式テンプレートと遅延評価を一緒に使用することは、少なくとも一時変数を排除することに関しては理にかなっているようです。

そのため、Eigen のようなライブラリはそのような機能を宣伝していますが、これがミドルウェア (Havok など) や非常に速度が重要なゲームで一般的に行われているとは思いません。誰でもこれに光を当てることができますか？非決定論または分岐予測と関係がありますか?

for (auto x : expr)式テンプレートは、暗黙的に含まれているように、C ++ 11のrangedに基づいて機能auto&& __range = exprしなくなり、参照がぶら下がることになると理解しています。

に基づいてrangedで正しく動作するように、または少なくともコンパイルエラーをスローするように、式テンプレートクラスを作成する方法はありますか？

基本的に、式テンプレートが正しくコンパイルされても、参照がぶら下がっているために実行時に失敗する可能性を防ぎたいと思います。ユーザーが式テンプレートをラップするのを忘れた場合にサイレントランタイムエラーが発生しない限り、範囲ベースで使用する前に式テンプレートを何かでラップする必要はありません。

私は次のようなことをすることを理解しています:

行列演算で式テンプレート ( などboost::ublas) を使用すると、サイレント ランタイム エラーが発生します。

コンパイラが実行時に期限切れの一時変数を使用する可能性があるコードをコンパイルしないように式テンプレートを設計する方法はありますか?

(この問題を回避しようとして失敗しました。その試みはこちらです)

次のコード（crtp.ccに格納されている）でコンパイラに依存する問題が発生しました：

実際、私がそれをコンパイルするとき：

私が得る：

これは予想される動作です。icpcを使用する場合：

代わりにを取得しSegmentation faultます。ランニング

ソースの29行目を指している

私はC++にまったく慣れておらず、結果が得られずにバグを探すのにかなりの時間を費やしたので、この問題が私が導入したエラーによるものかどうかを理解するために、より経験豊富な人の意見を聞きたいと思います。コンパイラのバグに。

編集：Mike Seymourからの回答の後、コードをそのまま変更しました。これでコンパイラの警告は表示されませんが、以前と同じ動作が得られます（同じvalgrind応答で）。誰かがIntelでコンパイルしようとしましたか？

編集：ウィキペディアの式テンプレートページでコードをコンパイルしようとしました。提供した例とまったく同じ動作が得られました。

編集：私は問題をさらに調査しました、そしてインテルと一緒にコンパイルすることicpcはオペレーターのようです

再帰的に自分自身を呼び出します。私が見つけた回避策の1つは、この演算子をメソッドに置き換えることです。

それに応じて、さまざまなクラスのコンストラクターを変更します。誰かがこれらの2つの振る舞いのどちらが正しいのか、それを説明するための標準を指している可能性があるかを知ることができますか？

私は現在、C ++テンプレート式ライブラリを作成しており、いくつかのインスタンス化をアセンブリレベルで手書きのコードと比較しています。手書き関数は次のとおりです。

このクラスは、メンバー関数vectorを使用して読み取ることができる4つのdoubleの単なるラッパーです。at<index>()設計上の決定により、4つのコンポーネントのインデックスは、通常のの代わりに1, 2, 4, 8アクセスされます。at<index>()0, 1, 2, 3

この関数の目的は、2つのベクトルの乗算の結果を返すことです（ミンコフスキー空間で）。幾何代​​数に精通している場合は、内積（の最初のコンポーネント、とresultの交換で対称）とウェッジ積（残りのコンポーネント、との交換で反対称）が表示されます。幾何代​​数に慣れていない場合は、この関数をベクトルを乗算するための処方箋として使用してください。abab

上記の関数をGCC4.7でコンパイルし、objdump -SC a.outこれによって与えられる逆アセンブルを見ると、次の出力が得られます。

これは私にはかなり良さそうです-最初の（%rsi）と2番目の（%rdx）ベクトルのコンポーネントは一度だけアクセスされ、実際の計算はレジスターでのみ行われます。最後に、結果はレジスターのアドレスに書き込まれ%rdiます。これは最初の引数レジスタなので、ここでは戻り値の最適化が採用されていると思います。

上記の関数の式テンプレートバージョンについては、これを次のリストと比較してください。

この関数のシグネチャは次のとおりです。

どちらのバージョンでも同じ結果が得られることを信頼していただければ幸いです。最初の2行は、参照としてに格納されている1番目と2番目のベクトルを抽出しproductます。私は次のことについて疑問に思いました：

• movsd 0x1f1(%rip),%xmm4と組み合わせて何をxorpd %xmm4,%xmm0しますか？これが「RIP相対アドレス指定」と呼ばれることはすでに知っています 。http：//www.x86-64.org/documentation/assembly.htmlを参照してください。
• なぜGCCは、たとえば0x10(%rax)4回読み取られるキャッシュに、より多くのレジスタを使用しないのですか？

また、100000000のランダムベクトルを生成し、両方の関数に必要な時間をかけて、両方の関数のベンチマークを行いました。

手書き関数は約10％高速です。誰かが式テンプレートの経験があり、手書きのテンプレートに近いパフォーマンスを実現する方法を知っていますか？

単一の変数で多項式を評価するために (バイナリ) 解析ツリーを取得し、ホーナーの規則に従って多項式を評価する同等の解析ツリーを返すアルゴリズムを教えてください。

意図された使用例は式テンプレートにあります。アイデアは、行列xの場合、解析ツリーは次から取得されるということです

の対応する解析ツリーに最適化されます

プログラムの線形代数エンジンとしてEigen行列ライブラリを使用したいと思います。Eigenは、式テンプレートを使用して遅延評価を実装し、ループと計算を簡素化します。

例えば：

Eigenは式テンプレートを使用するため、次のようなコードを使用します

上記のサンプルでは、​​一時的なものを作成せずに、長さ10の単一ループに縮小されます（40ではなく、フロートは4のチャンクによってレジストラに入れられます）。それはどれくらいクールですか？

しかし、このようにライブラリを統合すると、次のようになります。

次に、次のような式：

Eigenの実装方法を利用することはできません。そして、これが最後ではありません。Eigenで式テンプレートが使用されている例は他にもたくさんあります。

簡単な解決策は、演算子を自分で定義せずにdata_公開し、次のような式を記述することです。

これはカプセル化を破りますが、Eigenの効率を維持します。

他の方法は、独自の演算子を作成することですが、式テンプレートを返すようにします。しかし、私はC ++の初心者なので、これが正しい方法かどうかはわかりません。

質問が一般的すぎる場合は申し訳ありません。私は初心者で、誰にも尋ねることはありません。今まではstd::vector<float>どこでも使っていましたが、今は行列も使う必要があります。プロジェクト全体でEigenに切り替えることstd::vector<float>は大きな一歩であり、最初から間違った電話をかけることを恐れています。どんなアドバイスも歓迎します！