iensen's blog

Java memory problem
By iensen, 10 years ago, In English

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:)

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    As far as I know, in Java, all allocations are made in heap space.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      +1. All the arrays are allocated in heap.

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply