looping StringBuilder memory leak

Question

For a project in my data structures class, we have to traverse a graph using both breadth first and depth first traversals. Depth first traversals, in this case, are commonly between 1 and 100,000 nodes long.

The content of each node is a string. Traversing through the graph and finding the solution haven't been a large issue. However, once the traversal is completed, it must be displayed.

To do this, I went back through each node's parent, and added the node's string to a Stack. Still at this point the code runs fine (to my knowledge). The massive slowdown comes when attempting to display these strings.

Given a stack of several tens of thousands of strings, how do I display them? Straight calling System.out.println() takes way too long. Yet using a StringBuilder iteratively somehow just eats up the memory. I've tried to clear out the StringBuilder at a rather arbitrary interval (in a rather shoddy manner), and this seemed to slightly help. Also introducing a small sleep seemed to help as well. Either way, by the time the function is finished printing, either Java has run out of memory, or is incredibly slow and unresponsive.

Is there some way I can restructure this code to output all of the strings in a relatively timely manner (~10 seconds shouldn't be asking too much), without crashing the VM?

if(DFSResult.hash().equals(myPuzzle.answerHash()))
{
  System.out.println("Success");
  int depth = 0;
  while(DFSResult.parent != null)
  {
    depth++;
    if(in.equals("y")) dfs.push(DFSResult.hash());
    DFSResult = DFSResult.parent;
  }
  System.out.println("found at a depth of "+depth+"\n\n");
  StringBuilder s = new StringBuilder();
  int x = 0;
  boolean isSure = false;
  if(in.equals("y"))
  {
    System.out.println("Are you really sure you want to print out a lineage this long? (y/n)");
    try{
      if(input.readLine().toLowerCase().equals("y"))isSure = true;
    }catch (Exception e) {
    }//
  }
  s = new StringBuilder();
  while(!dfs.empty() && isSure)
  {
    //System.out.println(dfs.pop());
    s.append(dfs.pop()).append("\n");
    x++;
    if(x % 500 == 0)
    {//Flush the stringbuilder
      try{Thread.sleep(50);}catch(Exception e){e.printStackTrace();}
      System.out.println(s.toString());
      s.delete(0,s.length());//supposed 25% efficiency increase over saying s = new StringBuilder()
    }
  }
  System.out.println(s.toString());

Answer 1

You don't need to use StringBuilder in your example. Instead just do:

System.out.println(dfs.pop());

inside your loop. No sleeps needed either. Just one line inside the loop.

There's no problem with System.out.println() efficiency. Please consider the following code:

public class TestMain {
  public static void main(String[] args) {
    long timeBefore = System.currentTimeMillis();
    for (int i = 0; i < 50000; i++) {
        System.out.println("Value = " + i);
    }
    long timeAfter = System.currentTimeMillis();
    System.out.println("Time elapsed (ms): " + (timeAfter - timeBefore));
  }
}

This is the last lines of output on my machine:

. . .
Value = 49994
Value = 49995
Value = 49996
Value = 49997
Value = 49998
Value = 49999
Time elapsed (ms): 538

As you can see it's super fast. The problem is not in the println() method.

Example of stack usage below:

public static void main(String[] args) {
    long timeBefore1 = System.currentTimeMillis();
    Stack<String> s = new Stack<String>();
    for (int i = 0; i < 50000; i++) {
        s.push("Value = " + i);
    }
    long timeAfter1 = System.currentTimeMillis();
    long timeBefore2 = System.currentTimeMillis();
    while (!s.isEmpty()) {
        System.out.println(s.pop());
    }
    long timeAfter2 = System.currentTimeMillis();
    System.out.println("Time spent on building stack (ms): " + (timeAfter1 - timeBefore1));
    System.out.println("Time spent on reading stack (ms): " + (timeAfter2 - timeBefore2));
}

Output:

. . .
Value = 2
Value = 1
Value = 0
Time spent on building stack (ms): 31
Time spent on reading stack (ms): 551