JAVA Memory Limit Exceeded Problems

Question

I have written a JAVA program which hardly takes 3-4 MB of memory but still somehow exceeds the 16 MB memory limit on the grader in which I submit the problems for judging.

I have an Integer 2D Array of size 2500*100 which occupies around 1 MB ,and an adjacency list with a maximum of 2500 nodes and 2499 edges (Tree) .

Why does it exceed the 16 MB memory limit? I know JAVA has some overhead but I still can't understand why it exceeds the limit. It would be of great help to me if someone could explain the reason as to why the code consumes so much memory.I am also doing a DFS which will consume some stack memory but there is no reason for it to exceed the 16 MB Limit.

Here is the code:

import java.io.*;
import java.util.*;
class CateringContracts2pi
{
static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(2505);
static int mod = 10243;
static int ans=0;
static int dp[][]=new int[2501][101];
static int temp[]=new int[101];
static int N,K;
public static void main(String[]args)
{
    Scanner sc = new Scanner(System.in);
    for(int i=0;i<2505;i++)
        adj.add(new ArrayList<Integer>());
    N = sc.nextInt();
    K = sc.nextInt();
    for(int i=1;i<N;i++)
    {
        int u = sc.nextInt();
        int v = sc.nextInt();
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
    for(int i = 1; i <= N; i++)
    {
        dp[i][0] = dp[i][1] = 1;
    }
    dfs(1,0);
    System.out.println(ans);
}

static void dfs(int node,int par)
{
    int sz = adj.get(node).size();
    for(int i=0;i<sz;i++)
    {
        int next = adj.get(node).get(i);
        if(next==par)continue;
        dfs(next,node);
        Arrays.fill(temp,0);
        for(int j=1;j<=K;j++)
        {
            for(int k=1;k+j<=K;k++)
            {
                temp[j+k]+=dp[node][j]*dp[next][k] % mod;
            }
        }
        for(int j=1;j<=K;j++)
        {
            dp[node][j] += temp[j];
            dp[node][j] %= mod;
        }
    }
    ans+=dp[node][K];
    ans%=mod;
}

}

Dont post links to the code. Post the relevant code itself, in the question. — JB Nizet, Apr 06 '15 at 07:40
what is the System.in values? N = sc.nextInt(); is unlimited so it can exceed 16mb easily depending on the input. — MoonBun, Apr 06 '15 at 07:41
Can you elaborate Vladp ? N is an Integer between 1-2500. Point Noted JB Nizet — Animesh Fatehpuria, Apr 06 '15 at 08:15

score 0 · Answer 1 · answered Jun 17 '18 at 20:43

Have you entered ~2505 elements manually? I really don't envy you. I modified your example to more friendly view:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;

class CateringContracts2pi {
    private static final List<List<Integer>> adj = new ArrayList<>(2505);
    private static final int mod = 10243;
    private static final int dp[][] = new int[2501][101];
    private static final int temp[] = new int[101];
    private static int ans = 0;

    public static void main(String[] args) {
        long beforeUsedMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 2505; i++) {
            adj.add(new ArrayList<>());
        }
        System.out.print("Enter N:");
        final int N = sc.nextInt();
        long afterUsedMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        long actualMemUsed = afterUsedMem - beforeUsedMem;
        System.out.println("usage = " + actualMemUsed / 1024);
        for (int i = 1; i < N; i++) {
            int u = ThreadLocalRandom.current().nextInt(0, N);
//            int u = sc.nextInt();
//            int v = sc.nextInt();
            int v = ThreadLocalRandom.current().nextInt(0, N);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        actualMemUsed = afterUsedMem - beforeUsedMem;
        System.out.println("usage = " + actualMemUsed / 1024);
        for (int i = 1; i <= N; i++) {
            dp[i][0] = dp[i][1] = 1;
        }
        actualMemUsed = afterUsedMem - beforeUsedMem;
        System.out.println("usage = " + actualMemUsed / 1024);
        System.out.print("Enter K:");
        final int K = sc.nextInt();
        dfs(1, 0, K);
        System.out.println(ans);
        actualMemUsed = afterUsedMem - beforeUsedMem;
        System.out.println("usage = " + actualMemUsed / 1024);
    }

    private static void dfs(int node, int par, final int K) {
        int sz = adj.get(node).size();
        for (int i = 0; i < sz; i++) {
            int next = adj.get(node).get(i);
            if (next == par) continue;
            dfs(next, node, K);
            Arrays.fill(temp, 0);
            for (int j = 1; j <= K; j++) {
                for (int k = 1; k + j <= K; k++) {
                    temp[j + k] += dp[node][j] * dp[next][k] % mod;
                }
            }
            for (int j = 1; j <= K; j++) {
                dp[node][j] += temp[j];
                dp[node][j] %= mod;
            }
        }
        ans += dp[node][K];
        ans %= mod;
    }
}

I set up -Xmx4m JVM setting and ran it with different input parameters - everything what I got wasjava.lang.StackOverflowError. This exception doesn't have any relation to memory usage, heap memory I mean. You can set stack size by -Xss parameter but I think you need to refactor your dfs method.

What we can say about heap memory usage? Let's calculate :

dp[][] = new int[2501][101] = (2501 * 4 + 12) * 102 = 998Kb
temp[] = new int[101] = 101 * 4 + 12 = 416 bytes
List of Integers lists (2501 * 16 + 16) * 101 = 3,9Mb

So we have ~5Mb(max value when you fill all list of lists) for data and 1Mb for JVM. That's all.

score -1 · Answer 2 · edited May 23 '17 at 12:06

-1

JVM by itself sets how much memory it will use. Here are some tips which may help you: How is the default java heap size determined?. You may try to decrease amount of used memory using flags like -Xmx, -Xms and so on.

edited May 23 '17 at 12:06

Community

1
1

answered Apr 06 '15 at 07:50

jaroslawj

462
2
12

Can you elaborate a bit? – Animesh Fatehpuria Apr 06 '15 at 08:07
On the link which you sent , some answers state that default heap size is 4 MB while others state its 1/64 of 1 GB or something. In the latter case , its impossible for me to get any java code accepted.! – Animesh Fatehpuria Apr 06 '15 at 08:08
What amount is set depends on many factors: jvm version, total physical memory amount etc. Try to run your app with some limits, for example: java -Xmx6m -Xms4m CateringContracts2pi. If you encounter out of memory error, increase the values – jaroslawj Apr 06 '15 at 08:13

JAVA Memory Limit Exceeded Problems

2 Answers2