README.md

https://transparent-to-radiation.blogspot.com/2023/04/20234.html

記事「プログラミング言語の実行速度比較」の、Java追試

使い方

$ javac PnJava.java
$ time java PnJava

1億までの素数を数え上げる。 もろもろのパラメーターは省略&埋め込んだ。

オリジナルからの変更点

• ArrayListの代わりに固定配列を使った
• Integerの代わりにintで保存した
• 上限の1億や、素数を格納する配列のサイズは埋め込みにしてる

結果

• C言語で約11秒の環境で、約13秒の実行結果になった。
• オリジナルのまま実行すると約15秒の環境

考察

• JavaはGCで生き残るオブジェクト数が多くなると、GCにかかる時間が伸びる傾向にある (経験上100万個を超えるとキツくなりだす)
• int[] (固定)にすることで
  • 再アロケーション&メモリコピーがなくなる
  • オブジェクト数≒メモリ量は大幅に減っていると期待できる(ちゃんと観測したほうが良い)
  • GCの時間が減っていると期待できる(ちゃんと観測したほうが良い)
  • メモリレイアウトがシーケンシャル&コンパクトになり、局所的なアクセスができ速度向上が期待できる

備考

• intではなくlongで計算したら約40秒くらいになった。およそ記事オリジナルのGo版と同じ時間スケール感なので、やはり64bitで計算することがGo版の問題点だったと言えそう
• 上限数等を埋め込んでいるので、それにともないJITが必要以上に仕事して速くなってる可能性は否定できない

PnJava.java

import java.util.List;
import java.util.ArrayList;

public class PnJava {

    int[] primes = new int[5761455];
    int primeLast = 0;

    void addPrime(int n) {
        primes[primeLast] = n;
        primeLast++;
    }

    private int upperLimit = 0;

    PnJava(int upperLimit) {
        this.upperLimit = upperLimit;
    }

    boolean isPrimeNumber(int n) {
        for (int i = 0; i < primeLast; i++) {
            int pn = primes[i];
            if (pn * pn > n) {
                return true;
            }
            if (n % pn == 0) {
                return false;
            }
        }
        return true;
    }

    void run() {
        addPrime(2);
        System.out.println("Upper limit: " + upperLimit);
        for (int n = 3; n <= upperLimit; n += 2) {
            if (isPrimeNumber(n)) {
                addPrime(n);
            }
        }
        System.out.println("Count: " + primeLast);
    }

    public static void main(String[] args) {
        var app = new PnJava(100_000_000);
        app.run();
    }
}