Out of Memory: Java heap space

Question

I am doing a homework assignment on Big O Notation. We need to create lists with ever increasing number of integers and then time how long it takes to sort the list to determine which Big O Collection.sort() is.

I have written some code to do this and produce data on how long the sort method takes over the course of a few iterations of each list size.

I am able to sort a list of 50,000 integers, but if I try to do the exact same operation again I will run out of memory. I think the garbage collector should reclaim my memory, so in theory there should be no problem repeating the operation.

I've read about setting my large variables to null, and not storing references to my large lists outside the for loop block. I think there is no reason any reference to my integer list should be kept alive.

What am I doing wrong that garbage collector cannot reclaim my memory?

        private static TreeMap<Integer, ArrayList<Long>> doExperiment(int iterations, int step, int trials, List listType) {
    TreeMap<Integer, ArrayList<Long>> results = new TreeMap();
    for (int i = 1; i <= iterations; i++) {
        // Data size ranges from 1000 - 50,0000 if step = 1000 and iterations = 50
        int dataSize = i * step;
        ArrayList<Long> trialResults = new ArrayList<Long>();
        for (int j = 1; j <= trials; j++) {
            // This may be LinkedList, ArrayList depending on the parameter.
            List thisList = listType;
            // dataSize works up to 50,000 Integers.
            Testing t = new Testing(dataSize, thisList);
            long nanos = t.timedSort();
            // Prints a formatted string to standard output.
            processResults(nanos, j, trials, i, iterations);
            // The large list exists only within this Testing instance. Set it to null
            t = null;
            // Please, garbage collection Gods...
            System.gc();
        }
        results.put(dataSize, trialResults);
    }
    return results;
}

Answer 1

public static void main(String[] args) {
        // TODO code application logic here
        doExperiment(50000, 5, "ArrayList");
        doExperiment(50000, 5, "LinkedList");

    }

    private static void doExperiment(int iterations, int trials, String listType) {
        List list = null;
        List<Long> holdStartTimes = new ArrayList();
        List<Long> holdEndTimes = new ArrayList();

        switch(listType)
        {
            case"ArrayList":
                list = new ArrayList();
                break;
            case "LinkedList":
                list = new LinkedList();
                break;          
        }

        for(int t = 0; t < trials; t++)
        {
            Random random = new Random();
            //create list with random ints
            for(int i = 0; i < iterations; i++)
            {
                list.add(random.nextInt(50001));//random number in range from 0 to 50000
            }

            final long startTime = System.currentTimeMillis();//start Timer
            holdStartTimes.add(startTime);
            Collections.sort(list);//sort list
            final long endTime = System.currentTimeMillis();//end Timer
            holdEndTimes.add(endTime);
        }

        //sum times
        long sum = 0;
        for(int i = 0; i < holdStartTimes.size(); i++)
        {
            sum = sum + (holdEndTimes.get(i) - holdStartTimes.get(i));
        }

        System.out.println("Sorting " + listType + " with " + iterations + " iterations and " + trials + " trials takes " + sum + " milliseconds.");
    }

Answer 2

System.gc(); - not guaranty to launch garbage collector

List thisList = listType; - copies reference (I guess this is mistake) so when you do Testing t = new Testing(dataSize, thisList); - this is actually the same as Testing t = new Testing(dataSize, listType);

Probably you want to do : List thisList = new ArrayList(listType); - Yes. This create new list but in this case Testing will operate new list but not with the same one.

ArrayList<Long> trialResults = new ArrayList<Long>(); // you create new list
....
results.put(dataSize, trialResults); // do you want to put empty list in the result?