I asked this question to get to know how to increase the runtime call stack size in the JVM. I've got an answer to this, and I've also got many useful answers and comments relevant to how Java handles the situation where a large runtime stack is needed. I've extended my question with the summary of the responses.
Originally I wanted to increase the JVM stack size so programs like runs without a StackOverflowError.
public class TT {
public static long fact(int n) {
return n < 2 ? 1 : n * fact(n - 1);
}
public static void main(String[] args) {
System.out.println(fact(1 << 15));
}
}
The corresponding configuration setting is the java -Xss... command-line flag with a large enough value. For the program TT above, it works like this with OpenJDK's JVM:
$ javac TT.java
$ java -Xss4m TT
One of the answers has also pointed out that the -X... flags are implementation dependent. I was using
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1~8.04.3)
OpenJDK 64-Bit Server VM (build 16.0-b13, mixed mode)
It is also possible to specify a large stack only for one thread (see in one of the answers how). This is recommended over java -Xss... to avoid wasting memory for threads that don't need it.
I was curious how large a stack the program above exactly needs, so I've run it n increased:
fact(1 << 15)fact(1 << 17)fact(1 << 18)fact(1 << 19)fact(1 << 20)fact(1 << 21)fact(1 << 22)fact(1 << 23)fact(1 << 24)fact(1 << 25)From the numbers above it seems that Java is using about 16 bytes per stack frame for the function above, which is reasonable.
The enumeration above contains can be enough instead of is enough, because the stack requirement is not deterministic: running it multiple times with the same source file and the same -Xss... sometimes succeeds and sometimes yields a StackOverflowError. E.g. for 1 << 20, -Xss18m was enough in 7 runs out of 10, and -Xss19m wasn't always enough either, but -Xss20m was enough (in all 100 runs out of 100). Does garbage collection, the JIT kicking in, or something else cause this nondeterministic behavior?
The stack trace printed at a StackOverflowError (and possibly at other exceptions as well) shows only the most recent 1024 elements of the runtime stack. An answer below demonstrates how to count the exact depth reached (which might be a lot larger than 1024).
Many people who responded has pointed out that it is a good and safe coding practice to consider alternative, less stack-hungry implementations of the same algorithm. In general, it is possible to convert to a set of recursive functions to iterative functions (using a e.g. Stack object, which gets populated on the heap instead of on the runtime stack). For this particular fact function, it is quite easy to convert it. My iterative version would look like:
public class TTIterative {
public static long fact(int n) {
if (n < 2) return 1;
if (n > 65) return 0; // Enough powers of 2 in the product to make it (long)0.
long f = 2;
for (int i = 3; i <= n; ++i) {
f *= i;
}
return f;
}
public static void main(String[] args) {
System.out.println(fact(1 << 15));
}
}
FYI, as the iterative solution above shows it, the fact function cannot compute the exact factorial of numbers above 65 (actually, even above 20), because the Java built-in type long would overflow. Refactoring fact so it would return a BigInteger instead of long would yield exact results for large inputs as well.
This question is related to
java
stack
stack-overflow
If you want to play with the thread stack size, you'll want to look at the -Xss option on the Hotspot JVM. It may be something different on non Hotspot VM's since the -X parameters to the JVM are distribution specific, IIRC.
On Hotspot, this looks like java -Xss16M if you want to make the size 16 megs.
Type java -X -help if you want to see all of the distribution specific JVM parameters you can pass in. I am not sure if this works the same on other JVMs, but it prints all of Hotspot specific parameters.
For what it's worth - I would recommend limiting your use of recursive methods in Java. It's not too great at optimizing them - for one the JVM doesn't support tail recursion (see Does the JVM prevent tail call optimizations?). Try refactoring your factorial code above to use a while loop instead of recursive method calls.
Weird! You are saying that you want to generate a recursion of 1<<15 depth???!!!!
I'd suggest DON'T try it. The size of the stack will be 2^15 * sizeof(stack-frame). I don't know what stack-frame size is, but 2^15 is 32.768. Pretty much... Well, if it stops at 1024 (2^10) you'll have to make it 2^5 times bigger, it is, 32 times bigger than with your actual setting.
It is hard to give a sensible solution since you are keen to avoid all sane approaches. Refactoring one line of code is the senible solution.
Note: Using -Xss sets the stack size of every thread and is a very bad idea.
Another approach is byte code manipulation to change the code as follows;
public static long fact(int n) {
return n < 2 ? n : n > 127 ? 0 : n * fact(n - 1);
}
given every answer for n > 127 is 0. This avoid changing the source code.
I did Anagram excersize, which is like Count Change problem but with 50 000 denominations (coins). I am not sure that it can be done iteratively, I do not care. I just know that the -xss option had no effect -- I always failed after 1024 stack frames (might be scala does bad job delivering to to java or printStackTrace limitation. I do not know). This is bad option, as explained anyway. You do not want all threads in to app to be monstrous. However, I did some experiments with new Thread (stack size). This works indeed,
def measureStackDepth(ss: Long): Long = {
var depth: Long = 0
val thread: Thread = new Thread(null, new Runnable() {
override def run() {
try {
def sum(n: Long): Long = {depth += 1; if (n== 0) 0 else sum(n-1) + 1}
println("fact = " + sum(ss * 10))
} catch {
case e: StackOverflowError => // eat the exception, that is expected
}
}
}, "deep stack for money exchange", ss)
thread.start()
thread.join()
depth
} //> measureStackDepth: (ss: Long)Long
for (ss <- (0 to 10)) println("ss = 10^" + ss + " allows stack of size " -> measureStackDepth((scala.math.pow (10, ss)).toLong) )
//> fact = 10
//| (ss = 10^0 allows stack of size ,11)
//| fact = 100
//| (ss = 10^1 allows stack of size ,101)
//| fact = 1000
//| (ss = 10^2 allows stack of size ,1001)
//| fact = 10000
//| (ss = 10^3 allows stack of size ,10001)
//| (ss = 10^4 allows stack of size ,1336)
//| (ss = 10^5 allows stack of size ,5456)
//| (ss = 10^6 allows stack of size ,62736)
//| (ss = 10^7 allows stack of size ,623876)
//| (ss = 10^8 allows stack of size ,6247732)
//| (ss = 10^9 allows stack of size ,62498160)
You see that stack can grow exponentially deeper with exponentially more stack alloted to the thread.
I assume you calculated the "depth of 1024" by the recurring lines in the stack trace?
Obviously, the stack trace array length in Throwable seems to be limited to 1024. Try the following program:
public class Test {
public static void main(String[] args) {
try {
System.out.println(fact(1 << 15));
}
catch (StackOverflowError e) {
System.err.println("true recursion level was " + level);
System.err.println("reported recursion level was " +
e.getStackTrace().length);
}
}
private static int level = 0;
public static long fact(int n) {
level++;
return n < 2 ? n : n * fact(n - 1);
}
}
The only way to control the size of stack within process is start a new Thread. But you can also control by creating a self-calling sub Java process with the -Xss parameter.
public class TT {
private static int level = 0;
public static long fact(int n) {
level++;
return n < 2 ? n : n * fact(n - 1);
}
public static void main(String[] args) throws InterruptedException {
Thread t = new Thread(null, null, "TT", 1000000) {
@Override
public void run() {
try {
level = 0;
System.out.println(fact(1 << 15));
} catch (StackOverflowError e) {
System.err.println("true recursion level was " + level);
System.err.println("reported recursion level was "
+ e.getStackTrace().length);
}
}
};
t.start();
t.join();
try {
level = 0;
System.out.println(fact(1 << 15));
} catch (StackOverflowError e) {
System.err.println("true recursion level was " + level);
System.err.println("reported recursion level was "
+ e.getStackTrace().length);
}
}
}
Other posters have pointed out how to increase memory and that you could memoize calls. I'd suggest that for many applications, you can use Stirling's formula to approximate large n! very quickly with almost no memory footprint.
Take a gander at this post, which has some analysis of the function and code:
http://threebrothers.org/brendan/blog/stirlings-approximation-formula-clojure/
Add this option
--driver-java-options -Xss512m
to your spark-submit command will fix this issue.
Source: Stackoverflow.com