5

I've been coding one recursive function today and the recursion depth depends on the input length.

I was wondering from the pure interest point of view, is there some way to monitor, probably in some JVM logs or elsewhere, what has been the maximal call stack depth during a particular program execution?

After some thinking I can imagine an analytical approach to calculate this approximately but that would be very time-intensive and would require quite good knowledge of JVM internals and bytecode.

JVM allows to configure the limit of a stack size memory, but I've never seen anything about how to get the actually reached limit and not in memory size units but the number of allocated stack frames.

Alexander Arendar
  • 3,365
  • 2
  • 26
  • 38
  • The short answer is ... No. – Stephen C Sep 05 '18 at 14:12
  • 2
    The longer answer is... Yes. One can easily make JVMTI agent that handles [MethodEntry](https://docs.oracle.com/javase/8/docs/platform/jvmti/jvmti.html#MethodEntry)/[MethodExit](https://docs.oracle.com/javase/8/docs/platform/jvmti/jvmti.html#MethodExit) events to trace current stack depth. A less precise but almost no-overhead alternative would be to use sampling profiler, e.g. [async-profiler](https://github.com/jvm-profiling-tools/async-profiler). – apangin Sep 05 '18 at 15:10
  • 1
    If you are actually interested in the stack depth for a given program and input data, you could systematically run the program with different configured stack size per thread, until you discovered the stack size that causes the program to fail. – Raedwald Sep 05 '18 at 15:45
  • Since you’re talking about the stack size memory, it seems you’re not after the maximum number of recursions but rather the amount of stack memory needed for your program. The bad news is, [it is entirely non-deterministic](https://stackoverflow.com/q/27043922/2711488). Of course, you might be wondering what specifying an exact amount of stack memory in a JVM option will bring you then, but to me, having a JVM with automatic memory management for the heap, but fixed sized stacks which can not expand when needed, is an anachronism anyway. You should be very careful with recursive algorithms… – Holger Sep 05 '18 at 17:28
  • 1) create a repeatable test, 2) reduce the maximum stack size until it fails. – Peter Lawrey Sep 05 '18 at 17:55
  • On 64-bit processes the maximum stack size isn't important as making the size too high only wastes virtual memory, not actual memory. You might be trying to optimise something which hasn't been a problem from before Java was invented. – Peter Lawrey Sep 05 '18 at 17:56
  • @PeterLawrey “reduce the maximum stack size until it fails”—as explained in [my previous comment](https://stackoverflow.com/questions/52185905/is-there-a-way-to-know-maximally-reached-jvm-call-stack-depth-for-a-particular-p#comment91330862_52185905), this is entirely unreliable, as even on the same machine with the same JVM, the required amount of stack space may be different on the next run. Not to speak of different configurations or the problem of proving whether you really covered all possible scenarios of your application execution. – Holger Sep 06 '18 at 09:48
  • @Holger So creating a "create a repeatable test" might be hard and even then won't be accurate for a different OS/JVM. – Peter Lawrey Sep 06 '18 at 09:50
  • @PeterLawrey or simply impossible, as when you follow the link, you’ll learn that even forcing interpreted execution will lead to entirely different maximum stack sizes in each run, most likely because the JVM is *deliberately non-deterministic*, to make it harder to exploit bugs in that regard. Plus perhaps ASLR related effects. And well, even if you manage to create an artificial environment where the maximum stack size is reproducible, what does the result, which is only relevant to that specific artificial environment, help you with real life environments? – Holger Sep 06 '18 at 09:55
  • @Holger the JVM isn't reliably random in my experience. Perhaps I tend to work on simple tests but I find even System.identityHashCode() for objects get repeated from one run to the next. – Peter Lawrey Sep 06 '18 at 10:04
  • 1
    @Holger `System.out.println(System.identityHashCode("Hello World"));` prints the same number every time I run the program from scratch. – Peter Lawrey Sep 06 '18 at 10:06
  • @PeterLawrey I don’t see any connection between the identity hash code and the maximum stack size. Perhaps, you’ve fallen for the myth that the identity hash code had anything to do with memory addresses, but even if it was true, it was a heap address, without any relationship to the stack. But since it is a kind of serial number, it’s not surprising if it happens to be repeatable. The stack is a different beast, as said, *deliberately randomized by the operating system for security reasons*, and as also said, *follow the link* given in my previous comment. It contain a practical example. – Holger Sep 06 '18 at 10:13
  • @Holger I take your point that the actual stack depth you can achieve varies due to factors outside your control. I had assumed he wanted to see how much memory is used for a given test. The limit doesn't vary that much from one JVM run to another however within a JVM it can change as the code warms up which is factor you would need to take into account. – Peter Lawrey Sep 06 '18 at 10:20
  • @PeterLawrey you’re right in that the question literally reads “…for a particular program run”, but since I’m thinking about what the OP wants to do with that number and there’s some mentioning of “recursive function” in the question’s body, it’s important to warn about drawing wrong conclusions. And well, a particular run is not a “repeatable test”… – Holger Sep 06 '18 at 10:25
  • @Holger more to the point, even if you could do what I suggest, the number is unlikely to be helpful in a real application context which is not the same as the test in some possibly hard to predict way. – Peter Lawrey Sep 06 '18 at 10:27

1 Answers1

4

One can easily make JVMTI agent that will trace MethodEntry / MethodExit events and correspondingly increase or decrease stack depth counter. Here is an example of such agent. When the program ends, it will print the maximum recorded Java stack depth.

#include <jvmti.h>
#include <stdint.h>
#include <stdio.h>

static volatile int max_depth = 0;

static int adjust_stack_depth(jvmtiEnv *jvmti, int delta) {
    intptr_t depth = 0;
    (*jvmti)->GetThreadLocalStorage(jvmti, NULL, (void**)&depth);
    (*jvmti)->SetThreadLocalStorage(jvmti, NULL, (const void*)(depth + delta));
    return (int)depth;
}

void JNICALL MethodEntry(jvmtiEnv *jvmti, JNIEnv* jni, jthread thread, jmethodID method) {
    adjust_stack_depth(jvmti, +1);
}

void JNICALL MethodExit(jvmtiEnv *jvmti, JNIEnv* jni, jthread thread, jmethodID method,
                        jboolean was_popped_by_exception, jvalue return_value) {
    int depth = adjust_stack_depth(jvmti, -1);
    if (depth > max_depth) {
        max_depth = depth;  // TODO: replace with atomic CAS to avoid race condition
    }
}

JNIEXPORT jint JNICALL Agent_OnLoad(JavaVM *vm, char *options, void *reserved) {
    jvmtiEnv* jvmti;
    (*vm)->GetEnv(vm, (void**)&jvmti, JVMTI_VERSION_1_0);

    jvmtiCapabilities capabilities = {0};
    capabilities.can_generate_method_entry_events = 1;
    capabilities.can_generate_method_exit_events = 1;
    (*jvmti)->AddCapabilities(jvmti, &capabilities);

    jvmtiEventCallbacks callbacks = {0};
    callbacks.MethodEntry = MethodEntry;
    callbacks.MethodExit = MethodExit;
    (*jvmti)->SetEventCallbacks(jvmti, &callbacks, sizeof(callbacks));

    (*jvmti)->SetEventNotificationMode(jvmti, JVMTI_ENABLE, JVMTI_EVENT_METHOD_ENTRY, NULL);
    (*jvmti)->SetEventNotificationMode(jvmti, JVMTI_ENABLE, JVMTI_EVENT_METHOD_EXIT, NULL);

    return 0;
}

JNIEXPORT void JNICALL Agent_OnUnload(JavaVM *vm) {
    printf("Max stack depth = %d\n", max_depth);
}

Compile:

gcc -fPIC -shared -I $JAVA_HOME/include -I $JAVA_HOME/include/linux -o libmaxdepth.so maxdepth.c

Run:

java -agentpath:/path/to/libmaxdepth.so MyProgram

However, tracing each method entry and exit is very expensive. A less accurate, but much more efficient alternative would be a sampling profiler which periodically records a stack trace of a running thread, e.g. async-profiler or Java Flight Recorder.

apangin
  • 92,924
  • 10
  • 193
  • 247
  • But the number of nested invocations doesn’t help you estimating the required stack memory at all. So it’s just a meaningless number. – Holger Sep 06 '18 at 09:57
  • @Holger, I was asking precisely for number of allocated stack frames. Probably it is not very useful in real production life, but it does provide an interesting insight into how things work under the hood :) – Alexander Arendar Sep 06 '18 at 11:20
  • @AlexanderArendar actually, it’s the opposite of “how things work under the hood”; you get the formal number of nested method invocations, i.e. matching the number of invocations as written in your Java source code, precisely destroying any optimizations that would prevent the creation of a stack frame or make an invocation undetectable. That’s one reason why, as this answer says, “tracing each method entry and exit is very expensive”. It’s not doing what it would do normally anymore. – Holger Sep 06 '18 at 11:35
  • @apangin, I have actually compiled this and tried out. So I expected to see `Max stack depth = 1` output when testing this with a simplest program with empty `main` method. But actual output was `Max stack depth = 30` and it remained the same if I added some class instantiation and additional method call from `main`. Could you advise what am I doing wrong to test this? – Alexander Arendar Sep 09 '18 at 18:33
  • @AlexanderArendar There is nothing wrong here. Before starting `main` JVM runs application launcher code which loads and verifies the main class. The launcher is also written in Java, so in this case the agent basically counts the maximum depth of the launcher code. – apangin Sep 10 '18 at 00:56
  • I've [modified](https://gist.github.com/apangin/d81c5bef977e2ac910e2badc0390852c) the agent to count only frames above application's `main` method. – apangin Sep 10 '18 at 00:57