問題タブ [microbenchmark]

いくつかのベンチマークを実行しましたが、説明の仕方がわからない結果が得られました。

一言で言えば状況：

ジェネリック配列で同じ（計算量が多い）ことを行う2つのクラスがあり、どちらも特殊化を使用しています（@specialized、後で@spec）。1 つのクラスは次のように定義されます。

2番目: (シングルトン)

2 番目のケースでは、パフォーマンスが大幅に低下します。なぜこれが起こることができますか？(注: 現時点では、Java バイトコードも Scala コンパイラの内部もよく理解していません。)

詳細:

完全なコードはこちら: https://github.com/magicgoose/trashbox/tree/master/sorting_tests/src/magicgoose/sorting これは、Java からリッピングされたソート アルゴリズムであり、(ほぼ) 自動で Scala に変換され、比較操作が一般的なものに変更されています。ボクシングせずにプリミティブ型とのカスタム比較を使用できるようにします。加えて、単純なベンチマーク (さまざまな長さでのテスト、JVM のウォームアップと平均化)
結果は次のようになります: (左の列は元の Java ですArrays.sort(int[]))

後者は内部objectで定義されたもので、ひどいものです (約 4 倍遅い)。

更新 1

scalacoptimiseオプションを使用して、または使用せずにベンチマークを実行しましたが、顕著な違いはありません (コンパイルが遅いだけですoptimise)。

列がペアになっているxとの 2 つのデータ フレームがあります。weightsデータ フレームの例を次に示します。

列yr1とyr2は 1 つのペアであり、列yr3とyr4は別のペアです。私の実際のデータでは、列は最大にyr100なり、50 組の列があります。

yr1またはyr2が欠落している場合x、欠落している観測を次のように埋めます。

同様にyr3またはyr4:

ここで、5 (または 30) は列の要素で、x指定された要素のペアで欠落していません。最初の例の値 2 と 3 (および 2 番目の例の値 4 と 2) は、weightsデータ フレーム内の特定の要素ペアに対応するデータ フレーム内の要素xです。ペアの両方の要素が欠落している場合は、欠落しxたままにしておきます。

Rネストされた を使用して上記の操作を行うコードを次に示しfor loopsます。ただし、実際のデータ セットには 2000 または 3000 行あり、ネストされたデータ セットはfor loops現在 10 時間以上実行されています。

if3 番目と 4 番目のステートメントはおそらく必要ないことに気付きました。ifこの 2 つのステートメントを単純に削除すると、このコードの実行時間が大幅に短縮される可能性があります。

reshapeただし、ネストされたの代わりに使用する次の代替ソリューションも思いつきましたfor loops。

現在の R セッションをシャットダウンして上記のアプローチのいずれかを試す前に、より効率的な代替案を提案してください。私はmicrobenchmark少し使用しましたが、ここではまだ試していません。部分的には、考えられるソリューションごとに関数を作成するのが少し怖いからです。また、関数ファミリーを使用して解決策を考え出そうとしましたapplyが、思い付くことができませんでした。

私のreshape解決策は、次の質問から導き出されました。

複数のメジャー変数を持つデータ フレームの形状変更

計算時間に加えて、メモリ不足の可能性も懸念されます。

ベース R に固執するように努めていますが、他のオプションを使用して目的の出力を得ることを検討します。ご提案ありがとうございます。

Lua コードのマイクロベンチマークをいくつか試してみましたが、信じられないほど厄介な問題に遭遇しました。一貫した結果が得られないようです。

例: 以下は単純なフィボナッチ関数の時間を測定することになっている単純な Lua プログラムです。

続けて数回実行しようとすると、次のようなことが起こります。

(これは単なる例であり、簡潔にするために省略されていますが、私が見ている減速曲線の種類を表しています)

約 1.1 秒から始まる時間は、2 秒をはるかに超えて終了します。私がやっているのは、ここに座って上とエンターを繰り返し押していることだけです。Lua クロックを使用する代わりに の呼び出しでテストをラップしtimeたり、数秒かかるように数回ループさせたりすると、同じようなことが起こります。比例して遅くなるようです。しばらく放置すると、時間が戻ってしまうことがあります。そうでない場合もあります（おそらく、どれくらい放置するかわからないためです）。

これは Windows+MSYS 上にあります。Ubuntu (同じマシン) でこれを試すと、別のパターンにつながりますが、依然として一貫性がなく、使用できない結果が得られます (たとえば、テストには 2 秒、次に 3.5 秒、次に 4 秒、次に 2.5 秒かかります...)。タスク マネージャー/トップは、どちらの場合も、バックグラウンドで CPU を消費していないことを示しています。CPU 速度の切り替えは無効です。

私は何を間違っていますか？私のマシンは古いですが、それほど壊れているわけではありません（マシンのせいで、すべてのプログラムが毎秒非常に遅くなった場合、使用できないことに気付くでしょう...）。

私が実際にやろうとしていること：

私がやりたかったのは、バニラの Lua から始めて、変更がインタープリターのパフォーマンスにどのような影響を与えるかを微調整することによって、インタープリターの実装について学ぶことでした。ご覧のとおり、「コントロールの確立」はまだ完了していないため、実際にはまだ何も行っていません。ベンチマークの分散が上記のように高いため、行った変更はすべて完全に失われます。ノイズ。私が Lua を選んだ理由は、現実世界のプログラムでありながら、小さくて読みやすく、変更しやすいからです。これを行うためのより良い基本インタープリター、またはインタープリターのパフォーマンスをベンチマークするための確立された最良の方法がある場合は、回答にそれに関する提案を自由に追加してください。

編集：C従来のCタイミングユーティリティを使用するCプログラムでも同じことが発生しているため、タグを追加します。例：

...次を出力します。

これは、効果が個別の実行に限定されないことを示しています。これは、マシンまたは OS に問題があることを意味していると思います。

メモリをテストするために、C で小さなマイクロ ベンチマークを作成しようとしています。

私のマシン (Intel i5) のキャッシュ サイズは 8MB だと思います。

100% のキャッシュ ミス率を確保しながらメモリをテストするためのロジックを誰かが提案できますか?

現在、memcpy を使用して、私のプログラムは 1 秒間に 420,782,149 回 memcpy を呼び出しています。

キャッシュを回避するにはどうすればよいですか?

rhel 6.1 に基づく 3 ノードのクラスターがあります。

すべてのノードで、2 つの CPU と 4 つの GPU の Tesla M2090/

私は Openmpi 1.6.1 を使用しています。これは正常に動作します (GPU Linpak バージョンでテストされたシステム)。

mvapich2 1.9 をインストールすると、同じ問題が発生します。

このテストで多分トラブル？

Cuda バージョン 5.0

インフィニバンド - メラノックス。

このベンチマークのコンパイルは成功し、CPU (H to H) (localhost と 2 つのノードの両方) のみを使用してポイントツーポイントを開始すると、次のようになります。

mpirun -np 2 ./osu_latency HH

それはうまくいきます。しかし、GPU (CPU から GPU メモリへのコピー) を使用する場合:

mpirun -np 2 ./osu_latency HD

プログラムはsegmentation fault(11)でクラッシュします。

次のパラメーターを使用して、 http://www.nersc.gov/assets/Trinity--NERSC-8-RFP/Benchmarks/Dec17/OMB-NERSC8.tarからこのベンチマーク バージョン 3.7 をコンパイルします。

--prefix=/usr/local/bench/osu --enable-cuda --with-cuda=/usr/local/cuda-5.0 --with-cuda-include=/usr/local/cuda-5.0/include - -with-cuda-libpath=/usr/local/cuda-5.0 CC=/usr/local/mpi/openmpi16/bin/mpicc

絶対パスでプログラムを実行しようとしましたが、効果がありません。

問題はどこだ？少し早いですがお礼を！

この質問と同様に、マイクロベンチマークを実行して、大きな行列から単一の要素を読み取りました。行名を使用するとパフォーマンスが大幅に低下することに驚きました。

マトリックス要素を読み取るには、行名を使用する必要があります。どうすればパフォーマンスを向上させることができますか?

アップデート

Geoffreyの回答とsubset()のベンチマーク結果を追加しました。理由はわかりませんが、subset() の方が読み取り専用のパフォーマンスがはるかに優れています ([[]] では割り当てが可能ですが、subset() では不可能です):

コンピュータ サイエンスの専門家なら誰でも、O(n log n)理論的には HeapSort が最悪のケースで、QuickSort が最悪のケースであることを知っているでしょうO(n^2)。ただし、実際には、適切に実装された (優れたヒューリスティックを使用した) QuickSort は、すべてのデータ セットで HeapSort よりも優れたパフォーマンスを発揮します。一方で、最悪のケースはほとんど観察されず、他方では、CPU キャッシュ ライン、プリフェッチなどは、多くの単純なタスクに大きな違いをもたらします。また、たとえば、QuickSort は で事前に並べ替えられたデータを (適切なヒューリスティックを使用して) 処理できますがO(n)、HeapSort はO(n log n)既存の構造を利用しないため、常に でデータを再編成します。

私の玩具プロジェクトであるcaliper-analyzeでは、最近、ベンチマーク結果からアルゴリズムの実際の平均的な複雑さを推定する方法を検討しています。特に、Lawson と Hanson の NNLS フィッティングを異なる多項式で試しました。

ただし、まだうまく機能していません。使用可能な結果が得られる場合もあれば、そうでない場合もあります。より大きなベンチマークを実行すること、特により多くのパラメーターを試すことが役立つかもしれないと私は考えています。

次の結果は、ランダム性が 10% の SAW パターンで Double オブジェクトを並べ替えたものです。n は、この実行では最大 500 にすぎなかったため、実際の使用を代表するものではありません...数値は、サイズに対する実行時の推定依存性です。出力は手作業で編集され、手動で並べ替えられているため、ツールが現在提供しているものは反映されていません!

この特定の設定では (多くの場合、まったく満足のいく結果が得られません)、結果は既知の動作とほぼ一致することがわかります。バブル ソートは非常にコストがかかり、QuickSort の優れたヒューリスティックの方がはるかに優れています。ただし、たとえば、3 つのヒューリスティックの中央値を使用するO(n + n^2)QuickSort は推定値になりますが、他の QuickSorts は次のように推定されます。O(n + n log n)

だから今、私の実際の質問に：

• どの実装を予測するために、ベンチマーク データから実行時の複雑さの分析を実行するアルゴリズム/アプローチ/ツールを知っていますか?
• これに関する科学記事を知っていますか (実装の平均的な複雑さの推定)?
• ここでより正確な見積もりを得るのに役立つロバストなフィッティング方法を知っていますか? たとえば、NNLS の正規化されたバージョン。
• 合理的な見積もりを得るために必要なサンプル数の経験則を知っていますか? (特に、どのような場合にツールが推定値を提示することを控えるべきか?)

もう一度強調しておきますが、私は理論上の複雑さや形式的な分析には興味がありません。私は、 （理論的には同一のアルゴリズムの）実装が実際の CPU のベンチマーク データでどのように機能するかを確認することに興味があります...一般的な範囲の数値要因は、漸近的な動作よりも重要です。(そして、いいえ、長い目で見れば、時間の複雑さと並べ替えだけではありません。しかし、私はインデックス構造やその他のパラメーターに興味があります。また、間違っていなければ、キャリパーはたとえばメモリ消費量も測定できます)さらに、私はJavaで作業しています。私はmatlabの世界に住んでいないので、Matlabビルトインを呼び出すだけのアプローチは役に立ちません。

時間があれば、より多くのデータ ポイントを取得できるように、これらのベンチマークのいくつかをより多くのサイズで再実行してみます。多分それはうまくいくでしょう...しかし、より小さなデータセットからでもより良い推定値を得るために使用できる、より堅牢な回帰方法があると思います. さらに、サンプルが小さすぎてまったく予測できない場合を検出したいと思います!

LinuxでソートアルゴリズムのCPU時間と壁時間を測定します。getrusageCPU時間を測定しclock_gettime CLOCK_MONOTONIC、壁時間を取得するために使用しています。CPU時間が壁時間よりも大きいことに気付きましたが、それは正しいですか? 私はいつも、CPU 時間は壁時間よりも短くなければならないと考えていました。私の例の結果：

C/C++ コードをベンチマークしたいと考えています。CPU時間、壁時間、サイクル/バイトを測定したい。いくつかの測定関数を作成しましたが、サイクル/バイトに問題があります。

CPU 時間を取得するために、 で関数getrusage()を書きました。RUSAGE_SELFclock_gettimeMONOTONICrdtsc

1024: などのサイズの入力バッファを処理しますchar buffer[1024]。ベンチマークの方法:

1. ウォームアップ フェーズを実行し、単純にfun2measure(args)1000 回呼び出します。

for(int i=0; i<1000; i++) fun2measure(args);

1. 次に、ウォール タイムのリアルタイム ベンチマークを実行します。

   `unsigned long i; 倍の時間かかりました。double timeTotal = 3.0; // 3 秒処理

   for (timeTaken=(double)0, i=0; timeTaken <= timeTotal; timeTaken = walltime(1), i++) fun2measure(args); `

2. CPU時間については（ほぼ同じ）：

   for (timeTaken=(double)0, i=0; timeTaken <= timeTotal; timeTaken = walltime(1), i++) fun2measure(args);

しかし、関数の CPU サイクル カウントを取得する場合は、次のコードを使用します。

次に、サイクル/バイトをカウントします((e - s) / (i * inputsSize);。inputsSizeの長さなので、ここでは 1024bufferです。しかし、totalTime10 秒に上昇すると、奇妙な結果が得られます。

10 秒間:

5 秒間:

4 秒間:

私の質問:

1. それらの結果は大丈夫ですか？
2. 時間を増やすと、CPU で常に 0 サイクル/バイトになるのはなぜですか?
3. このようなベンチマークの平均時間、平均、標準偏差などの統計を測定するにはどうすればよいですか?
4. 私のベンチマーク方法は 100% 大丈夫ですか?

乾杯！

1回目の編集:

に変更iした後double：

私の結果は大丈夫のようです。したがって、質問＃2はもう質問ではありません:)