はじめに
AtCoderなどの競技プログラミングでは、与えられた問題を解くプログラムを書くわけですが、プログラムの実行に当たっては「時間」と「メモリ使用量」の2つの制約をクリアする必要があります。
多くの問題では、効率の良いアルゴリズムを使わないと制限時間に引っかかって(TLE=Time Limit Exceededと呼ばれています)不正解となってしまうので、競技プログラマーはいかに計算量を減らして実行時間を制限時間内に収めるかに苦労するわけです。
もう一つの制約としてメモリ使用量があります。これに引っかかる(MLE=Memory Limit Exceededと呼ばれています)ことは比較的少ないかもしれませんが、Java言語を使用した時に注意しないと引っかかるケースがあるので、今回はこれをテーマに書いていきたいと思います。
データのサイズ
プリミティブ型
まずは競プロでよく使う基本的なプリミティブ型のサイズを確認しておきます。この辺りは他の言語と特に差はないと思います。
| データ型 | メモリ使用量(byte) |
|---|---|
| int | 4 |
| long | 8 |
| double | 8 |
| boolean | 1 |
| char | 2 |
オブジェクト
プリミティブ型はちょっとプログラムをやったことがある人は知っていたと思いますが、オブジェクトがどのくらいメモリを使用するのかは知らない人も多いと思います(筆者も知りませんでした)。今回はjava.sizeOfというツールを使って実測してみました。
import net.sourceforge.sizeof.SizeOf;
public class MemoryTest {
public static void main(String[] args) {
SizeOf.skipFinalField(false);
SizeOf.skipStaticField(true);
System.out.println("Class0:" + SizeOf.deepSizeOf(new Class0()));
System.out.println("Class1:" + SizeOf.deepSizeOf(new Class1()));
System.out.println("Class2:" + SizeOf.deepSizeOf(new Class2()));
System.out.println("Class3:" + SizeOf.deepSizeOf(new Class3()));
System.out.println("Class4:" + SizeOf.deepSizeOf(new Class4()));
}
}
class Class0 {
}
class Class1 {
int a = 0;
}
class Class2 {
int a = 0;
int b = 0;
}
class Class3 {
int a = 0;
int b = 0;
int c = 0;
}
class Class4 {
int a = 0;
int b = 0;
int c = 0;
int d = 0;
}
こんな感じで変数の個数が異なるクラスのオブジェクトを生成してサイズを測ってみます。結果は以下の通りでした。
Class0:16
Class1:16
Class2:24
Class3:24
Class4:32
Javaには8バイト単位でバイト境界があるようで、使用バイト数は8の倍数になっています。上記の結果からすると、オブジェクトは単体で12バイトのメモリを使用し、あとはメンバ変数のサイズ分加算されて、8バイト単位に調整されているようです。例えばClass2は12バイトとintが2つ(8バイト)で計20バイトですが、8の倍数に調整されて24バイトとなっています。
ラッパークラス(Integer, Long等)
プリミティブ型のラッパークラスであるIntegerやLong等も、上記と同じ考え方で計算可能です。例えばIntegerは上記のClass1と同じくintを1つ持っていることになるので16バイトで収まっています。Booleanはbooleanが1バイトなので正味13バイトですが8の倍数に丸められて16バイトになります。
| データ型 | メモリ使用量(byte) |
|---|---|
| Integer | 16 |
| Long | 24 |
| Double | 24 |
| Boolean | 16 |
| Character | 16 |
文字列
String str = "";
for ( int i = 0 ; i < 100 ; i++ ) {
System.out.println(i + ":" + SizeOf.deepSizeOf(str));
str += "a";
}
このようなコードを書いて調べてみました。結果は以下の通りです。
| 文字数 | メモリ使用量(byte) |
|---|---|
| 0 | 40 |
| 1〜8 | 48 |
| 9〜16 | 56 |
| 17〜24 | 64 |
| … | … |
基本部分が40バイトで、1文字あたり1バイトを使用し、8バイト単位に丸められているようです。日本語などの2バイトもじを使用した場合は1文字2バイトになりますが、基本的に競プロでは出てこないので、1文字1バイトと覚えておけば良いでしょう。
配列
プリミティブ型の配列
プリミティブ型の配列は、基本的にベースの型×個数だけメモリを使用しますが、追加で16バイト使用しています。(表中の数字の単位はバイト)
| データ型 | N=0 | N=100 | N=10000 |
|---|---|---|---|
| int[N] | 16 | 416 | 40016 |
| long[N] | 16 | 816 | 80016 |
| double[N] | 16 | 816 | 80016 |
| boolean[N] | 16 | 120 | 10016 |
| char[N] | 16 | 216 | 20016 |
int[10000]なら、4 * 10000 + 16という感じでサイズが求められます。"16"の部分は実用上は誤差なので、単純に基本サイズ×個数と覚えておけば良いでしょう。
boolean[]のN=100のところがちょっと変ですが、8の倍数に丸められています。これも実用上はあまり気にする必要はないでしょう。なお、booleanは1ビットではなく1バイトであることは注意しておきましょう。
オブジェクトの配列
以下のような実験をしてみました。
int N = 10000;
Object[] array = new Object[N];
System.out.println("Object[N]:" + SizeOf.deepSizeOf(array)); // ==> 40016
for ( int i = 0 ; i < N ; i++ ) {
array[i] = new Object();
}
System.out.println("Object[N]:" + SizeOf.deepSizeOf(array)); // ==> 200016
要素10000個のObject型の配列を生成したところ、配列の生成直後は全ての要素がnullですが、この状態で40016バイトでした。この配列の各要素にオブジェクトを入れたところ、200016バイトになりました。
つまり、オブジェクトの配列は枠部分で1要素あたり4バイト、配列のヘッダとして16バイト、あとは実際に格納しているオブジェクトのサイズ×個数だけ使用することになります。
- 配列の枠部分 ： 4 × 10000 + 16 = 40016
- 全オブジェクト： 16 × 10000 = 160000
- 配列全体 ： 40016 + 160000 = 200016
となります。枠部分はオブジェクトによらず1個4バイトですが、オブジェクト部分は当然のことながらオブジェクトのサイズに依存するので注意してください。
2次元配列
上記を組み合わせて考えると、2次元配列がどれだけのメモリを使用するかがわかります。例えばlong[100][1000]だと、long[1000]の部分が8016バイトで、そのオブジェクトを要素とする100個の配列ということになるので、
- 配列の枠部分 ： 4 × 100 + 16 = 416
- 全オブジェクト： 8016 × 100 = 801600
- 配列全体 ： 416 + 801600 = 802016
となります。これも実用上はヘッダ部分は誤差なので、基本サイズ×要素数で概算可能です。ただし、Object[100][1000]などの場合、最初のObject[1000]の段階で各要素の格納に4バイトかかるので、各要素4+16=20バイトとして見積もる必要があることに注意してください。
ArrayListは要注意
さて、ここまで読んだところで疑問に思った方もいるでしょう。タイトルに「本当は怖い」と書かれているのに大体想定の範囲で何も怖くないではないか、タイトルは釣りか？と。この辺りからJava特有の罠があります。
グラフの問題などで、各頂点の接続先の頂点番号をArrayList<Integer>で持つケースがあると思います。これはちょっと注意が必要です。以下のようなプログラムを実行し、グラフを描いてみました。
ArrayList<Integer> array = new ArrayList<>();
for ( int i = 0 ; i <= 1000 ; i++ ) {
System.out.println(i + "," + SizeOf.deepSizeOf(array));
array.add(i);
}
グラフに不連続な点がありますが、これはArrayListが内部では配列でデータを格納していて、足りなくなると一気に拡張するためこのような挙動になっています。具体的には生成時点では長さ0の配列、1個目が入った場合に長さ10の配列、その後は足りなくなった場合に1.5倍に拡張されます。グラフでは読み取れませんが、生成時点ではサイズは40バイトで内長さ0の配列が16バイトを使用しています。1個追加時には96バイトになっていますが、配列の長さを10個に拡張する分で40バイト、Integer1個で16バイトで計56バイト増加しています。
不連続に増加してはいますが、全体的にならすとデータ個数が1個増えるごとに、配列分の4バイトとIntegerオブジェクトの16バイト、合計20バイト増えていきます。
この振る舞いは要注意で、int配列と同じ感覚で1個4バイトのつもりで使っていると、実際はその5倍メモリを使用するということです。
ArrayListが要注意というよりは、Javaの場合はプリミティブ型に対してArrayListなどの汎用的なユーティリティクラスを使おうとすると、ラッパークラスに変換されてしまうという動作に注意する必要があるということです。これはメモリ面でもそうですが、実行時間でも少しオーバーヘッドがあるので注意しましょう。
一応、データの個数ごとのサイズを表にしておきます。
| N | int[N] | ArrayList<Integer>() |
|---|---|---|
| 0 | 16 | 40 |
| 10 | 56 | 240 |
| 100 | 416 | 2,080 |
| 1,000 | 4,016 | 20,976 |
| 10,000 | 40,016 | 216,256 |
| 100,000 | 400,016 | 2,026,880 |
| 1,000,000 | 4,000,016 | 20,861,992 |
N=100万のときに、int[]だと約4MB、ArrayListでは約20MB使用します。最近の問題のようにメモリ制限が1024MBであればそれほど大きな問題にはならないかもしれませんが、一昔前の問題でメモリ制限256MBとかの場合はちょっと注意した方が良いでしょう。特に、グラフの辺の情報を保有する場合は、辺の両端で情報を持つことになることが多いので、辺の数の倍の個数になるので注意が必要です。
AtCoderの過去問をやっていて、グラフの強連結分解(SCC)の問題などで何気なくArrayListを使っていたらこのメモリ制限に引っかかるケースがあったので、今回この記事を書くことにしました。
IntegerのArrayListの話ばかりしましたが、他のクラスに対するArrayListはそのクラスのオブジェクトのサイズ+4バイトが1個分のデータ量になります。
コールスタック
競技プログラミングでは再帰呼び出しを使うことがよくあります。この場合、再帰が深くなるとその分コールスタックとしてメモリを使用すると考えられますが、それがどれくらいメモリを使用するのか測定してみました。
以下のようなプログラムを使用して、AtCoderのコードテストで測定しました。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.close();
rec(N);
}
static void rec(int N) {
if ( N > 0 ) rec(N - 1);
}
}
0回の時が約11MBで、100万回だと約50MBでした。1回あたり40バイトのスタック領域を使用するようです。このプログラムでは再帰呼び出しのメソッドではifの判定しかしていないですが、メソッドスコープの変数があるとその分も呼び出しごとに積まれることになるのでメソッドスコープの変数が多い場合は注意が必要です。
本当は怖いコールスタック
競プロの感覚的に100万回直線的に再帰するケースはそれほどないと思うので、上記のメモリ使用量はまぁ許容範囲のように思いますが、実験中ちょっと怖い挙動がありました。
public class Main {
public static void main(String[] args) {
int N = 10000;
rec(N);
}
static void rec(int N) {
if ( N > 0 ) { rec(N - 1); }
}
}
先ほどと違うのは再帰の回数を標準入力ではなくプログラム内に直書きしています。これでNの値を変えて実験してみると、50000回を超えたあたりからメモリ使用量が非常に不安定になりました。
| N | メモリ使用量(KB) |
|---|---|
| 0 | 8,744 |
| 10,000 | 9,720 |
| 20,000 | 10,664 |
| 30,000 | 11,636 |
| 40,000 | 12,044 |
| 50,000 | 13,268 |
| 60,000 | 12MB〜300MB |
| ... | ... |
| 500,000 | 23MB〜400MB |
| 600,000 | 〜2GB |
5万回くらいまでは1万回あたり〜1MB程度の増加でしたが、N=60000を測定したところ、1回目は293,632KB、2回目は12,496KBと数十倍違う測定結果となりました。メモリ使用制限が256MBだと既に危ないです。N=600000(60万)くらいになると、メモリ使用量が2GBを超えるケースもあり危険であることがわかりました。
標準入力で実装した時よりメモリ使用量は少なくなるはずなので、この挙動の理由はよくわかりません。標準入力で実装した場合は、このような不安定な挙動は（少なくとも測定している限りでは）発生しませんでした。AtCoderでは入力は標準入力から受け取るので、このようなことは起きないと思うのですが、理由がわからないのでちょっと怖いです。（どなたか理由をご存知の方がいらっしゃいましたら教えてください）
その他のトピック
MLEではなくREになるケース
これも理由はよくわからないのですが、MLEではなくREになるケースも存在するようです。競プロ典型90問の059で実際に発生したのですが、自分の書いたコードがREになりました。Javaの場合、REになるパターンはArrayIndexOutOfBoundsExceptionかNullPointerExceptionであるケースが多いので、その観点でソースコードを読み返しましたが特にそういう箇所はありませんでした。仕方なくコードテストで試してみたらOutOfMemoryErrorで落ちたというオチでした。どういう場合にOutOfMemoryErrorになって、どういう場合にMLEになるのかは不明ですが、REが出て、使用メモリ量が上限に近い場合はメモリ制限を疑ってみても良いと思います。
以上、JavaのMLEにまつわるトピックを書いてきました。皆様の競プロライフの一助になれば幸いです。