45

プロジェクトオイラーの問題5にはいくつかの異なる解決策がありますが、この特定の実装における2つの言語/プラットフォーム間の実行時間の違いに興味をそそられます。コンパイラフラグを使用して最適化を行うことはありませんでした。単純なjavac（コマンドライン経由）およびcsc（Visual Studio経由）だけです。

これがJavaコードです。55msで終了します。

public class Problem005b
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        int i = 20;
        while (true)
        {
            if (
                    (i % 19 == 0) &&
                    (i % 18 == 0) &&
                    (i % 17 == 0) &&
                    (i % 16 == 0) &&
                    (i % 15 == 0) &&
                    (i % 14 == 0) &&
                    (i % 13 == 0) &&
                    (i % 12 == 0) &&
                    (i % 11 == 0)
                )
            {
                break;
            }
            i += 20;
        }
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(end-begin + "ms");
    }   
}

これは同じC＃コードです。320msで終了します

using System;

namespace ProjectEuler05
{
    class Problem005
    {
        static void Main(String[] args)
        {
            DateTime begin = DateTime.Now;
            int i = 20;
            while (true)
            {
                if (
                        (i % 19 == 0) &&
                        (i % 18 == 0) &&
                        (i % 17 == 0) &&
                        (i % 16 == 0) &&
                        (i % 15 == 0) &&
                        (i % 14 == 0) &&
                        (i % 13 == 0) &&
                        (i % 12 == 0) &&
                        (i % 11 == 0)
                    )
                    {
                        break;
                    }
                i += 20;
            }
            DateTime end = DateTime.Now;
            TimeSpan elapsed = end - begin;
            Console.WriteLine(i);
            Console.WriteLine(elapsed.TotalMilliseconds + "ms");
        }
    }
}
4

7 に答える 7

40
  1. コードの実行時間を計るには、StopWatchクラスを使用する必要があります。
  2. また、JITやランタイムなどを考慮する必要があるため、テストを十分な回数（10,000、100,000回など）実行して、ある種の平均を取得します。プログラムではなく、コードを複数回実行することが重要です。したがって、メソッドを記述し、メインメソッドをループして測定値を取得します。
  3. アセンブリからすべてのデバッグ要素を削除し、リリースビルドでコードをスタンドアロンで実行できるようにします
于 2011-05-10T15:17:44.363 に答える
24

可能な最適化がいくつかあります。たぶん、Java JITはそれらを実行していますが、CLRは実行していません。

最適化＃1：

(x % a == 0) && (x % b == 0) && ... && (x % z == 0)

と同等です

(x % lcm(a, b, ... z) == 0)

したがって、あなたの例では、比較チェーンを次のように置き換えることができます

if (i % 232792560 == 0) break;

（もちろん、すでにLCMを計算している場合は、そもそもプログラムを実行しても意味がありません！）

最適化＃2：

これも同等です：

if (i % (14549535 * 16)) == 0 break;

また

if ((i % 16 == 0) && (i % 14549535 == 0)) break;

最初の除算はマスクに置き換えて、ゼロと比較できます。

if (((i & 15) == 0) && (i % 14549535 == 0)) break;

2番目の除算は、モジュラ逆数による乗算に置き換えることができます。

final long LCM = 14549535;
final long INV_LCM = 8384559098224769503L; // == 14549535**-1 mod 2**64
final long MAX_QUOTIENT = Long.MAX_VALUE / LCM;
// ...
if (((i & 15) == 0) &&
    (0 <= (i>>4) * INV_LCM) &&
    ((i>>4) * INV_LCM < MAX_QUOTIENT)) {
    break;
}

JITがこれを採用している可能性はやや低いですが、思ったほど遠くはありません。一部のCコンパイラは、この方法でポインタ減算を実装しています。

于 2011-05-10T16:32:25.840 に答える
12

これら2つを近づけるための鍵は、比較が公平であることを確認することです。

まず、デバッグビルドの実行に関連するコストを確認し、実行したようにpdbシンボルをロードします。

次に、初期化コストがカウントされていないことを確認する必要があります。明らかに、これらは実際のコストであり、一部の人にとっては重要かもしれませんが、この場合、ループ自体に関心があります。

次に、プラットフォーム固有の動作に対処する必要があります。64ビットWindowsマシンを使用している場合は、32ビットモードまたは64ビットモードのいずれかで実行している可能性があります。64ビットモードでは、JITは多くの点で異なり、結果のコードが大幅に変更されることがよくあります。具体的には、適切に推測すると、2倍の汎用レジスタにアクセスできます。

この場合、ループの内側のセクションは、単純にマシンコードに変換されると、モジュロテストで使用される定数をレジスタにロードする必要があります。ループに必要なすべてのものを保持するのに不十分な場合は、それらをメモリからプッシュする必要があります。レベル1のキャッシュから来たとしても、これはすべてをレジスターに保持することに比べて大きな打撃となるでしょう。

VS 2010では、MSはデフォルトのターゲットをanycpuからx86に変更しました。私はMSFTのリソースや顧客向けの知識に勝るものはないので、それを二度と推測しようとはしません。ただし、実行しているパフォーマンス分析のようなものを見ている人は、必ず両方を試してください。

これらの格差が解消されると、数値ははるかに合理的になります。それ以上の違いは、知識に基づいた推測よりも優れている必要があります。代わりに、生成されたマシンコードの実際の違いを調査する必要があります。

これについては、最適化コンパイラにとって興味深いと思うことがいくつかあります。

  • すでに述べたもの：
    • lcmオプションは興味深いですが、プログラマーのライターが気になっているのがわかりません。
    • 除算の乗算とマスキングへの削減。
      • 私はこれについて十分に知りませんが、他の人々は彼らがより最近のインテルチップの仕切りをかなり良く呼び出すことに注意しようとしました。
      • おそらく、SSE2を使用して複雑なものを配置することもできます。
      • 確かに、モジュロ16演算は、マスクまたはシフトへの変換に適しています。
    • コンパイラーは、どのテストにも副作用がないことに気付く可能性があります。
      • スーパースカラープロセッサでは、それらのいくつかを一度に投機的に評価しようとする可能性があります。これにより、処理がかなり高速になりますが、コンパイラのレイアウトがOO実行エンジンとどの程度相互作用するかに大きく依存します。
    • レジスターの圧力が厳しい場合は、定数を単一の変数として実装し、各ループの開始時に設定してから、進むにつれてインクリメントすることができます。

これらはすべて完全な推測であり、アイドル状態の蛇行と見なす必要があります。知りたい場合は分解してください。

于 2011-05-11T20:55:02.597 に答える
3

（OPから移動）

ターゲットをx86から​​anycpuに変更すると、平均実行時間が282msから84msに短縮されました。たぶん私はこれを2番目のスレッドに分割する必要がありますか？

更新：いくつかのテストの問題を指摘して
くれた以下のFemarefに感謝します。実際、彼の提案に従った後は時間が短くなり、VMのセットアップ時間がJavaではかなりの時間でしたが、C＃ではおそらくそうではなかったことを示しています。C＃では、重要なのはデバッグシンボルでした。

各ループを10,000回実行し、最後に平均ミリ秒のみを出力するようにコードを更新しました。私が行った唯一の重要な変更は、解像度を上げるために[StopWatchクラス] [3]に切り替えたC＃バージョンへの変更でした。十分に良いので、ミリ秒に固執しました。

結果：
テストの変更は、Javaが（まだ）C＃よりもはるかに高速である理由を説明していません。C＃のパフォーマンスは優れていましたが、これはデバッグシンボルを削除することで完全に説明できます。[Mike Two] [4]を読んで、このOPに添付されたコメントを交換すると、デバッグからリリースに切り替えるだけで、C＃コードの5回の実行で平均約280msが得られたことがわかります。

番号：

  • 変更されていないJavaコードの10,000カウントループにより、平均45ミリ秒（55ミリ秒から減少）が得られました。
  • StopWatchクラスを使用したC＃コードの10,000カウントループでは、平均282ミリ秒（320ミリ秒から減少）が得られました。

これらすべてが違いを説明できないままにします。実際、差はさらに悪化しました。Javaは約5.8倍高速から約6.2倍高速になりました。

于 2014-11-02T23:42:12.527 に答える
2

これは、適切なタイミングを実行するには短すぎるタスクです。両方を少なくとも1000回実行して、何が起こるかを確認する必要があります。これらをコマンドラインから実行しているように見えます。この場合、両方のJITコンパイラを比較している可能性があります。シンプルなGUIに両方の後ろのボタンを配置し、経過時間を返す前に、少なくともこのボタンを数百回ループさせてみてください。JITコンパイルを無視しても、OSスケジューラの粒度によってタイミングがずれることがあります。

ああ、そしてJITのせいで...ボタンを押したときの2番目の結果だけを数えます。:)

于 2011-05-10T15:29:32.523 に答える
1

おそらく、DateTimeオブジェクトの構築は。よりもはるかに高価であるためSystem.currentTimeMillisです。

于 2011-05-10T15:17:54.407 に答える
1

Javaでは、System.nanoTime（）を使用します。2秒未満かかるテストは、もっと長く実行する必要があります。Javaは、非効率的なコードや何もしないコードを最適化するのに非常に優れていることに注意してください。より興味深いテストは、コードを最適化した場合です。

ループを使用せずに決定できる解決策を取得しようとしています。つまり、別の方法でより適切に実行される問題です。

11から20の因数、つまり2、2、2、2、3、3、5、7、11、13、17、19の積が必要です。これらを掛け合わせると、答えが得られます。

于 2011-05-10T15:28:03.403 に答える