Блог пользователя iensen

Java memory problem
Автор iensen, 10 лет назад, По-английски

I do not understand why the program 7630586 gets ML, but 7631291 passes same test.

(This is the same program as 7631291 with a small fix that gets accepted: 7649167)

The only difference between 7630586 and 7631291 is that 

  long board[][] = new long[n][n];

is changed to 

  int board[][] = new int[n][n];

For n = 2000, the difference should be 4*2000*2000 bytes (about 16 MB), but it turns out to be more than 100 MB.

Any thoughts?

UPD: the program 7630586 that gives ML on java 6,7 gets accepted on java 8: 7649266 So, next time I need to use java 8 when I am not sure about the memory limit and java 6 or 7 otherwise:)

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem is you declare big Array on one method,getting one exception,you can't allocate this on one method,even you have enough memory on JVM.

I could be wrong,but changes on memory manager Java 8 (http://java.dzone.com/articles/java-8-permgen-metaspace) assigned more memory for this space or make dynamic change.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I do not fully understand your comment. Are you saying there is a certain limit (separate from max heap space) that is put on memory used in a single method call? If so, I would assume CF sets it to a number which is larger than memory limit for the problem.

    If I understood correctly what I read, I do not use much of permgen space. It should not be the problem.

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Although I don't know much about Java, a similar case in C++ shows that you can't allocate more than 16MB dynamically in stack(not static). Maybe it's that problem.

If you allocates too much once you could get badAlloc

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I've just tried to run the following code locally with different -Xmx settings.

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		int n = 2000;
		long[][] a = new long[n][n];
		Random rnd = new Random();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = rnd.nextInt();
			}
		}
		for (int i = 0; i < n; i++) {
			Arrays.sort(a[i]);
		}
	}
}

I've used 32-bit Java 7, and this code successfully runs with -Xmx31M, but fails with -Xmx30M.

Later I tried to run it with run.exe (one written by andrewzta), and it says that the peak memory consumption is about 42.2 MB. For comparison: an empty program consumes about 10.1 MB.

But Codeforces invoker says that this piece of code consumes about 51MB (0 MB for empty program).

So I'm pretty sure that Codeforces invoker measures memory consumption incorrectly.

→ Ответить