4

For an assignment we were asked to implement a data structure using single linked list.

My problem is that after adding items and then removing them the java program is still using the same memory as before.

Here is a simple example

Deque<Integer> deck = new Deque<>();
for( int i =0; i < 500000;i++) {
    deck.addFirst(i);
}

for( int i =0; i < 500000;i++) {
    deck.removeFirst();
}
System.out.println("end"); //Debugger here

Adding half a million items consumes 27mb of memory. After removing them is still at 27mb. Jumping with the debugger at the end, the variable deck has the fields first = null and count = 0;

Why is this the case? deck is empty and has no items but the memory is still used as before.

The code passes all the correctness tests but fails on the memory ones.

I also looked with the step by step debugger and is doing what is supposed to do.

Could it be that in removeFirst() I'm not setting anything to null and just assign first to be first.next ?

Edit: here is the output of a memory test

 Test 10: Total memory usage after inserting 4096 items, then successively
     deleting items, seeking values of n where memory usage is maximized
     as a function of n

               n        bytes
    ---------------------------------------------------
  => passed     3200        65592         
  => passed     1600        65592         
  => FAILED      800        65592   (1.7x)
  => FAILED      400        65592   (3.4x)
  => FAILED      200        65592   (6.7x)
  => FAILED      100        65592  (13.1x)
  => FAILED       50        65592  (25.3x)
  ==> 2/7 tests passed

As you can see at 50 elements is still using 65592

Edit2:

// remove and return the item from the front
public Item removeFirst() {
    if (this.isEmpty()) throw new java.util.NoSuchElementException();
    Item current = first.Item;
    first = first.Next;
    count--;
    return current;
}

This is removeFirst()

Edit3:

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.TimeUnit;

/**
 * Created by Alex on 6/30/2018.
 */

public class Deque<Item> implements Iterable<Item> {

    private Node first;

    private int count;

    private class Node {
        private Node Next;
        private Item Item;
    }

    // construct an empty deque
    public Deque() {
        first = null;
        count = 0;
    }

    // is the deque empty?
    public boolean isEmpty() {
        if (count == 0) {
            return true;
        }
        return false;
    }

    // return the number of items on the deque
    public int size() {
        return count;
    }

    // add the item to the front
    public void addFirst(Item item) {
        if (item == null) throw new IllegalArgumentException();
        Node temp = new Node();
        temp.Item = item;
        temp.Next = first;
        first = temp;
        count++;
    }

    // add the item to the end
    public void addLast(Item item) {
        if (item == null) throw new IllegalArgumentException();
        if (isEmpty()) {
            addFirst(item);
        } else {
            Node last = first;
            while (last.Next != null) {
                last = last.Next;
            }
            Node newLast = new Node();
            newLast.Item = item;
            newLast.Next = null;
            last.Next = newLast;
            count++;
        }
    }

    // remove and return the item from the front
    public Item removeFirst() {
        if (this.isEmpty()) throw new java.util.NoSuchElementException();
        Item current = first.Item;
        first = first.Next;
        count--;
        return current;
    }

    // remove and return the item from the end
    public Item removeLast() {
        if (isEmpty()) throw new java.util.NoSuchElementException();
        if (size() == 1) {
           return removeFirst();
        }else {
            Node newLast = first;
            Node oldLast = first;
            while (oldLast.Next != null) {
                newLast = oldLast;
                oldLast = oldLast.Next;
            }
            newLast.Next = null;
            count--;
          //  Item lastItem = ;
            return oldLast.Item;
        }
    }

    // return an iterator over items in order from front to end
    public Iterator<Item> iterator() {
        return new DequeIterator();
    }

    private void debug() {
        Iterator<Item> deckIter = iterator();
        while(deckIter.hasNext()) {
            System.out.println(deckIter.next());
        }
        System.out.println(isEmpty());
        System.out.println("Size:" + size());
    }

    // an iterator, doesn't implement remove() since it's optional
    private class DequeIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.Item;
            current = current.Next;
            return item;
        }
    }

    // unit testing (optional)
    public static void main(String[] args) throws InterruptedException {
        Deque<Integer> deck = new Deque<>();

        for( int i =0; i < 500000;i++) {
            deck.addFirst(i);
        }

        for( int i =0; i < 500000;i++) {
            deck.removeFirst();
        }
        System.out.println("end");
        TimeUnit.MINUTES.sleep(5);
    }
}

Edit4: Those are the memory constraints

https://i.stack.imgur.com/8d5iD.jpg

Thank you.

14
  • 6
    Java will reap the memory when it wants; no sooner. How are you determining how much memory is used? Also, how is the "correctness test" defined?
    – zero298
    Jul 2, 2018 at 16:59
  • I'm looking in task manager on Windows. Edit:the correctness tests are only testing the output of the program, I will add the output for memory test
    – Fox Alex
    Jul 2, 2018 at 17:01
  • Can you show your removeFirst() implementation? I'm also wondering how that test case is implemented.
    – zero298
    Jul 2, 2018 at 17:04
  • 4
    @FoxAlex Java probably won't release memory to the OS until the program ends. That memory will be available for future allocations with the new operator, though. It's a performance feature. Java can (or should be able to) get memory for a new request faster than the OS can. Jul 2, 2018 at 17:05
  • 1
    See stackoverflow.com/questions/1582209/… and stackoverflow.com/questions/30458195/…. (Possibly a duplicate? I don't think we can speculate much more about this than those Q&As cover.)
    – Radiodef
    Jul 2, 2018 at 17:25

1 Answer 1

0

It seems from my testing that the memory is still allocated, but awaiting garbage collection. The java.lang.Runtime class has some methods to inform you about memory usage, and a static method gc() to suggest running a garbage collect. Here's an extra method and a modification of your main() class that might help you:

private final static long MB = 1024*1024;
static void memStats(String when)
{
    Runtime rt = Runtime.getRuntime();
    long max = rt.maxMemory();
    long tot = rt.totalMemory();
    long free = rt.freeMemory();
    System.out.printf(
        "mem(mb): %5d tot, %5d free %5d used %5d max %s\n",
         tot/MB, free/MB, (tot-free)/MB, max/MB, when);
}

// unit testing (optional)
public static void main(String[] args) {
    Deque<Integer> deck = new Deque<>();
    memStats("startup");
    for( int i =0; i < 500000;i++) {
        deck.addFirst(i);
    }
    memStats("after alloc");

    for( int i =0; i < 500000;i++) {
        deck.removeFirst();
    }
    memStats("after removal");
    Runtime.getRuntime().gc();
    memStats("after gc");

    System.out.println("end");
    try {
        TimeUnit.MINUTES.sleep(5);
    } catch (InterruptedException ex)
    {
    }
}

Put those in place of main() in your Deque class and run it. I get:

mem(mb):    15 tot,    15 free     0 used   247 max startup
mem(mb):    29 tot,    10 free    19 used   247 max after alloc
mem(mb):    29 tot,    10 free    19 used   247 max after removal
mem(mb):    29 tot,    29 free     0 used   247 max after gc
end

As you can see, (1) memory allocated to Java starts at 15MB total allocation for Java objects, with 0MB used. (Ignore the max figure. That doesn't report what I thought it did.) It indreases to 29MB with 19 used after the allocation.

Immediately after releasing all the Nodes in the Deque, there's no change at all!

After the gc() call, though, notice that the total memory allocated to the heap hasn't changed, but all of is now free for use by other Java objects. That garbage collection would happen eventually--usually as soon as there's not enough contiguous memory in the heap to satisfy a new request.

As I said in comments, I'm not surprised that the extra 14MB or so added to the heap wasn't returned to the OS. If you use task manager in Windows, that memory will still be considered "in use". Going to the OS for memory is expensive, so normally that's done only to expand in large blocks (~15 million bytes, in this case, it seems) and only released at end of run. That's implementation-dependent behavior, though, and may be different on a different JVM.


A note on your code. I converted the Node class to:

private static class Node<Item> {
    Node<Item> next; // lowercase next
    Item item; // You were using Item for both a type and field name!?
}

...and converted pretty much every occurrence of Node to Node<Item>. That's as it should be, since the node item type is generic. That reduced the memory use from 19MB to 15MB on that same report. Non-static inner classes have each instance of the inner class tied to a specific instance of the surrounding class. You don't need that, and it costs time and memory.

That fix may help you pass tests.

Oh yes, note the field name changes from Next to next and Item to item. Start field and method names with a lowercase letter if you want to fit into traditional Java naming styles. In no case should you use Item for both a field name and a generic type name.

3
  • Thank you for your answer, I don't understand how others get pass this test with the single linked list...
    – Fox Alex
    Jul 2, 2018 at 18:17
  • @FoxAlex You never did explain what the test was. However, you might want to be aware that linked lists consume more space than arrays, and using a non-static inner class for Node costs, too. Jul 2, 2018 at 18:46
  • all the info that I have about the test is in the post on Edit, I know no more then that.
    – Fox Alex
    Jul 2, 2018 at 18:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.