3 ms·

I assume you're describing a degenerate case where a tree structure is unbalanced. When operating at that scale, the overhead from all the function calls alone

I assume you're describing a degenerate case where a tree structure is unbalanced. When operating at that scale, the overhead from all the function calls alone is going to be significant. It's likely going to be maddeningly slower than an iterative solution, like getting an answer in minutes vs. seconds. If it's a balanced tree, then consuming 9GB of stack to do a search would imply that the data structure is what, on the order of 2^1000000 in size? Yikes :-)

atq2119 5y ago
Not every unbalanced tree is necessarily a degenerate situation. Syntax trees aren't necessarily balanced naturally, for example. (They typically are somewhat balanced, of course, but if you do have one that's unbalanced, there's no way of balancing it.) Search trees for NP-hard problems may be an even better example.
- sgtnoodle 5y ago
  My statement was within the context of there somehow being 10GB of node metadata (which could mean different things, but I'm assuming it means 10GB of stack usage to recursively visit each node.) If you're up to 10GB worth of nodes in a syntax tree, you're probably doing something elaborate enough that you'd want to squeeze out every ounce of performance, and you're possibly a domain expert. Maybe you're making a static analysis tool? On the other hand, a lot of static analysis tools are painfully slow, so maybe there's a lot of recursive searching on deep data structures going on! Likewise, if you're trying to solve an NP-hard problem and you're recursing through 10GB of anything, you're probably already asking the computer to do something unreasonable by many orders of magnitude, and all a larger stack would do is delay an eventual out of memory error. Or, you're doing something clever and knowingly pushing the computer to its limits, and so you once again would want to squeeze out every ounce of performance and go with an iterative solution.

atq2119 5y ago

Not every unbalanced tree is necessarily a degenerate situation. Syntax trees aren't necessarily balanced naturally, for example. (They typically are somewhat balanced, of course, but if you do have one that's unbalanced, there's no way of balancing it.) Search trees for NP-hard problems may be an even better example.

sgtnoodle 5y ago
My statement was within the context of there somehow being 10GB of node metadata (which could mean different things, but I'm assuming it means 10GB of stack usage to recursively visit each node.) If you're up to 10GB worth of nodes in a syntax tree, you're probably doing something elaborate enough that you'd want to squeeze out every ounce of performance, and you're possibly a domain expert. Maybe you're making a static analysis tool? On the other hand, a lot of static analysis tools are painfully slow, so maybe there's a lot of recursive searching on deep data structures going on! Likewise, if you're trying to solve an NP-hard problem and you're recursing through 10GB of anything, you're probably already asking the computer to do something unreasonable by many orders of magnitude, and all a larger stack would do is delay an eventual out of memory error. Or, you're doing something clever and knowingly pushing the computer to its limits, and so you once again would want to squeeze out every ounce of performance and go with an iterative solution.