[concurrency-interest] Default Stack Size on 64-bit JVMs

Alex Otenko oleksandr.otenko at gmail.com
Mon Dec 7 04:39:45 EST 2015


What’s the difference between “plain recursion” and “Java stack”?

Alex

> On 2 Dec 2015, at 20:25, Jorge Branco <jorge.d.f.branco at gmail.com> wrote:
> 
> > Has it been considered to eliminate the use of recursion entirely from the concurrency library (or for that matter the JDK) ?  Any need for recursion can be readily transformed into the use of a stack.
> 
> Wouldn't that entail a huge performance cost? Some very raw experiments I've done in the past seemed to imply that a (Java) stack would give a terrible performance in comparison with equivalent algorithms using plain recursion.
> 
> On Wed, Dec 2, 2015 at 7:29 PM, Hanson Char <hanson.char at gmail.com <mailto:hanson.char at gmail.com>> wrote:
> Has it been considered to eliminate the use of recursion entirely from the concurrency library (or for that matter the JDK) ?  Any need for recursion can be readily transformed into the use of a stack.  This doesn't help prevent anyone abusing the library, but would eliminate the need to explain StackOverFlow error.  Shift the usage responsibility to the caller.
> 
> 2 cents.
> 
> Hanson 
> 
> On Wed, Dec 2, 2015 at 9:40 AM, Nathan Reynolds <nathan.reynolds at oracle.com <mailto:nathan.reynolds at oracle.com>> wrote:
> > In the mean time, there is some sentiment that default thread stack sizes on 64bit JVMs should be expanded keep up with the times. On 32bit systems the 1MB limit is completely defensible. But expanding to say 64MB on 64bit systems would reduce practical encounters with SOE in these kinds of constructions by a factor of 64 or so. 
> 
> I've had this debate on a C++ application as well.  The debate started because a lot of people were working on stack overflow issues.  Each time I would tell them to first fix the infinite recursion issue.  They would try to take the easy route and would set the stack size to something very large and hope the problem would go away.  It didn't.  After the recursion bugs were eliminated, we got to the point where the application really did need to do that much recursion and the recursion was acceptably finite.  We then went with larger stack sizes and chose a sane default size.  After changing the default size, we bumped into a couple of problems.  Nothing that says we shouldn't increase the stack size but maybe it should be documented.
> 
> First, the larger stack size eats up address space.  As far as resources go, it is very cheap at this point in time on a 64-bit machine.  25 years ago we said the same thing about virtual address space on 32-bit machines.  We've got about 60 years before we will start exhausting the 64-bit address space.  So, let's ignore that for now.  Today's problem comes when doing sizing calculations.  People will see the address space size and figure that is what is needed for the process in terms of RAM.  Then the entire sizing calculation goes haywire and machines end up over sized.  As a cloud provider, I don't mind people spending more money on RAM they aren't using.  :)
> 
> Second, it can take a while to overflow the 1 MB stack.  I've had a couple of situations where it took several minutes in Java to cause a stack overflow.  Obviously, the program isn't just doing recursive calls.  There is a computation or GC happening all the way down the stack.  A 64 MB stack would take a couple of hours.  This means the thread is busy for a long time and other operations will *hopefully* timeout waiting for it.
> 
> I think a smart approach would be to examine code (open source?) or production deployments and see how often the stack sizing parameter is used and what value it is set to.  This will give us a good idea if the default stack size needs to be adjusted and what is a good stack size to use.
> -Nathan
> On 12/2/2015 5:52 AM, Doug Lea wrote:
>> On 12/02/2015 05:34 AM, Millies, Sebastian wrote: 
>>> I have thought of a way of doing tail-recursion elimination with CompletableFuture. It works, but I do not understand why. There must be some inter-thread communication going on about which I have not been able to find documentation. Perhaps someone here can enlighten me. 
>>> 
>>> public static BigInteger fibTailRecursive(int n) { 
>>>      return n <= 2 ? ONE : fibTailRecursiveAux(n, ZERO, ONE); 
>>> } 
>>> 
>>> private static BigInteger fibTailRecursiveAux(int n, BigInteger a, BigInteger b) { 
>>>      return n <= 0 ? a : fibTailRecursiveAux(n - 1, b, a.add(b)); 
>>> } 
>>> 
>>> And here is the "optimized" version with TRE, 
>>> 
>>> public static BigInteger fibCF(int n) { 
>>>          return n <= 2 ? ONE : fibCF(n, ZERO, ONE).join(); 
>>> } 
>>> 
>>> private static CompletableFuture<BigInteger> fibCF(int n, BigInteger a, BigInteger b) { 
>>>          return n <= 0 ? terminate(a) : tailcall(() -> fibCF(n - 1, b, a.add(b))); 
>>> } 
>>> 
>>> Finally, here are my problematic implementations of terminate() and tailcall(): 
>>> 
>>> public static <T> CompletableFuture<T> terminate(T t) { 
>>>          return completedFuture(t); 
>>> } 
>>> 
>>> public static <T> CompletableFuture<T> tailcall(Supplier<CompletableFuture<T>> s) { 
>>>          return CF.thenComposeAsync(_x -> s.get(), THREAD); 
>>> } 
>> 
>> (Using default Async would work at least as well. 
>> Aside: using direct executors (run in the same thread as caller) 
>> is almost never a good idea with CompletableFutures.) 
>> 
>>> 
>>> private static final CompletableFuture<?> CF = completedFuture(null); 
>>> private static final Executor THREAD = Executors.newSingleThreadExecutor(new ThreadFactoryBuilder().setDaemon(true).build()); 
>>> 
>> 
>> This is a variation of the issues brought up by Chris Purcell a few months 
>> ago. In async mode, CF generally avoids StackOverflowError (SOE), 
>> because threads help clear out dependent tasks, which they do anyway to 
>> maximize parallelism. 
>> 
>> In non-async mode, you can still get SOE because java compilers do not 
>> loopify tail recursion. It would be possible to better avoid this 
>> kind of non-async SOE by thread-local trampolining at the expense 
>> of reducing parallelism, so we don't want to do it. 
>> 
>> It's still an open question whether we can find some scheme that 
>> combines both advantages. 
>> 
>> In the mean time, there is some sentiment that default thread stack 
>> sizes on 64bit JVMs should be expanded keep up with the times. On 
>> 32bit systems the 1MB limit is completely defensible. But expanding 
>> to say 64MB on 64bit systems would reduce practical encounters with 
>> SOE in these kinds of constructions by a factor of 64 or so. 
>> 
>> -Doug 
>> 
>> 
>> _______________________________________________ 
>> Concurrency-interest mailing list 
>> Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu> 
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest> 
>> 
> 
> 
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu>
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
> 
> 
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu>
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
> 
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20151207/bda7bc1f/attachment-0001.html>


More information about the Concurrency-interest mailing list