Skip to content

Instantly share code, notes, and snippets.

@koron
Last active April 22, 2023 03:27
Show Gist options
  • Save koron/e735dce532c29f509353ec0cb7fd47c4 to your computer and use it in GitHub Desktop.
Save koron/e735dce532c29f509353ec0cb7fd47c4 to your computer and use it in GitHub Desktop.

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

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

使い方

$ javac PnJava.java
$ time java PnJava

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

オリジナルからの変更点

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

結果

3回実行した結果

Javaのバージョン

考察

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

備考

  • intではなくlongで計算したら約40秒くらいになった。およそ記事オリジナルのGo版と同じ時間スケール感なので、やはり64bitで計算することがGo版の問題点だったと言えそう
  • 上限数等を埋め込んでいるので、それにともないJITが必要以上に仕事して速くなってる可能性は否定できない
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment