問題タブ [haskell-vector]

これを試すと：

...次のエラーが表示されます。

UndecidableInstances確かに使用すると消えますが、その拡張機能の使用には注意が必要です。この場合、物事を機能させる他の方法はありますか？(型をあまり変更しないことが望ましいです。)

Vectorインデックスから値のカスタム データ型 (またはタプル) を作成する関数を使用して、s のタプルを生成しようとしています。望ましい結果を達成するアプローチは次のとおりです。

以下に示すように、Vector ごとに 1 回の反復で実行したいことを除いて、 function の複数回の評価は避けますf。

注意として、Vectorライブラリが融合をサポートしていることは理解しており、最初の例はすでにかなり効率的です。概念の解決策が必要ですgenerate。他のライブラリには非常によく似たコンストラクターがあり (RepafromFunctionなど)、Vectorここでは単に問題を示すために s を使用しています。

関数呼び出しのある種のメモ化が機能するかもしれfませんが、何も考えられません。

編集：

Repa を使用した問題の別のデモ:

ベクトルと同じように、フュージョンはパフォーマンスを節約しますarrが、タプルの中間配列が依然として必要であり、これを回避しようとしています。

編集2：（3年後）

fromFunction上記の Repa の例では、遅延配列が作成されるため、中間配列は作成されません。代わりに、さらに悪いことに、fインデックスごとに 2 回評価されます。1 回目は最初の配列、2 回目は 2 番目の配列です。このような作業の重複を避けるために、遅延配列を計算する必要があります。

私は Haskell を学び始めていますが、チュートリアルが飛び越える小さなことを理解するのが難しいと感じています。現在、Vector.Fixed の形式でタプルを使用しています。

1. aとはどう違いbますか？

2. fに相当 する VF ベクトルを作成するにはどうすればよい[a, a] = [(7,7), (7,7)]ですか?

3. gに相当する VU ベクトルを作成するにはどうすればよい[[a], [a,a]] = [[(7,7)], [(7,7), (7,7)]]ですか?

質問 2 と 3 については、関数を使用しようとすると、型エラーを回避できませんconvert。

4. タプルの長さは常に 2 になることはわかっていますが、f固定サイズのタプルのリスト (または何でも) と、 g 2 次元の別のタプルが必要です (たとえば[[(1,2),(3,4)],[(1,2)]]、トップ リストもサブ リストも固定サイズ. と の同じ型に固執する必要がfありgますか?

5. Data.Vector.Fixed と Data.Vector.Unboxed はどちらも同じパッケージに由来するように見えますが、メンテナーが異なります。いわば両方とも公式のものですか、それともベクトル実装であること以外に類似点はありませんか?

だから...私は、vectorあまり考慮せずに、（パッケージからの）ボックス化されていないベクターを使用しました。vector-th-unboxそれらのインスタンスを簡単に作成できます。

ここで、これらのインスタンスを自動的に派生させることができないインスタンスに遭遇しました。これは、ファントム型パラメーターを持つデータ型です ( のように、長さをエンコードするVector (s :: Nat) a場所)。s

Storableこれにより、とUnboxedベクトルの違いについて考えさせられました。私が自分で考え出したこと：

• Unboxedたとえば、タプルを個別のベクトルとして保存し、これらの値の 1 つだけが必要な場合に帯域幅を無駄にしないことで、キャッシュの局所性を向上させます。
• StorablereadArray#ボックス化されていない値を返す単純な (そしておそらく効率的な) s にコンパイルされます (コアを読むことで明らかです)。
• Storable外部コードとの相互運用性を可能にする直接ポインタ アクセスを許可します。Unboxedしません。
• [編集]インスタンスは、 (つまりand )Storableインスタンスよりも実際には手で書く方が簡単です。UnboxVectorMVector

Unboxedそれだけでは、なぜ存在するのかさえ私には明らかになりません。それにはほとんど利点がないようです。おそらく私はそこに何かが欠けていますか？

最近 Data.Vector を使い始めました。私の理解では、ベクトル操作のチェーンを取り、それらを融合によって効率的に組み合わせることができるはずです。

特に、これら 2 つの関数が同様のパフォーマンス特性を持つことを期待します (つまり、searchTopDown が融合して searchTd のようなものになります)。

ただし、このコードをベンチマークすると、桁違いのパフォーマンスの違いが示されます。

質問: searchTopDown の融合を妨げているものは何ですか? それが融合するのを助けるために私は何ができますか? 一般的に、融合はいつ期待できますか?

ベンチマークに使用されるコード:

EDIT @Zeta の提案に従って (追加-O2)、両方の機能から優れたパフォーマンスが得られます。ただし、大規模なプロジェクトでこの問題が発生するため、ベンチマーク コードを変更して似たものにしました。この場合searchTopDownは線形のようです。i新しいベンチマーク コードと結果 (マイクロ秒):

Haskell で共有同時実行ベクトルを探しているので、ベクトル ライブラリを stm またはアトミック primops と組み合わせるという、ここで説明しているもの以外のパフォーマンスの高いソリューションを指す答えを受け入れます。

変更可能なベクトル ( ) と、アトミックに (たとえば、 stm またはatomic-primops を使用して) Data.Vector.Mutable.IOVector1 回切り替えることができるいくつかのフラグを共有する 2 つのスレッドがあります。スレッド 1 は、フラグをアトミックに切り替える前または後にベクトルに (非アトミックに) 書き込むことができ、スレッド 2 は、フラグが切り替えられたかどうかを確認する前または後にベクトルから読み取ることができます。TVarIORef

具体的にするために、いくつかの最小限の例を次に示します。それらを評価させるデータ競合はありundefinedますか？

• STM を使用した例: http://lpaste.net/362596
• アトミック primops の使用例: http://lpaste.net/362595

より一般的には、フラグのアトミック操作の相対的な順序付けは、ベクトルの操作間の何らかの順序付けを意味しますか? 特に、次のことが正しいかどうか疑問に思っています。

• チェックが切り替え前に行われる場合、チェック前の読み取りは、切り替え後の書き込みを認識できません。
• チェックが切り替え後に発生する場合、チェックに続く読み取りは、切り替え前の書き込みを確認する必要があります。

readIORefアトミックプリモップの場合、 /の使用について特に疑問があります。これはreadForCAS、ドキュメントがバリアを意味しないと述べているためです。

ソースにmodifyは、安全に実行できる場合はその場で操作が実行され、そうでない場合はベクトルのコピーが変更されると記載されています。

しかし、のコードを見るとmodify：

常に呼び出されているように見えますclone（不変のベクトルに対する破壊的な操作である必要があると思うので、これは理にかなっています）。

私はこれを誤解していますか？そうでない場合、 が呼び出されない例は何ですか?cloneまた、どのようData.Vectorにバイパスを実現しますか?